发表于

Beyond malloc efficiency to fleet efficiency

内存分配的优化可以带来巨大的成本效益。一般有两种做法，一是提高分配器的效率，减少分配器代码中的周期；一种是通过数据放置的策略来提高应用的整体性能。这篇文章主要关注的是hugepage，提出了一个叫TEMERAIRE的hugepage机制，以最大化hugapage的覆盖率和最小化碎片开销。

Introduction

本文主要关注的是通过提高内存分配器的大页面覆盖率来提升应用性能。Cache miss和TLB miss是现代系统中最主要的性能开销，Hugepages的出现可以显著减少TLB未命中的数量，增加大页的大小使得相同数量的TLB条目能够映射更大范围的内存，另外大页还能减少miss+填充的时间，因为页表遍历更快了。论文提出了一种TEMERAIRE 的设计，作为TCMALLOC的一部分减少应用代码的CPU开销，最大化大页覆盖、减少内存碎片。

The challenges of coordinating Hugepages

虚拟内存是通过TLB来将用户空间地址转换为物理地址的，TLB条目有限，如果使用默认页面大小，整个TLB覆盖的内存范围很小。现代的处理器通过在TLB中支持hugepage来加大覆盖范围，完整的大页（比如X86时2MB）仅仅占用一个条目。

传统的分配器以页面大小的块来管理内存，Transparent Huge Pages机制为内核使用大页来覆盖连续页面提供了可能性。但内存的释放面临着更大的挑战，对于非大页区域来说，内存的释放要求内核使用较小的页面来表示剩余的内存。又或者大页的返回需要整个页面都变成空闲状态，这就带来内存碎片的问题。因此对于大页的设计需要在内存碎片和TLB使用率之间权衡。

Overview of TCMALLOC

下图展示了TCMALLOC的内存组织，TCMALLOC将内存按spans分区，并且与页面大小对齐。

足够大的分配请求由仅仅包含分配对象的spans实现，至于其他的span则会包含多个相同大小的小对象，小对象的边界是256KB，小于这个的请求会四舍五入到100个大小类别中去。TCMALLOC将对象存储在一系列缓存中，如下图所示。span是从一个简单的pageheap分配的，它跟踪所有未使用的页面并进行best fit分配。pageheap还会负责定期释放内存回操作系统，减少过多的系统内存分配。

TCMALLOC会首先从local cache中分配，这里用的是per-hyperthread local cache，本地缓存会存着不同大小的空闲对象列表。如果请求不能满足要求，会路由到对应大小类别的central cache。这里有两个组件，一个是小的、快速的、互斥保护的transfer cache，另一个则是大的、互斥保护的central列表，包含了该大小对应的每一个span。当一个span的所有对象都返回到central list的一个span时，该span就会返回到pageheap。

TCMALLOC的pageheap有一些简单的内存接口：New(N)分配一个N页的span；Delete(S)向分配器返回一个新的span；Release(N)将pageheap缓存的>=N个未使用的页返回给操作系统；

TEMERAIRE’s approach

TEMERAIRE就是基于TCMALLOC提出的大页优化，将分配请求尽可能打包到频繁使用的大页上，同时形成完全未使用的大页面以便遍返回给操作系统。并且根据malloc的使用情况和TCMALLOC的结构制定了一些TEMERAIRE的选择原则：

  • 总内存的需求随时发生变化，并且是不可预测的；
  • 将不是几乎为空的大页面返回给操作系统的成本是比较高的，因此其设计必须能够将分配密集地打包到高度使用的区域中；另外虽然我们的目标是专门使用大页大小的二进制，但malloc也必须支持大于单个大页的分配大小；
  • 当一个大页完全为空时，可以选择是保留它以供将来分配内存，也可以将其返回给操作系统。适应性地做出这个决策非常重要；
  • 很少有分配请求会直接接触pageheap，但所有分配都通过pageheap支持；

TCMALLOC分配器通过委托给几个子组件来实现它的接口，如下图所示，每个组件都是根据上述原则构建的，都对最适合它处理的分配类型进行了设计。虽然TEMERAIRE的特定实现与TCMALLOC内部结构相关联，但大多数现代分配器都有类似的大页面分配支持。

The overall algorithm

这一章主要描述各个组件，其主要目标是最小化或重用生成的slack（slack就是大页之间的多余空间区域）。所有组件的背后是HugeAllocator组件，它负责处理虚拟内存和操作系统之间的关系，为其他组件提供了可备份可传递的内存。HugeCache则是一个完全为空的大页缓存。HugeFiller则是一个存着部分填充空间的大页列表。HugeRegion则是用来应对大页边界的分配请求的。TEMERAIRE使用下图算法根据请求大小将分配决策定向到其子组件。

为大页面大小的精确倍数，或那些足够大以至于slack无关紧要的分配请求由HugeCache负责；中等大小的分配由HugeCache负责（1MiB到1GiB）；例如，来自HugeCache的4.5MiB分配会产生1.5MiB的slack，这里的开销是比较高的。TEMERAIRE通过假装请求的最后一个大页面有一个单一的“前导”分配，将这个slack交由HugeFiller负责。如下图：

对于某些中等分配的请求来说，其往往会产生更多的slack。如下图，例如，许多1.1MiB的分配将产生0.9MiB的每个大页的slack。当检测到这种模式时，HugeRegion分配器会跨越大页边界进行分配，以最大限度地减少这种开销。

小请求(<= 1MB的)始终由HugeFiller提供服务。对于1MB和大页之间的分配，TEMERAIRE会评估了几个选项：

  • 如果有足够的可用空间，就会尽量使用HugeFiller；
  • 如果HugeFiller不能满足请求，接下来会考虑HugeRegion；如果已分配的HugeRegion能满足要求，TEMERAIRE就会使用它。如果不存在满足要求区域，就会考虑分配一个区域；
  • 否则就从HugeCache中分配一个完整的大页面，当然这样会产生slack，但预期其会在未来被填平；

对于TEMERAIRE来说，1个1GB的空闲范围内存和512 个不连续的free大页是被同等对待。

HugeAllocator

HugeAllocator会跟踪记录所映射的虚拟内存，所有操作系统的映射都在此进行。

HugeCache

HugeCache以完整的大页粒度来追踪返还的内存范围，HugeFiller填充和释放大页后，需要决定何时将大页返回给操作系统，需要权衡后续是否需要使用来做决定。HugeCache的做法是在 2 秒的滑动窗口内跟踪请求的周期性，并计算记录最大值和最小值，每当内存返回到HugeCache时，如果cache此时大于Demand_max-Demand_min，则将大页返回给操作系统。

HugeFiller

HugeFiller用来满足较小的分配请求，每个分配请求都尽量在单个大页完成。HugeFiller满足了大部分的分配请求，是真哥哥系统中最重要的组件。对于给定的大页，使用best-fit的算法来进行分配。

HugeFiller的两个目标，一是使得一部分大页尽可能地满，另一部分大页面尽可能为空；第二个目标是最小化每个大页内的碎片，使得新分配请求尽可能得到满足。因为几乎为空的大页非常宝贵，通过尽可能保留具备最长空闲内存范围的大页来满足上面的目标，将相应的大页组织到一个排序列表中，充分利用每个大页的统计数据。

在每个的大页中，HugeFiller会记录使用的页面位图。为了填充某个大页的请求，HugeFiller会从该位图进行best-fit的搜索。并且还记录了以下几个数据：尚未分配的连续页数，最长的空闲内存范围L；分配总数A；已使用的页面总数U。

通过上述三个统计信息来确定分配大页的优先级顺序——选择具有最小的合适L和最大A的大页。这个的决策选择是根据大量实验做出来的。

HugeRegion

HugeCache与HugeAllocator足以满足大内存分配，HugeFiller适用于可以打包成单个大页面的小内存分配，HugeRegion则是用来处理两者不好应付的场景。

考虑对1.1MiB内存的分配请求，这可以通过HugeFiller分配，对于2MiB的大页会留下0.9 MiB未使用的内存：这里会预期slack会被小于1.1MB的分配请求填充。但极限情况下，很可能会有一个二进制只请求1.1MB的请求。

HugeRegion是一个固定大小的分配（当前为1GB），与HugeFiller使用位图类似，以小页粒度进行追踪。对于内存请求，一样是采用best-fit策略来应对。出于与HugeFiller相同的原因，其保留了这些区域的列表，按最长空闲内存范围进行排序。

大多数分配不需要HugeRegion，只有积累了大量比程序小分配数量更多的slack，才会分配HugeRegion。对于键值存储来说，它会将一些大块数据加载到内存，并为服务请求进行一些短期分配。如果没有HugeRegion，请求相关的分配很可能产生大量的空缺。

Memory Release

如上所述，Release(N)由后台线程定期调用。为了实现接口的Release(N)方法，TEMERAIRE通常只是从HugeCache中释放大页的内存范围。释放的页数量超过提示也不会有问题，后台线程会以实际释放的数量作为反馈，并调整未来的调用以达到合适的总体数量。如果HugeCache不能释放N页内存，HugeFiller将会释放最空的大页上的空闲小页。

从部分填充的大页面中释放小页是减少内存占用的最后手段，因为该过程在很大程度上是不可逆的。通过在大页上返回部分填充的小页，使操作系统用剩余页面的小条目替换跨越整个页面的单页表条目，这会增加TLB的miss概率，减慢对剩余内存的访问，即便后续重新使用前面释放的内存，Linux内核仍然只使用小的页表项。

HugeFiller会对部分释放的大页有单独的处理，除非没有其他大页可用，否则不会从它们进行分配，直到这些大页完全为空。

Conclusion

TEMERAIRE通过更改内存分配器的使用方式来优化TLB的查找性能，从而极大提高了应用程序的性能。

发表于

CockroachDB: The Resilient Geo-Distributed SQL Database

本文介绍了一个叫CockroachDB的数据库系统。

INTRODUCTION

对于现代数据库来说，OLTP的工作负载越来越与地理分布有关。一些应用可能针对不同的地区分布有着不同的数据库需求，比如某些地区的数据需要有更严格的权限控制满足法律法规，有些地区则是处于快速增长的阶段，需要考虑成本、延时、性能等等的情况。

CockroachDB作为一款商业DBMS，满足了全球化公司关于数据库系统的种种需求：

  • 容错和高可用性：在不同的地区为每个分区至少维护三个副本。节点故障，能自动恢复；
  • 地理分布和副本放置：CockroachDB支持水平伸缩，添加节点时自动增加容量并迁移数据。并根据需求选择最优的数据放置方法，同时支持用户自定义选择；
  • 高性能的事务：CockroachDB的事务协议支持跨多个分区的分布式事务，而不需要特定的硬件；

除此之外，CockroachDB还实现了最新的查询优化器和分布式SQL执行引擎来支持更全面的SQL标准。

SYSTEM OVERVIEW

Architecture of CockroachDB

CockroachDB是典型的shared-nothing架构，其所有节点都参与计算和存储。这些节点可由同个数据中心或者多个数据中心组成，client可以连接到任意的节点。在单个节点内部具备以下的分层架构：

SQL

SQL层是最上层，负责与client进行交互，包括了解析器、优化器和SQL执行引擎，其将SQL语句转化成对KV存储的读写请求。SQL层并不清楚数据的具体分区情况。

Transactional KV

SQL层的请求会来到事务KV层，负责确保跨KV对的更新原子性。

Distribution

该层根据key排序呈现了一个key空间的抽象，包括系统元数据和用户数据都可以在该key空间内查找。CockroachDB使用范围分区的方法将数据划分为大小约为64MiB的连续有序块，称之为Range。Range之间的顺序在一组系统Range内的两级索引结构（前面说过用于内部数据结构和元数据的系统数据也会组成Range）中维护。Range会被缓存起来用于快速查找，同时该层也主要负责对上层查询做路由。

Range大小为64MB，并根据需要对Range进行合并和拆分（数据太多就拆分，太少就合并，还有根据一些热点策略做Range划分）。

Replication

默认情况下，每个Range都是三个副本，每个副本存储在不同的节点上。

Storage

最底下的就是存储层，CockroachDB主要依赖了RocksDB。

Fault Tolerance and High Availability

Replication using Raft

CockroachDB使用Raft算法来进行一致性的复制，其中Range的副本会组成一个Raft组，每个副本要么是leader，要么是follower。CockroachDB的复制单元是Command，它表示的是对存储引擎进行的一系列底层修改，当Raft commit日志的时候，每个副本会将Command应用到存储引擎上。

