把自动机用作 Key-Value 存储

原创 Topling 2024-07-12

191

最初我写了一些自动机算法，后来发现 succinct 可以用来对自动机进行极致的压缩，并且可以用来作为数据库索引，然后又基于自动机写了一个算法来压缩 Key Value 中的 Value，又写了 CSPP 取代 SkipList 作 MemTable，就有了 Terark，有了 Topling，ToplingDB，MyTopling。

原文：把自动机用作 Key-Value 存储（本文对原文进行了少量修改）
作者：csdn-whinah 发表日期: 2013年08月15日
分类: 自动机评论: 5 条阅读次数: 23,817 次

（一）前言

　　这篇文档只讨论 有穷状态自动机 ，不讨论具体的算法，对自动机只讨论一些基本概念。主要描述怎样使用自动机工具创建 KV 数据库，怎样使用自动机 API 访问 KV 数据库……

　　也有其他一些开源软件实现了本软件（2024年6月23日起开源）的部分功能，但总体上，不论是从功能还是性能（运行速度，内存用量）上考虑，到目前为止，我能找到的其它所有同类开源软件都完全无法与本软件竞争，如果你知道更好的软件，请不吝告诉我(rockeet at 163.com)！

（二）自动机的基本概念

关于自动机的形式化定义，可以参考 wikipedia：

自动机
有穷状态自动机 (FSA)
确定性的有穷自动机 (DFA)：这是本文的重点
非确定性的有穷自动机 (NFA)：很多 DFA 的构造需要 NFA 作为媒介

2.1 DFA 等同与等价

DFA 的等同：如果两个DFA 的状态转移图同构，那么这两个 DFA 等同
DFA 的等价：如果两个DFA 接受的语言集相同，那么这两个 DFA 等价
● 等价的不一定等同，等同的一定等价

2.2 DFA 最小化

对于任何一个 DFA，存在一个唯一的与该 DFA 等价的 MinDFA，该 MinDFA 的状态数是与原 DFA 等价的所有 DFA 中状态数最小的
最小化的 DFA 需要的内存更小
各种优化的 DFA 最小化算法是本软件的核心竞争力之一

（三）将 DFA 用做字典

3.1 什么是字典

　　字典，有时候也叫关联数组，可以认为就是一个 map<string, Value>，这是最简单直接的表达，在 C++ 标准库中，map 是用 RBTree 实现的，当然，也可以用 hash_map(unordered_map)。这些字典在标准库中都有，不是特别追求cpu和内存效率的话，可以直接拿来时使用。

　　但是，要知道，对于一般应用，将字典文件（假定是文本文件）加载到 map/hash_map 之后，内存占用量要比字典文件大两三倍。当数据源很大时，是不可接受的，虽然在现在这年代，几G可能都算不上很大，但是，如果再乘以3，可能就是十几二十G了，姑且不论数据加载产生的载入延迟（可能得几十分钟甚至一两个小时）。

　　用 DFA 存储字典，在很多专门的领域中是一个标准做法，例如很多分词库都用 DoubleArray Trie DFA 存储词库，语音识别软件一般也用 DFA 来存储语音。

3.2 无环DFA (ADFA, Acyclic DFA)

　　用做字典的 DFA 是无环DFA (ADFA, Acyclic DFA)，ADFA 的状态转移图是 DAG(有向无环图)。Trie 是一种最简单的 ADFA，同时也是（所有ADFA等价类中）最大的 ADFA。DoubleArray Trie 虽然广为人知，但相比 MinADFA，内存消耗要大得多。

　　ADFA 可接受的语言是有限集合，从乔姆斯基语言分类的角度，是 4 型语言（广义的 NFA 和 DFA 是 3 型语言）。当然，有限，只是有限而已，但这个集合可能非常大，一个很小的ADFA也能表达非常大的字符串集合，用正则表达式举例: [a-z]{9} ，这个正则表达式对应的DFA包含10个状态，除终止状态外，其他每个状态都有26个转移(图的边)，这个语言集合的大小是 $26^{9} = 5, 429, 503, 678, 976$ ：从 aaaaaaaaa 一直到 zzzzzzzzz。想象一下，用 HashMap 或者 TreeMap，或者 DoubleArray Trie 来表达该集合的话，将是多么恐怖！

（四）map 与 set

