写点什么

腾讯 TcaplusDB 核心引擎技术揭秘——存储篇

用户头像
TcaplusDB
关注
发布于: 2021 年 01 月 04 日
腾讯TcaplusDB核心引擎技术揭秘——存储篇

导言

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



发布于: 2021 年 01 月 04 日阅读数: 31
用户头像

TcaplusDB

关注

还未添加个人签名 2020.05.31 加入

TcaplusDB君

评论

发布
暂无评论
腾讯TcaplusDB核心引擎技术揭秘——存储篇