CockroachDB使用Range级别的租约，其中一般是Raft组的leader来充当租约持有者，它是唯一可以提供最新读取信息或者发起提议的副本，所有的写入也是通过租约持有者进行。对于用户Range，节点会每隔4.5秒在系统范围内发送一套特殊记录的心跳；对于系统Range，则是每9秒更新一次租约。

同时为了保证一致性，一次只有一个副本存留，尝试获取租约的副本会通过提交特殊的租约获取日志来达成目的。

Membership changes and automatic load (re)balancing

集群支持节点的添加和删除，节点的变更会导致负载在集群活动节点之间重新分布。

对于短暂的故障，只要大多数副本可用，Raft算法能保证CockroachDB正常运行。如果leader失败，则依赖Raft重新选举leader。对于故障节点重新加入集群，则可以通过以下方式追上更新：发送完整Range数据的快照；发送一组要Apply的Raft缺失日志。二选一。

对于长期故障，CockroachDB则是会根据不受影响的副本，创建一个新的副本，将其放到合适的位置。

Replica placement

CockroachDB支持手动和自动来控制副本的放置。自动放置副本的机制会根据一定的约束条件进行，并且会尽量平衡负载。

Data Placement Policies

CockroachDB的副本和租约holder的放置策略可以由用户根据性能和容错能力决定：

  • 副本按地理位置分区；
  • 租约holder按地理位置分区；
  • 重复索引：通过基于表来复制索引，并将每个索引的lease holder固定到特定地区，CockroachDB就可以通过较快的本地读取功能，同时提高容错性，但可能会带来写放大和跨区写延时的提高；

TRANSACTIONS

CockroachDB的事务可以跨越整个key空间，能在保证ACID的前提下访问到跨越整个集群的数据。CockroachDB是使用MVCC的变形来支持串行化隔离的。

Overview

SQL事务从SQl连接的节点开始，该节点负责扮演事务协调者的角色。

Execution at the transaction coordinator

下面的算法给出了基于协调者角度的事务处理逻辑，在执行事务过程中，协调者接受一些列来自SQL层的KV操作。

从途中可以看出，在下一个操作发出前，需要对当前操作进行应答，为了提高性能，协调者做了两个优化：写流水线和并行提交。因此，协调者需要跟踪还没完全复制成功的操作和维护了事务时间戳（第一行）。

写流水线：如果某个操作未尝试提交，并且该操作与先前任何操作都没有重叠，则可能立即执行该操作（第七行）。这就是为什么写流水线可以对不同key的进行多个操作。如果该操作依赖于先前的操作完成复制，则需要pipeline等待。inflightOps就是对运行中的状态进行追踪。第九行就是协调者将操作发送给租约持有者并等待回应。如果返回的时间戳更待，意味着存在了另一个事务影响了租约持有者的时间戳。协调者此时会调整事务时间戳，并通过一轮RPC去验证新时间戳返回的值是否相同，如果不同则事务失败。（第十到十四行）

本质就是事务内语句流水线并行执行，如果两条语句有操作重叠，则通过事务上下文追踪执行过的key，如果重叠则需要等待其执行成功。

并行提交：一个标准的2PC，往往需要两轮consensus，一轮完成Prepare，一轮将事务设置为Committed。并行提交的做法是使用了staging来表示一个事务操作的所有写入是否已经都复制完成，持久化staging状态和Prepare写数据同时进行（第五行），假设两者都成功，则协调者可以立即确认事务已经提交（第十五行），并且在终止前会异步将事务状态记录为commit。（十六和十七行）

Execution at the leaseholder

如下，当lease holder接收到来自协调者的操作请求时，会按下图执行。第二行险检查租约有效性，第三行会去获取操作依赖的所有key的latch。第四行会校验相关依赖的操作完成。第五和第六行则是在执行写操作时，保证时间戳在任何冲突读取之后，并且根据需要增加时间戳。

接下来则是评估操作需要转换为对存储引擎的哪些操作。如果不是事务则无需要等待复制，lease holder可以直接响应协调者。如果是写操作则会被复制，达成共识后会应用到本地引擎。最后释放锁，响应协调者。

Atomicity Guarantees

CRDB通过观察所有事务的write intents来实现原子提交。write intents就是一个常规的MVCC kv对，所有写入都先写到临时的write intents，其带有的一个元数据指示是intents。该元数据会指向一个事务记录，事务记录就是一个特殊的key，保存了事务当前的状态：pending, staging, committed和aborted。通过write intents，一个Reader会读取其事务记录，如果事务记录已提交，则Reader会将intents视为常规值，并执行清除操作。如果事务是pending的，则会阻塞直至完成。如果是事务是Staging，则可能是commit，也可能是Abort，Reader尝试中止该事务。（如果所有写操作都已经完成复制，实际上就是commit，并对其进行更新）。

Concurrency Control

如前所述，CRDB对每个事务都以commit时间戳来执行写入和读取。这样可以实现串行化的执行，但同时也会因为事物之间的冲突需要调整时间戳。

Write-read conflicts

读请求遇到未commit的intent，如果其时间戳更小，则需要等待事务结束。否则可以忽略，并不需要等待。

Read-write conflicts

以时间戳tb写一个key的时候，如果存在对该key有更大时间戳tb的读请求，则无法直接写入。CRDB强制将写入事务的commit时间戳增加到tb以后。

Write-write conflicts

写请求如果遇到一个时间戳更小的未commit intent，则等到较早的事务完成。相反，遇到较大时间戳的committed key，则会推进该时间戳。写写冲突可能导致冲突，CRDB会采用分布式死锁检测算法来中止循环等待中的一个事务。

Read Refreshes

前面提到的冲突会导致事务的commit timestamp推进。如果可以证明事务在ta读取的数据于(ta, tb]时间间隔内没有更小，可以将事务的read timestamp推进到tb > ta。如果发生了数据变更，则会导致事务重启。

为了确定时间戳是否可以推进，CRDB会在事务的读取集中维护键的集合，并会发出一个Read Refreshes请求来确认key在某个时间间隔内有没有被更新。

Follower Reads

CRDB允许非租约持有者的副本通过查询修饰符“AS OF SYSTEM TIME”来为带有时间戳的只读查询提供服务。为了提供该功能，其要求在给定时间戳T上执行读取操作的非租约持有者副本确认：将来不存在任何写操作使得读操作无效，并且具备读取所需要的所有数据。即要求Follower提供在时间戳T上的读取内容，并且租约持有者不再接受时间戳T'<=T的写操作，Follower还要追上影响到MVCC快找的Raft前缀日志。

因此，租约持有者需要记录所有传入请求的时间戳，并定期在节点级别生成closed timestamp，在该时间戳以前，将不接受进一步的写操作。closed timestamp与当时的Raft日志索引一起在副本之间定期交换，这样Follower副本就可以使用该状态来决定它们是否剧本在特定时间戳下提供一致性读取所需的所有数据。

CLOCK SYNCHRONIZATION

CRDB不依赖特定的硬件来进行时钟同步，通过NTP或者Amazon Time Sync Service在公有云或者私有云的服务器即可。

Hybrid-Logical Clocks

CRDB在集群的每个节点里都维护一个混合逻辑时钟HLC，该时钟提供了物理时间和逻辑时间组合的时间戳。物理时间基于节点的粗同步系统时钟，洛基适中则是基于Lamport时钟。

HLC提供了一些重要的属性：

  1. HLC在每次节点交换时钟时通过其逻辑组建提供了因果追踪。节点在发送消息的时候会附加上HLC时间戳，并使用接收到的信息里的时间戳来更新本地时钟。
  2. HLC在单个节点上的重启内或者重启之间都提供了严格的单调性。
  3. 在瞬态时钟的偏斜波动情况下，HLC能提供自我稳定的功能。

Uncertainty Intervals

CRDB不支持严格的可串行化，而是通过追踪每个事务的不确定间隔来满足单key线性化属性，事务协调者的本地HLC会分配一个commit_ts，不确定性间隔为[commit_ts, commit_ts + max_offset]。

当事务遇到在高于commit_ts且在不确定间隔内遇到key时，它会执行不确定性重启，将commit_ts移动到高于不确定值的位置，并保持不确定间隔的上限不变。

Behavior under Clock Skew

这里主要是考虑时钟偏离范围的系统行为。本身在单个Range内，通过Raft日志的读写是能够保持任意时钟偏斜下的一致性。但因为引入了Range的租约，如果存在较大的时钟偏移，多个节点可能会发生脑裂，都认为自己拥有租约。CRDB采用两种保护措施来做保护：

  1. Range租约包含了开始和结束时间戳。租约持有者不能为超出租约间隔的读写提供服务；
  2. 每次写入Range的Raft日志时，都会包含建议使用的Range租约序列号。由于Range本身的租约变更也会被写入Range的Raft日志，因此某个时刻内只有一个租约持有者能够对Range进行变更；

SQL

SQL Data Model

每个SQL表或者索引都是存储在若干个Ranges里。所有的用户数据则存储在若干个索引中，其中一个是primary index，primary index在主key上，其他列存储在value里。Secondary Index则是在索引key上，并且还会存储主key以及所以模式所示定的任意数量列。

Query Optimizer

CRDB中的转换规则时通过Optgen的DSL编写的，提供了用于定义、匹配等简洁语法。Optgen编译为Go，然后与其余CRDB代码库无缝衔接。另外，考虑到CRDB的某些规则涉及到地理分布和分区性质，因此优化器会将数据分布考虑到cost model内，会复制辅助索引以使每个地区都有其自己的副本，从而提高性能，减少跨地区的数据通信。

Query Planning and Execution

CRDB的SQL查询执行存在两种模式： gateway-only mode和distributed mode。

由于分布层提供了一个全局key空间的抽象视图，SQL层可以对任何节点上的Ranges执行读写操作。CRDB根据需要的网络带宽来决定采用哪种模型。对于distributed mode，CRDB通过物理计划阶段，将查询优化器的计划转换为物理SQL运算符的有向无环图。物理计划将逻辑扫描操作分为多个TableReader操作符，每个节点都会包含一个扫描需要读取的Range。扫描被分割后，剩余的逻辑运算符会被安排到与TableReader相同的节点上，从而将filters, joins, and aggregations这些推到尽可能接近物理数据的位置。

在数据流内部，CRDB根据输入基数和计划复杂性采用两种不同的执行引擎： Row-at-a-time execution engine和Vectorized execution engine。前者主要是基于Volcano迭代器模型，一次一行。后者则是采用受MonetDB/X100启发的向量化执行引擎，主要面向的是列数据，而不是行，从CRDB的KV层读取时，会将磁盘数据从行格式转换为列格式，才发送会有用户之前再次将列格式转换为行格式。

Schema Changes

CRDB使用一种协议来执行Schema Changes，例如添加列或二级索引，该协议允许在Schema Changes期间保持表能提供在线的读写服务，允许不同的节点在不同时间内异步过渡到新表。具体的实现是将每个Schema Changes分解为一系列增量变更的协议来实现。

CONCLUSION

CockroachDB是一个开源的SQL DMBS，支持全球性分布的OLTP业务，并提供了灵活的SQL使用，保证了更好的伸缩性和高可靠性、高性能。

发表于

编码

第一章先来看一下Rocksdb的编码情况，具体的实现在：util/coding.cc, util/coding.h, util/coding_lean.h。Rocksdb的编码实现与leveldb基本一致的，由于需要将Key、Value等数据按序写入到内存中，并最终flush到磁盘上，因此需要一个高效的编解码实现。这里的编解码很多会用在key size、value size的整型编码上面。

Rocksdb的整型编码方式很简单，主要支持两种方案：定长编码和变长编码。

  • 定长编码：定长编码的实现比较简单，比如可以直接将4字节/8字节的整型直接按序写入到指定的位置；
  • 变长编码：节省空间，如果用定长编码的方式，实际上对于小数来说，很多位其实是没必要存储。结合ASCII码的特点，所有字符ASCII码的最高位都是0，可以利用最高位去做一些特别的标记；

实现

字节端序

关于编码，首先需要了解计算机在存储字节时分为大端字节序和小端字节序两种，Rocksdb是用小端序存储（低位放在较小的地址处，高位放在较大的地址处）的，因此需要提供根据不同平台对内存存储模型进行转换的选项。

在port/port.h文件内包含了一些平台相关的的头文件：

1
2
3
4
5
#if defined(ROCKSDB_PLATFORM_POSIX)
#include "port/port_posix.h"
#elif defined(OS_WIN)
#include "port/win/port_win.h"
#endif