　　传统上，ADFA 只能用作 set<Key> ，也就是字符串的集合。但是，本软件可以把 ADFA 用作 map<Key, Value>，有两种方式可以达到这个目标：

　　第一种（map1）：扩展 ADFA（从而 DFA 的尺寸会大一点），查找 key 时，同时计算出一个整数 index，该 index 取值范围是 [0, n)，n 是 map.size()。从而，应用程序可以在外部存储一个大小为 n 的数组，用该 index 去数组直接访问 value。

　　本软件中有一个 utility 类用来简化这个流程。

　　本质上，这种方法无法动态插入 (key,val)；但可以追加 (key,val)，追加的意思是说，前一个加入的 key，按字典序必须小于后一个加入的 key。

　　第二种（map2）：将 Value 编码成 string 形式，然后再生成一个新的 string kv = key + '\t' + value，将 kv 加入 ADFA，在这种情况下，同一个 key 可以有多个 value，相当于 std::multimap<string, Value>，这种方法的妙处在于，如果多个 key 对应的 value 相同，这些 value 可以被自动机压缩成一份！

　　这种方法可以动态插入、删除 (key,value)，不过，在支持动态插入、删除功能的情况下，额外需要 4~5 倍的内存。（所以一般情况下都是预先 Offline 创建自动机，Online 使用。）

　　更进一步，这种方法可以扩展到允许 key 是一个正则表达式！（目前已经完美支持正则表达式）

（五）内存用量/查询性能

　　我们实现了两种 DFA，一种为运行速度优化，另一种为内存用量优化，前者一般比后者快 4~6 倍，后者一般比前者节省内存 30~40%，具体使用哪一种，由使用者做权衡决策。

　　不同的数据，DFA有不同的压缩率。对于典型的应用，为内存优化的DFA，压缩率一般在 3 倍到 20 之间，相比 RBTree/HashMap 的膨胀 3 倍，内存节省就有 9 倍到 60 倍！同时仍然可以保持极高的查询速度（keylen=16字节，QPS 在 40万到60万之间），为速度优化的版本，QPS 有 250万。下面是几个性能数据（map指map1，为了对齐，在一些数字前面补了0）：

写这篇文章并进行这些测试的时候，我们还未实现 Succinct 与 NestLoudsTrie，使用 Succinct 与 NestLoudsTrie 之后，可以对 DFA 进行更进一步的压缩。

	size(bytes)	gzip	DFA(small+slow)	DFA(big+fast)	KeyLen	QPS(big+fast)	DFA Build time
File1(Query)	226,433,393	96,293,588	map:101,125,415 set:073,122,182	170,139,298	016.7	24,000,000	47’seconds
File2(URL)	485,968,345	25,094,568	map:13,990,737 set:10,850,052	035,548,376	109.2	00,900,000	16’seconds

　　URL 文件的冗余比较大，虽然文件尺寸大一倍多，但最终的 dfa 文件却要小得多，创建 dfa 用的时间也少得多！dfa文件的加载速度非常快，相当于整个文件读取，如果文件已在缓冲区，则相当于 memcpy （使用 -m 选项，加载时会 mmap，就连这个 memcpy 也省了）。

　　特别提示：直接将 url 等 key 存入 DFA，比保存其 md5 需要的空间更小，而且小得多。

　　严重警告：如果 key 中包含有随机串，例如 guid、md5 等，会大大增加自动机的内存用量！不要自作聪明把自然的串转化成 md5 等 hash 串再插入自动机！

（六）自动机实用程序

　　我们实现了一些工具程序，用来从文本文件生成自动机，生成的自动机可以用 C++接口访问，这样，就将自动机的存储与业务逻辑完全分离。另外，还有一个 adfa_unzip，用来将各种自动机当做压缩文件进行解压。adfa_build 有最多的自动机类型选项，其他创建程序一般只有 -O 和 -o。

