8000 ZRANDMEMBER and HRANDFIELD perform O(N) work for small random samples · Issue #839 · kividbio/kividb · GitHub
[go: up one dir, main page]

Skip to content

ZRANDMEMBER and HRANDFIELD perform O(N) work for small random samples #839

Closed

Description

@Parikalp-Bhardwaj

Summary

ZRANDMEMBER collects all sorted-set members into a Vec before picking a random member, even when requesting just one.

HRANDFIELD with a count also builds full-length field and index vectors before sampling.

Both perform unnecessary O(N) work for small random samples.

Benchmark

Tested on macOS (Apple M3 Pro), KiviDB master af664901 (release) against Redis 8.10.3.

Dataset: 1 million sorted-set members and 1 million hash fields. One client, 1,000 requests, persistence disabled.

Command KiviDB avg Redis avg Slowdown
ZRANDMEMBER z 2.422 ms 0.089 ms 27.2x
ZRANDMEMBER z 5 2.493 ms 0.086 ms 29.0x
HRANDFIELD h 0.096 ms 0.058 ms 1.7x
HRANDFIELD h 5 0.367 ms 0.057 ms 6.4x

These are single-run measurements.

Root cause

ZRANDMEMBER — src/commands/zset.rs

let entries: Vec<(&ZMember, f64)> =
    inner.members.iter().map(|(k, &v)| (k, v)).collect();

HRANDFIELD — src/commands/hash.rs

let fields: Vec<(&String, &Arc<[u8]>)> = inner.iter().collect();
let mut indices: Vec<usize> = (0..len).collect();

These allocations happen while holding collection read locks.

Expected behavior

Small random samples should avoid traversing and allocating storage for the entire collection.

Possible improvements:

  • HRANDFIELD: Use IndexMap::get_index() and sample distinct indices directly.
  • ZRANDMEMBER: Investigate efficient random sampling from the underlying member storage, without significantly increasing memory or slowing writes.

The goal is to reduce small-sample overhead while preserving uniform sampling and Redis-compatible behavior.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      0