Uma query por leitura: key_hash e o índice único

O curso de nível Júnior "Solid Cache: cache no banco de dados" terminou na tabela: SolidCache::Entry, uma linha por fragmento cacheado, com uma coluna byte_size real que dava para somar. Este curso abre a gem e lê o código que coloca essas linhas ali. Cada afirmação abaixo foi executada contra o banco de cache de desenvolvimento desta aplicação, com o log de queries ligado, usando a solid_cache 1.0.10.

Comece pela menor operação possível. Rails.cache.read("probe:sql:demo") produziu uma instrução SQL:

SELECT "solid_cache_entries"."key", "solid_cache_entries"."value"
FROM "solid_cache_entries"
WHERE "solid_cache_entries"."key_hash" IN (-9004577815424453708)

Releia a cláusula WHERE. A chave que você passou não está nela. O banco recebe um inteiro de 64 bits de que nunca ouviu falar, e esse inteiro é o assunto desta aula.

A tabela e seus índices

O db/cache_schema.rb desta aplicação é o que o generator de instalação da gem escreveu, sem alterações:

create_table "solid_cache_entries", force: :cascade do |t|
  t.integer "byte_size", null: false
  t.datetime "created_at", null: false
  t.binary "key", null: false
  t.bigint "key_hash", null: false
  t.binary "value", null: false
  t.index ["byte_size"], name: "index_solid_cache_entries_on_byte_size"
  t.index ["key_hash", "byte_size"], name: "index_solid_cache_entries_on_key_hash_and_byte_size"
  t.index ["key_hash"], name: "index_solid_cache_entries_on_key_hash", unique: true
end

key e value são binary, que no Postgres vira bytea. Não existe índice nenhum sobre key. Existe um índice único sobre key_hash, um segundo sobre byte_size e um composto sobre o par. O caminho de leitura usa só o único. A aula 4 trata dos outros dois, e eles existem por um motivo que não tem nada a ver com ler.

De onde vem o número

O SolidCache::Entry da gem, em app/models/solid_cache/entry.rb, calcula o hash assim:

def key_hash_for(key)
  # Need to unpack this as a signed integer - Postgresql and SQLite don't support unsigned integers
  Digest::SHA256.digest(key.to_s).unpack("q>").first
end

O SHA-256 da chave dá 32 bytes. unpack("q>") lê os 8 primeiros como um inteiro de 64 bits com sinal, big-endian, e o comentário explica o sinal. O Postgres não tem bigint sem sinal, então o bit mais alto vira bit de sinal e metade das chaves gera hash negativo. É por isso que a query capturada carrega um número negativo. Rode você mesmo e os dois batem:

SolidCache::Entry.send(:key_hash_for, "development:probe:sql:demo")
# => -9004577815424453708
Digest::SHA256.digest("development:probe:sql:demo").unpack("q>").first
# => -9004577815424453708

Repare no prefixo development:. Antes do hash, o store normaliza a chave como todo ActiveSupport::Cache::Store faz: expande arrays em strings e prefixa o namespace. O Solid Cache ainda força o resultado para encoding binário. O namespace vem do config/cache.yml desta aplicação, namespace: <%= Rails.env %>, e é por isso que toda linha do banco de desenvolvimento começa com development:.

Há mais uma normalização própria deste store. Chaves com mais de 1024 bytes (DEFAULT_MAX_KEY_BYTESIZE) são cortadas e recebem um sufixo, para que duas chaves longas com o mesmo primeiro kilobyte ainda gerem hashes diferentes:

def truncate_key(key)
  if key && key.bytesize > max_key_bytesize
    suffix = ":hash:#{ActiveSupport::Digest.hexdigest(key)}"
    truncate_at = max_key_bytesize - suffix.bytesize
    "#{key.byteslice(0, truncate_at)}#{suffix}".b
  else
    key
  end
end

Uma chave de 2000 caracteres saiu com 1024 bytes, terminando em :hash: seguido de um digest hexadecimal de 32 caracteres da chave inteira.

Por que fazer hash da chave em vez de indexá-la

Uma B-tree sobre key funcionaria. Mas seria uma B-tree sobre strings binárias de até um kilobyte cada, comparadas byte a byte, com o índice crescendo junto com as chaves. Uma B-tree sobre bigint guarda oito bytes fixos por entrada, comparados como um único inteiro de máquina. O hash troca uma chance minúscula de colisão por um índice pequeno, denso e rápido, seja qual for o tamanho das suas chaves de cache.

