数据库与DFA自动机的内存表示

（一）背景

ToplingDB 实现了远超 RocksDB 的性能，其中最重要的提升来自数据的表达方式。这些数据的表达方式，其主要的设计思想来自于十多年前在 DFA 自动机算法与数据结构的实践（2024年6月23日起开源：Topling-Ark）。

构建在 ToplingDB 之上的 MyTopling(兼容MySQL)，自然获得了这个天生的优势，虽然受制于 MySQL 自身的弱点，但是仍展示出了优异的外在表现：

本文通过 Topling 动态 DFA 自动机的内存表示，来揭示 ToplingDB 数据结构的设计思想。

（二）DFA 自动机的定义

我们回顾一下 DFA 的定义，DFA 是个五元组 $(𝑄,\Sigma ,\delta ,{𝑞}_0,𝐹)$ ：

• 有穷状态集合 Q
• 字符集 Σ
• 状态转移函数 δ : Q × Σ → Q
• 初始状态 ${𝑞}_0\in 𝑄$
• 终止状态集合 $𝐹\subseteq 𝑄$

我们来直译这个定义，Σ 设为 0~255 的整数，并用整数ID标识状态，直译为 C++：

struct DFA {
  using StateID = unsigned int; // 状态标识
  using SigmaChar = uint8_t; // 字符集 Σ
  static constexpr StateID q0 = 0; // 初始状态，可为任意值，为求方便定义为0
  struct StateNode { // 单个状态/结点
    bool is_final; // true 表示该状态属于【终止状态集合 ⊆ 】
    std::map<SigmaChar, StateID> delta;
  };
  vector<StateNode> states; // 有穷状态集合 Q
  StateID delta(StateID source, SigmaChar c) const
    { return states[source].delta[c]; }
  bool is_final(StateID s) const { return states[s].is_final; }
};

这个直译非常简单直接，并且便于动态增删改查，但是内存消耗会很大。龙书中介绍了几种对 General DFA 的比较紧凑的表达方式；对于 Trie 这种树形的 DFA，存在一些流行的表达方式，例如双数组等；本文对此不予讨论。

（三）Topling 的实现方式

DFA 实现中最重要的是状态转移函数 δ : Q × Σ → Q 的表达方式，从抽象的角度看，这就是一个矩阵/二维数组。在实践中，这个矩阵一般是非常稀疏的。

作为动态 DFA，要支持增删改查，同时还要尽可能节省内存，Topling 的实现为（代码）：

struct StateNode { // StateNode 按 1 byte 对齐
  using StateID = uint32_t; // 或 uint64_t
  static constexpr StateID nil = (1ull<<link_bits) - 1;
  StateID spos  : link_bits; // spos*MemPool_Align is the offset to MemPool
  StateID minch : char_bits; // min char
  StateID maxch : char_bits; // max char, inclusive
  StateID term_bit : 1; // term 在 DFA 语境中为 final 的同义词
  StateID pzip_bit : 1;
  StateID free_bit : 1;
}; // 所有 bit 总数为 n*8，n 可为 {4,5,6,8}

根据一个状态 s 的目标状态数量，采用不同的表达方式，分为两种情况：① s 的目标状态数量为 0 或 1；② s 的目标状态数量大于 1

• 当 minch==maxch 时，对应情况 ①，此时 StateNode::spos 直接存储目标状态的值，当 spos 的值为 nil 时，表示目标状态数量为 0。
• 当 minch < maxch 时，s 至少有两个目标状态，对应情况 ②，此时 spos 的含义是指向 mempool 中的一个偏移量，用来在 mempool 中寻址定位，相应位置存储了一个位图和所有目标状态的值，位图的尺寸根据 maxch - minch 确定。

• term_bit 表示该状态是否终止状态；
• pzip_bit 表示该状态还存储了一个压缩路径，对于压缩路径，稍微复杂点；
• free_bit 表示该状态是否空闲状态，如果是空闲状态，则 spos 保存的是空闲链表的链指针(整数)。
  　　整个链表的头指针保存在 DFA 对象的空闲链表头结点字段上。

以这样的方式，我们尽最大努力降低了内存空间的占用，同时支持高效的增删改查。

注1：统计表明，在未进行路径压缩的，用来存储字典的 DFA 中，95% 以上的状态结点都只有一个目标状态，这种状态结点直接指向目标结点，不需要 mempool 空间，大幅降低了内存需求。
注2：ToplingDB 的 CSPP MemTable 索引采用 Trie形状的 DFA，内存管理采用对象实例级的 Thread Local MemPool，是对这里的 MemPool 的多线程扩展，实现了性能随 CPU 数量的线性提升。

（四）代码阅读指引

我们为 DFA 定义了一些基础的原语函数，其中最重要的有：

• state_move(s, ch)：即 delta 函数(细节)
• for_each_move(s, callback(target, ch))：遍历状态 s 的所有状态转移

通过阅读这两个函数，可以充分理解该 DFA 的实现方式。

（五）特殊的 Hash Table 与 Hash 函数

该 DFA 最早用于实现【DFA 自动机的状态等价与最小化】中提到的 ICoMAFSA 算法，随后成为【Topling 中文纠错算法】的基本构造块。这两个算法的核心是自底向上的 DFA 最小化，这里面的状态等价是通过 Hash Table 来实现的。这个 Hash Table 的 Key 是 StateID，而 StateID 只有在具体的 DFA 上才有意义，所以 Hash 函数是该 DFA 的成员函数：

uint DFA::StateHash(StateID s) const { // 简化版代码
   uint h = 1234567; // magic number for init hash
   ForEachDelta([&h](SigmaChar c, StateID t) {
      h = HashCombine(h, c);
      h = HashCombine(h, t);
   });
   return HashCombine(h, IsFinal(s) ? 1 : 0);
}
bool DFA::StateEqual(StateID s1, StateID s2) const { // 简化版代码
   if (IsFinal(s1) != IsFinal(s2)) return false;
   vector<pair<SigmaChar, uint> >
      v1 = GetAllDelta(s1),
      v2 = GetAllDelta(s2);
   return v1 == v2; // v1.size == v2.size && contents are all equal
}

这个 Hash Table 的特别之处在于：对于每个要插入的 Key【StateID】，先在 DFA 中创建一个 State 并将其 StateID 作为 Key 去插入(find_or_add)，如果已经存在，再删除这个 State，因为这里的 DFA 自带以 StateID 链接的空闲链表，所以这里创建&删除状态结点都是非常快的。

创建时，如果空闲链表非空，取头结点，非空就向 states 数组 push_back 新结点，取该新结点的 StateID。
删除时，直接放入空闲链表。

以这样的方式，专门为该目的实现专有的 Hash Table，这个 Hash Table 只需要 Hash Bucket 和 Hash 冲突链，均以 StateID 作为链接：

struct HashTable { // 简化的代码
  // key 是 DFA 的状态结点标识，是 states 数组的索引/下标。
  // 返回值含义类似 std::set::insert(key)
  pair<StateID, bool> find_or_add(StateID key) {
    auto head = dfa->StateHash(key) % num_bucket;
    for (auto hit = bucket[head]; hit != nil; hit = link[hit]) {
      if (dfa->HashEqual(key, hit))
        return {hit, false}; // 已存在，.second 为 false
    }
    // ... 省略装载因子判断、rehash 等
    link[hit] = head; // 链接到冲突链头结点
    bucket[head] = hit; // 更新冲突链头指针
    return {key, true}; // 插入成功，.second 为 true
  }
  DFA*            dfa;
  StateID*        bucket;
  size_t          num_bucket;
  vector<StateID> link; // dfa->states 的平行数组
};

我们说数组 a, b 是平行数组，意思是说 a[i] 和 b[i] 是相关联的数据，效果上就象把这两个数组的所有成员合并到单个结构体中并用这个结构体的单个数组 c 代替原先先的 a 和 b，c[i].a 等效于 a[i]，c[i].b 等效于 b[i]。ToplingDB 的各种数据结构大量采用了平行数组的思想。

（六）更紧凑的 DFA：Succinct

Trie 可以用 LOUDS (Succinct) 进行高效的压缩，当 DFA 不是 Trie 的时候，一个状态/结点可能有多个前驱，就不能使用 LOUDS 来压缩了。不过我们仍然有办法：将 DFA 的宽度优先生成树使用 LOUDS 表达，再用一个 bitmap 来标识树边与非树边，并将压缩路径使用 NestLoudsTrie 进行再次压缩。这在 Topling 中文纠错算法 起到了极好的效果（演示）。

其中的 NestLoudsTrie 也用在了 ToplingDB 中作为通用的可检索压缩索引。

（七）稠密的 DFA

用来存储字典的 DFA 的状态转移矩阵一般是稀疏矩阵，但是正则表达式 RegEx 对应的 DFA 的状态转移大多是稠密矩阵。在这种情况下，前面这种 DFA 的实现就不够高效了，为此我们实现了 DenseDFA。

RegEx 对应的稠密 DFA 有很多规律，这些规律表现为相应的统计特征，我们根据这些统计特征，实现了对 DenseDFA 的压缩：Virtual Machine DFA(Builder)，不仅仅有极高的（数十倍到数百倍）压缩比，还大幅提升了搜索/匹配性能。这在我们的【多正则引擎】中表现出了非常优异的效果。

在 ToplingDB 的 ToplingZipTable 的创建过程中，同样通过计算数据的统计特征，选取恰当的索引类型、Value 压缩算法……

（八）通过 mmap 加载

在十多年前的设计之初，所有这些 DFA，都可以在创建之后，通过 mmap 加载，因为内部数据结构都使用整数代替指针实现链接关系，所以这些数据结构是位置无关的，加载之后，不需要额外的构建操作，可以立即执行搜索。

ToplingDB 的所有数据存储，包括 Zip SST、Fast SST、MemTable(可直接转化为SST) 等，都是 mmap 直接加载，采用可重定位的数据结构，无需构建操作，秒速加载……

相对的，业内明星 ART (一种 Trie 实现) 最近一两年才实现了位置无关的特性。

【完】