adfa_build Options [ input_text_file ]
　　输入文件的格式一般是： key \t value， \t 是 key, value 的分隔符，\t 也可以是其它字符，只要该分隔符不在 key 中出现即可，value 中则可以包含分隔符。该程序本质上不管每行的的内容是什么，只是忠实地将每行文本加入自动机。分隔符的作用体现在后面将要提到 match_key 方法中。
　　adfa 可以使用 NestLoudsTrie 对 dfa 中的压缩路径执行进一步压缩；adfa 还可以使用 succinct 来表达，此时使用了一种方法把非 Tree 形状的 DAG 也表达为 succinct。
　
dawg_build options [ input_text_file ]
　　生成扩展的 DFA，可以计算 key 的 index 号(字典序号)，对应 map 的第一种实现方式(map1)，使用方法同 adfa_build，输入文件的每行是一个 Key。理论上讲，dawg不需要 kvbin_build 那种自动机的新能力就可以完美支持二进制数据作为key。
　
nlt_build options [ input_text_file ]
　　创建一个 NestLoudsTrie，其接口与 DAWG 相同，但实现方式完全不同，它是一颗嵌套 LOUDS Succinct Trie。一般情况下，占用空间比 DAWG 更小。在特殊情况下，DAWG 会更小，例如输入为 [a-z]{9}。
　
adfa_unzip [ dfa_binary_file ]
　　解压 dfa_binary_file，按字典序将创建自动计时的输入文件 input_text_file 的每行写到标准输出 stdout ，可以接受基本 dfa(由 adfa_build.exe 生成的)文件和扩展dfa(由 dawg_build.exe 生成的)文件。
　
on_suffix_of P1 P2 … [ < dfa_binary_file ]
　　打印所有前缀为 Pn 的行 (adfa_build.exe 或 dawg_build.exe 输入文本的行) 的后缀
　
on_key_value text1 text2 … [ < dfa_binary_file ]
　　打印匹配所有 textn 的前缀的 Key (adfa_build.exe 或 dawg_build.exe 输入文本的行) 的 value，用于测试 map 实现方法2 (Key Value 之间加分隔符)
　
pinyin_build，这个很复杂，详见链接
pinyin_build(文档)：Topling 中文纠错算法

（七）自动机的 C++接口

　　本软件使用了 C++11 中的新特性，所以必须使用支持 C++11 的编译器，目前测试过的编译器有 gcc4.7 和 clang3.1。不过为了兼容，我提供了C++98 的接口，一旦编译出了静态库/动态库，C++11 就不再是必需的了。

7.1 class BaseDFA

　　头文件 terark/fsa/fsa.hpp 中主要包含 class BaseDFA，是最主要的 DFA 接口，用户代码总是从 BaseDFA::load_from(file) 加载一个自动机（adfa_build 或 dawg_build 或 regex_build生成的自动机文件），然后调用各种查找方法/成员函数。采用 map2 的方式：

size_t for_each_suffix(prefix, on_suffix[, tr])

该方法接受一个字符串prefix，如果prefix是自动机中某些字符串的前缀，则通过 on_suffix(nth,suffix) 回调，告诉应用程序，前缀是prefix的那些字符串的后缀（去除prefix之后的剩余部分），nth 是后缀集合中字符串的字典序。 tr 是一个可选参数，用来转换字符，例如全部转小写，将 ::tolower 传作 tr 即可
例如：对字符串集合 {com,comp,comparable,comparation,compare,compile,compiler,computer}, prefix=com 能匹配所有字符串(其中nth=0的后缀是空串)，prefix=comp能匹配除com之外的所有其它字符串，此时nth=0的也是空串，而 compare 的后缀 are 对应的 nth=1
返回值是后缀集合的尺寸，一般情况下没什么用处，可以忽略

size_t match_key(delim, str, on_match[, tr])

该方法用于实现 map2，delim 是 key,value 之间的分隔符(如 ‘\t’ )，key 中不可包含 delim，str 是扫描的文本，如果在扫描过程中，发现 str 的长度为 Kn 的前缀 P 匹配某个 key，就将该 key 对应的所有 value 通过 on_match(match_len, idx, value) 回调告诉调用方， idx 是同一个 key 对应的 value 集合中当前 value 的字典序。tr 是字符转换函数，例如 tolower/toupper （用来忽略大小写）。
如果自动机是用 kvbin_build.exe 创建出来的，delim 参数可以省略，或者将 256 作为 delim 传入
返回值是最长的 部分匹配 的长度，一般情况下没什么用处，可以忽略

7.2 BaseDAWG

　　这个类用来实现 map1，DAWG 的全称是 Directed Acyclic Word Graph，可以在 ADFA 的基础上，在匹配的同时，计算一个字符串在 ADFA 中的字典序号（如果存在的话），同时，也可以从字典序号计算出相应的字符串，时间复杂度都是O(strlen(word))。