Esta é a troca, medida na tabela de desenvolvimento desta aplicação quando ela tinha cerca de duas mil linhas:

EXPLAIN (ANALYZE, BUFFERS) SELECT key, value FROM solid_cache_entries
  WHERE key_hash IN (-9004577815424453708)

Index Scan using index_solid_cache_entries_on_key_hash on solid_cache_entries
  (cost=0.28..8.30 rows=1 width=870) (actual time=0.008..0.008 rows=0 loops=1)
  Index Cond: (key_hash = '-9004577815424453708'::bigint)
  Buffers: shared hit=4
Execution Time: 0.014 ms

EXPLAIN ANALYZE SELECT key, value FROM solid_cache_entries
  WHERE key = '\x00'::bytea

Seq Scan on solid_cache_entries  (cost=0.00..1101.42 rows=1 width=870)
  (actual time=3.144..3.144 rows=0 loops=1)
  Filter: (key = '\x00'::bytea)
  Rows Removed by Filter: 2018
Execution Time: 3.152 ms

Quatro buffers e 14 microssegundos pelo índice, contra uma varredura completa que tocou todas as linhas. A diferença aumenta conforme a tabela cresce, e um cache de produção movimentado pode ter milhões de linhas.

O que uma colisão faria

Duas chaves podem compartilhar os 8 primeiros bytes do SHA-256. A linha guarda a key completa para que isso degrade com segurança. Na leitura, Entry.read_multi devolve {chave_armazenada => valor}, e o store consulta esse hash pela chave que pediu. Uma linha colidida tem outra chave armazenada, então a consulta não devolve nada e a leitura é um miss, nunca um valor errado. Na escrita, o upsert da aula 2 substitui a linha colidida, e a outra chave vira miss também. Com n linhas, a chance de algum par colidir é de aproximadamente n² / 2^65: uns 3% com um bilhão de linhas, praticamente zero com um milhão.

Muitas chaves, uma instrução

read_multi é a mesma query com uma lista IN mais longa. A gem monta e memoriza um template SQL por quantidade de chaves, então um read_multi com três chaves reaproveita uma string guardada com três placeholders:

SELECT "solid_cache_entries"."key", "solid_cache_entries"."value"
FROM "solid_cache_entries"
WHERE "solid_cache_entries"."key_hash" IN (-1024625935248787865, 3052837480685391812, 4478237884703623321)

Acima de MULTI_BATCH_SIZE, 1000 chaves, ela fatia em várias instruções. Todas rodam dentro de without_query_cache, que é uncached(dirties: false). O query cache por requisição do Active Record não pode servir uma linha de cache velha, e leituras de cache não podem contar como escritas que o limpam.

O cache na frente do cache

O SolidCache::Store faz prepend de ActiveSupport::Cache::Strategy::LocalCache, e a pilha de middleware desta aplicação (bin/rails middleware) inclui ActiveSupport::Cache::Strategy::LocalCache::Middleware. Dentro de uma requisição, leituras repetidas da mesma chave batem num hash em memória depois da primeira query.

Medido: três leituras de uma chave num script bin/rails runner geraram três SELECTs. As mesmas três leituras dentro de Rails.cache.with_local_cache { ... } geraram um. Isso não ajuda entre chaves diferentes. É por isso que o curso de nível Júnior "Querying: detecção N+1" viu um SolidCache::Entry Load por card de curso no roadmap: cada card tem a própria chave, e cada chave é a própria busca no índice.

O que este curso cobre

1. Esta aula: o caminho de leitura, key_hash e o único índice que leituras usam.
2. O caminho de escrita: um único upsert, compressão e de onde vem o byte_size.
3. FOR UPDATE, e o teste com dez threads que mostra onde unless_exist e increment deixam de ser atômicos.
4. Estimar o tamanho do cache inteiro a partir dos dois índices que leituras nunca tocam.
5. Expiração: primeiro a entrar, primeiro a sair, por id, e não pelo uso mais recente, e por que não existe índice em created_at.
6. Failsafe, shards e a thread de fundo que faz as deleções.
7. Um fetch rastreado de ponta a ponta, e a escolha entre isso e Redis.

A aula 2 começa onde esta parou: a linha que uma escrita coloca atrás daquele inteiro, e a única coluna que o caminho de escrita toma cuidado para nunca atualizar.