伯克利推出世界最快的KVS数据库Anna：秒杀Redis和Cassandra
题外话：RISE实验室的前身是赫赫有名的伯克利AMP实验室，该实验室曾开发出了一大批大获成功的分布式技术，这些技术对高性能计算产生了深远的影响，包括Spark、Mesos、Tachyon等。如今，原AMP实验室博士生，同时也是Spark和Mesos核心作者之一的Matei已经转身去了斯坦福，并于去年年底推出了以普及机器学习实践为目的的开源项目DAWN（详见AI前线报道)，而RISE实验室也在没多久后推出了志在取代Spark的新型分布式执行框架Ray（详见AI前线报道）。
过去几年，RISE实验室把研究重点放在如何设计一个无需协调的分布式系统上。他们提出了CALM基础理论（http://db.cs.berkeley.edu/papers/sigrec10-declimperative.pdf），设计出了新编程语言Bloom（http://bloom-lang.net/），开发出了跨平台程序分析框架Blazes（https://arxiv.org/pdf/1309.3324.pdf），发布了事务协议HATs（http://www.vldb.org/pvldb/vol8/p185-bailis.pdf）。但在推出Anna之前，他们还未就这些理论、语言、框架或协议在多核环境下或云环境中能够提供怎样的性能有过任何测试或评估。
而Anna的推出正好印证了他们之前的研究成果。Anna的论文显示，在单个AWS实例上，Anna的速度是Redis的10倍。而在一个标准的交互式基准测试中，也以10倍的速度打败了Cassandra。为了获得更多的比较结果，他们还拿Anna与其他主流的键值系统进行了性能对比：比Masstree快700倍，比英特尔的“无锁”TBB哈希表快800倍。当然，Anna并没有提供类似其他键值系统那样的线性一致性。不过，Anna使用了本地缓存存放私有状态，仍然提供了极佳的无协调一致性，比“hogwild”风格的C++哈希表要快上126倍。而且一旦到了云端，Anna更是独领风骚，其他的系统无法真正提供线性伸缩，但Anna却可以。
Anna的性能和伸缩性主要归功于它的完全无协调机制，节点工作进程有90%的工作负载是在处理请求，而其他大部分系统（如Masstree和英特尔的TBB）只有不到10%的时间在处理请求，它们其余的90%时间花在了等待协调上。不仅如此，其他系统因为使用了共享内存，还会出现处理器缓存击穿问题。
Anna不仅速度快，在一致性方面也达到了很高的水准。多年前，他们发布的事务协议HATs就已表明，无协调的分布式一致性和事务隔离性存在很大的提升空间，包括级联一致性和读提交事务级别。Anna将Bloom的单格子组合设计模式移植到了C++中，是第一个实现了上述所有级别一致性的系统。当然，也是因为设计上的简洁，才能达到如此快的速度。
RISE的研究员们在设计Anna的过程中学到了很多，它们已经远远超出了一个键值数据库的范畴，可以被应用在任何一个分布式系统上。他们正基于Anna开发一个新的扩展系统，叫作Bedrock。Bedrock运行在云端，提供了无需人工干预、低成本的键值存储方案，而且是开源的。
Anna架构简析
图1：Anna架构
上图是Anna单节点的架构图。Anna服务器由一系列独立的线程组成，每个线程运行无协调的actor。每个线程对应一个CPU核心，线程数量不超过CPU的总核数。客户端代理负责将远程请求分发给actor，每个actor都有一个私有的哈希表，这些哈希表存放在共享内存中。线程间的变更通过内存广播进行交换，而服务器间的变更则通过protobuf进行交换。
这种线程和CPU核心一对一的模型避免了上下文切换开销。actor之间不共享键值状态，通过一致性哈希对键空间进行分区，并使用多主复制机制在actor之间复制数据分区，而且复制系数是可配置的。actor基于时间戳将键的更新通知给其他actor副本，每个actor有自己的私有状态，这个状态保存在一个叫作“格子”的数据结构中，确保在消息发生延迟、重排或重复时仍然能够保证一致性。
Anna性能评测
下面就Anna的无协调actor模型在多核CPU上的并行能力、多服务器伸缩能力进行评测，并将它与其他流行的键值数据库进行对比。
无协调actor模型的伸缩性
在无协调actor模型中，每个actor对应一个线程，对任何一个共享状态都有自己的一份私有拷贝，并通过异步广播将更新通知给其他actor。在多核服务器上，这种模型比传统的共享内存模型的性能要高出一个数量级。
为此，RISE研究员设计了一个对比实验，将Anna与其他基于共享内存的TBB、Masstree和自己实现的一个键值存储系统（姑且把它叫作“Ideal”）进行了对比。他们在AWS的m4.16xlarge实例上运行实验，每个实例配备了32核的CPU。实验中使用了1百万个键值对，键的大小为8字节，值的大小为1KB。在实验过程中，他们基于zipfian分布和各种系数生成不同的压力负载，模拟不同层次的冲突。
在第一次实验中，他们对比了Anna与TBB、Masstree和Ideal在单台服务器上的吞吐量。他们逐渐增加线程数量，直到达到服务器CPU核数的上限，并观察它们的吞吐量。
图2是在高并发情况下，线程数与吞吐量的变化关系，其中zipf系数为4。图3是在高并发情况下，CPU时间的使用情况。CPU时间被分为5类：处理请求（RH）、原子指令（AI）、合并格子（LM）、广播（M）和其他。最右边一栏是L1缓存击穿数量（CM）。
图2
图3
从图中可以看出，在这样的负载压力下，TBB和Masstree几乎失去了并行能力。因为大部分是更新操作，针对同一个键值的并行更新操作会被串行化，它们需要同步机制来防止多个线程同时更新同一个键值。因此，随着线程数量的增加，它们性能也只能趋于平缓。Ideal虽然比TBB和Masstree的性能高出6倍，但相比Anna，还是差了很多。尽管它没有使用同步机制，但在多个线程修改共享内存地址时，仍然存在缓存一致性方面的开销。
相反，在Anna中，更新操作是针对本地状态进行的，不需要进行同步，并定时通过广播进行变更交换。在高并发情况下，尽管它的性能仍然受限于其复制系数，但比基于共享内存的系统要好很多。Anna有90%的CPU时间用于处理请求，花在其他方面的时间则很少。可见，Anna的无协调actor模型解决了键值存储系统在多核环境里的伸缩性难题。
图4是在低并发情况下，线程数与吞吐量的变化关系，其中zipf系数为0.5。图5是在低并发情况下，CPU时间的使用情况，其中最右边一列表示内存占用（MF）。
图4|图5
当复制系数为1时，Anna因为内存占用率极低而获得了更好的伸缩性。不过，随着复制系数的增加（增加到3），吞吐量出现了明显下降（下降了四分之三）。这里有两个原因。首先，增加复制系数会占用更多的内存，而且在低并发的情况下，唯一键的更新操作大量增加，所以无法通过合并的方式进行变更交换。图5显示，当复制系数为3时，Anna有69%的CPU时间用于处理广播变更。而在使用完整的复制系数时，Anna也停止了伸缩，因为此时相当于每个线程只能处理一个请求。不过，尽管TBB和Masstree没有广播开销，但在内存占用和同步操作方面仍然存在大量开销。因此，从这个实验中可以得出这样的结论：对于一个支持多主复制的系统来说，在低并发量情况下使用高复制系数对性能是一种伤害。
图6是在多个服务器上增加线程数时的吞吐量变化情况。Anna的复制系数设置为3，先是启动第一台服务器的32个线程，然后是第二台服务器的32个线程，最后是第三台服务器的所有剩余线程。从图中可以看出，Anna的吞吐量随着线程数量的增加呈线性增长。在启动第33个线程时吞吐量有轻微下降，不过那是因为第33个线程是属于第二台服务器的。但从整体来看，吞吐量的增长是很稳定的。可见，借助Anna的无协调actor模型，是可以实现吞吐量线性增长的。
图6
与其他系统的比较
为对比Anna与其他流行键值系统之间的性能差异，RISE研究员设计了两次实验，第一次在单节点上与Redis进行对比，第二次在一个大型的分布式系统上与Cassandra进行对比。
Anna具有多线程并行能力，而Redis使用的是单线程模型。所以，在第一次实验中，他们在同一台服务器上搭建了一个Redis集群，让Anna与这个集群进行比较。实验是在AWS的的EC2实例上运行的，其中Redis集群使用了尽可能多的线程。
从图7(a)可以看出，在高并发情况下，Redis集群的整体吞吐量几乎保持不变，而Anna可以在副本之间分散热键。Anna的吞吐量随着复制系数的增加而增长，直到达到平缓。如果热键完全被复制，吞吐量还会随着线程的增加继续增长。从图7(b)可以看出，在低并发情况下，Anna和Redis集群都获得了不错的并行能力，它们的吞吐量都随着线程数的增加而增长。
图7
从这次实验可以看出，在高并发情况下，Anna通过复制热键的方式在性能方面吊打Redis集群，而在低并发情况下，Anna可以与Redis集群达到相似的性能。
在第二次实验中，RISE研究员将Cassandra的一致性设置为最低级别（ONE），也就是说，只要一个节点确认就表示更新操作成功。他们在AWS的四个EC2可用区域（奥尔良、北弗吉尼亚、爱尔兰和东京）上运行该实验，并通过调整可用区域的节点数量来评测它们的伸缩性。它们的复制系数都被设置为3。
从图8可以看出，随着节点的增加，Anna和Cassandra的性能都呈现出线性增长。不过，Anna比Cassandra的性能高出一大截。事实上，在每个节点使用4个线程时，Anna就可以打败Cassandra，而当把所有的线程都用上，Anna比Cassandra的性能高出10倍以上。
图8
参考资料：https://rise.cs.berkeley.edu/blog/anna-kvs/?twitter=@bigdata