Anna: A key-value store for any scale

The post touches on the underlying problem. Distributed stuff is fundamentally very difficult. As Jepson has shown so definitively, getting these protocols right is very unlikely even for very experienced developers. Small changes can destroy correctness, or influence the assumed consistency / isolation level in surprising ways.

The NoSQL fad embraced one extreme: the simplicity and performance of Eventual Consistency, essentially pushing any complexity that creates onto the application. At the other extreme, the Spanner paper explicitly argues for prioritizing correctness first, using a conservative transaction design more straightforward to implement and use, at the cost of potentially much worse performance under high contention.

Both approaches have merits, but I think it's clear they aren't one size fits all solutions. Or even fits most. Hence the explosion in systems trying to find some balance between these extremes. With time the picture should resolve. The early days of rdbms's went through a similar explosion then consolidation down to the most effective algorithms.

We don't really need more than that.

Nearly every lookup system can be built with a KV. Heck a lot of modern DBs literally are just a sql engine on top of KV.

Fundamentally they can do it because partitions are relatively small, so you'll have hundreds of partitions from hundreds of different tables on a single machine and a handful of hot partitions are only a tiny blip. (There is of course a limit to how hot a partition can be, they'll cut you off before you start consuming a large amount of resources on the host.)

Unfortunately single-tenant systems are more constrained in this, because you don't have millions of partitions to spread across thousands of machines.

(this may be out of date)

dynamodb differs from the dynamo architecture quite a bit. ddb's partitioning of the hash ring is contiguous and each partition is backed by a set of replicas. when a partition gets hot for whatever reason the partition is split and each half gets its own set of replicas. this historically led to two issues

1. splitting also split RCUs/WCUs proportionally, so if you split a bunch then scaled down your db would have a very low amount of RCU/WCUs available per partition leading to surprisingly throttling. if you did a load test right before your launch, you would be better off trashing the db to avoid this.

2. responsiveness to hot spotting. dynamodb wasn't as good about burst capacity management and so between when you hit a hot spot and dynamodb reacted, you'd be up a creek.

I also have a similar question: how could a consistent hash ring "infinitely scale"? As the number of nodes increases, the chances that some nodes flip-flop their membership will increase, and the system will become less reliable. Such temporary instability is very annoying for operations (alert mitigation in particular), especially when the requests per second is high.

I think there's a reason that large-scale KV stores use range-based partitions, such as FB's Tectonic and Google's Colossus (Colossus uses Spanner for metadata, and Spanner uses hierarchical range-based partitioning).

Here's two reasons which come to my mind:

* Operationally, there's no turn-key, hosted solution. Getting it set up locally for testing and CI is not trivial. You have to really want to use it. This criticism 100% applies to Anna too.

* FoundationDB provides serializable transactions (yay!), but it doesn't provide the tools to make this work well in the face of contention. FoundationDB uses fully optimistic concurrency control. Consider you have a workload where, say, you want users to do something as simple as increasing a counter. In FoundationDB, you're going to have a bad time if there are lots of concurrent writes. You might instead need to reorganize the problem into having the increments each just write a row and then in the background, read the older rows and turn them into an increment in a single-threaded way. In Anna, you can define your counter data structure inside the system. That's cool. More generally though, Anna pushes the problem of consistency further into the database, which, while cool, is also not super convenient. It does scale. Other databases use pessimistic locking to deal with contention. That is going to be lower throughput because the work will need to serialize. It'll still be higher throughput and lower latency than a fully-optimistic approach.

FoundationDB is operationally very complex; there's a multitude of processes, no reference architectures of at-scale deployments (althought those do exist; at least at Snowflake and Apple), no docker images with helm charts, and no cloud managed solution.

It's also extremely low level, at the query layer, it's simply an ordered map of (byte[], byte[]). The sibling comment also mentions optimistic concurrency control as a built-in primitive that can scale poorly with high contention. These two issues and similar others are left for the query layer to resolve. Foundationdb is not really intended to be used directly as a general purpose key/value store but to provide a distributed transaction and storage layer for a query layer to be implemented on top of it.

I think it's interesting to think about foundationdb as a higher-layer from rocksdb which has quickly become the de-facto standard for the single node storage-layer. For building highly scalable, globally distributed ACID systems, foundationdb could very well be the clear winner like you say, although systems in this category have opted to implement their own consensus and transaction layers. At least, all the spanner and calvin derivatives I know of (cloud spanner, yugabyte, cockroach, faunadb) implement their own. But for use cases where strict serializability is not required, there's ample room for innovation and I think this is where things like Anna can potentially fit in

Plenty of user facing apps do need strong consistency. We use Cassandra at Ripple, for API access to the XRP ledger, and strong consistency is a requirement. Records refer to other records, and not being able to reason about when things are going to show up in the database would lead to a ton of complexity. For instance, I read a transaction, then I want to read the account that sent or received that transaction. I need to know the record for the account is going to be there in the database, and is consistent with the transaction, as opposed to stale. Or, a client might be paging through data over several calls, where we return a marker to allow the client to resume. This wouldn't work if some nodes might not know about the marker.

When do you need anything stronger than causal consistency? Eg when I was a jpmorgan, actual customer financial transactions in practice just needed causal consistency. Anything stronger than that really was about consistent snapshot reads for reporting purposes.

I disagree. Most user-facing apps I've seen in my career don't really need strong consistency.

The question is the performance of eventuality for propagating changes. If it's sub-second level, I'd say 99% of apps (of those which don't need strong consistency) can live with that. Single-digit seconds could still serve many purposes.

Does this mean Anna favors availability and partition tolerance over consistency?

> this is not scalable

what

I was impressed reading that as well, but after looking at the code, I wonder if it’s really 2000? It seems more.

Regardless, the code is clearly well-organized, easy to read and to the point. I like it.

https://github.com/hydro-project/anna

server.cpp alone is 798 lines, it's definitely more than 2K total.

Most code written for a paper is effectively abandoned before or soon after the paper is released.