导言

数据库是应用系统的基石，数据库中存储着大量的数据信息，数据库的稳定性、性能、扩展性，对业务的运营起着至关重要的作用。很多人用过数据库，但是很少有人设计和实现过一个数据库，特别是实现一个分布式数据库。了解数据库的实现原理和细节，一方面可以提高个人技术，对构建其他系统有帮助，另一方面也有利于用好数据库。研究一门技术最好的方法是研究其技术原理，数据库也不例外。由于分布式数据库自身的复杂性，很多人并不能很好的理解整个数据库，所以我们希望能通过一系列文章，自顶向下，由浅入深，讲述一些技术原理，包括用户可见的技术以及大量隐藏在 SDK 界面后用户不可见的技术点。为了便于读者理解，文章以腾讯自研分布式NoSQL数据库TcaplusDB为例展开。

正文

数据库最核心的功能是把数据存储下来，并提供快速读、写能力。保存数据的方法多种多样，最直接的方法是在内存中建一个数据结构，保存数据。比如用一个List，每当收到一条数据就向List中追加一条记录。这个方案非常简单，性能良好，但问题是数据存放在内存中，一旦服务器停机或重启，数据就会永久丢失。为了解决数据丢失问题，可以把数据持久化存放在非易失存储介质（比如硬盘）中。可以使用磁盘的文件，每当收到一条数据就向文件中 Append 一行。这是一个持久化存储数据的解决方案，如果磁盘损坏呢？ RAID是一个单机冗余存储方案。如果主机损坏呢？网络存储是一个解决方案，通过软件层进行存储副本的复制。似乎我们可以解决数据安全问题，但是做存储副本复制过程中是否能保证副本之间的一致性？还有更多的问题等待解决：

• 如何确保写入速度足够快？
• 如何确保读取速度足够快？
• 如何修改数据，如何并发的修改数据？
• 如何确保修改数据过程的原子性？
• 如何读写嵌套或复杂数据结构？

这些问题每一项都值得研究，为了解决这些问题，腾讯自研了分布式NoSQL数据库 TcaplusDB 。接下来向大家介绍一下 TcaplusDB 的一些设计思路和概念。

存储模块整体架构

TcaplusDB存储引擎采用分层架构设计，包括接口层、引擎适配层和存储引擎：  **引擎计算层 TcapRecord：**为灵活支持多种表类型及复杂数据存储，引擎计算层设计了TcapRecord对象来表达复杂数据记录对象，在引擎计算层将复杂数据对象转换成简单的key-value二进制数据记录，以对底层引擎屏蔽数据表描述等细节，实际底层只需实现key-value模型的通用存储接口。

**引擎适配层 Key-value Storage Abstract：**为适配多种存储引擎，引擎计算层和存储引擎层之间加入引擎适配层。

**TXH存储引擎 TXHDB：**基于HASH表的Key-value存储引擎TXHDB。TXHDB引擎将所有数据存储在一个文件中，并基于文件进行数据读写，并基于LRU的算法，进行内存和硬盘的冷热淘汰策略。 **Memory存储引擎 MemoryDB：**基于HASH表的Key-value存储引擎MemoryDB。MemoryDB引擎将所有数据存储在一个内存对象中，并基于对象进行数据读写。

存储引擎--TXHDB

TcaplusDB作为数据存储系统，首先要确定数据存储模型，也就是数据以什么样的形式存储的问题。TcaplusDB 的选择是 Key-Value 模型。我们可以将 TcaplusDB 看做一个巨大的 HashMap。接下来以TXHDB为例来介绍一下存储引擎的具体设计。

存储引擎格式

持久化的存储引擎，数据终归要保存在磁盘上，TcaplusDB的数据落地在腾讯完全自研的TXHDB存储引擎中。

TcaplusDB的数据文件大致可以分为3个区，头部区、内存映射区和文件访问区，见下图。其中内存映射区和文件访问区是用于存放真实数据的。  其中：

• 头部区，用于存放元数据、统计数据、Hash桶、空闲块链表头，扩展数据等信息。

• 内存映射区，这部分空间会在数据文件加载时，通过mmap的方式映射到内存地址空间中，使用读写内存的方式读写该区域，间接地达到缓存在内存中的效果。该区域位于数据文件的前部，默认大小为1G。

• 文件访问区，紧接着内存映射区后面就是所谓的文件访问区，该区域的数据读写通过普通的文件读写接口进行。

更详细的格式内容如下： 

整个文件分为头部控制信息区和数据区域；

数据文件打开时，从文件最开始建立文件映射对象，对于写操作，至少将控制头部区域放入内存映射范围；

