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

[K-ANOY]

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!