Hash para identidade contra alocação

Esta aplicação calcula hashes em três lugares, e nenhum deles é o uso do hash consistente. Ver a diferença é o caminho mais rápido para entrar no assunto.

Os três hashes daqui

1. Uma chave de cache vira um inteiro de 64 bits

# 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

O Solid Cache guarda a chave e um hash dela, e busca as entradas pelo hash, porque um índice em bigint é mais barato que um índice sobre dados binários quaisquer.

2. Um certificado ganha um código público curto

# 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. Uma imagem enviada ganha um sufixo aleatório no nome do arquivo

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

O que os três têm em comum

Cada um transforma algo num número para dar nome a ele: uma chave de busca, um identificador público, um nome de arquivo.

Nenhum deles decide onde algo fica guardado. Há uma tabela de cache, um volume de armazenamento e um banco. O hash responde "como isto se chama?", e a resposta para "onde isto fica?" é sempre o mesmo lugar.

Isso é hash para identidade, e é o caso comum.

Para que serve o hash consistente

Ele serve para o hash de alocação: dada uma chave e N servidores, qual servidor a guarda?

A exigência muda tudo: cada participante precisa chegar sozinho à mesma resposta, sem coordenação e sem tabela de consulta. Um cliente, um proxy e um servidor precisam concordar sobre qual nó de cache guarda course/42, sem perguntar a ninguém.

A resposta ingênua cabe numa linha:

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

Ela é correta, rápida e bem distribuída, e é a resposta errada, por um motivo que não aparece até o dia em que o nodes.size muda. Esse é o assunto da lição 2.

flowchart TB
  I["hash para identidade"] --> I1["um key_hash de cache, um código de certificado, um nome de arquivo"]
  I1 --> I2["responde: como isto se chama"]
  P["hash para alocação"] --> P1["qual dos N servidores segura esta chave"]
  P1 --> P2["todo participante precisa calcular a mesma resposta sem coordenação"]
  P2 --> P3["o módulo funciona até N mudar"]

Um parêntese medido sobre hashes de identidade

O código do certificado usa oito caracteres hexadecimais: trinta e dois bits, ou 4.294.967.296 códigos possíveis.

Pelo limite do aniversário, a chance de dois certificados terem o mesmo código chega a metade por volta de 77.000 certificados emitidos. Vale conhecer esse número em vez de supor.

Aqui isso é uma propriedade cosmética, e não um risco, e as rotas mostram por quê. Um certificado é buscado por u/:username/certificates/:course_slug, então o código é exibido e enviado ao LinkedIn, mas nunca é usado para encontrar nada. Dois códigos iguais seriam uma curiosidade, e não uma confusão.

A regra geral é a parte útil: um hash truncado começa a colidir por volta de √(2^bits), e se isso importa depende de alguma coisa buscar pelo valor.

Por que a alocação é a difícil

Leia a última linha. As entradas de um hash de identidade são estáveis. As de um hash de alocação incluem o cluster, e o cluster muda.

Pontos-chave

• Esta aplicação usa hash para identidade três vezes: um key_hash de cache, um código de certificado e um nome de arquivo de imagem.
• O hash de identidade responde "como isto se chama?". O hash de alocação responde "qual dos N servidores guarda isto?".
• A alocação exige que cada participante chegue à mesma resposta sem coordenação e sem tabela de consulta.
• Um hash truncado colide por volta da raiz quadrada do espaço: 32 bits colidem perto de 77.000 itens.
• A parte difícil da alocação é que a entrada dela inclui o cluster, e o cluster muda.