目前MyTopling 已上线阿里云计算巢，在这个过程中，我们和阿里云计算巢的团队进行了非常密切的合作，阿里云两位非常资深的技术专家亲临我们公司进行技术交流，和我们一起分析需求，跟我们分享计算巢的最佳实践。开源数据库MyTopling是基于开源存储引擎ToplingDB的MySQL，MyTopling 分叉自 MyRocks，兼容 MyRocks，ToplingDB 分叉自 RocksDB，兼容 RocksDB。

开源数据库MyTopling是基于开源存储引擎ToplingDB的MySQL，MyTopling 分叉自 MyRocks，兼容 MyRocks，ToplingDB 分叉自 RocksDB，兼容 RocksDB。

最初我写了一些自动机算法，后来发现 succinct 可以用来对自动机进行极致的压缩，并且可以用来作为数据库索引，然后又基于自动机写了一个算法来压缩 Key Value 中的 Value，又写了CSPP取代SkipList 作MemTable，就有了 Terark，有了 Topling，ToplingDB，MyTopling。　　这篇文档只讨论有穷状态自动机，不讨论具体的算法，对自动机只讨论一些基本概念。主要描述怎样使用自动机工具创建 KV 数据库，怎样使用自动机 API访问 KV 数据库……

ToplingDB实现了远超 RocksDB 的性能，其中最重要的提升来自数据的表达方式。这些数据的表达方式，其主要的设计思想来自于十多年前在 DFA 自动机算法与数据结构的实践。构建在 ToplingDB 之上的MyTopling，自然获得了这个天生的优势，虽然受制于 MySQL 自身的弱点，但是仍展示出了优异的外在表现：。本文通过 Topling 动态 DFA 自动机的内存表示，来揭示 ToplingDB 数据结构的设计思想。龙书中介绍了几种对 General DFA 的比较紧凑的表达方式；对于 Trie 这种树形的 DFA，存在一些流行的表达方式，例如双数组等；本文对此不予讨论。term_bit 表示该状态是否终止状态；　　整个链表的头指针保存在 DFA 对象的空闲链表头结点字段上。注1：统计表明，在未进行路径压缩的，用来存储字典的 DFA 中，95% 以上的状态结点都只有一个目标状态，这种状态结点直接指向目标结点，不需要 mempool 空间，大幅降低了内存需求。通过阅读这两个函数，可以充分理解该 DFA 的实现方式。该 DFA 最早用于实现中提到的ICoMAFSA算法，随后成为的基本构造块。

C++ 继承了 C 语言的函数指针，大多数情况下，我们使用 C 函数指针实现回调。在 C++ 中，另有成员函数指针：。同时，func_ptr 的最低位用来标识该成员函数指针指向的是否虚函数，如果是虚函数，func_ptr 表示该虚函数在虚表中的。由此可见，相比普通函数指针，通过成员函数指针调用成员函数，需要一些额外操作，例如以上 call_pmf 函数编译为：。由此可见，通过成员函数指针的调用代价远高于常规函数指针，但是，大家对性能的追求是永无止境的，为了解决这个问题，GCC 提供了一个扩展 Feature：Bound member functions。这里get_vpmf囊括了几乎最复杂的情形：先将有虚函数的 B 的对象的指向虚函数的成员函数指针转化为没有虚函数的基类 A 的成员函数指针，再将其转化为常规函数指针。msvc 隔绝于 gnu 界，其成员函数指针与普通函数指针相同，使用另外的机制实现虚函数、多继承等成员函数的绑定。

开源数据库MyTopling是基于开源存储引擎ToplingDB的MySQL，MyTopling 分叉自 MyRocks，兼容 MyRocks，ToplingDB 分叉自 RocksDB，兼容 RocksDB。

DFA 可以简单地分成两类：① 接受有限个字符序列； ② 接受无限个字符序列。其中 ① 必然有环， ② 必然无环。对于无环的 ②，可以再分为两种： 树形的，每个状态仅有一个父状态； 非树形的，至少有一个状态有多个父状态。虽然 Topling 的关系数据库MyTopling和 存储引擎ToplingDB表面上与 DFA 自动机无关，但是其索引压缩算法和 Value 压缩算法都是来源于自动机算法的助力。《自动机原理》教科书会更深入地讲解各种自动机，有些会略微提一下 DFA 的最小化。但是都不会详细深入地讲解 DFA 最小化的各种算法、原理，我们在此进行一点补充。等价但形状不同的 DFA，状态数最少的那个，称为最小的 DFA，最小的等价的 DFA 形状必然相同，非最小的状态数相同的等价的 DFA 形状有可能不同。时间复杂度最低的通用的 DFA 最小化算法是 Hopcroft 算法，不管有环的还是无环的都可以用 Hopcroft 算法来最小化。中 t1 和 t2 都等价，并且 s1,s2 同为终止状态或者非终止状态，那么 s1 和 s2 等价。0~63 的二进制串的最小化 DFA 比 0~62 的更小，更多例子。

