疯狂的Anna：快、可扩展、支持多种一致性模型的KVS

最近在网上看到一篇文章《伯克利推出世界最快的KVS数据库Anna：秒杀Redis和Cassandra》，标题中有两点比较吸引眼球：

伯克利

这个大学在计算机学术界、工业界的地位举足轻重，其中的AMP实验室曾开发出了一大批大获成功、 对计算机行业产生深远影响的分布式计算技术，包括 Spark、Mesos、Tachyon 等。作为AMP的继任 者，于2017年2月新成立的RISE实验室致力于开发实时、智能、可安全执行的新一代大数据处理系 统，已经开源了新型分布式执行框架Ray等项目

世界最快

这个就有点标题党了，但加州伯克利出品的KVS也不可小觑

you have to redesign your system every time you scale by 10x

而RISE实验室的研究员们就是要反其道而行之，致力于设计一个通用的KVS系统，使其性能在任意硬件架构下（单核、多核、集群甚至跨多可用区域的云环境）都能够线性扩展。博文作者认为《Anna: A KVS For Any Scale》（已被ICDE18收录）已在系统原型层面实现了这个目标，后续基于Anna设计理念的Bedrock开源项目也会真正在云端生产环境中落地。

读完博文，我们可以得出Anna是加州伯克利大学RISE实验室出品的原型KVS系统，能够在多种硬件基础设施规模下线性扩展，不仅性能比肩若干世界领先的KVS系统，还支持多种一致性模型。让我们带着惊讶与疑惑，通过公开的论文粗略了解一下它是如何做到的。

引子

Anna是加州本地一种蜂鸟的名字，相对于其身体长度，是世界上飞行速度最快的鸟类。论文将自己的KVS系统取名Anna，一方面是它们都出自加州；另一方面是借蜂鸟的小巧、灵活、快速等特点隐喻该KVS系统代码精简、性能高、灵活的一致性模型支持。

Joseph M. Hellerstein是加州大学伯克利分校计算机科学系的教授，RISE实验室联合创始人之一，他的研究小组长期致力于无协调的分布式系统的设计，他们先后提出了CALM理论、设计了新的编程语言Bloom、实现了跨平台程序分析框架Blazes、发布了高可用事务协议HATs，Anna 的推出验证了这些理论、语言、框架或协议在多核或云环境中能够提供怎样的性能。

Anna论文的主要贡献在于：

确认了业界流行的并发处理模型actor能够保证系统性能在多种规模的硬件架构下线性扩展、弹性伸缩

基于格理论能够优雅地实现无协调一致性模型，代码不仅精简而且更加模块化

在各种部署架构下对Anna进行了性能验证

其无协调一致性模型的理论基础主要来自于HATs，格理论主要来自于Bloom-L。如果读者能够简要阅读上述两篇论文，会有助于更好地理解Anna论文中的内容。

背景

现代云平台为应用提供了单核、多核、集群、多可用区等多种不同规模的硬件基础设施

现有的KVS设计要么面向集群（scale out）；要么面向单机（scale up）

目标

一种软件架构满足从单核到多集群规模的良好扩展性、伸缩性

比现有的KVS系统性能更好或相当

比现有的KVS系统支持更多的一致性模型

设计原则

单核级数据分区

一种软件架构在任意硬件规模下都适用，必须以CPU单核实例为粒度进行架构设计，就好像物质是由原子组成的一样

存储任意规模的数据，必须以range或hash方式对数据进行分区，而且hash更通用一些

多主复制消除热点

在任意数据访问分布下没有读热点，必须支持多副本，负载均衡热点key的访问

在任意数据访问分布下没有写热点，必须支持多个主副本，负载均衡热点key的更新

单机无等待执行

在满足数据一致性的前提下，将单机多核机器的性能发挥到极致，让工作线程满负荷运行

无协调一致性模型

必须在不损失系统性能的前提下，支持尽可能多的一致性模型，满足应用的多样一致性需求

