Repository navigation
SCAN-family commands traverse entire collections for each scan page #624
Description
Summary
KiviDB's HSCAN, SSCAN, ZSCAN, and keyspace SCAN use the common scan_page() helper. To produce a page, the caller iterates over collection entries and scan_page() collects entries at or after the cursor into a temporary vector, then selects a page boundary.
Consequently, a small requested COUNT does not bound the work for one scan request: the traversal is O(N) in the collection size, and the temp
8000
orary vector can require O(N) memory. A minimum page size (len / pages) limits the number of such scans needed to complete an iteration, but can also produce large replies for small COUNT values.
This appears to be a deliberate implementation trade-off rather than a correctness bug. The request is to explore a more incremental scan design that avoids repeatedly traversing whole large collections.
Measured results
| Metric | 100K hash fields | 1M hash fields |
|---|---|---|
| Average latency | 0.633 ms | 7.714 ms |
| p50 latency | 0.639 ms | 7.375 ms |
| p99 latency | 0.911 ms | 11.375 ms |
| Maximum latency | 1.335 ms | 13.855 ms |
| Throughput | 1,536.10 requests/s | 127.99 requests/s |
Increasing the collection size by 10× increased mean request latency by about 12.2×.
With one million fields, changing COUNT had limited effect on throughput until the larger reply at COUNT 10000:
| COUNT | Throughput |
|---|---|
| 10 | 143.37 requests/s |
| 100 | 153.61 requests/s |
| 1,000 | 153.26 requests/s |
| 10,000 | 110.19 requests/s |
These results were measured for HSCAN. The other SCAN-family paths share the helper, but their latencies have not been separately benchmarked here.
Code path
In src/commands/helpers.rs, lines 1218–1252:
let want = count.max(len / pages.max(1)).max(1);
let mut ahead: Vec<(u64, T)> = elements
.filter(|(position, _)| *position >= cursor)
.collect();
// ...
ahead.select_nth_unstable_by_key(want, |(position, _)| *position);Call sites:
HSCAN,src/commands/hash.rsSSCAN,src/commands/sets.rsZSCAN,src/commands/zset.rsSCAN,src/commands/generics.rs
For a one-million-field hash and pages = 1024, len / pages is 976, so COUNT 10 requests a page of at least 976 entries internally. COUNT is a hint in Redis too; the concern here is the full traversal and proportional temporary allocation, not exceeding an exact reply-size limit.
Impact
- Individual scan requests over large collections can take several milliseconds despite a small
COUNThint. - Repeated pagination revisits large portions of the collection and creates substantial cumulative work.
- Each request may allocate a temporary vector proportional to the number of eligible entries.
- Under concurrent access, long scans may increase contention for the collection or shard locks. This effect has not yet been directly measured in this reproduction.
Possible directions
A bucket-oriented cursor or another incremental traversal mechanism could reduce per-request work, but the implementation must preserve scan iteration guarantees through table growth, shrinkage, deletion, and compaction. Different collection backends may require different approaches; an incremental prototype for one command might be safer than changing the shared helper all at once.
Would maintainers be open to exploring a bounded-work cursor implementation, perhaps starting with HSCAN or SSCAN?
Activity