3 ms·

> 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 ke

> 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.

hintymad 5y ago
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).
- packetslave 5y ago
  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.
  - hintymad 5y ago
    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.
    - packetslave 5y ago
      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.
      - tlipcon 5y ago
        Colossus metadata is stored in Bigtable: see https://cloud.google.com/blog/products/storage-data-transfer/a-peek-behind-colossus-googles-file-system 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.
        packetslave 5y ago
        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-Keynote.pdf http://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-Ke...
luhn 5y ago
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.
dastbe 5y ago
(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.

hintymad 5y ago

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).

packetslave 5y ago
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.
- hintymad 5y ago
  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.
  - packetslave 5y ago
    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.
    - tlipcon 5y ago
      Colossus metadata is stored in Bigtable: see https://cloud.google.com/blog/products/storage-data-transfer/a-peek-behind-colossus-googles-file-system 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.
      - packetslave 5y ago
        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-Keynote.pdf http://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-Ke...

luhn 5y ago

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.

dastbe 5y ago

(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.