核心设计点

多线程模型

现今的大多数KVS系统在单机多核硬件架构下都是基于共享内存架构（包括SEDA）实现的：

操作系统调度多个线程，线程数远大于CPU核数

多线程并发访问共享的数据存储内存结构

通过锁或无锁技术控制并发访问

随着单机核数的增加，共享内存架构下的CPU缓存一致性同步开销已经成为多核机器性能扩展的瓶颈，即便是无锁算法也无法从根本上解决问题，于是业内提出了异步消息通知架构：

一个线程绑定一个CPU核，避免线程切换、L1 cache miss

每个CPU线程运行一个event loop从输入队列中响应用户及其它CPU线程发来的请求

每个线程访问自己的私有内存结构，避免内核/用户态锁切换、CPU缓存一致性开销

线程与线程之间通过消息队列异步非阻塞通信，避免同步阻塞开销

Anna必须采用异步消息通知架构才能满足单机性能极致的需求

副本策略及数据版本冲突管理

现代的分布式存储系统都会采用多副本策略，一方面可以提供数据的可靠性、可用性；另一方面可以将读热点负载均衡，提高系统的读吞吐性能。但是对于写操作会有如下两种处理策略：

单主副本

每个KV根据key路由到一个确定的CPU线程处理，通过paxos、raft、zab等算法保证副本一致性。在提 供数据强一致的同时，也限制了单KV更新吞吐量的理论上限

多主副本

每个KV根据key路由到任意一个负责该KV副本的CPU线程处理，单KV更新吞吐量的性能上限随着副本 系数的增长而增长，但系统只能保证数据的最终一致

Anna追求的是无协调的极致性能及扩展性，必须避免读热点和写热点，每个副本可读、可写才能满足需求。但这样做，需要解决多主副本的一致性，有如下两种策略：

多主同步更新

KV更新请求随机路由到某个主副本，在本地处理完请求后同步广播给其它主副本，但广播发生在每一 次请求处理的关键路径上，对更新性能有较大影响

多主异步更新

KV更新请求随机路由到某个主副本，在本地处理完请求后即可返回，无需同步广播更新，由本地后台 线程周期性或在系统负载低峰时异步广播更新。这种方式下的广播没有同步开销，但也不可避免地造 成多副本数据在某一时间周期内的不一致，需要一个可靠的机制保证多副本数据的最终一致

Amazon Dynamo的反熵是一种基于状态的异步副本同步协议，它会定期在副本结点间传递副本的Merkle树，如果发现有副本不一致，则通过向量时钟机制在系统层面自动进行数据版本合并；如果版本冲突不能合并，需要交给应用层来解决。应用层与系统层在冲突解决逻辑上紧密耦合，降低了系统的鲁棒性，也容易导致应用层代码逻辑错误。为了实现一个鲁棒、正确的分布式最终一致性系统，业内提出了两个方案：

CRDT

根据CRDT定义的数学规则，实现一个从数学意义上（单调增长且具有半格的性质）保证无冲突的抽象 数据类型，应用需要注册一个在该数据类型上满足交换律、结合律和幂等律的合并函数。该方案存在 两 个问题：需要用户保证合并函数满足三律；无法从理论上保证两个相关CRDT数据对象的最终一致

单调逻辑

CALM理论认为所有的单调程序（可以用CRDT和过滤、投影、联结等单调操作符表示的代码）都能保 证无协调的最终一致性。在此理论框架下设计的扩展Bloom语言能够保证用户使用语言原生的各种支持 Lattice属性的数据类型写出能够通过形式化验证程序证明的单调程序

Anna采用基于操作的异步副本同步协议，定期广播一段时间内的副本更新日志到相关副本结点，借鉴Bloom语言实现Lattice属性数据类型的思想，以系统化、模块化的编码方式实现actor私有的一致性状态数据结构，通过其合并函数（支持用户自定义）完成数据版本的合并及冲突解决。这里简单了解一下格的定义：

  半格（semilattice），以下简称格，是一个偏序集，其中LUB为一个上确界二元运算符，满足结合律(Associativity)、交换律（Commutativity)、幂等律(Idempotence)，统称ACI属性

