Potential hash-collision CPU amplification in multi-field Redis HASH commands

Aperta
  • Qualcosa non va?
#3,619 1 commento 0 reazioni 1 assegnatario Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

@garvit-arora ci sta già lavorando.

Dal 8/10/2026.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
35/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
cpp, redis
Ambito
databases, performance, security

Direzione di ricerca

Inizia tracciando i percorsi dei comandi e dei container citati in src/commands/cmd_hash.cc e src/types/redis_hash.cc, inclusi HDEL, HSET/HMSET e le cache di scadenza dei campi. Esegui quindi il kvrocks_hash_bench.cpp fornito per riprodurre il comportamento isolato, poi esamina THREAT_MODEL.md §8.6/§9 e i costi di compatibilità e dei carichi di lavoro normali prima di valutare le mitigazioni. Il lavoro è completato quando una mitigazione o una conclusione è supportata da test e misurazioni, senza affermare che il benchmark isolato sia un risultato della latenza del server.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

bug
Search before asking
  • I had searched in the issues and found no similar issues.
Version

Kvrocks commit: c92e7abdaf3ceb0ea0dc7dd455d035430e3bfc91.

Minimal reproduce step

Source paths (steps 1-3) plus an isolated container benchmark (step 4). A live RESP reproduction against a running instance was not performed.

  1. Follow CommandHDel::Execute() in src/commands/cmd_hash.cc:473-485 to Hash::Delete() in src/types/redis_hash.cc:954-975. For an existing Hash key, client-supplied field names enter a default-hashed set before field lookup.

  2. Follow CommandHMSet::Execute() at cmd_hash.cc:643-647 to Hash::MSet() at redis_hash.cc:1018-1054. Both HSET and HMSET use this path, including when creating a new Hash key.

  3. For the field-expiration paths, follow HSETEX/HGETEX at cmd_hash.cc:925,966 to the caches at redis_hash.cc:687-688,858-859, then LoadFieldStates() at 274-285. These paths require non-legacy Hash encoding; the default is legacy (kvrocks.conf:80-88). HGETEX also requires an existing Hash key to reach its cache.

  4. Build and run the accompanying kvrocks_hash_bench.cpp:

    g++ -std=c++17 -O2 kvrocks_hash_bench.cpp -o kvrocks_hash_bench
./kvrocks_hash_bench

    This standalone program uses the same set type and lack of reserve as HDEL, and a state-cache model of std::unordered_map<std::string, FieldStateLike> with reserve(N), where FieldStateLike has the same layout as Kvrocks' HashFieldState (enum + std::string + uint64_t). Random and colliding field names are the same fixed length (16 bytes), so the comparison controls for key length. Colliding fields are chosen so std::hash % bucket_count collide; for the unreserved set that count is its final count after N insertions. Collision generation occurs outside the measured interval.

What did you expect to see?

Temporary field-processing containers should avoid disproportionate CPU amplification from deliberately colliding field names. Potential mitigations include a keyed string hasher or configurable field-count limits, evaluated against compatibility requirements and normal-workload overhead.

What did you see instead?

The reviewed paths insert raw client-supplied field names into per-command containers using default string hashing:

  • HDEL: std::unordered_set<std::string_view> field_set at redis_hash.cc:970-973. The Hash key must exist, but the supplied fields need not.
  • HSET/HMSET: a separate std::unordered_set<std::string_view> field_set at 1038-1047. It processes pairs in reverse to retain the last value for each field.
  • HSETEX/HGETEX: std::unordered_map<std::string, HashFieldState> state_cache, populated by LoadFieldStates(). The helper calls reserve(fields.size()) before insertion; collision tests must preserve that behavior.

With predictable hashing and bucket behavior in the target build, sufficiently many distinct colliding fields can cause quadratic cumulative container work. Entries do not accumulate across commands.

An isolated container benchmark (libstdc++, g++ 11.4, -O2, median of 3) measures insertion wall time, excluding RESP parsing and RocksDB. Random and colliding field names are the same 16-byte length, and the state-cache model's value type matches HashFieldState's layout:

N HDEL-style set random set colliding ratio State-cache model random model colliding ratio
4000 0.23 ms 14.0 ms 61× 0.27 ms 20.6 ms 78×
8000 0.34 ms 53.7 ms 159× 0.57 ms 87.4 ms 152×
16000 0.76 ms 257.0 ms 338× 0.90 ms 348.2 ms 386×

After insertion, all N colliding fields occupy one bucket; the random baseline peaks at 5-8. As N doubles, the colliding column grows about 4x while random grows about 2x, i.e. quadratic vs linear. At N=16000, insertion wall time is about 0.26 s for the isolated set and 0.35 s for the map model. These are wall-clock measurements of the container in isolation, not CPU-time measurements or timings of a Kvrocks command.

The relevant input limits are 1,048,576 RESP array elements, including the command and key, and 512 MiB per bulk string by default; inline commands are limited to 16 KiB (src/server/redis_request.h:35-36; redis_request.cc:73-85,114-116). No smaller field-count cap appears in the HDEL/HSET/HMSET loops, so N here is far below the protocol ceiling. A namespace-authenticated client can run these commands; admin permission is not required.

Commands execute synchronously on the handling worker, and write commands hold key-derived locks (src/server/redis_connection.cc:463-471,639-680). Collision-related work in those paths could delay the worker and competing writes, but this benchmark does not measure that effect. Real HDEL interleaves a RocksDB lookup with each distinct field insertion; the isolated timings cannot simply be added to a server latency estimate. A keyed hasher designed to resist hash flooding should be evaluated against these inputs and normal workloads; merely randomizing an arbitrary hash's initial seed is not a sufficient security guarantee.

Kvrocks' THREAT_MODEL.md §8.6/§9 disclaims a general anti-DoS guarantee beyond configured limits. This report therefore describes a potential performance-hardening opportunity, not a demonstrated violation of that security contract.

Anything Else?

No response

Are you willing to submit a PR?
  • I'm willing to submit a PR!
Lingua principale
C++
Stelle
4.5k
Fork
686
Merge medio
2g 19h
PR unite (30g)
37

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

  • Include un Dockerfile o un file Docker Compose
  • Nessun modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di apache/kvrocks

Tutte le issue di apache/kvrocks

Issue simili

Altre issue su C++

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.