apache / apache/kvrocks

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

Open
#3,619 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
C++
Stars
4.4k
Forks
658
Avg merge
1d 20h
Merged PRs (30d)
10

Description

### Search before asking

- [x] I had searched in the [issues](https://github.com/apache/kvrocks/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`:

```sh
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` 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 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 field_set` at `1038-1047`. It processes pairs in reverse to retain the last value for each field.
- **HSETEX/HGETEX:** `std::unordered_map 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!

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by tracing the cited command and container paths in src/commands/cmd_hash.cc and src/types/redis_hash.cc, including HDEL, HSET/HMSET, and the field-expiration caches. Run the supplied kvrocks_hash_bench.cpp to reproduce the isolated behavior, then review THREAT_MODEL.md §8.6/§9 and compatibility and normal-workload costs before evaluating mitigations. Done means a mitigation or conclusion is supported by tests and measurements without claiming the isolated benchmark is a server latency result.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, redis
Domain
databases, performance, security
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.