5 ms·

Interestingly, for other systems you sometimes want the exact opposite: for your key space to be distributed across indexes to balance the load (vs wanting them

Interestingly, for other systems you sometimes want the exact opposite: for your key space to be distributed across indexes to balance the load (vs wanting them all to hit the same “hot” index for MySQL). For example, Google’s Cloud Firestore is bottlenecked to 500 writes/second if your key is monotonically increasing (like a timestamp or these timestamp-based UUIDs) causing you to “hotspot” the index: https://cloud.google.com/datastore/docs/best-practices#high_readwrite_rates_to_a_narrow_key_range https://cloud.google.com/datastore/docs/best-practices#high_...

ummonk 5y ago
Yeah S3 has similar performance issues where accessing objects with the same prefixes has lower throughput because they get sharded onto the same server. It's very counterintuitive when you're used to how performance works on single computers where you want to optimize for cache-locality.
- nielsole 5y ago
  Ugh really? Why would they not hash the whole filename for shard assignment?
  - bowmessage 5y ago
    Because the file name includes the "directory" prefix, i.e. each file's name stores the `/entire/bucket/dir/tree`, which can get large.
    - manigandham 5y ago
      The size of the input doesn't affect the hashing.
      - bowmessage 5y ago
        It affects the runtime of the hashing.
  - mmoskal 5y ago
    In these systems you typically can list blobs based on prefix. If you shard blobs sharing prefix to different nodes that becomes difficult.
- sterwill 5y ago
  This used to be the case, but it's not true any more. For example, previously Amazon S3 performance guidelines recommended randomizing prefix naming with hashed characters to optimize performance for frequent data retrievals. You no longer have to randomize prefix naming for performance, and can use sequential date-based naming for your prefixes. https://docs.aws.amazon.com/AmazonS3/latest/userguide/optimizing-performance.html https://docs.aws.amazon.com/AmazonS3/latest/userguide/optimi...
  - henrydark 5y ago
    The doc is talking about how the full prefix is now part of the sharding, in contrast to previous times when only the few characters mattered. But if you put many files with the exact same prefix - even sequential dates - then you hit the threshold the doc says, about 5000 ops/sec.
    - sterwill 5y ago
      I re-read your comment and you do say "same" prefixes (I think I read it as "shared"), which AWS hasn't changed the behavior of (AFAIK). You're right that objects with the exact same prefix are still routed to the same shard (set?) and have that throughput limit. P.S.: In a few projects I've built prefixes using timestamps, but not at the very beginning, and worried that they weren't getting sharded out. The change I linked to fixes that problem.
espadrine 5y ago
That is generally true for most if not all NewSQL databases, as far as I know. Spanner, CockroachDB, TiDB, … Maybe even Aurora? The second argument on secondary indexes’ size still holds water, if it matters for a given application.
kyrra 5y ago
Your other option is to hash your monotonically increasing numbers. You don't want to use something like SHA, as it does not give good distribution. You use something like murmur hash (https://en.m.wikipedia.org/wiki/MurmurHash https://en.m.wikipedia.org/wiki/MurmurHash). I've used it before for indexes at Google for values that may hotspot. See Google's impl here: https://github.com/google/zetasketch/blob/master/java/com/google/zetasketch/internal/hash/Fingerprint2011.java https://github.com/google/zetasketch/blob/master/java/com/go...
- rossmohax 5y ago
  > You don't want to use something like SHA, as it does not give good distribution How come? Even distribution is one of requirements for crypto hash functions.
  - kyrra 5y ago
    You know, likely am wrong here. I think murmur is good because it had a good distribution and is much faster than SHA? I did find someone that compared murmur to other non crypt hashes here: https://softwareengineering.stackexchange.com/a/145633 https://softwareengineering.stackexchange.com/a/145633. I'd love to see this compared with sha1.
- isoprophlex 5y ago
  Can you elaborate on the claim about SHA? If I'm not mistaken, all these cryptographic hashes have a 50% chance of flipping any one output bit upon changing a single input bit -- is there some hidden gotcha I'm unaware of?
  - withinboredom 5y ago
    It’s about random distribution. If you output an array of the key space as a bitmap, it should look like white noise. SHA doesn’t look like white noise. There are certain parts of the space it rarely goes with certain classes of inputs (numeric, usernames, etc) while murmur and md5 give that white noise look.
mdasen 5y ago
Is it that they truly want it distributed across the key space or distributed across the shards? With MySQL, you're writing to a single box. Because of that, you'll want to be on hot pages. With Firestore, you're writing to many boxes. If you hotspot with Firestore, you're only writing to one box. If you write completely randomly to Firestore, maybe each box is bottlenecked to 400 wires/second (rather than 500) because there's no locality on each box. But if Google isn't charging you based on locality, there's no penalty for you since it'll scale up to more boxes (invisibly behind the scenes). If you're only writing to one box, might as well take advantage of locality. If you have the opportunity to write to many boxes, you don't want all of the load going to one box. However, one could imagine a distributed system where you could try and get both. Create an ID that has the ShardId to route it to the correct box and then something sequential after the ShardId. If you had 1,000 shards and 25 boxes, each box would be responsible for 40 shards so you wouldn't be perfectly sequential, but you'd kinda end up with 40 hot pages rather than randomly writing all over the place. It would also give you ample room to scale up your cluster. So there is room to apply this technique to a distributed system as well. Oh, one thing I'd note is that MySQL's InnoDB uses index-oriented (clustered) tables as they note in the article (which is why this is important with MySQL). PostgreSQL doesn't use index-oriented tables so new rows are (I believe) just written sequentially by default regardless of ID. It will have to update the primary-key index, but because the PK will be a lot smaller than the whole rows, you probably don't have to worry as much about randomly writing there. It's easier to keep an index hot than to keep a whole table hot.

ummonk 5y ago

Yeah S3 has similar performance issues where accessing objects with the same prefixes has lower throughput because they get sharded onto the same server. It's very counterintuitive when you're used to how performance works on single computers where you want to optimize for cache-locality.

nielsole 5y ago
Ugh really? Why would they not hash the whole filename for shard assignment?
- bowmessage 5y ago
  Because the file name includes the "directory" prefix, i.e. each file's name stores the `/entire/bucket/dir/tree`, which can get large.
  - manigandham 5y ago
    The size of the input doesn't affect the hashing.
    - bowmessage 5y ago
      It affects the runtime of the hashing.
- mmoskal 5y ago
  In these systems you typically can list blobs based on prefix. If you shard blobs sharing prefix to different nodes that becomes difficult.
sterwill 5y ago
This used to be the case, but it's not true any more. For example, previously Amazon S3 performance guidelines recommended randomizing prefix naming with hashed characters to optimize performance for frequent data retrievals. You no longer have to randomize prefix naming for performance, and can use sequential date-based naming for your prefixes. https://docs.aws.amazon.com/AmazonS3/latest/userguide/optimizing-performance.html https://docs.aws.amazon.com/AmazonS3/latest/userguide/optimi...
- henrydark 5y ago
  The doc is talking about how the full prefix is now part of the sharding, in contrast to previous times when only the few characters mattered. But if you put many files with the exact same prefix - even sequential dates - then you hit the threshold the doc says, about 5000 ops/sec.
  - sterwill 5y ago
    I re-read your comment and you do say "same" prefixes (I think I read it as "shared"), which AWS hasn't changed the behavior of (AFAIK). You're right that objects with the exact same prefix are still routed to the same shard (set?) and have that throughput limit. P.S.: In a few projects I've built prefixes using timestamps, but not at the very beginning, and worried that they weren't getting sharded out. The change I linked to fixes that problem.

espadrine 5y ago

That is generally true for most if not all NewSQL databases, as far as I know. Spanner, CockroachDB, TiDB, … Maybe even Aurora? The second argument on secondary indexes’ size still holds water, if it matters for a given application.

kyrra 5y ago

Your other option is to hash your monotonically increasing numbers. You don't want to use something like SHA, as it does not give good distribution. You use something like murmur hash (https://en.m.wikipedia.org/wiki/MurmurHash https://en.m.wikipedia.org/wiki/MurmurHash). I've used it before for indexes at Google for values that may hotspot. See Google's impl here: https://github.com/google/zetasketch/blob/master/java/com/google/zetasketch/internal/hash/Fingerprint2011.java https://github.com/google/zetasketch/blob/master/java/com/go...

rossmohax 5y ago
> You don't want to use something like SHA, as it does not give good distribution How come? Even distribution is one of requirements for crypto hash functions.
- kyrra 5y ago
  You know, likely am wrong here. I think murmur is good because it had a good distribution and is much faster than SHA? I did find someone that compared murmur to other non crypt hashes here: https://softwareengineering.stackexchange.com/a/145633 https://softwareengineering.stackexchange.com/a/145633. I'd love to see this compared with sha1.
isoprophlex 5y ago
Can you elaborate on the claim about SHA? If I'm not mistaken, all these cryptographic hashes have a 50% chance of flipping any one output bit upon changing a single input bit -- is there some hidden gotcha I'm unaware of?
- withinboredom 5y ago
  It’s about random distribution. If you output an array of the key space as a bitmap, it should look like white noise. SHA doesn’t look like white noise. There are certain parts of the space it rarely goes with certain classes of inputs (numeric, usernames, etc) while murmur and md5 give that white noise look.

mdasen 5y ago

Is it that they truly want it distributed across the key space or distributed across the shards? With MySQL, you're writing to a single box. Because of that, you'll want to be on hot pages. With Firestore, you're writing to many boxes. If you hotspot with Firestore, you're only writing to one box. If you write completely randomly to Firestore, maybe each box is bottlenecked to 400 wires/second (rather than 500) because there's no locality on each box. But if Google isn't charging you based on locality, there's no penalty for you since it'll scale up to more boxes (invisibly behind the scenes). If you're only writing to one box, might as well take advantage of locality. If you have the opportunity to write to many boxes, you don't want all of the load going to one box. However, one could imagine a distributed system where you could try and get both. Create an ID that has the ShardId to route it to the correct box and then something sequential after the ShardId. If you had 1,000 shards and 25 boxes, each box would be responsible for 40 shards so you wouldn't be perfectly sequential, but you'd kinda end up with 40 hot pages rather than randomly writing all over the place. It would also give you ample room to scale up your cluster. So there is room to apply this technique to a distributed system as well. Oh, one thing I'd note is that MySQL's InnoDB uses index-oriented (clustered) tables as they note in the article (which is why this is important with MySQL). PostgreSQL doesn't use index-oriented tables so new rows are (I believe) just written sequentially by default regardless of ID. It will have to update the primary-key index, but because the PK will be a lot smaller than the whole rows, you probably don't have to worry as much about randomly writing there. It's easier to keep an index hot than to keep a whole table hot.