Anna将格的思想应用到存储KV更新请求及异步合并数据更新状态，有以下两点好处：

具有Lattice属性的数据状态管理结构对数据更新的延迟、乱序、重复不敏感，天然具备良好的扩展性

借鉴Bloom语言的思想，在统一的规则下将具备格属性的基本数据类型，通过单调逻辑自底向上组合 成复杂的类型或代码段，不仅能够灵活表达各种一致性模型，而且在构建的过程中由形式逻辑自动保 证没有破坏最终一致性

  综上所述，Anna支持多副本，且每个副本都可读写，采用基于操作的异步副本同步协议，通过具备Lattice属性数据类型的合并函数自动完成副本数据版本合并及冲突解决。对用户来说，与Dynamo提供的最终一致性性机制相比，Anna最终一致性的维护更加简单、可靠，Anna称此最终一致性为简单最终一致性。

整体架构

存储服务

采用Actor模型，一个CPU核绑定一个线程，每个线程具有自己的eventloop并维护私有的内存哈希表（C++ unordered map）

每个actor负责接收proxy转发来的KV请求，并在本地缓存变更历史

利用ZeroMQ实现线程间通信（同机线程共享内存/异机线程网络套接字）

actor之间以固定时间间隔交换次周期内的更新请求并合并从而实现最终一致，读到的数据的stale程度取决于固定时间间隔的设定

利用格的ACI属性，使用发送端预先合并技术减少广播更新变更的通信开销及接收端的计算开销

支持PUT/GET/DELETE接口

代理服务

路由用户的KV请求至存储服务，支持超时和重试

基于actor和server的负载均衡

数据基于单核actor的一致性哈希算法进行分区

可调参的多副本复制支持高可用

通过写缓冲和读缓存支持事务一致性语义

支持PUT/GET/DELETE/BEGIN/END接口

actor的动态添加/删除

所有的proxy和actor都会本地维护一个全局的hash环，通过广播与通知机制动态更新全局hash环信息

添加

actor既可以在已有结点上添加， 也可以在新结点上添加。每个新actor加入时需要向所有的actor广 播自己的id，其它actor收到id后更新本地维护的hash环， 将新actor需要处理的数据发送给新actor并 删除自己的本地相关数据，如果此时该结点收到了新结点负责的KV请求需要转发给新的actor。新 actor收到了所有负责处理的数据后，广播自己的id给所有的代理服务，代理服务会更新自己维护的 hash环，并将属于新actor负责的KV请求路由给新的actor

删除

actor在退出时需要将它管理的KV数据及退出信息发送给需要接管的actor，新的请求也需要路由给 接管actor。对应actor在接收完数据之后将待退出的actor从自己本地维护的hash环上删除。待退出 actor在所有数据发送完成后将退出消息广播给所有的代理服务，代理服务更新自己本地的hash环后 将新的请求路由到新的actor，原来失败的请求会重试

一致性模型的实现

一致性模型

Anna的一致性模型概念源自HATs论文。该论文认为虽然传统数据库号称支持事务ACID，支持强一致，但大多数系统的默认事务隔离级别都是读提交，而大多数现有应用在该隔离级别下也能正常运行。AP系统只要能支持读提交隔离级别的事务，也能适用于这些应用，与此同时还能提供极高的性能和可用性。这里先说明几个和一致性相关且容易混淆的概念：

事务原子性

一个事务内的操作要么全部成功、要么全部失败，这句话隐含了一种快照读一致性约束，即其它事务 要么能看到这个事务的所有更新操作，要么什么都看不到。在单机环境下，事务原子性由事务日志和 锁来保证；在分布式环境下，需要由客户端缓冲和快照读来保证

事务一致性

