Paper Note: [ICDE'18] Anna: A KVS for any scale

Anna is a key-value store researched at UC Berkeley [1]. Its pioneering use of lattices allows users to define custom conflict-resolution methods, which in turn enables custom consistency levels and can greatly improve system performance in specific scenarios. Anna uses the actor model rather than the traditional shared-memory model to build the system, allowing it to handle communication and coordination in single-node and distributed scenarios in an almost uniform way while fully exploiting the concurrency provided by the hardware. The paper does not describe the implementation details of these two aspects in depth. Because both are challenging to implement, I look forward to future research disclosing further details.

At a high level, Anna has the same architecture as Amazon Dynamo [2]. The difference is that Dynamo’s nodes are physical nodes, whereas Anna’s nodes are actors. Anna binds actors to the available threads on each node, avoiding thread-switching overhead and providing higher-performance service. Anna handles reads and writes without a coordinator, while Dynamo’s sloppy quorum requires one.

Anna’s basic ideas come from [3] and [4] ([5] is a supplement to [4]). Highly Available is defined as guarantees a response from each non-failing server in the presence of arbitrary network partitions between them. As shown in Partial ordering of HAT, the consistency levels in red are impossible to achieve under HA constraints, while the others may still be achievable under HA constraints. So if we need both HA and replication, how do we achieve consistency? The answer is eventual consistency: respond immediately when receiving a client request, then periodically propagate the change in the background and make all replicas converge under a certain protocol. How should this eventual-consistency protocol be designed? Based on prior experience [7] from the Bloom language [6], Anna uses lattices as a structure that lets users define CRDTs themselves [4]. During conflict resolution, the required consistency guarantees can then be provided according to the user-defined CRDT.

For CRDT design, the CRDT is required to satisfy the ACI properties, as shown in ACI properties.

Satisfying these properties has the following benefits. Idempotence lets us easily handle the problems caused by message propagation with at least once semantics. Associativity and commutativity let us arrange and combine these operations in any order. This means we only need to record the merge-operation log for client requests and then synchronize it among replicas, without handling the ordering relationships between them. My understanding is that a lattice records causality and versioning internally, so in practice this is handled similarly to Dynamo; it is simply more flexible than Dynamo in conflict resolution.

Anna’s performance evaluation shows that it has a significant advantage over other key-value stores. I think there are several possible reasons: