使用 MapReduce 创建超大巨型自动机

我们已使用 terark.com 进行商业化运营

一直以来,自动机的创建程序(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 呢?这是一个方向上的突破,只要方向对了,问题的最终解决是不可避免的……

 

我们已使用 terark.com 进行商业化运营

作者:
该日志由 rockeet 于2014年07月08日发表在MapReduce, 自动机分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 使用 MapReduce 创建超大巨型自动机
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

1 个回复

  1. 123说道:

    这是什么算法,真的假的,也太厉害了吧?

发表评论

您必须 登录 后才能发表评论。