Performance Question: Could EXISTS command benefit from MultiGet optimization?

[cyningsun]

Search before asking

• I had searched in the issues and found no similar issues.

Motivation

Summary

Hi! 👋 While exploring the codebase, I noticed the EXISTS command uses sequential Get operations, while other multi-key commands like MGET and MDEL use MultiGet. I'm wondering if this is intentional or if there might be a performance optimization opportunity here.

Current Implementation

Currently, Database::existsInternal() uses a sequential approach:

rocksdb::Status Database::existsInternal(engine::Context &ctx, const std::vector<std::string> &keys, int *ret) {
  *ret = 0;
  rocksdb::Status s;
  std::string value;
  for (const auto &key : keys) {  // Sequential Get operations
    s = storage_->Get(ctx, ctx.GetReadOptions(), metadata_cf_handle_, key, &value);
    if (!s.ok() && !s.IsNotFound()) return s;
    if (s.ok()) {
      Metadata metadata(kRedisNone, false);
      s = metadata.Decode(value);
      if (!s.ok()) return s;
      if (!metadata.Expired()) *ret += 1;
    }
  }
  return rocksdb::Status::OK();
}

What I observed

Other multi-key commands use MultiGet:

• MDEL and MGET both use storage_->MultiGet() for batch operations
• EXISTS uses a loop with individual Get calls

Questions

I'm curious about:

1. Is there a specific reason EXISTS uses sequential Get instead of MultiGet?
2. Would a MultiGet-based performance optimization be welcome?

Potential benefits

A MultiGet-based implementation could potentially provide:

• Better performance through batch operations (fewer RocksDB calls)
• Consistency with other multi-key commands (MGET, MDEL, etc.)

Code location

src/storage/redis_db.cc - Database::existsInternal() (lines 624-639)

Solution

No response

Are you willing to submit a PR?

• I'm willing to submit a PR!

[PragmaTwice]

Feel free to make a benchmark and post the result here : )

[mapleFU]

Besides, I found a MayExists for this, but I don't know would it making faster

[git-hulk]

Besides, I found a MayExists for this, but I don't know would it making faster

MayExist should only read from the block cache tier if my memory serves.

[cyningsun]

@PragmaTwice Thanks for the suggestion! I'm will run the benchmarks and post the results here once they are complete. I configured the test environment based on the following:

Host Info

• Intel(R) Xeon(R) Silver 4116 CPU @ 2.10GHz*2
• SAS SSD, 4*960G, RAID 5

DB initialization

KEYSPACE_SIZE=100000000       #  (100 Million keys)
TEST_DATA_SIZE=50000000       #  (50 Million existing keys - implying a 50% data density)
VALUE_SIZE=128              # 128 bytes

    for ((i=0; i<batches; i++)); do
        local start_key=$((i * batch_size + 1))
        local end_key=$(((i + 1) * batch_size))
        if [ $end_key -gt $TEST_DATA_SIZE ]; then
            end_key=$TEST_DATA_SIZE
        fi

        printf "\r[INFO] load batch %d/%d (key %d-%d)..." $((i+1)) $batches $start_key $end_key

        $MEMTIER -s $HOST -p $PORT -P redis -c 8 -t 2 -n $((batch_size / 16)) \
            --ratio=1:0 --key-pattern=R:R --key-minimum=$start_key --key-maximum=$end_key \
            --data-size=$VALUE_SIZE --random-data --randomize --distinct-client-seed --hide-histogram > /dev/null 2>&1
    done

Total sst file size is 3.7G

1st Round test matrix is:

- Single Key EXISTS (0% hit, 50% hit, 100% hit)
- 10 Keys EXISTS (0% hit, 50% hit, 100% hit)

Let me know if my understanding and plan align with your expectations. I'll post a summary once all the data is collected and analyzed. Appreciate your patience!

[cyningsun]

1st Round(Memory/Disk Ratio, 2:3.7)

Client Side

Test matrix

• Single Key EXISTS (0% hit, 50% hit, 100% hit)
• 10 Keys EXISTS (0% hit, 50% hit, 100% hit)

Test Commands

TEST_REQUESTS=1000000 # 1 million requests
TEST_ROUNDS=3 # 3 round test

run_disk_test() {
    local test_name="$1"
    local test_command="$2"
    for ((round=1; round<=TEST_ROUNDS; round++)); do
        print_info "Execute $round/$TEST_ROUNDS round test..."

        local test_output=$(eval $test_command 2>&1)
        local exit_code=$?

        if [ $exit_code -ne 0 ]; then
            print_warning " $round round test fail"
            continue
        fi
        if [ $round -lt $TEST_ROUNDS ]; then
            print_info "Cooling for 10 seconds..."
            sleep 10
        fi
    done
}