从应用的角度，事务对数据库系统的更新不应该破环应用系统定义的完整性约束，比如实体完整性、 参照完整性、数据项之间需要始终维持的不变性关系

事务隔离性

研究在多个数据项上的并发读写操作对应用一致性造成的影响，大致有以下几种隔离级别：串行化/可 重复读/快照读/游标稳定性读/读提交/读未提交等

分布式系统一致性

研究在单个数据项上的并发写操作对其它会话的可见性，大致有以下几种一致性级别：强一致/线性一 致/顺序一致/因果一致/会话一致/最终一致等

HATs论文认为，不管是事务隔离性还是数据一致性，都是对数据项一致性、可见性的描述，统称为一致性模型。在高可用（不是多数派可用）前提下（包括用户请求始终路由到同一会话的场景），分布式系统能够支持的最强一致性模型为MAV+P-CI，即快照读一致性（不同于快照隔离级别，无法防止丢失更新）

I-CI（Item Cut Isolation）

不能防止丢失更新也不能防止幻读的可重复读隔离级别

P-CI（Predicate Cut Isolation）

不能防止丢失更新但能防止幻读的快照隔离级别

MAV（Monotonic Atomic View）

单调原子视图隔离级别，高于读提交级别，但低于可重复读级别，定义为不能防止丢失更新，不能防 止不可重复读，也不能防止幻读

具备Lattice属性的基本类型的组合

Anna通过C++模板定义了具备Lattice属性的基本类型。每个actor访问的私有内存结构实现为key、value类型可参数化的MapLattice模板类，key为任意不可变类型，value为ValueLattice。MapLattice定义了merge函数，用户的多个PUT请求与MapLattice合并实现为两个输入哈希表的并集。如果有相同key，则调用ValueLattice的merge函数合并value。对于Cassandra用户，可以将自定义的冲突解决逻辑在ValueLattice的merge函数中使用系统提供的基本Lattice类型及单调语句实现，由系统保证数据副本的一致。

基于Lattice实现数据一致性

因果一致性

通过向量时钟可以记录一个数据项更新的因果序并解决并发冲突。向量时钟在Anna中可以实现为一个MapLattice，key为代理服务ID，value为代理服务维护的数据版本号。版本号实现为一个MaxIntLattice，合并函数定义为取输入和当前值中的最大值，保证版本号是递增的；当用户执行read-modify-write操作时，先获取数据的向量时钟，再增加对应代理服务ID下的版本号，将新的向量时钟及数据写入存储服务。假设有P(a, b)和Q(a, b)两个PairLattice，如果P.a和Q.a之间存在偏序关系P.a

基于Lattice实现事务一致性

读未提交

在此隔离级别下，只需要保证没有脏写。（论文中关于此隔离级别的实现描述是不严谨的，给一个事务中的所有写操作仅添加语句号和代理服务的本地时间戳，不能解决有多个代理服务以相同本地时间戳写相同数据项的冲突，还是需要使用向量时钟的方式。后续为了叙述方便，先假设添加本地时间戳的方式是合理的）将事务中的写操作实现为一个PairLattice，左值是一个代理服务的本地时间戳（可以用MaxIntLattice实现），右值是用户value，合并函数实现为取时间戳大的value

读提交

在此隔离级别下，需要防止脏写和脏读。在读未提交的实现方案下，Anna将事务的写操作缓冲在代理服务的会话内存中直到事务提交，由此保证其它事务不会看到未提交的更新

数据项快照读（I-CI）

在读提交的实现方案下，Anna将事务的读操作缓存在代理服务会话内存中，当事务再次读取相同值时，直接从缓存中读取，缓存在事务结束时释放

谓词快照读（P-CI）

与数据项快照读的实现方案一致，在事务开始的时候需要将符合谓词条件的所有数据项读入会话缓存，后续的谓词读直接从缓存中读取，缓存在事务结束时释放

单调原子视图（MAV）

