Hacker News Reader

Comment by yeldarb | Hacker News Reader

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

View on HN

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.

Ugh really? Why would they not hash the whole filename for shard assignment?

Because the file name includes the "directory" prefix, i.e. each file's name stores the `/entire/bucket/dir/tree`, which can get large.

The size of the input doesn't affect the hashing.

It affects the runtime of the hashing.

In these systems you typically can list blobs based on prefix. If you shard blobs sharing prefix to different nodes that becomes difficult.

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

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.

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.

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.

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

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

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. I'd love to see this compared with sha1.

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?

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.

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.

Reply on news.ycombinator.com