main() {
    # Common parameters
    local base_cmd="$MEMTIER -s $HOST -p $PORT -P redis -c 8 -t 2 -n $((TEST_REQUESTS / 16)) --randomize --distinct-client-seed --hide-histogram"

    # Single Key
    run_disk_test "Single Key EXISTS (random)" \
        "$base_cmd --command=\"EXISTS __key__\" --command-key-pattern=R --key-minimum=1 --key-maximum=$KEYSPACE_SIZE"

    run_disk_test "Single Key EXISTS (100% hit)" \
        "$base_cmd --command=\"EXISTS __key__\" --command-key-pattern=R --key-minimum=1 --key-maximum=$TEST_DATA_SIZE"

    # 10 Keys
    run_disk_test "10 Keys EXISTS (random)" \
        "$base_cmd --command=\"EXISTS __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__\" --command-key-pattern=R --key-minimum=1 --key-maximum=$KEYSPACE_SIZE"

    run_disk_test "10 Keys EXISTS (100% hit)" \
        "$base_cmd --command=\"EXISTS __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__\" --command-key-pattern=R --key-minimum=1 --key-maximum=$TEST_DATA_SIZE"

    run_disk_test "10 Keys EXISTS (0% hit)" \
        "$base_cmd --command=\"EXISTS __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__ __key__\" --command-key-pattern=R --key-minimum=$((TEST_DATA_SIZE + 1)) --key-maximum=$KEYSPACE_SIZE"
}

main "$@"

Kvrocks

core configurations

rocksdb.block_cache_size 1024

Other parameters are default values, such as workers: 8

Use systemd to isolate service

systemd-run --scope --property=CPUQuota=600% --property=MemoryMax=2G ./kvrocks-baseline -c ../kvrocks.conf

Performance results with sample statistics

Note: 9 rounds of testing were conducted for each scenario, and samples with deviations exceeding 20% were excluded from the result analysis

Test Scenario	Version	OPS (Mean±Std)	Latency (Mean±Std)	Samples (Used/Total)	Improvement
Single Key EXISTS (Random)	MultiGet	60,206 ± 5,919	0.2917 ± 0.0207 ms	8/9 (88.9%)	-3.41%
	Baseline	62,330 ± 8,897	0.2920 ± 0.0554 ms	9/9 (100.0%)
Single Key EXISTS (100% Hit)	MultiGet	40,429 ± 3,708	0.4143 ± 0.0550 ms	7/9 (77.8%)	+2.90%
	Baseline	39,290 ± 3,862	0.4367 ± 0.0323 ms	8/9 (88.9%)
Single Key EXISTS (0% Hit)	MultiGet	117,286 ± 7,345	0.1455 ± 0.0048 ms	9/9 (100.0%)	+3.89%
	Baseline	112,892 ± 9,175	0.1449 ± 0.0037 ms	9/9 (100.0%)
10-Key EXISTS (Random)	MultiGet	10,402 ± 1,367	1.6445 ± 0.2453 ms	8/9 (88.9%)	+15.12%
	Baseline	9,035 ± 1,235	1.7791 ± 0.2845 ms	5/9 (55.6%)
10-Key EXISTS (100% Hit)	MultiGet	5,040 ± 447	3.1481 ± 0.3318 ms	6/9 (66.7%)	+15.30%
	Baseline	4,371 ± 268	3.6938 ± 0.3087 ms	5/9 (55.6%)
10-Key EXISTS (0% Hit)	MultiGet	80,642 ± 7,411	0.2256 ± 0.0282 ms	9/9 (100.0%)	+1.70%
	Baseline	79,297 ± 5,613	0.2250 ± 0.0131 ms	9/9 (100.0%)

In Single KEY scenario, MultiGet is equal to or slightly lower than the sequential Get version; MultiGet is significantly better than sequential Get versions in Multi Key scenarios

[mapleFU]

What's your benchmark environment? On what kind of cpu and ssd disk?

[cyningsun]

@mapleFU Use systemd to isolate service

systemd-run --scope --property=CPUQuota=600% --property=MemoryMax=2G ./kvrocks-baseline -c ../kvrocks.conf

Host info

• Intel(R) Xeon(R) Silver 4116 CPU @ 2.10GHz*2
• SAS SSD, 4*960G, RAID 5

[cyningsun]

2st Round(Memory/Disk Ratio, 6:3.7)

Client Side

• Single Key EXISTS (0% hit, 50% hit, 100% hit)
• 2 Keys EXISTS (0% hit, 50% hit, 100% hit)
• 3 Keys EXISTS (0% hit, 50% hit, 100% hit)
• 5 Keys EXISTS (0% hit, 50% hit, 100% hit)
• 10 Keys EXISTS (0% hit, 50% hit, 100% hit)

more scenarios with different keys are added to confirm the impact of the number of keys

Kvrocks

core configurations

rocksdb.block_cache_size 2024