该算法已经于 2024年6月23日 开源：topling-ark，具体代码：pinyin_build.cpp。该算法与 Topling 的主营业务数据库没啥关系，不过我们的数据库其底层索引与存储引擎也用到了我们实现的更基础的自动机算法。当搜索词中有错别字时，搜索引擎会尝试纠错，其中一种方案是通过相似拼音纠错：搜索引擎把这些字还原成拼音，用一个拼音相同的已知的搜索词代替。现存的解决方案是用 Trie 树，或者 hash table 来实现。这其中最大的问题是多音字引起的组合爆炸，我们的方法解决了这个组合爆炸问题。相当于正则表达式 : . 其它单元格中的内容也类似，红色表示匹配。利用DFA求交进行纠错也已经是一个成熟算法。该算法先从输入词条的拼音创建一个 DAG 形状的 NFA，然后将该 NFA 转化为 DFA。在创建 NFA 的过程中，对每个有拼音的不同子串，使用ICoMAFSA的算法创建包含多

ToplingDB的分布式 Compact中 Client-Server 交互，使用了topling-zip中的序列化框架，该序列化框架初版完成于 2006 年，后来命名为 febird 库在 google code 上开源，再后来 google code 停止服务，febird 迁移到 github，有段时间重命名为 nark，之后重命名为 terark，目前 topling-zip 中代码的 namespace 仍是 terark。从 2006 年至今，除 namespace 名称之外，该序列化框架的接口一直保持稳定，2016 年的时候，针对 C++11 进

ToplingDB的分布式 Compact中 Client-Server 交互，使用了topling-zip中的序列化框架，该序列化框架初版完成于 2006 年，随后基于该序列化框架，实现了一个 RPC 系统。后来整个库命名为 febird 库在 google code 上开源，再后来 google code 停止服务，febird 迁移到 github，有段时间重命名为 nark，之后重命名为 terark，目前 topling-zip 中代码的 namespace 仍是 terark。从 2006 年至今，除 namespace 名称之外，该序列化框架的接口一直保持稳定，2016 年的时候，针对 C++11 进行了模板推导相关的大幅优化，但仍保持了接口的稳定。以下为原文正文，排版有轻微改动。当然，首要的是为了有用，其次是挑战自己驾驭 C++ 的能力，目前已经全部完成，并且取得了非常好的效果。使用该 RPC 的简短示例代码：。该客户端代码展示了同步和异步 RPC 调用，同步的更简单。cout << "vec[" << i << "]=" << vec[i] << "/n";

MyTopling 是基于ToplingDB的 MySQL，分叉自 MyRocks，ToplingDB 则分叉自 RocksDB，兼容 RocksDB 接口，从而MyTopling

ToplingDB分布式 Compact中 Client-Server 交互，使用了topling-zip中的序列化框架，该序列化框架初版完成于 2006 年，后来命名为 febird 库在 google code 上开源，再后来 google code 停止服务，febird 迁移到 github，有段时间重命名为 nark，之后重命名为 terark，目前 topling-zip 中代码的 namespace 仍是 terark。从 2006 年至今，除 namespace 名称之外，该序列化框架的接口一直保持稳定，2016 年的时候，针对 C++11 进行了模板推导相关的大幅优化，但仍保持了接口的稳定。以下为原文正文，排版有轻微改动。代码表示的是数据格式，DATA_IO_LOAD_SAVE 定义在 <febird/io/DataIO.h> 中。表2：读取性能，时间单位是微秒，loop 表示相同的数据重复读 count 次，而不是读 .size() 个不同的数据。其中，205.55和1355.98这两个数字，我自己也非常吃惊，甚至感觉有点不可思议，但是，这就是实测结果！

C++ 拥有所有其它语言都不具备的优势：在保持高度抽象的同时达到极高的性能。然而要实现这一点并不容易，需要对 C++ 有深刻的理解和灵活的运用，作为序列化/反序列化库，C++ 的这个优势就是一个耀眼的亮点。十几年以前，我就写过这样一个库：。ToplingDB分布式 Compact中 Client-Server 交互，使用了 topling-zip 中的序列化框架，该序列化框架初版完成

大家好，今天跟大家介绍一款 Topling 的新产品——MyTopling。MyTopling 是基于 ToplingDB ，兼容 MySQL 的 云原生数据库，ToplingDB 和 MyTopling 的关系，相当于 InnoDB 和 MySQL 的关系。MyTopling 是真正的云原生数据库，架构上基于存储计算分离，并且实现了前台计算与后台计算的分离，把耗费 CPU 最多的后台计算转移到了

大家好，今天跟大家介绍一款 Topling 的新产品——MyTopling。MyTopling 是基于 ToplingDB ，兼容 MySQL 的 云原生数据库，ToplingDB 和 MyTopling 的关系，相当于 InnoDB 和 MySQL 的关系。MyTopling 是真正的云原生数据库，架构上基于存储计算分离，并且实现了前台计算与后台计算的分离，把耗费 CPU 最多的后台计算转移到了

Todis 提供了人性化的，可观测的监控页面，分别是 Grafana 监控和引擎观测 Web。这对于实时掌握数据库状态、调优、解决 bug 等非常有用。监控页面，除去普通指标，以及直方图指标的 P50、P90、P99 等等，我们还做了直方图全域展示。引测观测 WEB 页面中，展示了 Todis 的配置信息，LSM 树的实时状态、详细信息，SST 文件的信息，分布式 Compact 的运行状态等等。