Open levy5307 opened 3 years ago
https://levy5307.github.io/blog/Anna/
在现在KV存储系统中，有些设计成全球范围内分布式的，有些设计成单机的。然而在近些年都逐渐收敛到云上。基于这个背景，我们设计了一个可以在任何scale上都运行的很好的KV系统。针对该KV系统，我们发现了四个设计需求：
partition。为了实现data scaling当然需要partition。但是我们实现partition不仅需要云上跨机器的，也需要跨cpu核以提供更高性能。 multi-master replication。为了实现workload scaling，我们需要实现multi-master replication使用多线程来同时响应读写请求。 wait-free execution。为了更大化使用多核机器的硬件使用率和性能，我们需要实现wait-free execution。这意味着每个线程都是在做有意义的工作，而无需等待其他线程。 coordination-free一致性模型。为了支持更广范围的应用，我们需要实现一个广泛范围的coordinator-free一致性模型。
这篇论文描述了Anna的设计和实现，为跨scale设计提供了一套架构和经验：
Coordination-free Actors。我们可以确定coordination-free actor模型对于scale从单机多核到分布式都提供了很优秀的性能，好过当前最高水平，并且可以提供平滑的扩缩容容以及时得repartition更加具有弹性。 Lattice-Powered Coordination-Free Consistency。一致性代码很简短而且模块化：不同的一致性level仅有至多60行代码的区别。 Cross-Scale Validation。我们与其他横跨不同scale的KV系统进行了对比：单机的Redis和根据地理位置分片的Apache Cassandra。我们发现Anna的性能在任何scale下都具有很有竞争力的性能，并且还能提供不同等级的一致性。
Lattices
Anna的一个设计核心组件便是lattice的使用。lattice的重要性主要体现在下面两点：
lattice对于update的操作顺序不敏感。这意味着即使不同的副本执行不同的update次序，也能够保证一致性。 lattice的组合可以实现一系列范围的一致性。之前的研究表明coordinator-free不能够实现最强等级一致性，例如linearizability或者serializability，但是可以实现相对强等级的一致性，例如causality和read-committed。我们的贡献在于证明可以使用lattice可以实现很多不同等级的一致性。
Distributed state model
这一节描述了Anna的actor模型。每个actor使用率lattice维护了一个状态机。当时我们发现即使这样也不够高效。因为共享内存的同步操作会耗费很多性能，因此Anna中基于异步信息发送避免了使用共享内存
Limitations of shared-memory
大量的multi-core kv系统使用了共享内存将整个存储的状态在多个线程间共享：每个线程都可以进行读或者写。需要对读和写操作进行同步，来防止冲突产生。同步可以通过有锁或者无锁的方式来实现，然而不管是否有锁，都会影响竞争情况下的可扩展性，因为cache一致性带来的性能损耗。latice并没有改变上述情况，如果使用了共享内存，一样会有相应的同步开销。
Message-passing
message-passing结构由一系列的actor组成，每个actor运行在一个单独的cpu核上。每个actor维护自己的状态且其他actor不可访问。actor运行一个loop，循环从input queue中获取客户端的请求以及其他核发来的消息进行处理。由于每个actor只会处理自己的local state，所以避免了共享内存，因此也避免了同步操作
message-passing有两种管理key的选择：single-master和multi-master replication。
single-master replication。在该模式下，每个key都会指派给一个单独的actor。这防止了对一个key的同时修改，因此而保证了一致性。但是这将一个key的更新频率限制在了单个actor的更新频率。 multi-master replication。一个key会被复制到多个actor，每个actor读取或者更新其本地副本。这也分为两种模式：coordination和coordination-free： coordination是指当更新一个key时，actors可以参与协调控制，使得update按照一个全局的顺序，尽管多个actor可以处理updates，然而全局有序的广播使得每个actor都将这些update按照相同的顺序进行处理。 coordination-free模式中，每个actor在本地处理请求，并且不会引入inter-actor communication。所有update的communication在timer被触发、或者actor的请求负载减少的情况下进行。
coordination-free的multi-master模式将会导致副本间的不一致，因为副本将会以不同的顺序处理请求。因此Anna引入了lattice，借助lattice可以避免不一致的情况。
Anna architecture
https://levy5307.github.io/blog/Anna/
在现在KV存储系统中，有些设计成全球范围内分布式的，有些设计成单机的。然而在近些年都逐渐收敛到云上。基于这个背景，我们设计了一个可以在任何scale上都运行的很好的KV系统。针对该KV系统，我们发现了四个设计需求：
这篇论文描述了Anna的设计和实现，为跨scale设计提供了一套架构和经验：
Lattices
Anna的一个设计核心组件便是lattice的使用。lattice的重要性主要体现在下面两点：
Distributed state model
这一节描述了Anna的actor模型。每个actor使用率lattice维护了一个状态机。当时我们发现即使这样也不够高效。因为共享内存的同步操作会耗费很多性能，因此Anna中基于异步信息发送避免了使用共享内存
Limitations of shared-memory
大量的multi-core kv系统使用了共享内存将整个存储的状态在多个线程间共享：每个线程都可以进行读或者写。需要对读和写操作进行同步，来防止冲突产生。同步可以通过有锁或者无锁的方式来实现，然而不管是否有锁，都会影响竞争情况下的可扩展性，因为cache一致性带来的性能损耗。latice并没有改变上述情况，如果使用了共享内存，一样会有相应的同步开销。
Message-passing
message-passing结构由一系列的actor组成，每个actor运行在一个单独的cpu核上。每个actor维护自己的状态且其他actor不可访问。actor运行一个loop，循环从input queue中获取客户端的请求以及其他核发来的消息进行处理。由于每个actor只会处理自己的local state，所以避免了共享内存，因此也避免了同步操作
message-passing有两种管理key的选择：single-master和multi-master replication。
coordination-free的multi-master模式将会导致副本间的不一致，因为副本将会以不同的顺序处理请求。因此Anna引入了lattice，借助lattice可以避免不一致的情况。
Anna architecture