Hashing for identity versus placement

This application hashes things in three places, and none of them is what consistent hashing is for. Seeing the difference is the fastest way into the topic.

The three hashes here

1. A cache key becomes a 64-bit integer

# db/cache_schema.rb
t.binary "key", null: false
t.bigint "key_hash", null: false
t.index ["key_hash"], name: "index_solid_cache_entries_on_key_hash", unique: true

Solid Cache stores the key and a hash of the key, and looks entries up by the hash, because a bigint index is cheaper than an index on arbitrary binary data.

2. A certificate gets a short public code

# app/policies/enrollment/certificate_code.rb
digest = OpenSSL::HMAC.hexdigest("SHA256", Rails.application.secret_key_base, "certificate:#{enrollment.id}")
"NOR-#{digest[0, 4].upcase}-#{digest[4, 4].upcase}"

3. An uploaded image gets a random suffix in its filename

hash = SecureRandom.hex(4)
new_filename = "#{@lesson.slug}-#{index + 1}-#{hash}.webp"

What all three have in common

Each one maps something to a number in order to name it: a lookup key, a public identifier, a filename.

None of them decides where anything is stored. There's one cache table, one storage volume and one database. The hash answers "what is this called?", and the answer to "where does it live?" is always the same place.

That's hashing for identity, and it's the common case.

What consistent hashing is for

It's for hashing for placement: given a key and N servers, which server holds it?

The requirement differs in a way that changes everything: every participant must compute the same answer on its own, with no coordination and no lookup table. A client, a proxy and a server must all agree on which cache node holds course/42, without asking anybody.

The naive answer is one line:

node = nodes[hash(key) % nodes.size]

It's correct, fast and evenly distributed, and it's the wrong answer, for a reason you can't see until the day nodes.size changes. That's lesson 2.

flowchart TB
  I["hashing for identity"] --> I1["a cache key_hash, a certificate code, a filename"]
  I1 --> I2["answers: what is this called"]
  P["hashing for placement"] --> P1["which of N servers holds this key"]
  P1 --> P2["every participant must compute the same answer with no coordination"]
  P2 --> P3["modulo works until N changes"]

A measured aside on identity hashes

The certificate code uses eight hex characters: thirty-two bits, or 4,294,967,296 possible codes.

By the birthday bound, the chance that two certificates share a code reaches one half at around 77,000 certificates issued. That number is worth knowing rather than assuming.

Here it's a cosmetic property, not a risk, and the routes prove it. A certificate is fetched by u/:username/certificates/:course_slug, so the code is displayed and passed to LinkedIn, but never used to find anything. Two identical codes would be a curiosity, not a mix-up.

The general rule is the useful part: a truncated hash starts colliding at roughly √(2^bits), and whether that matters depends on whether anything looks the value up.

Why placement is the hard one

Read the last row. An identity hash's inputs are stable. A placement hash's inputs include the cluster, and the cluster changes.

Key takeaways

• This application hashes for identity three times: a cache key_hash, a certificate code and an image filename.
• Identity hashing answers "what is this called?". Placement hashing answers "which of N servers holds it?".
• Placement requires every participant to compute the same answer with no coordination and no lookup table.
• A truncated hash collides at roughly the square root of its space: 32 bits collide near 77,000 items.
• The hard part of placement is that its input includes the cluster, and the cluster changes.