Key-value数据记录通过hash表进行组织，hash冲突解决策略有二叉平衡树和线性链两种，通过引擎文件创建时通过参数可以决定使用哪种冲突解决策略；二叉树平衡树通过对key计算另外一个hash值（称为二次hash）建立；

数据在mmap区域外时，对数据的访问通过基于文件起始位置的偏移，使用pread/pwrite来访问。

头部控制区域分为以下几个部分：

1. 基本控制信息区：包含magic、版本信息、文件类型、记录对齐参数、空闲块参数、压缩属性、桶数、记录数、文件大小、首条记录位置、桶信息、空闲块信息等。
2. Hash桶信息区：存储hash每个桶首条记录的存储偏移；
3. 内存空闲链表头：此文件中处于mmap区域范围内的空闲数据块链表表头；
4. 文件空闲块表头：mmap区域外空闲数据块链表的表头；
5. LRU信息区域：跟踪mmap区域数据记录访问情况的LRU链；
6. 扩展区域：对txhdb透明存储区域，tcapsvr通过此区域存储数据表描述信息；

空闲块管理

数据记录的大小不一，数据记录在存储过程中，大小改变或删除会导致文件中出现一些空闲块，为减少大小不一空闲块的整理利用的开销。TXHDB采用块空间来存储数据记录，块空间通过一个apow的参数设定其对齐方式，即通过apow定义数据块的最少大小；整个存储块由按照最小对齐单元进行逐层线性增长的块数组组成，数据块的级数通过fpow参数决定，如果apow为8，fpow为10，则空闲数据块起示意图如下： 

实际数据key或value通过某一级别的一个或多个空闲块来存储，空闲块分配原则：

• 优先使用内存空闲块，然后使用文件块

• 基于内存优先使用连续块，然后使用离散块

• 基于文件只能使用连续块

如果记录均为小记录，那么整个文件可能会存在过多的离散记录，可以通过数据搬迁整理的方式定期对数据做整理。

Key Value分离

基于HASH表存储数据记录，每个数据的读写都必须访问数据的Key，TXHDB采用Key-value分离的思路，优化数据检索效率，具体如下：

将Key和Value分离存储，分别存储到Key结点和Value结点，Hash值映射到Key结点，Key结点再映射到Value结点。Key结点优先存储在内存中，Value结点有可能存储在内存中也有可能存储在磁盘中。 

具体说明如下：

• 一条记录的key，可能有多个块组成， 一个Head块， 多个split块，每一个块中记录下一个块的offset. 同时key head块中记录的有value头块的offset。

• 一条记录的val， 也可能有多个块组成， 一个head块， 多个spl块，val的offset，记录再key的head中。

• 通过将key的offset记录在hash桶中， 冲突的记录，offset记录在keyHead的left和right中以实现链表或二叉树。

• 线上业务通常width_等于32，即4B。 则 keyHead默认最小块为64B（apow的取值最小为6，2**6=64B）， 其中引擎自有信息需要占用32B – 33B， 业务可用为31B到32B, 业务据此可设计更有效的key，使key占用的块尽可能少。

多级LRU链 进行数据热度管理

为记录数据的访问热点，对mmap区域内的数据建立多级LRU链来跟踪，LRU链的级数通过参数可以定制，采用多级LRU而非一级LRU链主要是淘汰时除考虑最近访问时间外，还评估最近访问次数。 

• 多级LRU，综合考虑最近访问时间和访问次数

• 读写访问时增加访问计数，定位扫描时减访问次数

• 优先淘汰访问次数为1的LRU链中的记录

• 换出条件：剩余内存低于一定阀值

• 换入条件：剩余内存高于一定阀值

引擎计算层-TcapRecord

表结构

TcaplusDB底层是Key-value存储格式， 如何映射到用户的操作的类似Table的结构呢？

field1 field2 field3 field4 field5 field6 ....

一个表，有N多字段，在TcaplusDB中可以选定一个表的多个字段做为key，其他字段做为value来存储到TcaplusDB中。 用户还可以选定多个key字段中的部分字段来做索引（注意索引必须包含splittablekey --- 依据该key来做数据分布）。

引擎计算层负责表结构到Key-value结构的映射. 本质上就是把所有的key字段根据表结构序列化为一个key, 所有的value字段根据表结构序列化为一个value， 如下图所示: 

嵌套数据结构

使用TcaplusDB的嵌套数据结构，有助于将关系型数据库使用时需要的多张表定义，转化为单张表定义。在解析数据时，对二进制数据进行遍历，根据tag信息解析各字段的field number及value数据。在数据打包时，遍历各字段，根据字段field number，类型，value数据，打包tag及value数据到指定的buffer里。在遇到解析的value为嵌套数据结构时，则根据元数据的定义，将value按照tag、length、value进行逐个字段遍历及解析，实现嵌套数据结构的读写能力。 

数据读写流程

单Shard的数据组织形式就是一张Hash表，同一个Hash桶中的数据又是以一棵AVL树的形式组织。

数据的读写过程类似于内存中Hash表的读取过程，区别在于这里的Hash表是要持久化到文件，而磁盘IO的效率远不及内存，如何保证在主要的场景下这些存储在文件中的数据访问效率最优化，就是数据存储引擎要考虑的主要问题。

一条数据写入到数据文件的过程

本节主要讲述数据的插入（Insert）过程，当然数据的写操作还包括修改（Update）和替换（Replace）。

• 首先通过Hash算法，计算得到数据的Hash桶号，数据将会插入到对应Hash桶中。这个桶是逻辑上的概念，同一个桶中的数据，并不意味着它们一定会集中存储在磁盘上的某个位置。桶号 = hash(数据Key) % 桶数。

• 对Hash桶加锁。由于写数据的过程中涉及到检查数据是否已存在和修改桶中的数据组织结构，通过加锁可以防止这个过程因为并发而出现数据不一致等问题。

• 在Hash桶中搜索（搜索的过程参考AVL树算法描述）是否已经存在与待插入数据Key值相同的数据，如果存在，则直接结束插入流程，并提示数据已存在。如果不存在，则开始写数据到数据文件中。

• 数据引擎为新数据分配存储空间，由于数据的Key和Value在内容和使用上都较大的区别，为了尽可能的保证数据的访问效率，Key和Value的存储空间是分开分配的，而且分配策略上也略有不同。

存储空间分配的基本策略

• 优先使用数据文件的前1G的空间。原因是存储引擎启动时，会将数据文件的前1G空间通过mmap映射到内存中，访问效率较高，而剩余的空间中数据是直接对接文件IO的方式访问的；
• 数据的Key比数据的Value更有权利优先使用前1G的空间。原因是通常情况下Key的访问频率要比Value高。当前1G空间中原先分配给Key使用的空闲块不足时，会将前1G空间中原先分配给Value使用的空闲块挪给Key使用；
• 所有数据的Key尽量存放在一起。这是因为我们有很多Key遍历的场景（比如数据迁移），Key放在一起，可以一定程度上加快遍历的过程，减少磁盘IO；
• 空闲块的查找策略为Best-Fit，即找满足需求的最小空闲块，目的是为了尽可能的让数据存在同一块中，避免数据的Split。

存储空间的详细分配过程参见下图（下图拆分成了两个部分，两幅图通过虚线框的”尝试从文件空间分配“节点联系在一起）： 

存储空间详细分配过程图 

从文件空间中分配图

策略设计的考虑

存储引擎根据空间分配策略，会先分配数据Value的存储空间，写入数据Value部分后，再分配数据Key的存储空间，并写入数据Key部分。之所以是这样的顺序，有两方面的原因：

• 数据Key的头部需要记录它所指向的Value的存储地址，需要先分配Value的存储空间，得到Value的存储地址头，再写Key；

• 数据访问入口是Key，按照这个顺序，Key写成功，我们也基本可以认为Value也是写成功了，可以减少数据不一致的情况。

从前面的内容，我们也了解到，数据的Key，在写入文件的时候，会有头部信息，里面会记录数据在AVL树中的左右子树节点的信息，当插入新数据的时候，因为树节点的关系会发生变化，因此会涉及其它数据Key头部信息的修改，这个过程与新数据的插入是一起完成的。写数据的最后一步就是写Binlog文件，Binlog记录当前数据的最后的状态，主要用于主备节点的数据同步等场景。

一条数据从数据文件读出的过程

相比数据的写入过程，数据的读取过程要简单一些：

• 首先和写入数据一样，要找到存储要查找的数据的Hash桶，Hash桶号的计算方法，与写入数据完全一致。

• 在Hash桶内，执行AVL树的搜索过程，查找找指定的Key，如果没找到，直接返回，并提示数据不存在，如果找到，读取Key，并从Key的头部信息中找到Value的存储位置，将Value一并读取。

其他

我们已经了解了 TcaplusDB 的一些基本概念和细节，理解了这个分布式的 NoSql数据库的引擎结构、表结构以及如何实现数据的读写。后续将陆续揭秘TcaplusDB在高可用、索引等方面的内容。需要了解更多可以查看TcaplusDB官方文档。