HATs论文中为满足事务原子性定义的隔离级别，Anna在论文中并未提及如何实现这种一致性，但事务一致性模型的实现前提就应该是保证事务原子性，这里给出HATs论文中提到的一种解决方案：所有副本需要支持多版本存储，副本间通过gossip协议协商出当前存在于所有副本的数据版本。数据库中所有数据都有一个满足上述要求的数据版本，这就构成了一个全局的数据版本快照，全局快照随着后续事务的提交不断向前推进。当事务开始时，代理服务可以选择一个小于或等于当前全局快照的读时间戳，在事务执行的过程中，涉及到的每个数据项都只返回读时间戳中指定的数据版本

总结

将MAV和P-CI隔离级别结合，我们在高可用、最终一致的NoSQL系统上实现了快照读隔离级别，事务中的读操作可能读到一个较老的数据版本但一定是提交后的；写操作相对复杂，需要分情况讨论：

如果只有事务自身更新了数据项，事务提交后，在最终一致性保证下，更新内容能够体现在所有的副本中

如果只有事务所在代理服务中的事务更新过数据项且当前事务读到了老的数据项，事务提交后，由于合并规则为时间戳大者优先，会出现丢失之前更新的现象

如果其它代理服务中的事务更新过数据项且当前事务读到了老的数据项，事务提交后，合并时会触发用户自定义合并函数，此时的行为不确定

在真正的高可用系统中，上述写异常情况是无法避免的；若允许牺牲一定的可用性，可以做到当前事务无法提交

与其它KV系统的对比

论文从硬件架构、内存模型、单key一致性模型、多key一致性模型等四个维度对比了Anna和已有的KV系统，从表中可以看出Anna的最大不同是在高可用、高性能下支持事务级隔离级别

性能评估

架构的优良需要性能数据说话，任何一篇优秀的工程实践论文，其中的性能测试设计方案及结果分析是非常重要的。论文中针对Anna原型系统设计了四组实验，实验的设计及分析建议大家直接看论文，这里仅对实验覆盖的场景及结果做一个总结性的概括：

单机多核架构

有热点（32线程）

无热点

TBB/Masstree系统90%以上的CPU时间在处理原子指令

Ideal系统90%以上的CPU时间在处理有效请求，吞吐量是TBB/Masstree的6倍，其性能优势在 于无需处理原子指令

Anna系统90%以上的CPU时间在处理有效请求，在单副本配置下吞吐量是TBB/Masstree的50 倍；在全副本配置下系统吞吐量能够随着线程数的增加线性增长，吞吐量是TBB/Masstree的 700倍；lattice更新合并和变更广播的开销很小

从上述结果可以看出，Anna的性能优势在于无CPU缓存一致性的开销，无原子指令处理开 销，而且在高数据争用场景下，共享数据访问对性能的影响非常大

Anna系统在单副本配置下吞吐量能够线性扩展；在三副本/全副本配置下60%以上的CPU时间 用于处理变更广播，吞吐量扩展性受到较大影响

其它对比系统的吞吐量在Anna单副本配置下依然没有优势

Ideal（共享内存架构，线程不安全）

TBB（共享内存架构，线程安全，哈希表）

Masstree（共享内存架构，线程安全，B树）

Anna（异步消息通知架构，线程安全，哈希表）

测试对象

测试目标

观察被测试KVS系统在有热点和无热点的只写工作负载下，随着线程数的增加，系统吞吐量是否能 线性增长，从而证明单机无共享架构在并发性能上的优势

测试结果

多机多核架构

测试对象

Anna

测试目标

验证Anna在无热点的只写混合工作负载下，在多机硬件架构上的吞吐量性能是否可线性扩展

测试结果

符合预期

多机多核架构可伸缩性

测试对象

Anna

测试目标

观察Anna在无热点的读写混合工作负载下，在工作负载增加/减少的情景下，是否能够通过增加/减 少CPU核数/节点数使得系统请求响应时间保持平稳

测试结果

符合预期

与现有KV系统