以port_posix.h为例，这里包含了posix平台关于大小端的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#undef PLATFORM_IS_LITTLE_ENDIAN
#if defined(OS_MACOSX)
  #include <machine/endian.h>
  #if defined(__DARWIN_LITTLE_ENDIAN) && defined(__DARWIN_BYTE_ORDER)
    #define PLATFORM_IS_LITTLE_ENDIAN \
        (__DARWIN_BYTE_ORDER == __DARWIN_LITTLE_ENDIAN)
  #endif
#elif defined(OS_SOLARIS)
  #include <sys/isa_defs.h>
  #ifdef _LITTLE_ENDIAN
    #define PLATFORM_IS_LITTLE_ENDIAN true
  #else
    #define PLATFORM_IS_LITTLE_ENDIAN false
  #endif
  #include <alloca.h>
#elif defined(OS_AIX)
  #include <sys/types.h>
  #include <arpa/nameser_compat.h>
  #define PLATFORM_IS_LITTLE_ENDIAN (BYTE_ORDER == LITTLE_ENDIAN)
  #include <alloca.h>
#elif defined(OS_FREEBSD) || defined(OS_OPENBSD) || defined(OS_NETBSD) || \
    defined(OS_DRAGONFLYBSD) || defined(OS_ANDROID)
  #include <sys/endian.h>
  #include <sys/types.h>
  #define PLATFORM_IS_LITTLE_ENDIAN (_BYTE_ORDER == _LITTLE_ENDIAN)
#else
  #include <endian.h>
#endif

constexpr bool kLittleEndian = PLATFORM_IS_LITTLE_ENDIAN;
#undef PLATFORM_IS_LITTLE_ENDIAN

定长编码

定长编码比较简单，首先判断大小端序，对于小端，value本身就是按小端排放的，可以直接拷贝；对于大端，则是将value的最低位放置在内存的最低地址端。

1
2
3
4
5
6
7
8
9
10
inline void EncodeFixed32(char* buf, uint32_t value) {
  if (port::kLittleEndian) {
    memcpy(buf, &value, sizeof(value));
  } else {
    buf[0] = value & 0xff;
    buf[1] = (value >> 8) & 0xff;
    buf[2] = (value >> 16) & 0xff;
    buf[3] = (value >> 24) & 0xff;
  }
}

解码也一样，Rocksdb提供了三种整型编解码：uint16_t,uint32_t,uint64_t。解码时，gcc会优化里面的memcpy的操作，变成inline copy loops，提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline uint32_t DecodeFixed32(const char* ptr) {
  if (port::kLittleEndian) {
    // Load the raw bytes
    uint32_t result;
    memcpy(&result, ptr, sizeof(result));  // gcc optimizes this to a plain load
    return result;
  } else {
    return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0]))) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16) |
            (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24));
  }
}

变长编码

前面提到的，为了节省空间，Rocksdb使用变长的编码方式varint。Rocksdb使用最高位来表示编码是否结束，而低7bit则存储实际的数据。根据统计来说，小整型出现的概率更高，这样就能节省更多的空间，比如0-127的整数都可以只用一个字节来表示，而uint32较大的数字则需要5个字节。

1
2
3
4
5
6
7
0001 0001 ====>> 表示33
^                           A: 最高位为0，表示结束；
A
=======================================================
1000 0011 0110 1111 ====>> 表示1007
^         ^                 A: 最高位为1，表示未结束，实际值是000 0011；
A         B                 B: 最高位为0，表示结束，实际值是110 1111；

具体的编码以uint32_t为例，将uint32_t编码成变长字符：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
char* EncodeVarint32(char* dst, uint32_t v) {
  // Operate on characters as unsigneds
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  static const int B = 128;
  if (v < (1 << 7)) {
    *(ptr++) = v;
  } else if (v < (1 << 14)) {
    *(ptr++) = v | B;
    *(ptr++) = v >> 7;
  } else if (v < (1 << 21)) {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = v >> 14;
  } else if (v < (1 << 28)) {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = (v >> 14) | B;
    *(ptr++) = v >> 21;
  } else {
    *(ptr++) = v | B;
    *(ptr++) = (v >> 7) | B;
    *(ptr++) = (v >> 14) | B;
    *(ptr++) = (v >> 21) | B;
    *(ptr++) = v >> 28;
  }
  return reinterpret_cast<char*>(ptr);
}

uint64_t的变长编码实现，作者用了循环来编码，每7bit一组，并在最低位判断是否需要置位1。因此对于64位整型，最多需要10个字节：

1
2
3
4
5
6
7
8
9
10
inline char* EncodeVarint64(char* dst, uint64_t v) {
  static const unsigned int B = 128;
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  while (v >= B) {
    *(ptr++) = (v & (B - 1)) | B; // leveldb的实现是v | B; 不明白区别在哪
    v >>= 7;
  }
  *(ptr++) = static_cast<unsigned char>(v);
  return reinterpret_cast<char*>(ptr);
}

