News for hackers. Stuff that matters.
Re:Anna: A key-value store for any scale by rmbyrro on Friday April 29, 2022 @03:51PM (#31209880)
> Following the Dynamo design, Anna applies a CRC32 hash on the id to assign the actor to a position on the hash ring and applies the same hash function to a key in order to determine the actors responsible for storing the key.

I think this choice is what led to the "hot-partition" hell that early versions of DynamoDB suffered from, is that correct?

Anyone knows how DynamoDB handles this nowadays? What I know is they eliminated the hot-partition issue, at least from the user/developer perspective.

Re:Anna: A key-value store for any scale by luhn on Friday April 29, 2022 @04:55PM (#31210486)
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.

Re:Anna: A key-value store for any scale by dastbe on Friday April 29, 2022 @06:09PM (#31211155)
(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.

Re:Anna: A key-value store for any scale by hintymad on Friday April 29, 2022 @04:47PM (#31210391)
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).

Re:Anna: A key-value store for any scale by packetslave on Friday April 29, 2022 @09:58PM (#31212683)
Colossus doesn’t use Spanner for metadata unless the design has changed (always possible). Colossus metadata is self-hosted, except for the “ring zero” metadata needed to bring up the cluster, which is in Chubby.
Re:Anna: A key-value store for any scale by hintymad on Saturday April 30, 2022 @07:17PM (#31220427)
Thanks. I must've got it wrong then. I remember the Colossus paper said Colossus built a scalable metadata system, but someone from Google told me that the metadata system was based on Spanner, and I took it for granted.
Re:Anna: A key-value store for any scale by packetslave on Saturday April 30, 2022 @08:25PM (#31220865)
It's entirely possible they've re-architected Colossus to run on top of Spanner by now (I left in 2018). A lot of distributed systems problems just disappear when you throw Spanner into the mix, so it would make sense. The only argument against it would be adding a dependency.
Re:Anna: A key-value store for any scale by tlipcon on Sunday May 01, 2022 @01:59AM (#31222592)
Colossus metadata is stored in Bigtable: see https://cloud.google.com/blog/products/storage-data-transfer...

Spanner stores its data in Colossus, so there would be some bootstrapping issues to resolve to move it to Spanner over Bigtable. (Bigtable also has the bootstrap issues but has solved them already and there are additional difficulties due to some details that I probably am not at liberty to share)

Spanner is used for metadata for many other very very large storage systems, though.

Re:Anna: A key-value store for any scale by packetslave on Sunday May 01, 2022 @12:36PM (#31226393)
Yeah, that was my understanding as well. Colossus stores metadata in Bigtable on top of a smaller Colossus, which stores its metadata in Bigtable on top of an even smaller Colossus, which… [insert more stacks of turtles here] ends up in Chubby.

Public presentation here: http://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-Ke...