刷网站关键词排名原理,网站域名怎么购买吗,腾讯企点下载安装,网页调用wordpress数据库存储引擎是一个有历史的技术#xff0c;经过数十年的发展#xff0c;已经出现很多优秀成熟的产品。阿里巴巴 X-Engine 团队撰写的论文 X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing#xff0c;详细讲述了团… 数据库存储引擎是一个有历史的技术经过数十年的发展已经出现很多优秀成熟的产品。阿里巴巴 X-Engine 团队撰写的论文 X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing详细讲述了团队在数据库存储引擎上所做的原创性工作今年早些时候已经被 SIGMOD19 Industrial Track 接收SIGMOD 是数据库领域最重要也是最有影响力的会议之一。本文将对这篇论文做一个前导性分析。 背景
X-Engine 是阿里数据库产品事业部自研的 OLTP 数据库存储引擎作为自研数据库POLARDB X 的存储引擎已经广泛应用在阿里集团内部诸多业务系统中其中包括交易历史库钉钉历史库等核心应用为业务大幅缩减了成本同时也作为双十一大促的关键数据库技术挺过了数百倍平时流量的冲击。
数据库存储引擎是一个有历史的技术经过数十年的发展已经出现很多优秀成熟的产品。各式存储引擎已经在索引组织缓存管理事务处理查询优化方方面面都做过细致的研究。即便如此这个领域的演进仍在持续每年都会涌现很多的新技术。
近年来LSM (Log-Structured Merge-Tree)结构受到越来越多的关注虽然这个技术本身出现很多年了不算什么新事物不过早先在 KV 存储系统中被应用的更多一些近年开始在数据库存储引擎领域崭露头角RocksDB 即是典型代表。
LSM 之所以变得流行一是因为其简单二是特点鲜明。写入模型是简单的追加不会更新既有的数据数据组织为简单的逻辑排序由此带来的特点是写强而读弱持久化数据只读的特点便于压缩。但是大多数数据库的应用场景其实都是读多写少的直接使用 LSM 结构未必合适想要另辟蹊径须得扬长辟短。
架构
X-Engine 使用了 LSM 作为基础架构目标是作为一个通用的高性能低成本存储引擎追求读写性能更为均衡因此在其上做了大量的改进主要围绕几个方向进行
利用先天优势持续优化写性能。优化 compaction 降低对系统性能的冲击使得系统性能表现趋于平稳。利用持久化数据层只读特点发挥压缩优势降低成本。利用天然分层结构结合硬件能力使用冷热分层结构降低综合成本。利用精细化访问机制和缓存技术弥补读性能短板。
X-Engine 的整体架构如下图根据数据冷热进行分层代替 LSM 本身的持久化数据分层热数据层和数据更新使用内存存储利用了大量内存数据库的技术(Lock-Free index structure/append only)提高事务处理的性能设计了一套事务处理流水线处理机制把事务处理的几个阶段并行起来提升吞吐。而访问频度低的冷(温)数据逐渐淘汰或是合并到持久化的存储层次中结合当前丰富的存储设备层次体系(NVM/SSD/HDD)进行存储。
我们对性能影响比较大的 compaction 过程做了大量优化主要是拆分数据存储粒度利用数据更新热点较为集中的特征尽可能的在合并过程中复用数据精细化控制 LSM 的形状减少 I/O 和计算代价并同时极大的减少了合并过程中的空间放大。同时使用更细粒度的访问控制和缓存机制优化读的性能。 既然 X-Engine 是以 LSM 为基础架构的所以一切还要从 LSM 本身说起。
LSM基本逻辑
一条数据在 LSM 结构中的旅程从写入 WAL(Write Ahead Log) 开始然后进入MemTable这是 Ta 整个生命周期的第一处落脚点。随后flush 操作将 Ta 刻在更稳固的介质上compaction 操作将Ta带往更深远的去处或是在途中丢弃取决于 Ta 的继任者何时到来。
LSM 的本质是所有写入操作并不做原地更新而是以追加的方式写入内存。每次写到一定程度即冻结为一层(Level)写入持久化存储。所有写入的行都以主键(Key)排序好后存放无论是在内存中还是持久化存储中。在内存中即为一个排序的内存数据结构(Skiplist, B-Tree, etc.)在持久化存储也作为一个只读的全排序持久化存储结构。
普通的存储系统若要支持事务处理尤其是ACI需要加入一个时间维度借此为每个事务构造出一个不受并发干扰的独立视域。存储引擎会对每个事务定序并赋予一个全局单调递增的事务版本号(SN)每个事务中的记录会存储这个 SN 以判断独立事务之间的可见性从而实现事务的隔离机制。
如果 LSM 存储结构持续写入不做其他的动作那么最终会成为如下结构
注意这里每一层的 SN 范围标识了事务写入的先后顺序已经持久化的数据不再会被修改。每一层数据按 Key 排序层与层之间的 Key range 会交叠。 这种结构对于写入是非常友好的只要追加到最新的内存表中即完成为实现 crash recovery只需记录 WAL(Redo Log)因为新数据不会覆盖旧版本追加记录会形成天然的多版本结构。
可以想见如此累积冻结的持久化层次越来越多会对查询会产生不利的影响对同一个 key 不同事务提交产生的多版本记录会散落在各个层次中不同的 key 也会散落在不同层次中读操作诸如顺序扫描便需要查找各个层并合并产生最终结果。
LSM 引入了一个 compaction 的操作解决这个问题这个操作不断的把相邻层次的数据合并并写入这个更低层次。而合并的过程实际上就是把要合并的相邻两层(或是多层)数据读出来按 key 排序相同的 key 如果有多个版本只保留新(比当前正在执行的活跃事务中最小版本号新)的版本丢掉旧版本数据然后写入新的层。可以想见这个操作非常耗费资源。
LSM compaction 操作有几种作用一是为了丢弃不再被使用的旧版本数据二是为了控制 LSM 层次形状一般的 LSM 形状都是层次越低数据量越大(倍数关系)这样放置的目的主要是为了提升读性能。 一般来讲任何存储系统的数据访问都有局部性大量的访问都集中在少部分数据上这也是缓存系统能有效工作的基本前提在 LSM 存储结构中如果我们把访问频率高的数据尽可能放在较高的层次上保持这部分数据量规模可以存放在快速存储设备中(比如 NVM,DRAM)而把访问频率低的数据放在较低层次中使用廉价慢速存储设备存储。这就是 X-Engine 的根据冷热分层概念。
要达到这种效果核心问题是如何挑选合适的数据合并到更低的层次这是compaction 调度策略首先要解决的问题根据冷热分层的逻辑就是优先合并冷数据(访问频率相对低)。
识别冷数据有很多方法对于不同的业务不尽然相同对于很多流水型业务(如交易日志系统)新近写入的数据会有更多的概率被读到冷热按写入时间顺序即可区分也有很多应用的访问特征跟写入的时间不一定有关系这个就要根据实际的访问频率去识别冷数据或是热数据。
除了数据热度以外挑选合并数据还有其他一些维度会对读性能产生影响比如数据的更新频率大量的多版本数据在查询的时候会浪费更多的I/O和CPU因此需要优先进行合并以减少记录的版本数量X-Engine 综合考虑了各种策略形成自己的compaction 调度机制。
Refined LSM
上面是 LSM 宏观逻辑结构如果具体来论读写操作和 compaction 如何进行就需要探讨每一层的数据组织方式, 每个 LSM 变种的实现各不相同。
X-Engine 的 memtable 使用了 Locked-free SkipList. 求的是简单而且并发读写的性能都比较高。当然有更高效的数据结构或者同时使用多种索引技术。这个部分X-Engine 没有做过多优化原因在事务处理的逻辑比较复杂写入内存表还没有成为其瓶颈。
持久化层如何组织更显高效这就需要讨论每层的细微结构。
数据组织
简单来说X-Engine 的每层都划分成固定大小的 Extent存放每个层次中的数据的一个连续片段(Key Range). 为了快速定位 Extent为每层 Extents 建立了一套索引(Meta Index)所有这些索引加上所有的 memory tables(active/immutable)一起组成了一个元数据树(Metadata Tree)root 节点为Metadata Snapshot, 这个树结构类似于 B-Tree当然不尽相同。 需要注意的是X-Engine 中除了当前的正在写入的 active memtable 以外其他结构都是只读的不会被修改。给定某个时间点, 比如 LSN1000, 上图中的 Metadata Snapshot1 引用到的结构即包含了(LSN1000)时刻的所有的数据的快照(这也是为什么这个结构被称为 Snapshot 的原因)。
即便是 Metadata 结构本身也是一旦生成就不会修改。所有的读都是以这个 Snapshot 结构为入口这个是 X-Engine 实现 SI 隔离级别的基础。之前讲过随着数据写入累积数据越多需要对 memtable 冻结flush, 以及层与层的compaction. 这些操作都会修改每层的数据存储结构所有这些操作都是用 copy-on-write 来实现方法就是每次都将修改(switch/flush/compaction)产生的结果写入新的 Extent然后依次生成新的Meta Index结构乃至新的Metadata Snapshot以一次 compaction 操作为例 可以看到Metadata Snapshot 2相对于Metadata Snapshot 1并没有太多的变化仅仅修改了发生变更的一些叶子节点以及索引节点。这个技术颇有些类似B-trees, Shadowing, and Clones如果你读过那篇论文会对理解这个过程有所帮助。 事务处理
得益于 LSM 轻量化写机制写入操作固然是其明显的优势但是事务处理远不只是把更新的数据写入系统那么简单这里要保证 ACID涉及到一整套复杂的流程。X-Engine 将整个事务处理过程分为两个阶段读写阶段和提交阶段。
读写阶段需要校验事务的写写冲突读写冲突判断事务是否可以执行或回滚重试或是等锁。如果事务冲突校验通过则把修改的所有数据写入Transaction Buffer, 提交阶段包括写 WAL写内存表以及提交并返回给用户结果的整个过程这里面既有 I/O 操作(写日志返回消息)也有 CPU 操作(拷贝日志写内存表)。
为了提高事务处理吞吐系统内会有大量事务并发执行单个I/O操作比较昂贵大部分存储引擎会倾向于聚集一批事务一起提交称为Group Commit能够合并I/O操作但是一组事务提交的过程中还是有大量等待过程的比如写入日志到磁盘过程中除了等待落盘无所事事。
X-Engine 为了进一步提升事务处理的吞吐采用了一种流水线的技术把提交阶段分为四个独立的更细的阶段拷贝日志到缓冲区(Log Buffer)日志落盘(Log Flush)写内存表(Write memtable)提交返回(Commit)。我们的事务提交线程到了处理阶段都可以自由选择执行流水线中任意一个阶段这样每个阶段都可以并行起来只要流水线任务的大小划分得当就能充分并行起来流水线处于接近满载状态。
另外利用的是事务处理的线程而非后台线程每个线程在执行的时候要么选择了流水线中的一个阶段干活要么逛了一圈发现无事可做干脆回去接收更多的请求这里没有等待也无需切换充分的调动了每个线程的能力。 读操作
LSM 在处理多版本数据的方式是新版本数据记录会追加在老版本数据后面从物理上看一条记录不同的版本可能存放在不同的层在查询的时候需要找到合适的版本(根据事务的隔离级别定义的可见性规则)一般查询都是查找最新的数据总是由新的层次(最新写入)往老的层次方向找。
对于单条记录的查找而言一旦找到便可终止如果记录还在比较靠上的层次比如memtable很快便返回如果记录不幸已经落入了很低的层次(可能是很随机的读)那就得经历逐层查找的漫漫旅途也许 bloomfilter 可以跳过某些层次加快这个旅程但毕竟还是有更多的I/O操作。
X-Engine 针对单记录查询引入了 Row Cache在所有持久化的层次的数据之上做了一个缓存在 memtable 中没有命中的单行查询在 Row Cache 之中也会被捕获。Row Cache 需要保证缓存了所有持久化层次中最新版本的记录而这个记录是可能发生变化的比如每次 flush 将只读的 memtable 写入持久化层次时就需要恰当的更新 Row Cache 中的缓存记录这个操作比较微妙需要小心的设计。
范围扫描的操作就没这么幸运了。因为没法确定一个范围的key在哪个层次中有数据也许是每层都有只能扫描所有的层次做合并之后才能返回最终的结果。X- Engine 同样采用了一系列的手段比如 Surf(SIGMOD18 best paper)提供 range scan filter 减少扫描层数还有异步 I/O 与预取对大范围扫描也有显著的提升。 读操作中最核心的是缓存设计Row Cache 来应付单行查询Block Cache 负责Row Cache miss 的漏网之鱼也用来应付 scan由于 LSM 的 compaction 操作会一次大批量更新大量的 Data Block导致 Block Cache 中大量数据短时间内失效带来性能的急剧抖动。
X-Engine 同样做了很多的处理
减少 Compaction 的粒度减少 compaction 过程中改动的数据(见稍后章节) compaction 过程中针对已有的cache数据做定点更新由此可以基本将 cache 失效带来的抖动降到最低的水平。
X-Engine 中的缓存比较多样memtable 也可算做其中一种。以有限的内存如何恰当的分配给每一种缓存才能实现价值最大化是一个还未被妥善解决的问题X-Engine 也在探索当中。
当然LSM 对读带来的也并非全是坏处除了 memtable 以外的只读的结构在读取路径上可以做到完全无锁( memtable 也可设计成读无锁)。
Compaction
compaction 操作是比较重的。需要把相邻层次交叉的 key range 数据读出来合并然后写到新的位置。这是为前面简单的写入操作不得不付出的代价。X-Engine 为优化这个操作重新设计了存储结构。
如前所述X-Engine 将每一层的数据划分为固定大小的 Extent一个 Extent 相当于一个小的完整的 SSTable, 存储了一个层次中的一个连续片段其中又会被进一步划分一个个连续的更小的片段Data Block相当于传统数据库中的Page只不过是只读的而且是不定长的。 回看数据组织一节中合并操作对元数据的改变, 对比Metadata Snapshot2和Metadata Snapshot1的区别可以发现 Extent 的设计意图。是的每次修改对结构的调整并不是全部来过而是只需要修改少部分有交叠的数据以及涉及到的Meta Index节点。
两个Metadata Snapshot结构实际上共用了大量的数据结构。这个被称为数据复用技术(Data Reuse)而 Extent 大小正是影响数据复用率的关键Extent 作为一个完整的被复用的物理结构需要尽可能的小这样与其他 Extent 数据交叉点会变少但又不能非常小否则需要索引过多管理成本太大。
X-Engine 中 compaction 的数据复用是非常彻底的假设选取两个相邻层次(Level1, Level2)中的交叉的 Key Range 所涵盖的 Extents 进行合并合并算法会逐行进行扫描只要发现任意的物理结构(包括 Data Block 和 Extent )与其他层中的数据没有交叠则可以进行复用。只不过Extent的复用可以修改 Meta Index而 Data Block 的复用只能拷贝即便如此也可以节省大量的 CPU.
一个典型的数据复用在 compaction 中的过程可以参考下图 可以看出对于数据复用的过程是在逐行迭代的过程中完成的不过这种精细的数据复用带来另一个副作用即数据的碎片化所以在实际操作的过程中也需要根据实际情况进行折中。
数据复用不仅给 compaction 操作本身带来了好处降低操作过程中的 I/O 与 CPU消耗更对系统的综合性能产生了一系列的影响。比如 compaction 过程中数据不用完全重写大大减少了写入空间放大更因为大部分数据保持原样数据缓存不会因为数据更新而失效减少合并过程中因缓存失效带来的读性能抖动。
实际上优化 compaction 的过程只是 X-Engine 工作的一部分还有更重要的就是优化 compaction 调度的策略选什么样的 Extent定义 compaction 任务的粒度执行的优先级都会对整个系统性能产生影响可惜并不存在什么完美的策略X-Engine 积累了一些经验定义了很多规则而探索如何合理的调度策略是未来一个重要方向。
后记
X-Engine 是阿里云智能事业群-数据库产品事业部的重要核心技术之一。
作为兼容 MySQL 的数据库 POLARDB X 的存储引擎之前是在服务阿里集团业务中逐渐打磨成熟今年下半年我们将在阿里云平台上推出 MySQL(X-Engine) 的RDS 公有云服务为阿里云上的公有云客户提供低成本高性能的数据库服务。
原文链接 本文为云栖社区原创内容未经允许不得转载。