解码的实现也有一些优化，主要是利用内联函数提高效率，当数字小于等于127时，直接返回结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
inline const char* GetVarint32Ptr(const char* p,
                                  const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
    if ((result & 128) == 0) {
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

const char* GetVarint32PtrFallback(const char* p, const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const unsigned char*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return nullptr;
}

总结

编解码这里还是比较简单和高效的，比较有意思的是实现了一个variant编码，源码值得一看。

发表于

Dynamo

原文是2007年SOSP上Amazon发布的分布式存储经典论文《Dynamo: Amazon’s Highly Available Key-value Store》。这是一个高可用的分布式KV存储——Dynamo，Amazon的一些核心服务就是依赖Dynamo提供持续可用的服务，为了达到这种可用级别，Dynamo牺牲了几种特定场景下的一致性。并且，Dynamo大量地使用了对象版本化和应用层面的冲突解决机制。

INTRODUCTION

支撑着Amazon电商发展的是建立在分布于全球数据中心成千上万的服务器基础上的，因此对性能、可靠性和效率都有很高的要求。同时为了支撑业务的持续增长和避免因故障导致的经济损失，平台需要有足够好的可扩展性、可靠性。

Amazon使用的是去中心化的、松耦合的、面向服务的架构，这种服务架构对持续可用的存储技术有着强烈的诉求。例如，即便是磁盘故障、路由抖动、数据中心被摧毁，用户仍然能够向购物车添加和查看商品。因此Amazon推出了一款高可用的kv存储组件——Dynamo。Dynamo用于管理对可靠性要求非常高的服务，这些服务还要求对一致性、成本效率和性能有很强的控制能力。

Dynamo使用了一些常见的技术来实现了可扩展性和高可用性：

  • 数据通过一致性哈希来分区和复制；
  • 通过对象版本化来实现一致性；
  • 副本之间的一致性使用了类似quorum的技术和一个去中心化的副本同步协议；
  • gossip-based分布式故障检测和成员检测协议；

Dynamo是一个极少需要人工管理的、完全去中心化的系统，向Dynamo添加或者删除节点不需要人工调整哈希节点和重分布节点间数据。

BACKGROUND

传统上生产系统会使用关系型数据库来存储状态，但这并不是一种理想的方式，大多数服务并不需要RDBMS提供的复杂查询和管理功能，这些额外的支持带来的硬件成本并不经济，并且这类数据库的复制功能有局限，往往是通过牺牲可用性来换取一致性。

System Assumptions and Requirements

Dynamo对于使用它的服务有几点假设：

  • Query Model：通过唯一的key对数据进行读写，存储状态是binary objects。没有relational schema需求，无跨data items的操作。存储对象较小，往往小于1MB；
  • ACID Properties：Dynamo的设计目标是使用部分一致性来换取更高的可用性；
  • Efficiency：存储系统必须满足那些严格的SLA；
  • Other Assumptions：内部使用，假设环境足够安全；

Service Level Agreements (SLA)

在Amazon去中心化的基础设施中，SLA会扮演着重要的角色，客户端和服务端会定义一个 SLA协议。Amazon不是使用传统的平均值、中位数和方差来描述面向性能的SLA，而是更多使用了P99.9分布，来确定性能的长尾结果。

Design Considerations

前面提过，很多系统中数据复制算法一般是同步的，为了提供一个强一致性的数据访问结果，往往会牺牲掉某些场景下的可用性。考虑到这一点，Dynamo最终被设计为最终一致的数据存储系统。

在分布式系统中，需要关注的是机器或者网络故障时可能会导致数据冲突，需要检测和解决冲突。一些传统的数据库可能会在写的时候解决冲突，牺牲一点可用性。但Dynamo的目标是提供一个持续可写的存储，因此将解决冲突的逻辑放到了读操作，从而避免写操作被拒绝。同时Dynamo可以配置是存储系统来解决冲突还是应用选择自行实现冲突解决操作。

SYSTEM ARCHITECTURE

本文主要介绍了Dynamo用到的部分分布式系统技术：包括partitioning, replication, versioning, membership, failure handling 和 scaling。

System Interface

Dynamo的存储接口非常简单，只有两个：

  • get()：会返回存储key对应的所有对象副本，以及一个context；
  • put()：确定对象的存储位置，写入到相应的磁盘。

Dynamo将调用方提供的key和对象都视作是opaque array of bytes，其对key应用MD5哈希得到一个128bit的ID，并根据ID计算应该存储到哪个存储节点。

Partitioning Algorithm

Dynamo的设计有一个核心诉求：支持增量扩展。这就要求有一种机制能够将数据分散到系统的不同节点中，Dynamo的方案是基于一致性哈希，其哈希函数的输出是一个固定范围，作为一个循环空间环，每个节点会随机分配一个循环空间内的值，代表着节点在环上的节点。

Dynamo寻找item对应节点的方法：

  • 首先对key做哈希得到哈希值；
  • 然后在环上沿着顺时针方向找到第一个多带值被这个哈希值更大的节点；

这种方法有一个缺陷，就是每个节点随机分配的位置可能会导致数据不均匀分布负载，也没有考虑到节点的异构因素。为了解决这些问题，Dynamo做了优化，每个节点不是映射到环上的一个点，而是多个点。Dynamo使用了虚拟节点的概念，一个新节点加入到系统后，会在环上分配多个位置（对应多个token）。

虚拟节点的好处就是：

  • 当一个节点不可用离开时，会将该节点管理的虚拟节点平均分配给其他真实节点均衡管理；
  • 同理，新节点加入时，会从现有虚拟节点中拿出虚拟节点分配给新节点；
  • 一个节点负责的虚拟节点数量可以根据节点容量来决定，充分利用机器的异构性信息；

Replication

为了实现高可用性和持久性，Dynamo会将数据复制到N台机器上，N可配置。

具体的做法是，每个Key都会分配一个coordinator节点，coordinator负责落到它管理范围内的复制，除了自己存储一份之外，还会沿着顺时针方向的其他N-1个节点存储一份副本。

如下图，B除了自己存储一份之外，还会将数据存储到C和D节点。D实际存储的数据，其key范围包括了(A, B]、(B, C] 和 (C, D]。

存储某个特定key的所有节点会组成一个preference list，为了防止节点的failure，整这个preference list可能多于N个节点，另外由于引入了虚拟节点机制，preference list会保证N个节点不落在相同的物理机上。

Data Versioning

Dynamo提供最终一致性，所有更新操作会异步地传递给所有的副本。put()操作返回时，更新可能还没有应用到所有的副本，后续的get操作可能去不到最新数据。Amazon有些应用是可以容忍这种不一致性的，应用在这种情况下能继续运行。以操作购物车威力，如果购物车的最新状态不可用，用户对一个老版本的购物车状态做了修改，这种修改是需要保留的，由后续的步骤来解决冲突。

为了解决冲突，Dynamo将每次修改结果都作为一个全新的版本，允许系统多个版本共存。使得冲突一致化的两种方式：syntactic reconciliation和semantic reconciliation。在大多数情况下，新版本都包含了老版本的数据，而且系统可以判断哪个是权威版本，这就是syntactic reconciliation。

但是在发生故障并且并发更新的情况下，版本可能发生分叉，系统无法处理这种情况，需要客户端介入，从而将多个版本分支合并成一个，这就是semantic reconciliation。这种操作的好处是写操作永远可用，但会导致业务应用上一些奇怪现象，比如已经删除的商品偶尔又在购物车中冒出来。

Dynamo使用向量时钟（vector clock）来追踪同一个对象不同版本之间的因果关系，一个向量时钟就是一个 (node, counter) 列表。一个向量时钟关联了一个对象的所有版本，可以用来判断对象两个版本是并行分支还是具备因果关系。如果对象的第一个时钟上的所有 counter 都小于它的第二个时钟上的 counter，那第一 时钟就是第二个的祖先，可以安全的删除。否则需要进行reconciliation。

在Dynamo中，客户端更新一个对象需要指明基于哪个版本进行更新。流程是先读拿到context，context带有vector clock，写的时候把context带下去。在读的时候如果发现了多个版本，并且系统无法reconcile这些版本，就会返回所有的版本，待解决了冲突将多个版本分支合并起来。

以下图为例

  • 客户端写入一个对象。处理这个key的写请求节点Sx增加key的counter，系统有了一个对象D1和它的时钟[(Sx, 1)]；
  • 客户端更新这个对象。假设还是Sx处理这个请求。此时，系统有了对象D2和它的时钟 [(Sx, 2)]，但可能D1在其他节点的副本还没有看到这个更新；
  • 假设这个客户端，再次更新了对象，并且这次是由另外的一个节点Sy处理 请求。此时，系统有了D3和它的时钟[(Sx, 2), (Sy, 1)]。假设另一个客户端读取D2，并尝试更新它，写请求由另一个节点Sz处理。 现在，系统有D4（D2的后代），版本clock是[(Sx, 2), (Sz, 1)]。
  • 此时，D3和D4各自的改动都没有反映在对方之中。因此这两个版本都应当被保留，然后交给客户端，由客户端在下次读取的时候执行semantic reconciliation；
  • 假设某个客户端读到了D3和D4，即[(Sx, 2), (Sy, 1), (Sz, 1)]。如果客户端执行 reconciliation，并且节点Sx执行协调写，Sx会更新自己在clock中的序列号。最终新生成的数据D5的clock格式如下：[(Sx, 3), (Sy, 1), (Sz, 1)]。

vector clock的一个潜在问题是，如果有多个节点先后协调同一个对象的写操作，那这个对象的clock vector会变得很长。这种情况发生的可能性不大，只有在网络分裂或多台服务器挂掉的情况下，写操作才可能由非preference list前N个节点来执行，导致vector clock变长。

为了避免这个问题，Dynamo采用的方法是clock truncation scheme，另外保存一个和(node, counter) 对应的时间戳，记录最后一次更新该记录的时间，当vector clock达到阈值时就删掉最老的一个。这种方案可能会导致无法精确判断部分后代的因果关系，但论文说生产环境没遇到过这个问题。

Execution of get () and put () operations

Dynamo中所有存储节点都可以接受key的读写操作。

读写操作由Amazon基础设施相关的请求处理框架发起HTTP请求。客户端有两种选择：

  • 将请求路由到负载均衡器，由后者根据负载信息选择后端节点；
  • 使用能感知partition的客户端，直接路由到coordinator节点；

前者是负载均衡器转发到环上任意一个节点，如果收到请求的节点不是preference list前N个节点中的一个，那它就不会处理这个请求，而是转发到preference list第一个节点。

读写操作需要preference list中有不可用节点，就跳过。优先访问preference list中编号较小的节点。

为了保证副本的一致性，Dynamo使用了一种类似quorum的一致性协议。这个协议有两个配置参数：R 和 W：

  • R：允许执行一次读操作所需的最少节点数；
  • W：允许执行一次写操作所需的最少节点数；

设置R + W > N，就得到了一个quorum系统。在这种模型下，读写请求由R/W副本中最慢的一个决定。

当收到写请求后，coordinator 会为新版本生成 vector clock，并将其保存到节点本地。然后将新版本（和对应的vector clock）发送给N个排在最前面的、可用的节点，只要有至少W-1个节点返回成功，就认为写操作成功。

读操作类似，如果coordinator收集到多个版本，它会将所有系统判断没有因果关系的版本返 回给客户端。客户端需要对版本进行reconcile，合并成一个最新版本，然后将结果写回 Dynamo。

Handling Failures: Hinted Handoff

如果使用传统的quorum算法，Dynamo无法在节点不可用时保持可用。Dynamo采用了一种更为宽松quorum：所有读和写操作在preference list的前N个健康节点上执行，遇到不可用节点，会沿着哈希环的顺时针方向顺延。

以下图为例，如果A临时不可用，正常情况下发到A的请求会发送到D，发到D副本的元数据中会提示这个副本数据应该发到A，然后这个数据会被D保存到本地的一个独立数据库中，并且有一个定期任务不断扫描，一旦A可用了，就将这个数据发送回 A，然后D就可以从本地数据库中将其删除了。

Handling permanent failures: Replica synchronization

如果出现了在hinted副本移交给原副本节点之前就变的不可用，就会威胁到持久性。Dynamo基于Merkle trees实现了一种逆熵（副本同步）协议来保证副本是同步的。

Membership and Failure Detection

Ring Membership

Amazon使用显式机制来向Dynamo环增删节点，管理员通过命令行或web方式连接到 Dynamo node，然后下发一个成员变更命令增删节点。负责处理这个请求的 node 将成员变动信息和对应的时间写入持久存储。成员变动会形成历史记录。Dynamo使用一个gossip-based的算法传播成员变更信息。

External Discovery

上面的逻辑会有个问题，假设管理员同时添加两个节点，那么它们不会立即感知到对方，导致临时的逻辑分裂。为了避免这个问题，论文将部分Dynamo节点作为种子节点，所有节点都知道种子节点的存在，因为所有节点最终都会和种子节点reconcile成员信息，所以逻辑分裂就几乎不可能发生了。种子是从静态配置文件或者配置中心获取的。

Failure Detection

故障检测在Dynamo中的读写操作或者partition和hinted replica时移跳过不可用的节点。其做法是，节点B只要没有应答节点A的消息，A就认为B不可达。在有持续的client请求时，Dynamo Ring上的节点会有持续的交互，能定期检查及诶但是否恢复。使用简单的gossip协议就可以感知到节点的增删。

Adding/Removing Storage Nodes

当新节点加入系统后，会获得一些随机分散到Ring上的token，此时原本负责某些key range的节点会将此时负责的key转移到新节点。

IMPLEMENTATION

Dynamo支持选择不同的本地存储组件来作为存储引擎，其实以插件的方式引入的，包括了BDB、Mysql、in-memory buffer with persistent backing store等。应用能够为不同的访问类型选择最合适的存储引擎。

coordinator会代替客户端执行读写请求，每个客户端请求都会在收到这个请求的节点上创建一个状态机，包括了所有相关的逻辑。

对于写请求，前面提到过由preference list前N个节点中任一个coordinate，总是由第一个来coordinate的好处是使得在同一个地方完成写操作的顺序化，但可能会导致复杂不均匀。为了解决这个问题，preference list内的所有N个节点都可以coordinate写操作，另外由于写操作前面都带有读操作，写操作的coordinator会选择前一次读操作返回最快的节点（这个信息会被存在返回的上下文中）。由于这项优化使得前一次读操作选中的存储节点更容易被选中，提高了read-your-writes的概率。

CONCLUSIONS

本文介绍了Dynamo作为一个高可用、高可扩展性的数据存储系统，在Amazon的诸多核心系统中都有应用。Dynamo提供了期望的可用性与性能，能够很好处理节点不可用、网络分裂的情况。Dynamo最大的意义是证明了：一些去中心化的技术结合起来能够提供一个高可用的系统，并且在很多应用环境中投产了。

发表于

TIDB

ABSTRACT

Hybrid Transactional and Analytical Processing (HTAP，混合事务和分析处理)数据库要求独立地处理事务和分析查询，避免相互干扰。为了实现这一点，需要为两类查询维护不同的数据副本。然而，为存储系统中的分布式副本提供一致性视图并不容易。在该系统中，分析请求可以大规模地、高可靠性地从事务工作负载中读取一致的实时数据。

INTRODUCTION

关系型数据库（RDBMS）一直因其关系模型、强力的事务保证和SQL接口而广受好评，但它不具备高可扩展性和高可用性。因此NoSQL就应运而生，像Google bigtable和DynamoDB之类的放宽了一致性要求，提供了更高的可扩展性。但由于业务又需要事务处理能力、数据一致性和SQL接口等，就慢慢出现了像CockroachDB和Spanner之类的NewSQL。此外，像许多架构在Hadoop之上的SQL系统一样，在线分析处理系统（OLAP）也在迅速发展。

以前一般认为针对OLAP和OLTP应该采用的不同的数据模型和技术方案，但维护多个系统的成本很高。业界开始探索OLTP和OLAP的混合系统HTAP。HTAP系统需要满足几个关键点：一是数据新鲜度，即OLAP需要拿到最新的数据；二是隔离，即为单独的OLTP或者OLAP查询提供不同的硬件资源处理，避免性能相互影响。

本文就是基于上面的考虑，提出了一个以Raft为共识算法的HTAP数据库——TiDB，在Raft中引入了一个专门的节点Learner，Learner会异步地复制Leader节点的事务日志，并为OLAP查询构造新副本，并将日志中的行格式元组转换为列格式，便于查询。

RAFT-BASED HTAP

使用共识算法如Raft、Paxos等可以基于复制状态机在服务器之间实时可靠地复制数据，通过调整，该论文的做法可以针对不同的 HTAP 工作负载将数据复制到不同的服务器，并且保持资源隔离和数据新鲜度。

如上图所示，TiDB将数据按行格式存储在多个Raft Group里，每个Raft Group由一个Leader和多个Follower组成，另外为每个组增加一个Learner角色，可以异步复制Leader的数据，并将行格式转换为列格式。另外，扩展的查询优化器用来构建访问列存和行存的物理计划。

在该实现中，Leader不参与Leader选举，也不计入日志复制的个数，不参与Quorum。读数据时，需要保证Leader和Learner之间的强一致性和日志复制的低延迟。行列格式的转换也有优点，行格式可以利用索引来高效进行事务查询，列格式可以有效利用数据压缩和矢量化处理。由于Learner部署在单独的物理资源中，OLAP和OLTP可以在独立的资源中得到处理。

总的来说，这个设计克服了几个困难：一是基于Raft的系统如何应对高并发读写；二是资源独立如何保证数据新鲜度；另外就是如何构建查询计划在行式存储和列式存储中选择最优的。

ARCHITECTURE

如下图所示，这是TIDB的架构，兼容MySQL协议，由三个核心组件组成：分布式存储层、Placement Driver布局驱动器和计算引擎层。

  • 分布式存储层

由行式存储（TiKV）和列式存储（TiFlash）组成，存储在TiKV的数据是有序的key-value对，key由两个整数table id和row id组成，其中row id就是主键列，value就是真实的行数据。

1
2
Key: {table{tableID} record{rowID}}
Value: {col0, col1, col2, col3}

为了保证可扩展性，TiDB采用了range partition的策略，将kv对映射分割成若干个连续的范围，每个范围称为一个region，每个region都有多个副本来保证可用性，Raft就是用于维护每个region中若干个副本的一致性的。

PD负责管理region，包括提供每个key对应的region和其物理位置，以及自动转移region以平衡负载。同时PD也是时间戳分配器，提供了严格递增全剧唯一的时间戳。PD不具备持久状态。

计算引擎层是无状态、可扩展的，其SQL引擎由cost-based query optimizer和distributed query executor组成。另外TiDB基于Percolator实现了2PC协议。

除此之外，TiDB还与Spark集成，方便集成TiDB和HDFS中存储的数据。

MULTI-RAFT STORAGE

下图展示了分布式存储层的架构，其由TiKV和TiFlash组成。每个Region的副本之间都使用Raft来维护数据一致性。当数据复制到TiFlash的时候，为了方便扫描，多个Regions会被合并成一个Partition。

Row-based Storage

TiKV是由多个TiKV服务器组成的，每个TiKV服务器都可以是不同Region的Raft Leader或者Follower，另外在TiKV服务器上，数据和原数据都会保存在RocksDB上。

基于Raft算法响应读写请求的过程如下：

  1. Region的Leader从SQL引擎层接受请求；
  2. Leader将请求Append到日志中；
  3. Leader向Follower发送新的日志条目，Follower会将接收到的日志Append到自己的日志中；
  4. Leader等待Follower回应，满足指定数量的节点响应成功后，Leader会在本地commit并Apply；
  5. Leader将结果发送给客户端；

Optimization between Leaders and Followers

为了提高吞吐，可以在Leaders和Followers之间的操作做一些优化。首先是，上述过程的第二步和第三步可以并行进行，即便第二步失败了，只要第三步成功了仍然可以提交日志。另外就是，第三步中Leader可以缓冲这些日志条目，并批量发送。并且发送日志后也不需要等待Follower响应，可以假设发送成功，并利用预测的日志索引发送后来的日志。即便出现错误，Leader可以调整日志索引进行重发。还有就是，第四步中，Leader应用日志可以交给其他线程去做。整体流程就变成：

  1. Region的Leader从SQL引擎层接受请求；
  2. Leader并行地向Follower发送日志，并同时Append本地日志；
  3. Leader继续接收请求，重复2；
  4. Leader commit日志，并将应用逻辑交给另外的线程去做；
  5. 应用日志后，Leader返回结果；

Accelerating Read Requests from Clients

从Leader读取数据具有线性化的语义，但通过常规的Raft流程来保证会导致很高的网络IO开销。为了提高性能，可以避免日志同步阶段。

Raft保证：一旦Leader成功写入数据，就可以响应任何读取请求，而无需同步日志。但Leader是可能改变的。为了实现从Leader读取，TiKV做了以下优化：

  • read index：Leader响应请求时，会将当前的提交索引记录为本地read index，然后向Follower发送heartbeat确认Leader地位。如果确实是Leader，并且应用的索引大于或等于read index，就可以返回值。
  • lease read：为了减少heartbeat开销，Leader和Follower之间维护一个Lease期限，Follower在这期间不发出选举请求，因此Leader在此期间也无需与Follower进行heartbeat交流。

Follower也可以响应client的读请求，但需要向Leader询问read index，如果本地应用索引等于或大于read index，则Follower可以将值返回给客户端。

Managing Massive Regions

为了实现跨机器平衡Region，Plancement Driver会对Region副本数量和位置施予限制。一个就是必须要在不同的TiKV实例上放置至少三个Region副本。PD通过Heartbeat从服务器收集信息、监控服务器负载，并将热Region进行转移。

另一方面，维护大量Region涉及Heartbeat信息和元数据管理导致的大量的网络和存储开销，会被PD根据负载情况调整心跳频率。

Dynamic Region Split and Merge

这里主要设计Region的拆分和合并。热点Region或者大型Region会被拆成小Region，小或者访问少的Region，会被合并成大Region，以减少由于维护小Region心跳和元数据带来的网络和CPU开销。

PD操作Region，是通过向TiKV发送拆分和合并指令，然后以Raft流程来完成更新请求。Region拆分比较简单，只需要更改元数据。合并的话，PD会移动两个Region的副本，放到单独的服务器上。然后通过两阶段操作，在每台服务器上本地合并两个Region的并置副本：即停止其一Region的服务并将其与另一Region合并。

Column-based Storage (TiFlash)

考虑到TiKV中的行存数据并不适合OLAP，因此将列存储TiFlash合并到TiDB中。TiFlash由Learner节点组成，仅从Raft组接收Raft日志，并将行格式的元祖转换为列存数据。

用户可以通过SQL语句为表设置列格式副本，ALTER TABLE x SET TiFLASH REPLICA n;其中x是表名，n是副本数量。在TiFlash中，每个表会按partitions进行划分，每个partitions包括几个连续Regions，更大的Regions便于范围扫描。

当初始化一个TiFlash实例时，相关Region的Leader开始讲数据复制到新的Learner。一旦初始化完成后，TiFlash开始监听Raft组的更新。Learner收到日志后，会将日志应用到本子状态机，包括日志重放、转换数据格式和更新本地存储中的引用值。

Log Replayer

由于在Raft中，Learner接收到的日志时可线性化的，因此重放日志也会按照FIFO的策略重放日志，具体步骤包括：

  • 压缩日志：事务日志分为三种状态：预写、提交或回滚。回滚的日志不需要写盘；
  • 解码元组：缓冲区中的日志被解码为行格式的元组，去除关于事务的冗余信息；
  • 转换数据格式：行元组会被转换为列数据；

更具体的步骤可以参考上图。

Schema Synchronization

为了实时将元组转换为列格式，Learner需要知道最新的schema，因此TiFlash会通过Schema syncer与TiKV中最新的Schema同步。同时为了减少TiFlash向TiKV的请求次数，每个Learner都会维护一个schema cache。这里采取两阶段策略：

  • Regular synchronization：定期同步；
  • Compulsive synchronization：synced检测到不匹配的schema，就会主动从TiKV拉去最新的Schema；

Columnar Delta Tree

TiFlash设计了一个新的列存储引擎——Delta Tree，该引擎支持快速追加增量更新，然后将其与每个Partitions的稳定版本合并。如下图所示，在Stable space中，Partitions以chunks的形式存储，每个chunk都覆盖了一个较小的元组范围。TiFlash将元组的列数据及其元数据存储到不同的文件中，以同时更新文件。

新进来的增量更新时插入或者删除数据的原子批处理，这些增量会缓存到内存中，并持久化道磁盘。另外TiFlash会定期将小增量压缩成大增量，并持久化。传入增量的内存副本有助于读取最新数据。

另外，读取的时候由于需要合并增量文件和稳定空间中的数据，而且增量文件本身也可能存在空间放大的问题。TiFlash需要定期将增量合并到稳定空间中，每个增量文件及其相关chunks被读入内存进行合并，合并后的chunks自动替换磁盘中的原始chunks。

由于相关的键在增量空间中是无序的，合并成本较高，并且也会影响合并读的速度，因此会在增量空间构建B+ Tree索引，每个增量更新项都被插入到 B+ Tree 中，并按其关键字和时间戳进行排序。便于快速响应读请求，和有序数据也更易与稳定块合并。

Read Process

与Follower read类似，Learner提供snapshot isolation，在接收到读取请求后，Learner向其Leader发送read index请求，以获取涵盖所请求时间戳的最新数据。Learner拿到日志后，回放日志，写入Delta Tree，就可以读到特定数据响应请求了。

HTAP ENGINES

为了提供OLAP和OLTP查询，TiDB引入了SQL引擎来为了查询计划做决策。SQL引擎使用Percolator模型来实现分布式集群的乐观和悲观锁，并基于优化器、索引和下推算子来支持OLAP查询。

Transactional Processing

TiDB为ACID事务提供了snapshot isolation语义或者repeatable read语义，前者允许每个请求读取版本一致的数据，后者则是事务中的不同语句可能为同一个key读取不同的值，但重复读取将会读取到相同的值。这是基于MVCC实现。

如下图，TiDB中的事务由SQL引擎、TiKV和PD三个组件共同完成：

TiDB对于悲观锁和乐观锁的实现启发自Percolator模型。

  1. client接收到Begin命令后，SQL引擎向PD请求一个start_ts时间戳；
  2. SQL引擎从TiKV读取数据并在本地内存中执行SQL DMLs。TiKV提供在start_ts之前最近的commit_ts数据；
  3. SQL引擎收到client的commit命令后，启动2PC协议。随机选择一个主键，并行锁定所有的key，并将prewrite发送TiKV节点；
  4. 如果所有的prewrite都成功了，SQL引擎会向PD请求一个commit_ts，并向TiKV发送commit命令。TiKV commit主键，并响应成功回到SQL引擎；
  5. SQL引擎向Client响应成功；
  6. SQL引擎向TiKV发送commit命令，异步并行地提交从键和清除锁；

悲观事务和乐观事务的区别在于获取锁的实际，前者是在第二步执行DMLs的时候获取，后者则是第三步prewrite的时候。

Analytical Processing

TiDB通过两阶段查询优化来实现优化器：rule-based optimization生成逻辑计划， cost-based optimization将逻辑计划转换为物理计划。由于TiDB有两类存储、因此扫描表往往有三种选项：扫描TiKV的行格式表、扫描TiKV中有索引的表和骚婊TiFlash的列。

索引可以提高点查询和范围查询的性能，TiDB实现了可扩展性的索引，由于维护索引会消耗大量资源，因此会在后台以非同步的形式构建或删除索引。索引是以与数据相同的方式按Regions分割，并作为键值存储在TiKV 中。唯一键索引上的索引项编码为：

1
2
Key: {table{tableID} index{indexID} indexedColValue}
Value: {rowID}

非唯一索引上的索引项被解码为

1
2
Key: {table{tableID} index{indexID} indexedColValue rowID}
Value: {null}

物理计划的执行是由SQL引擎层使用pulling iterator model进行的，通过将部分计算下推到存储层，可以进一步优化执行。在存储层，执行计算的组件称为coprocessor，coprocessor在不同的服务器上并行执行substrees of an execution 破烂，这减少了必须从存储层发送到引擎层的元组数量。

总结

本文主要是介绍了一个投入生产环境的HTAP数据库——TiDB。TiDB建立在TiKV上，这是一个基于Raft的分布式行式存储，并引入一个TiFlash组件用于实时分析，作为Raft的learner从TiKV异步复制日志，并将行格式的数据转换为列格式。

发表于

SuRF

本文介绍了一种SuRF的数据结构实现，用以替代传统的布隆过滤器，支持单点查询和范围查询使用。

INTRODUCTION

LSM树是市面上数据库常用的底层存储引擎，能提供快速写和一定速度的读取。但该设计的一个问题是由于SSTable的多层设计导致大量磁盘IO读取，由此引入了布隆过滤器作为内存数据结构来帮助查询。布隆过滤器对于单点查询很有用，但并不能处理范围查找，尽管也有一些类似的设计（如前缀布隆过滤器）做了优化，但总体不够灵活通用。

因此本文提出了Succinct Range Filter（下文简称SuRF），这是一种快速紧凑的过滤器，提供了精确匹配过滤、范围过滤和近似范围计数等功能。SuRF是建立在Fast Succinct Trie（FST）这一新型空间高效简洁的数据结构上，FST每个trie节点仅需要10bit。文章使用SuRF替代了RocksDB的布隆过滤器，这将范围查询的速度提高了1.5倍到5倍，但极端情况下会导致单点查询变慢40%。

FAST SUCCINCT TRIES

SuRF的核心数据结构是FST，这是一种空间优化的静态tire，可以做单点查询和范围查询，其设计基于以下的思路：一个tire的上层节点较少，但访问量很大；下层节点虽多，但访问不算频繁。因此FST使用了基于位图的快速编码方案（LOUDS-Dense）来对上层节点编码，下层则用LOUDS-Sparse方案来编码，节省空间。

Background

如果一颗树所占用的空间接近于信息论的下限，则该树可以认为是succinct。论文使用的是一种叫Level-Ordered Unary Degree Sequence的技术，LOUDS以广度优先的顺序遍历节点，并使用一元编码Unary coding对每个节点的度进行编码，例如下图节点3有三个字节点，因此被编码成"1110"。

编码完成后，该树会变成一组bit序列，需要访问节点时，则使用rank＆select两种操作：

  • rank1(i): 返回[0, i]位置区间中, 1的个数；
  • select1(i): 返回第i个1的位置(整个bit序列)；
  • 对应的则是rank0(i)和select0(i)操作；

如今关于rank＆select的实现会使用查找表预算存取计算好的结果，保证查询时可以在常数时间里完成。有了rank＆select的支持，LOUDS就可以在常数时间内实现SuRF需要的点查询和范围查询。假设节点代号和bit位置都是从0开始的：

  • 在bit序列中第i个节点的位置：select0(i)+1；
  • 在bit序列中从p开始的节点的第k个子节点：select0 (rank1 (p + k)) + 1；
  • 始于p的节点的父节点位置：select1 (rank0 (p))；

LOUDS-Dense

LOUDS-Dense使用三个bit map和一个value的字节序列对每个trie节点按层级进行编码：

  • D-Labels：记录每个节点的分支标签；上图中根节点具有标记为f，s和t的三个分支。 D-Labels位图设置第102位（f），115位（s）和116位（t）并清除其余位；
  • D-HasChild：表示节点是叶子节点还是中间节点，以上图根节点为例，f和t都有子节点，但s没有，所以102和106两个bit会设置为1；
  • D-IsPrefixKey：标记当前前缀是否为有效key；以上图根节点为例，f既作为前缀，同时也是trie里的有效key；
  • D-Values : 存储的是固定大小的 value，本文中则是三种后缀的指针；

用rank&select操作trie树，则是：

  • 第一个孩子节点：D-ChildNodePos(pos)=256 × rank1(D-HasChild, pos)；
  • 父节点：DParentNodePos(pos)=select1(D-HasChild,[pos / 256])；

LOUDS-Sparse

如上图所示，LOUDS-Sparse使用四个字节或者bit序列对trie节点进行编码，然后将编码的节点按层次顺序进行串联。

  • S-Labels：记录分支标签，按level order顺序记录所有节点的label，并且使用0xFF($)来标记该key同时也是key节点；
  • S-HasChild：使用一个bit记录节点的label是否含有分支子节点；
  • S-LOUDS：使用一个bit记录每个label是否为该节点的第一个label；
  • S-Values：与上面类似；

用rank&select操作trie树，则是：

  • 孩子节点：S-ChildNodePos(pos) = select1(S-LOUDS, rank1(S-HasChild, pos) + 1);；
  • 父节点：S-ParentNodePos(pos) = select1(S-HasChild, rank1(S-LOUDS, pos) - 1)；

LOUDS-DS and Operations

LOUDS-DS就是一种混合trie，上层用LOUDS-Dense编码，下层使用LOUDS-Sparse编码。其中的分界点则根据性能和空间进行调整，LOUDS-Dense-Size(l)表示从0到l（不包含l）层采用LOUDS-Dense编码，而LOUDS-Sparse-Size(l)则表示从l到H层采用LOUDS-Sparse方式编码：

1
LOUDS-Dense-Size(l) × R ≤ LOUDS-Sparse-Size(l) // 通常使用R = 64作为默认值，R越小，性能越好但空间使用更多

LOUDS-DS支持三个基本操作：

  • ExactKeySearch(key)：如果key存在，则返回key的值（否则返回NULL）；
  • LowerBound(key)：返回一个迭代器，该迭代器指向的键-值对(k, v)，其中k是按字典顺序的满足k≥key的最小的键；
  • MoveToNext(iter)：将迭代器移至下一个键值；

对于点查询，则是先在LOUDS-Dense上查询，查不到即到LOUDS-Sparse查询。对于范围查询，则是执行LowerBound，找到最小的满足k≥key的键后，则光标将从当前的叶子标签位置开始并向前移动，就是正常的tree搜索方式。

Space and Performance Analysis

考虑到在LOUDS-DS中LOUDS-Sparse的节点更多，假设这是一个具备n个节点的trie，其中会有8n位用于S标签，2n位用于S-HasChild和S-LOUDS，总共10n位。

对于点查询，在每个LOUDS-Dense级别上进行搜索都需要两次数组查找，以及对位向量D-HasChild的rank操作。因此，主要操作是对所有位向量进行rank和 select，并在LOUDS-Sparse层进行标签搜索。

Optimizations

论文针对LOUDS-DS中的三个关键操作：rank、select和label search进行了优化。

  • Rank

上图展示了一个简洁的Rank结构，将bit vector分割成B bits大小的块，每个块用32bits的字段预先计算好的到这个block的rank值。对于一个pos来说，就有rank1(pos) = LUT[i / B] + popcount[i / B * B, i]。popcount是内置的CPU指令，可以快速计算出某一段区间1的个数。

  • Select

同样是使用LUT的方法，预先计算好值。假设采样周期是3，上图中第三个LUT保存的就是3x2，也就是第6个1的pos值，即8。那就有select1(i) = LUT[i / S] + (selecting (i - i / S * S)th set bit starting from LUT[i / S] + 1) + 1。

  • Label Search

使用SIMD指令在LOUDS-Sparse中执行标签搜索。

  • Prefetching

在切换到LOUDS-DS中的不同位/字节序列之前进行预取。

SUCCINCT RANGE FILTERS

基于FST构建SuRF，最重要的是在false positive rate和filter所需要的内存使用之间取得平衡。论文的做法是使用裁剪trie，通过截断低层次的trie，并使用从key获得的后缀位（key本身或者key的哈希值）做替代。论文介绍了4种不同的trie树裁剪方式。

  1. Basic SuRF

Basic SuRF的基本思路就是只存储key的共有前缀和一个额外的byte，裁剪掉树的部分叶节点。Basic SuRF的FPR与key的分布有关。

  1. SuRF with Hashed Key Suffixes

在Basic SuRF基础上，通过对key进行哈希计算，将hash值的n个bits存储到value中，这种方法可以降低FPR，但对范围查询没有帮助。

  1. SuRF with Real Key Suffixes

SuRF-Real存储n个bits的真实key，这样同时增强了Point query和Range query，但其FPR还是要比SuRF-Hash高。

  1. SuRF with Mixed Key Suffixes

SuRF-Mixed的做法是混合使用2和3两种方式，一部分是real key，另一部分是hashed key。

Operations

论文总结了如何使用FST实现SuRF的基本操作。

  • build(keyList)：根据给定的key构建fitter；
  • result = lookup(k)：对k执行点查询，返回true意味着k可能存储。以上面SuRF为例，首先搜寻key，直到叶子结点。如果未到叶节点就终止了则返回false；否则计算k的相关bits与叶节点的相关bits做比较；
  • iter, fp_flag = moveToNext(k)：这个操作实际上是LowerBound执行，返回满足>=k的最小key的双向迭代器；
  • count, low_fp_flag, high_fp_flag = count(lowKey, highKey)：返回在[lowKey, highKey]范围内的key个数；

EXAMPLE APPLICATION: ROCKSDB

论文将SuRF与RocksDB集成在一起，以替代其Bloom过滤器。下图显示了RocksDB中Get，Seek和Count查询的执行路径。Next的核心算法类似于Seek。过滤器操作在红色框中。如果该框为虚线，则可能由于误报需要检查边界key。

对于Get(key)，SuRF的用法与Bloom过滤器完全相同。

对于Seek(lk, hk)，RocksDB首先通过在块索引中搜索lk来决定所有级别的候选SSTable。在没有SuRF的情况下，RocksDB会检查每个候选SSTable并获取满足>=lk的最小的块。 RocksDB然后比较候选key，找到全局最小key。使用SuRF，则无需获取实际的块，RocksDB可以通过在其SuRF上执行moveToNext(lk)查询来避免每个SSTable都进行IO，从而获取每个SSTable的候选key。如果查询成功（例如，是Open Seek或K≤hk），RocksDB将从选定的SSTable中精确地获取一个包含全局最小值K的块。如果查询失败（即，K>hk），则不没有读盘IO。

CONCLUSION

本文介绍了SuRF，该filter支持单点查询、范围查询和计数查询，SuRF建立在一个新的succinct数据结构上，即FST。FST的性能极高，并且SuRF本身的内存使用也是较为搞笑的，其空间使用与FPR的权衡可以通过不同数量的后缀位来调整。通过在RocksDB上替换了bloom filter的测试，显著地减少了IO并提高了范围查询的吞吐量。

发表于

Percolator

本文是谷歌的经典论文，介绍了一个对大型数据集做增量处理更新的系统Percolator，谷歌用它来构建索引系统，极大地提高了处理速度。Percolator基于BigTable构建的，由于BigTable不支持跨行事务，更像是给BigTable打补丁。

Introduction

索引系统是Google Web搜索的核心系统，在应对海量索引数据时，索引创建和索引的实时更新必须要面对的挑战。Google使用Mapreduce解决了高效创建索引的问题，但MR对于实时更新的场景是不合适的，因此他们构建了一个新的增量更新系统Percolator。Percolator主要关注的是跨行事务和Notification，支持在PB级别存储库中进行随机访问，并提供强一致性的保证。

Design

Percolator为了大规模的增量更新提供了两个抽象：

  • 基于随机访问库的ACID事务；
  • observers，一种处理增量计算的方式；

每个Percolator系统包含三个二进制文件：Percolator的worker、一个BigTable的tablet服务器和一个GFS chunkserver。所有的observer都会连接到Percolator的worker中，该worker会扫描所有在BigTable中发生改变的列，然后调用observer中的回调逻辑。另外Percolator还会依赖两个服务：timestamp oracle和一个轻量级锁服务，前者通过递增的时间戳提供了快照隔离协议，后者则是依赖锁服务来搜索“dirty notification”。

BigTable

Percolator是在BigTable基础上构建，数据被组织到BigTable的行列中，元数据则存储在旁边的特殊列中，基于BigTable的接口封装了大量的API，主要目的是提供BigTable缺失的功能：多行事务和observer框架。

至于BigTable和SSTable所在的GFS的具体实现可以查看对应的论文。

Transactions

Percolator使用ACIS快照隔离来基于BigTable的跨行跨表事务。Percolator使用Bigtable中的timestamp，对每个数据项都存储多版本，以实现快照隔离。在一个事务中，按照某个timestamp读出来的版本数据就是一个快照，然后再用一个往后的timestamp写入新数据。快照隔离可以有效解决write- write冲突，如果事务A和B并行运行，同时往某个cell执行写操作，大部分情况下都能正常提交。任意的timestamp都代表了一个一致快照，读取一个cell仅仅需要用给出的timestamp执行BigTable查询即可。

考虑到Percolator不能直接控制对存储介质的访问，而是需要修改BigTable的状态，所以Percolator需要明确地维护锁，以实现分布式事务。这个锁服务需要具备几个特点：高可用，能够解决锁在2PC阶段消失的情况；高吞吐，上千台机器同时请求锁；低延时，读请求需要读取锁。BigTable作为存储介质，恰好满足这些需求，所以Percolator将数据和锁存储在同一行，特殊的内存列存取锁。访问某一行数据时，Percolator将在一个BigTable行事务中同时对同行的锁进行Read and Modify。

下图是Percolator在执行事务期间，数据和元数据的布局情况。以银行转账为例，Bob向Joe转7元，该事务从start_ts=7开始，commit_ts=8结束。

下图则展示了Percolator在BigTable中的列所展现的作用，其在BigTable中使用了5个列，其中3个与事务相关：

  • c:lock：事务产生的锁，未commit的事务会写该列，映射对是{key,start_ts}=>{primary_key}；
  • c:write: 已commit的数据信息，映射对是{key,commit_ts}=>{start_ts}；
  • c:data: 具体存储的数据，映射对是{key,start_ts} => {value}；

事务的处理流程则是经典的两阶段提交，首先是Prewrite：

  • client首先从Oracle获取全局唯一的时间戳start_ts；
  • client然后从所有key中选出一个primary，其余作为secondaries，并将所有数据写入请求并行发往存储节点；
    • 存储节点首先会进行write-write冲突检查，从c:write获取当前key的最新数据，如果该列中的commit_ts>=start_ts，则返回写冲突错误；
    • 然后会检查key是否被锁，如果锁了则返回错误；
    • 向c:lock写入{key, start_ts} => {primary_key}；
    • 向c:data写入{key,start_ts} => {value}；
1
2
3
4
5
6
7
8
9
10
11
12
// prewrite tries to lock cell w, returning false in case of conflict.
bool Prewrite(Write w, Write primary) {
	Column c = w.col;
	bigtable::Txn T = bigtable::StartRowTransaction(w.row);

	if (T.Read(w.row, c+"write", [start_ts_, max])) return false;
	if (T.Read(w.row, c+"lock", [0, max])) return false;

	T.Write(w.row, c+"data", start_ts_, w.value);
	T.Write(w.row, c+"lock", start_ts_, {primary.row, primary.col});
	return T.Commit();
}

Prewrite成功后，则进入第二阶段commit：

  • 从Oracle获取全局唯一的时间戳commit_ts；
  • 向primary key所在节点发起commit请求；
  • primary commit成功后则标记为事务成功了，紧接着就是向secondaries发起commit请求（事实上这里primary commit成功后，即可响应client，后续异步往secondaries发起commit即可）；
  • 存储节点的处理：
    • 首先是检查key的lock是否合法；
    • 往c:write写入{key,commit_ts}=>{start_ts}；
    • 清除c:lock中内容，释放锁；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool Commit() {
	Write primary = write_[0];
	vector<Write> secondaries(write_.begin() + 1, write_.end());
	if (!Prewrite(primary, primary)) return false;
		for (Write w : secondaries)
			if (!Prewrite(w, primary)) return false;

	int commit_ts = oracle.GetTimestamp();

	// Commit primary first.
	Write p = primary;
	bigtable::Txn T = bigtable::StartRowTransaction(p.row);
	if (!T.Read(p.row, p.col+"lock", [start_ts_, start_ts_]))
		return false; // aborted while working
	T.Write(p.row, p.col+"write", commit_ts, start_ts_); // Pointer to data written at start_ts_
	T.Erase(p.row, p.col+"lock", commit_ts); // 应该是start_ts_
	if(!T.Commit()) return false;  // commit point

	// Second phase: write our write records for secondary cells.
	for (Write w:secondaries) {
		bigtable::write(w.row, w.col+"write", commit_ts, start_ts_);
		bigtable::Erase(w.row, w.col+"lock", commit_ts);
	}
	return true;
}

Percolator的读取操作则相对简单，由于c:write记录了key的commit记录，client读取key的时候会先从c:write找到start_ts_，然后到c:data查找相对应的数据，具体流程：

  • 检查[0, start_ts_]内是否存在锁，若存在，则意味着有未commit的事务，client则必须进行等待和cleanup操作；
  • 否则，获取最新的commit记录，从c:write中获取start_ts；
  • 根据{key, start_ts}从c:data中获取数据；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool Get(Row row, Column c, string* value) {
	while(true) {
		bigtable::Txn = bigtable::StartRowTransaction(row);
		// Check for locks that signal concurrent writes.
		if (T.Read(row, c+"locks", [0, start_ts_])) {
			// There is a pending lock; try to clean it and wait
			BackoffAndMaybeCleanupLock(row, c);
			continue;
		}
	}

	// Find the latest write below our start_timestamp.
	latest_write = T.Read(row, c+"write", [0, start_ts_]);
	if(!latest_write.found()) return false; // no data
	int data_ts = latest_write.start_timestamp();
	*value = T.Read(row, c+"data", [data_ts, data_ts]);
	return true;
}

至于事务处理过程中如何应对异常：若commit一个事务时出现了异常，导致前面Prepare阶段的锁留下来，为避免阻塞住后来的事务，Percolator采取lazy的方式清理这些锁，即访问到了这个key才会去处理。

Prewrite阶段遇到锁冲突会直接返回失败，因此锁的清理是在读阶段进行的。当事务执行过程中commit失败时，事务会留下一个commit point（Primary Key写入c:write了），但可能留下一些锁没有清理。另一个事务发现锁冲突时，会去Primary上查找primary lock是否存在。如果存在，说明前面的事务没有提交，进行roll back；如果不存在，则需要检查c:write是否已经被写入，写入了就说明事务已经被成功提交，此时执行Roll Forward（在secondaries上将c:lock替换成c:write）。BigTable的行级事务避免了数据竞争。

Timestamps

时间戳oracle是一个分配严格递增时间戳的服务器，考虑到每个事务需要调用oracle两次，因此oracle需要具备很好的可扩展性。oracle会定期分配一定范围的时间戳，并把该范围的最大值持久化存储，这样如果服务器挂了就直接从上次范围的最大值作为开始值进行分配。为了减少RPC消耗，Percolator的worker会维持一个长连接RPC到oracle，低频批量地获取时间戳。

事务协议使用严格递增的时间戳，保证了Get操作能看到所有在start_ts之前已提交的写操作。

Notifications

Percolator提供了一种方法来触发和运行事务，用户编写的代码即observer会表的变化而触发，observer会被放入Percolator worker中，随着每一个tablet服务器运行。每个observer都会向Percolator注册一个function和它感兴趣的列，一旦这些列发生了变化就会调用function。

与数据库中的触发器不一样，假设写操作触发了observer，但他们会运行在各自的事务中，产生的结果不是原子的。Percolator提供了一种保证：对于一个被观察列的变化，至多一个observer的事务被提交。反之则不然，对于一个被观察列的多次变化，可能只会触发一次observer事务。

为了实现通知机制，Percolator为每个被监测的列额外提供一个“acknowledgment”列。包含最近一次observer事务的开始时间戳。当被监测的列发生改变时，Percolator启动一个事务来处理通知，该事务读取被监测列和它对应的acknowledgment列，判断acknowledgment列的时间戳是否在被检测列之前，若是则意味着可以开启observer事务，否则意味着已经有observer被运行了。

为了实现通知机制，Percolator需要高效找到被观察的脏cell，其在BigTable的locality group维护了一个特殊的“notify”列，表示该cell是否为脏，当一个事务对被监测列进行写入时，同时会写对应的notify cell。每个Percolator的worker指定几个线程负责扫描这些脏cell。

Percolator的通知机制主要是异步实现的，当改变发生时，并不是立刻以同步方式调用observer，而是写入一个notify列，等worker线程扫描到才会调用observer。

总结

Percolator的一大特点就是构建在仅支持单行事务的BigTable之上，提供了良好的跨行事务，实现了比较简洁的分布式事务。但其性能本身不够高效，每个work都需要发送大量的RPC（比如获取两次事务timestamp，比如可能读取secondary的lock列是指向primary的，还要多读取一次），虽然论文提到了一些合并RPC，延迟发送，提高并行和增大BatchSize等措施来优化RPC的调用，但Percolator对于写协议本身也要需要多次在BigTable做持久化，读的话则可能遇到由于先写primary再同步到其他参与者导致的锁被持有而等待的问题。

发表于

《UCB cs294》Required Reading 3

论文一

《Hidden Technical Debt in Machine Learning Systems》这篇文章是谷歌基于多年的机器学习系统开发和使用经验总结出来的，着重强调了在机器学习系统中出现的technical debt：

  • Complex Models Erode Boundaries

在一般的软件开发中，人们会使用封装、模块化等抽象手段，但机器学习系统由于其依赖大量外部数据，特征的改变会影响全局。论文提到的解决方法是模型隔离和监测模型中的变化。

  • Data Dependencies Cost More than Code Dependencies

这个主要是将对数据依赖关系的分析成本比通常的代码依赖关系分析要高，一是因为数据依赖关系不够稳定，可能存在把一个输出当成另一个地方外部输入的使用；二是存在不必要的数据依赖。对于这两个问题，论文的解决方法是做数据输入的版本控制和定期检查去除不必要的依赖。

  • Feedback Loops

机器学习系统的一大特征就是他们未来的更新很可能会影响到自身，导致analysis debt的出现，在模型部署之前很难预测模型的行为。Direct Feedback Loops是指模型直接影响自身的特征选择，Hidden Feedback Loops是指系统之间间接影响对方，这种Feedback Loops的问题更加严重。

  • ML-System Anti-Patterns

在实际的机器学习系统中，仅仅一小部分代码是用于学习和预测的，慢慢地，系统中会出现各种系统设计的Anti-Patterns。比如出现大量的机器学习库代码，论文的建议是使用胶水语言封装API；数据准备阶段积攒了更多的输入信号，混杂着各种数据操作；机器学习实验过程中，代码出现了一些不必要的条件分支，导致技债出现；还有就是一些代码的code smell比较差。

  • Configuration Debt

由于机器学习系统和算法比较复杂，大型的ML系统往往依赖大量的配置，因此需要关注配置的可维护性、易读性、需要做code review提交到库中。

  • Dealing with Changes in the External World

这个指的是ML系统与外部世界有较多的交互，外部世界的变化会影响系统、影响模型等。因此需要高效的监控预警配套。

  • Other Areas of ML-related Debt

Data Testing Debt，提供基本的、完整的代码测试；Reproducibility Debt，真实的ML系统由于外部世界的变化、并行学习中的随机等等难以保持严格的可重复性；Process Management Debt，模型的管理问题，真实的系统可能存在数以百计的模型，如何分配资源、控制优先级等很重要；Cultural Debt，文化问题，研究员和系统工程师可能存在沟通不当的情况。

论文二

《TFX: A TensorFlow-Based Production-Scale Machine Learning Platform》这篇论文主要介绍了Google开发的一个机器学习平台TFX。TFX最大的特点就是将机器学习所需的各个组件部分集成在一起，提供训练模型、分析验证模型和模型部署的完整工作流，避免了机器学习pipeline各个部分的割裂。

platform overview

作为一个机器学习平台，不单单只关注机器学习算法，还需要考虑到依赖分布式系统架构促使数据和模型的并行，机器学习工作流便于搭建，拥有集中的仓库跟踪保存训练过的多模型等等。

TFX的设计主要考虑了以下几点：

  • 平台能应对多种学习任务，除了选用tensorflow作为核心算法库，还支持数据验证分析和可视化工具、模型验证评估和推断工具等；
  • 持续训练，TFX考虑支持多种持续训练策略；
  • 易用的配置与工具；
  • 生产级别的可靠性与可扩展性；

基于上述的特点，把多种组建模块集成在一起，就形成了下图的平台。

DATA ANALYSIS, TRANSFORMATION, AND VALIDATION

对于机器学习来说，了解数据并及时发现异常数据是至关重要的，有利于避免下游数据出错。这一章主要讲TFX将数据分析、转换和验证作为独立又相互关联的部分。

数据分析的时候，需要对输入的数据集进行统计，输出一系列统计数据，如连续型数据需要分位数、直方图等等，离散数据需要top-K值和频率等等。

数据转换则是对数据进行格式转换，如将特征转换为特定的整数。这里的关键是保证在训练和推断期间确保转换逻辑的一致性。TFX会将任何数据转换导出为经过训练的模型的一部分，从而避免了不一致的问题。

数据验证则是使用schema来描述数据规范，每个算法团队维护自己的schema，数据验证时可以快速确认数据集的异常情况，如何进行修正，反映出数据的变化情况。

MODEL TRAINING

TFX的设计一大核心是尽可能流水线地、自动化地完成训练生产模型，支持训练使用Tensorflow配置的所有模型。TFX使用了warm starting来在模型质量和模型时效性之间达到一个平衡，这是迁移学习使用的技术，讲一个训练好的基准模型应用另一个场景。

论文另外一点就是TFX用了定义和描述模型的API——model specification API，通过对Tensorflow的封装减少代码冗余，提高开发速度。

MODEL EVALUATION AND VALIDATION

模型的评估是模型上线前验证模型有效性的关键步骤，TFX对于好模型的定义主要是：safe to serve和the desired prediction quality，前者关心的是模型完整性，不会使得推断服务crash，资源使用少，后者则主要是模型预测准确率。

TFX一方面也使用了各种准确率标准来做AB Test，根据不同的产品团队要求提供告警配置，另一方面也支持对数据集根据feature做slice切分，帮助更好地评估模型在不同feature伤的表现。

MODEL SERVING

最后则是模型服务，TFX主要依赖Tensorflow serving去做这个事情，通过多用户隔离和快速的训练数据反序列化来满足系统的低时延和高性能要求，总的来说提供了一套工业级的模型上线推断服务。

论文三

《Towards Unified Data and Lifecycle Management for Deep Learning》这篇论文主要关注了深度学习中数据和生命周期管理系统的实现，提出了一个modelHub系统，包括了三个部分，一种DSL来帮助泛化对模型的探索、查询，一种新的模型版本管理系统（Dlv）和一种读参数优化的参数归档存储系统（PAS）。

ModelHub主要分为local组件和远程组件，local functionality包括了一些DNN系统与本地计算机集群的集成，remote functionality则是不同用户组共享模型与其版本。

DLV是一种通过命令行工具的版本控制系统，可以用来与其他本地或者远程组件进行交互，替代了传统的git/svn可以方便其更好地描述查询建模过程中生成的artifacts内部结构。另外通过DQL模块可以帮助研究员开发新模型。Model Learning模块本质是特定DNN系统的wrapper。

至于本地仓库的PAS则是用来存储大量的模型学习参数，PAS的目标是在不影响查询性能的情况下，尽可能维护大量学习的模型信息。其中一大特点是使用了一种新的近似模型评估技术，适用于分段存储PAS。由于浮点算数表示中浮点数具备高熵，难以压缩，PAS提供了按字节分割的浮点矩阵存储方案，通过分割高阶和低阶尾数位，浮点数矩阵按块存储，第一个块由8个高位组成，其余的每个块被分割为一个字节，由于高阶位具有低熵，能更好地做压缩。

这篇论文描述了如何通过ModelHub去解决一些在管理和调整深度学习模型中的关键数据管理挑战：

  • 通过调整网络结构和超参数，更容易优化潜在的模型效果；
  • 减少跟踪模型的负担；
  • 在不影响查询和检索性能的前提下，尽可能多地存储大量模型和构造快照；

发表于

C++ atomics, from basic to advanced

背景

在C++11中引入了对多线程的支持，同时也带来了关于mutex和atomic相关的一些列标准，定义了memory model。这篇文章将关注C++11带来的一个无锁编程工具——atomics。

简介

无锁编程

在文章开始之前，首先来关注一些无锁编程这个概念（lock free——不使用锁来保持代码同步）。一般人在使用无锁编程或者了解这个概念之前，会先入为主地认为无锁编程性能更快，相对使用锁来同步拥有更好的运行速度。

实际上，无论是lock free还是更严格的wait free都没有直接跟运行速度有直接关系，他们关联的是“steps”，但在程序运行过程中“step”的运行时间不一定是一样的。无锁编程的优势在于通过减少阻塞和等待来提高并发的可能性，消除race condition、死锁等潜在危机。因此在使用无锁编程之前应该先测试程序，观察代码的算法逻辑是否有问题。

接下来我们开始了解C++的原子操作。

C++ atomics

何谓原子操作

原子操作是一种以单个事务来执行的操作，这是一个“不可再分且不可并行的”操作，其他线程只能看到操作完成前或者完成后的资源状态，不存在中间状态可视。

从底层来看，原子操作是一些硬件指令，其原子性是由硬件保证的，C++11对原子操作抽象出统一的接口，避免使用时嵌入平台相关的代码来支持跨平台使用。

先来看看如果多线程中没有原子操作会发生什么情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int x = 0;
// ===============
// Thread 1
{
  int tmp = x; // 0
  ++tmp; // 1
  x = tmp; // 1
}
// Thread 2
{
  int tmp = x; // 0
  ++tmp; // 1
  x = tmp; // 1!!! What!!!
}

这是一个很典型的Read-modify-write的递增场景，多线程环境下就会出现data race。为什么会这样，以一个简易的计算机架构图来举例，这里存在三级缓存，变量在内存中初始化好为0，由于这里没有同步机制，每个CPU都从主存中将变量取出来（此时变量都是0），在寄存器中进行递增，最后将递增后的值1写回内存。

那么我们怎么在C++中进行数据共享呢？在C++11之前是没有标准的线程库的，在C++11之后引入了std::atomic模版类来提供原子操作。一个简单例子：

1
2
std::atomic<int> x(0); // Not support std::atomic<int> x = 0
++x; // now atomic operation

std::atomic的使用

std::atomic是一个模版，那么哪些类型可以实例画该模版呢？按照标准的说法，需要是Trivially Copyable的类型，简单来说就是满足三个条件：

  • 连续的内存；
  • 拷贝对象意味着按bit拷贝（memcpy）；
  • 没有虚函数；

用代码来表达则是自定义结构满足下面5个条件：

1
2
3
4
5
std::is_trivially_copyable<T>::value
std::is_copy_constructible<T>::value
std::is_move_constructible<T>::value
std::is_copy_assignable<T>::value
std::is_move_assignable<T>::value

那么对于一个合法的std::atomic<T> 类型来说，它能进行哪些操作？一个是assignment，则读写操作；另一个则是特定的原子操作和跟类型T相关的其他操作。下面几种操作要么编译失败、要么是非原子：

1
2
3
4
std::atomic<int> x{0};
x *= 2; // compile error
x = x + 1; // Not atomic: Atomic read followed by atomic write
x = x * 2; // Not atomic: Atomic read followed by atomic write

还有一个就是原子自增不支持浮点数。其他的原子操作包括CAS、exchange等等；

1
2
3
4
5
6
7
8
std::atomic<T> x;
T y = x.load(); // same sa T y = x
x.store(y); // same as x = y
T z = x.exchange(y); // Atomically: z = x; x = y;
// if x == y, make x=z and return true
// Otherwise, set y=x and return false
// 还有一个compare_exchange_week，x == y也可能会失败，主要是因为某些平台会对锁有类似超时释放的操作，满足其高效调度
bool success = x.compare_exchange_strong(y, z);

这里重点看一下CAS的使用，CAS在大多数无锁算法中都有应用，除了原子自增外，CAS还支持递增浮点数，进行乘法运算：

1
2
3
4
5
6
7
8
std::atomic<int> x{0};
int x0 = x;
while (!x.compare_exchange_strong(x0, x0+1)) {}
while (!x.compare_exchange_strong(x0, x0*2)) {}
// fetch_xxx() == some operators
std::atomic<int> x{0};
x.fetch_add(y); // same as x += y
int z = x.fetch_add(y); // same as z = (x += y) - y;

std::atomic与无锁的关系

这里有一个关键的信息：std::atomic并不意味着一定是无锁的；首先来看下面的代码：

1
2
3
4
5
6
long x; // lock free
struct A { long x; }; // lock free
struct B { long x; long y; }; // run-time and platfrom dependent. x86 is lock free
struct C { long x; long y; long z; }; // > 16 bytes. not lock free
struct D { long x; int y; }; // alignment 16 bytes. lock free
struct E { long x; int y; }; // 12 bytes. not lock free

判断atomc是否无锁可以通过一个成员函数std::atomic<T>::is_lock_free()，这是一个运行时的判断（C++17提供了编译时判断constexpr is_always_lock_free()），之所以会出现无锁不确定的情况主要是因为对齐alignment。

假设atomic是无锁的，但也有可能出现两个atomic变量互相等待的情况，假设存在这样的场景，两个atomic变量：

1
2
3
4
5
std::atomic<int> x[N];
// thread 1
++x[0];
// thread 2
++x[1];

这种情况下就会出现两个atomic变量互相等待的可能性，主要是因为这两个操作都是在同一个cache line，都从主存到CPU来回写入，因为两个CPU可能互斥访问同一个cache line，这就是所谓的false sharing。一个提高性能解决这个问题的方式是将每个线程的数据对齐到充满整个cache line。（NUMA机器上，可能是整个page）

memory barrier

memory barrier控制着某个CPU对内存的修改被另一个CPU可见的方式，这是一个对所有CPU的全局控制。这是通过硬件实现，确定指令的特定操作顺序。简单来说，就是CPU在执行指令的时候不一定按照编写顺序来执行，从而挖掘更多并行能力。

如果仔细观察std::atomic相关操作的参数，会发现其还接受一个memory_order的枚举作为参数。

1
2
3
4
5
6
7
8
typedef enum memory_order {
	memory_order_relaxed,
	memory_order_consume,
	memory_order_acquire,
	memory_order_release,
	memory_order_acq_rel,
	memory_order_seq_cst
	} memory_order;
  • memory_order_relaxed：不对执行顺序做任何保证，即该原子操作指令可以任由编译器重排或者CPU乱序执行；
  • memory_order_acquire：当前线程里，所有在该原子操作之后的读操作，都不能重排到该原子操作指令之前执行。原子操作指令先读；
  • memory_order_release：当前线程里，所有在该原子操作之前的写操作，都不能重排到该原子操作指令之后执行。原子操作最后写；
1
2
3
4
5
6
7
8
9
10
11
int Thread1(int)
{
    int t=1;
    a.store(t,memory_order_relaxed);
    b.store(2,memory_order_release); // a必须在b之前完成写入
}
int Thread2(int)
{
    while(b.load(memory_order_acquire)!=2); // b必须在a之前读 
    cout＜＜a.load(memory_order_relaxed)＜＜endl;//输出1. 
}
  • memory_order_acq_rel：包含memory_order_acquire和memory_order_release两个标志；
  • memory_order_seq_cst：默认标志。顺序一致，确保代码在线程中的执行顺序与顺序看到的代码顺序一致，禁止重拍指令和乱序执行；

改变memory order参数，在一定程度上可能会提高程序的性能，从代码中表达出程序员的意图。

总结

C++的atomic操作在一定条件下能很好提高程序的性能，并且也提高了易用性，但也存在很多容易踩坑的地方，因此在使用前仍然需要做详细的设计。使用atomic的时机也需要细细斟酌，对于不适用的地方使用无锁或者atomic操作可能收效甚微。

参考资料

https://www.infoq.com/news/2014/10/cpp-lock-free-programming/

https://www.youtube.com/watch?v=ZQFzMfHIxng

发表于

Macro Free In Cpp

One of C++'s aims is to make C's preprocessor redundant because I consider its actions inherently error prone

背景

C预处理器本质是一个文本替换工具，用来在实际编译之前进行一定的预处理操作，一般情况下#开头的预处理操作并不认为是语言本身的一部分，因为编译器永远看不到这些宏定义符号。

以C++来说，用宏的目的并不是出于性能的缘由，更多的只是为了减少重复的代码和进行条件编译。随着modern cpp的发展，越来越的新特性加入使得对宏的使用依赖进一步降低。本文将关注如何使用C++新特性替换C预处理程序。

如何替代宏的使用

  1. 表达式别名

有一些宏定义会用在表达式别名，替换后的文本会被识别为C++表达式，对于这种情况比较简单的是使用常量表达式或者lambda替换宏，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define PI 3.14
#define SEVEN 3 + 4
#define FILENAME "header.h"
#define SUM a + b
void summer()
{
  int a = 1, b=2;
  int c = SUM;
}
// ========================>>>
constexpr auto PI = 3.14;
constexpr auto SEVEN = 3 + 4;
constexpr auto FILENAME = "header.h";
void summer()
{
  int a = 1, b=2;
  auto SUM = [&a, &b]() { return a + b; };
  int c = SUM();
}
  1. 类型别名

类型别名是一个类似于对象的宏，其替换文本可以识别为C ++类型表达式。对于这种，可以使用C++的别名声明来替换：

1
2
3
#define A T
// ========================>>>
using A = T;
  1. 参数表达式

参数表达式是一种类似于函数的宏，替换文本后会扩展为表达式或语句。对于这种使用，C++中的最佳实践是使用内联模版函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define ASSIGN(A, B) { B = A; }
// ========================>>>
template <typename T1, typename T2>
inline auto MIN(T1&& A, T2&& B)
  -> decltype(((A) < (B) ? (A) : (B)))
{
  return ((A) < (B) ? (A) : (B));
}
template <typename T1, typename T2>
inline void ASSIGN(T1&& A, T2&& B) {
  B = A;
}

这里引入了内联，自动的推导类型和完美转发等modern c++的特性。完美转发使得调用方可以根据需要决定参数传递的类型。

  1. 参数化类型别名

这种其实就是模版别名，在C++11之前需要用宏去实现。

1
2
3
4
#define AliasMap(T) std::map<std::string, T>;
// ========================>>>
template <typename T>
using AliasMap = std::map<std::string, T>;
  1. 条件编译

目前绝大多数开源的C++项目都会依赖宏来进行条件编译，其本质意义是通过定义宏与否来改变某个定义/声明。

比如存在一个绘制三角形的API，但其具体实现会根据操作系统而变化，通过预处理器就可以很好地实现类似的兼容：

1
2
3
4
5
6
7
8
void draw_triangle()
{
  #if _WIN32
    // Windows triangle drawing code here 
	#else
    // Linux triangle drawing code here
	#endif
}

其中某个分支的代码会在进行编译之前被去掉，这样编译时就不会出现API未定义的错误。

在C++17中有了新的语法特性if constexpr，我们可以用来替代一部分#if … #else的使用。以下面的使用为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void do_sth()
{
  #if DEBUG_MODE
    log();
  #endif
  // …
}
// ========================>>>
void do_sth()
{
  if constexpr (DEBUG_MODE) {
    log(); 
  }
  #endif
  // …
}

使用if constexpr的好处是其只会检查语法错误，像宏那样的使用方式，一旦DEBUG_MODE出现typo的错误，编译器是无法准确辨识的。

当然if constexpr的使用也是有其不足之处的，以上面的draw_triangle函数为例，即便某个条件分支不会被使用，你仍然需要有相关冗余的声明。所以对于这种情况，个人建议还是不需要使用if constexpr替代宏。

  1. 源码位置

目前几乎所有的断言或者宏会用到宏，比如需要使用__LINE__, __FILE__, __func__ 等定位断言的位置，又或者需要断言开关等等。

要想替代对这些宏的使用则需要用上C++20的std::source_location，该类可以表示关于源码的具体信息，例如文件名、行号以及函数名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string_view>
#include <source_location>
 
void log(std::string_view message,
         const std::source_location& location = std::source_location::current())
{
  	std::cout << "info:"
      				<< __FILE__ << ':'
              << __LINE__ << ' '
              << message << '\n';
  	// ========================>>>
    std::cout << "info:"
              << location.file_name() << ':'
              << location.line() << ' '
              << message << '\n';
}

总结

这里提供了一些更“现代”的C++写法来替换不够安全的、使用了宏定义的老式代码，事实上C++的发展过程中一直在提出一些减少预处理宏使用依赖的方案。但从目前来看，还是有不少预处理使用无法替换，即便如此，个人认为适当使用宏和合适的，其AST的生成功能是非常强大的工具，并且某种情况下能使得代码更加易读。

参考资料

  1. 《cppcon 2019》——https://www.youtube.com/watch?v=c6NkeF1eChs
  2. 《Rejuvenating C++ Programs through Demacrofication》——https://www.stroustrup.com/icsm-2012-demacro.pdf
  3. 《if statement》——https://en.cppreference.com/w/cpp/language/if
  4. 《The year is 2017 - Is the preprocessor still needed in C++?》——https://foonathan.net/2017/05/preprocessor/