systemd-run --scope --property=CPUQuota=600% --property=MemoryMax=6G ./kvrocks-baseline -c ../kvrocks.conf

memory& block cache is increased to verify full memory hit scenarios

Performance results

KEY Number	Test Scenario	Optimized	Baseline	Improvement	Samples
1-Key	0% Hit	108,471±10,094	115,225±9,159	-5.86%	9/9
	Random	99,408±5,312	102,604±7,129	-3.12%	9/9
	100% Hit	85,996±10,000	98,568±6,305	-12.75%	9/8
2-Key	0% Hit	102,198±8,977	109,244±4,600	-6.45%	9/9
	Random	83,008±9,668	92,535±6,864	-10.30%	9/9
	100% Hit	61,147±6,925	77,361±7,678	-20.96%	9/9
3-Key	0% Hit	104,107±7,213	103,640±8,009	+0.45%	9/9
	Random	64,250±5,672	80,313±7,174	-20.00%	7/8
	100% Hit	53,666±4,641	52,662±5,887	+1.91%	8/6
5-Key	0% Hit	98,686±5,088	96,161±5,003	+2.63%	9/8
	Random	51,699±4,220	67,390±7,113	-23.28%	8/7
	100% Hit	32,736±2,989	37,946±4,992	-13.73%	6/5
10-Key	0% Hit	75,275±8,696	74,361±7,120	+1.23%	9/9
	Random	31,080±1,732	36,520±4,033	-14.90%	7/8
	100% Hit	17,570±1,947	27,273±3,436	-35.58%	7/7

[cyningsun]

After the second round of testing, it was found that the server CPU was not fully utilized (the number of client connections was too low; the number of server workers was too small), and there were differences in QPS between each round, possibly due to uneven thread connections. Therefore, increase both parameters to the following, and repeat two rounds of pressure measurement data as follows. But the results are not much different from the first two rounds

Client

    local base_cmd="$MEMTIER -s $HOST -p $PORT -P redis -c 32 -t 4 -n $((TEST_REQUESTS / 16)) --randomize --distinct-client-seed --hide-histogram"

Note:
The number of client connections is increased to avoid uneven connections between kvrocks threads
1st/2nd Round: 8*2
Now: 32*4

Kvrocks

workers: 36

Note:
workers is increased to make the CPU fully loaded

3st Round(Memory/Disk Ratio, 2:3.7)

Test Scenario	Baseline (ops/sec)	Optimized (ops/sec)	Improvement
Single Key 0% hit	136,648	128,987	-5.61%
Single Key random	100,574	96,022	-4.53%
Single Key 100% Hit	78,562	79,420	+1.09%
2 Keys 0% hit	119,949	116,567	-2.82%
2 Keys random	70,851	76,876	+8.50%
2 Keys 100% Hit	47,415	59,806	+26.13%
3 Keys 0% hit	104,871	102,866	-1.91%
3 Keys random	56,258	64,206	+14.13%
3 Keys 100% Hit	36,380	51,678	+42.05%
5 Keys 0% hit	84,997	89,525	+5.33%
5 Keys random	37,097	50,382	+35.81%
5 Keys 100% Hit	22,784	36,795	+61.50%
10 Keys 0% hit	52,976	66,352	+25.25%
10 Keys random	21,500	32,056	+49.09%
10 Keys 100% Hit	11,901	21,633	+81.78%

4st Round Performance results (Memory/Disk Ratio, 6:3.7)

Test Scenario	Baseline (ops/sec)	Optimized (ops/sec)	Improvement
Single Key 0% hit	236,030	214,487	-9.13%
Single Key random	209,624	203,763	-2.80%
Single Key 100% Hit	197,707	175,252	-11.36%
2 Keys 0% hit	217,805	201,392	-7.54%
2 Keys random	184,263	153,708	-16.58%
2 Keys 100% Hit	143,926	134,788	-6.35%
3 Keys 0% hit	195,673	189,907	-2.95%
3 Keys random	145,087	131,117	-9.63%
3 Keys 100% Hit	117,732	104,677	-11.09%
5 Keys 0% hit	169,918	170,719	+0.47%
5 Keys random	113,350	98,228	-13.34%
5 Keys 100% Hit	80,902	76,194	-5.82%
10 Keys 0% hit	117,294	125,547	+7.04%
10 Keys random	65,890	63,913	-3.00%
10 Keys 100% Hit	46,398	45,219	-2.54%

[cyningsun]

Based on the test results, I searched source codes of PIKA and Tendis, and found neither of them used MultiGet API.

And given that Cluster mode doesn't support cross-slot access and has a large number of slots (16384), the number of keys in a single command is inherently limited. In this context, using MultiGet as a direct replacement for Get might indeed not be the most optimal choice. Anyone has better suggestions on how to approach such case?