一直以来，自动机的创建程序（adfa_build/dawg_build/kvbin_build 等）性能虽然尚可，以最常用的 adfa_build 来说，根据不同的输入文本，平均吞度量能达到每秒钟 5~20M 。这个速度看上去还不错，至少比竞品要快了许多，但是，如果有非常大的数据，比如 100亿个url，合计600GB（创建成DFA不超过100GB），以这个速度，即便内存够用，也要跑 8~30 个小时，是完全不能忍受的。

经过艰难的思考与权衡，大概两个月前，终于得到了一个几乎完美的解决方案：使用 MapReduce (Hadoop Streaming), 结合 TotalOrderPartitioner，在 Reduce 阶段为每个 partition 创建一个DFA。

因为使用了 TotalOrderPartitioner ，这些 DFA 的 UnionDFA 必然只有很少的合并状态，基于这些分析，我实现了一个特殊的 DFA Union 算法，只需要非常小的额外内存（对于这100亿个url的例子，额外内存不到百万分之一），就可以把这些 DFA 在逻辑上看做是一个 DFA，并且，这 1/1000000 不光是一层胶水，因为这部分很小，所以可以对它用空间换时间，从而它更是一个 Cache，总的查询速度反而会更快！

另一方面，因为每个 DFA 都比较小，DFA 的状态转移的指针可以使用更少的 bit，从而，每个 DFA 的尺寸会比一个物理上超大的 DFA 更小，所以，付出了那 1/1000000的内存，却收获了10~20% 的内存。

在 API 上，甚至不用增加新的接口，只是允许原先的 DFA_Interface::load_from(filename) 中的 filename 可以是 空格，分号，或者逗号分隔的多个文件名，在多个文件名的情况下，load_from 返回一个由多个 DFA 组成的逻辑 UnionDFA 对象，这一切对用户程序是完全透明的。

目前 adfa 和 dawg 都支持这个功能，因为我的这个自动机库已经闭源，所以算法的细节不再公开。

———————————————

这个问题曾经困扰了我很久，原因是我一直想着创建一个超大的物理 DFA，这只能单方面提高 adfa_build/dawg_build 的性能，而这已经不能再提高了。后来我又想着先创建多个DFA，再将它们合并起来，就写了一个 dfa_union 程序，我的 dfa_union 比几乎所有的 dfa_union 实现都快，但是，比起直接用 adfa_build/dawg_build 创建单个DFA，并无优势，瓶颈仍然无法突破……

那段时间我非常烦躁，甚至连觉都睡不好，直到有一天，我忽然想通了：TeraSort 都没有创建单个的超大物理文件，我为什么非要创建一个超大的物理 DFA 呢？这是一个方向上的突破，只要方向对了，问题的最终解决是不可避免的……