Redis单机多核

Cassandra多可用区（最终一致性级别）

Anna和Cassandra在结点数增加的情况下吞吐量都能线性扩展；在单机单线程模式下，Anna与 Cassandra性能相当；在单机多线程模式下，Anna最好性能指标是Cassandra的10倍（与 SyllaDB性能相当），这得益于Anna的share nothing架构

Redis没有处理并发更新热点key的能力，系统吞吐量受限于单线程

Anna在全副本配置下吞吐量能够线性扩展；在三副本配置下性能受限于副本数；在单副本 配置下性能与Redis相当

有热点

无热点

Redis和Anna都能线性扩展且性能相当。另外在万兆网络环境下，Anna的变更广播已不是性 能的主要瓶颈

Redis cluster（单线程集群架构）

Cassandra（多线程共享内存集群架构）

Anna（异步消息通知架构）

测试对象

测试目标

与生产可用的KVS系统在有热点和无热点的读写混合工作负载下比较吞吐量是否能够随着处理节点 的增加线性扩展

测试结果

不同一致性模型

测试对象

Anna

测试目标

观察Anna在无热点的读写混合工作负载下，支持不同一致性级别对吞吐量性能的影响

测试结果

与简单最终一致性相比，因果一致性模型的实现对性能没有明显影响；读未提交/读提交一致性模型 由于在代理端引入了读缓存和写缓冲机制，性能反而会有提升

综上，根据上述四组性能测试，用实验数据证明了Anna是一个在任意硬件架构下性能可线性扩展，具备弹性伸缩能力，支持灵活一致性模型，性能可与生产级KVS比肩的内存级KVS原型系统

综述

论文的大致内容已经介绍完毕，下面谈一些自己的想法：

在Anna的架构下，热点Key的解决方案非常亮眼，这也是Anna在与其它KVS比较时反复强调的差别，当然这种解决方案的致命缺点是无法保证数据的线性一致，这个取决于应用的一致性需求了

在工程实践上，Anna没有什么创新的东西，只是借鉴了许多现代多核、分布式系统实现的最新思想，但整个系统基于具备Lattice属性的类型在统一的框架下实现数据一致性，不仅从工程实现上能够做到核心组件模块化、复用化、代码简洁化，而且能够通过外部验证程序以形式逻辑的方式证明系统的最终一致性，同时也简化了应用层更新冲突解决的复杂性

一个分布式KVS系统的核心是一致性保证，要先保证结果的正确性和可预期性。Anna核心模块基于具备Lattice属性的数据类型来构建，最终一致性机制的正确性从数学意义上得到保证。在此基础上去扩展对一致性模型的支持，对更大规模节点的管理，只是一个工程实现的问题

在CAP定理的框架下，分布式数据库系统要么在保证数据强一致性的前提下，尽量保证高可用，比如Spanner、OB；要么在保证高可用的前提下，尽量支持更强的数据一致性，比如Dynamo、CosmosDB。在事务一致性语义下，前者有完善的事务隔离级别及分布式事务；后者很少有事务语义支持，Anna正是致力于解决这个问题

Anna是一个POC原型系统，后续的开源版本Bedrock才是一个生产环境可用的分布式KVS系统，让我们拭目以待！

苹果在4月20日刚刚开源FoundationDB，一个支持ACID事务语义的分布式NoSQL数据库，Anna追求的目标正好与其一致，这是一个巧合，还是又一个新的数据库时代来临了？

参考

Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS

Anna: A KVS For Any Scale

Logic and Lattices for Distributed Programming

Highly Available Transactions: Virtues and Limitations(Extended Version)

Consistency Analysis in Bloom: a CALM and Collected Approach

Conflict-free Replicated Data Types

The Declarative Imperative Experiences and Conjectures in Distributed Logic

Dynamo: Amazon’s Highly Available Key-value Store

A Critique of ANSI SQL Isolation Levels

(本文内容仅代表作者个人观点，不代表OceanBase官方)