iframe-proxy

Vectorshine · 2024-04-18T13:01:49Z

Implements the SIEVE cache eviction policy in the cache framework (CacheBase), available alongside the existing LRU and SLRU policies.

SIEVE is a simple, scan-resistant eviction algorithm: a single "hand" walks a FIFO queue of entries and evicts the first entry whose visited flag is clear, clearing the flag as it passes set entries. See the paper for details: https://junchengyang.com/publication/nsdi24-SIEVE.pdf

This continues the original work by @Vectorshine, brought up to date with master:

Reworked SIEVECachePolicy to match the current ICachePolicy interface (CurrentMetrics tracking, maxCount, contains, per-entry OnRemoveEntryFunction), mirroring LRUCachePolicy.
Fixed a bug in remove where the stored queue iterator was advanced in place and the wrong node was erased.
Added unit tests in gtest_sieve_cache.cpp, including a step-by-step test of the eviction logic.
Randomized the mark and uncompressed cache policy across LRU, SLRU and SIEVE in stateless functional tests (ci/jobs/functional_tests.py) and the stress test (tests/docker_scripts/stress_runner.sh). SIEVE is only implemented for the CacheBase-backed caches, so the filesystem cache (backed by FileCachePolicy) is not randomized to it, and it is excluded during bugfix validation, which runs downloaded master-side binaries.

Closes: #58910

Changelog category (leave one):

New Feature

Changelog entry (a user-readable short description of the changes that goes into CHANGELOG.md):

Added a new cache eviction policy SIEVE. It can be selected for the in-memory caches backed by CacheBase, such as the mark cache and the uncompressed cache, via the corresponding *_cache_policy server settings (for example, mark_cache_policy and uncompressed_cache_policy). It is not available for the filesystem cache.

Documentation entry for user-facing changes

Documentation is written (mandatory for new features)

CLAassistant · 2024-04-18T13:01:55Z

clickhouse-ci · 2024-04-18T13:02:22Z

This is an automatic comment. The PR descriptions does not match the template.

Please, edit it accordingly.

The error is: More than one changelog category specified: 'Improvement', 'Performance Improvement'

clickhouse-ci · 2024-04-18T13:02:25Z

This is an automatic comment. The PR descriptions does not match the template.

Please, edit it accordingly.

The error is: More than one changelog category specified: 'Improvement', 'Performance Improvement'

robot-ch-test-poll · 2024-04-18T13:35:41Z

This is an automated comment for commit 21fce56 with description of existing statuses. It's updated for the latest CI running

✅ Click here to open a full report in a separate page

Successful checks

Check name	Description	Status
Docs check	Builds and tests the documentation	✅ success
Fast test	Normally this is the first check that is ran for a PR. It builds ClickHouse and runs most of stateless functional tests, omitting some. If it fails, further checks are not started until it is fixed. Look at the report to see which tests fail, then reproduce the failure locally as described here	✅ success
Flaky tests	Checks if new added or modified tests are flaky by running them repeatedly, in parallel, with more randomization. Functional tests are run 100 times with address sanitizer, and additional randomization of thread scheduling. Integration tests are run up to 10 times. If at least once a new test has failed, or was too long, this check will be red. We don't allow flaky tests, read the doc	✅ success
Integration tests	The integration tests report. In parenthesis the package type is given, and in square brackets are the optional part/total tests	✅ success
Stateful tests	Runs stateful functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Stateless tests	Runs stateless functional tests for ClickHouse binaries built in various configurations -- release, debug, with sanitizers, etc	✅ success
Style check	Runs a set of checks to keep the code style clean. If some of tests failed, see the related log from the report	✅ success
Unit tests	Runs the unit tests for different release types	✅ success

alexey-milovidov · 2024-04-20T21:14:43Z

Let's add the cache policy to randomization in our functional tests.

kssenii

You can add randomization of cache policies in CI similar to

ClickHouse/docker/test/stress/run.sh

Lines 73 to 88 in 38a0edd

    
           # Randomize cache policies. 
        
           cache_policy="" 
        
           if [ $((RANDOM % 2)) -eq 1 ]; then 
        
               cache_policy="SLRU" 
        
           else 
        
               cache_policy="LRU" 
        
           fi 
        
           echo "Using cache policy: $cache_policy" 
        
           if [ "$cache_policy" = "SLRU" ]; then 
        
               sudo cat /etc/clickhouse-server/config.d/storage_conf.xml \ 
        
               | sed "s|<cache_policy>LRU</cache_policy>|<cache_policy>SLRU</cache_policy>|" \ 
        
               > /etc/clickhouse-server/config.d/storage_conf.xml.tmp 
        
               mv /etc/clickhouse-server/config.d/storage_conf.xml.tmp /etc/clickhouse-server/config.d/storage_conf.xml 
        
           fi

but instead of cache_policy setting in storage_conf.xml you should change the mark_cache_policy in another server config. We do not yet have it explicitly enabled in CI, so you'll also need to add a file with this setting to ClickHouse/tests/configs/config.d/. Also do not forget to add an according file installation into ClickHouse/tests/config/install.sh

Vectorshine · 2024-06-18T13:24:27Z

reopen

alexey-milovidov · 2024-06-18T14:10:33Z

@Vectorshine, what happened?

rschu1ze · 2024-06-18T15:46:00Z

@Vectorshine Thanks for checking. There is no need to close and re-open this PR over and over 😄 I just started CI to see how the tests respond.

clickhouse-gh · 2025-11-18T13:21:09Z

Dear @antonio2368, this PR hasn't been updated for a while. You will be unassigned. Will you continue working on it? If so, please feel free to reassign yourself.

clickhouse-gh · 2026-06-01T15:33:43Z

Dear @antonio2368, you haven't been active on this PR for 30 days. You will be unassigned. Will you continue working on it? If so, please feel free to reassign yourself.

# Conflicts: # src/Common/CacheBase.h # tests/config/install.sh # tests/docker_scripts/stateless_runner.sh # tests/docker_scripts/stress_runner.sh

Mark the `assertQueue` test helper as `static` so it does not trigger `-Werror,-Wmissing-prototypes`, and take `expected_keys` by const reference. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

clickhouse-gh · 2026-06-16T03:13:54Z

Workflow [PR], commit [5f8cf6a]

Summary: ✅

Performance Comparison: Performance dashboard

AI Review

Summary

This PR adds SIEVE as an optional eviction policy for CacheBase-backed caches, documents the newly accepted setting value across those server settings, and exercises the policy in unit tests plus functional/stress cache-policy randomization. I did not find any unresolved correctness issues in the current merged tree; the prior bot findings about filesystem-cache randomization, filesystem-cache documentation, broader setting documentation, and update-time tail protection are addressed in the current code.

Missing context / blind spots

⚠️ The local checkout contains the synthetic merge commit 7eb79838f35887c9144784d523077a52c3329b20, while GitHub reports PR head 5f8cf6a6c0da71c706141d7fa5e7e9e76ac3588a; fetching the PR ref was blocked by a read-only .git/FETCH_HEAD. I reviewed the merged tree and the GitHub PR diff, and would use the reported head SHA for any inline comments.

Final Verdict

Status: ✅ Approve

List the supported cache eviction policies (`LRU`, `SLRU`, `SIEVE`) in the descriptions of the `uncompressed_cache_policy`, `mark_cache_policy`, `index_uncompressed_cache_policy` and `index_mark_cache_policy` server settings, and in the documentation of the filesystem cache `cache_policy` setting. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

The cache-policy randomization joined two `s|...|...|` substitutions into a single `sed` expression with `;`, but dropped the closing `|` of the first substitution, producing `sed: -e expression ClickHouse#1, char 94: unknown option to 's'` whenever a non-default policy (`LRU` or `SIEVE`) was selected for the mark and uncompressed caches. Split them into two `-e` expressions in both `ci/jobs/functional_tests.py` and `tests/docker_scripts/stress_runner.sh`. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

The `CacheBase` constructor ran `LOG_TRACE(getLogger("CacheBase"), ...)`. Some caches are function-local `static` objects, so the constructor runs during their lazy initialization; logging from there can re-enter the same initialization, and with `send_logs_level=trace` `clickhouse-local` aborted with `libc++abi: __cxa_guard_acquire detected recursive initialization`, hanging the process. This caused `04240_80087_clickhouse_local_logs_on_exception` to time out in the Fast test. Drop the log line (and the now-unused `logger_useful.h` include); `master` never logged the cache policy here. Reproduced and verified locally: before, `clickhouse local --send_logs_level=trace -q "SELECT * FROM nonexistent_table"` hung; after, it prints the buffered logs and the exception and exits. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

The filesystem cache (`storage_conf*.xml` `cache_policy`) is backed by `FileCachePolicy`, which only supports `LRU` and `SLRU` (and their overcommit variants) — not `SIEVE`. Setting it to `SIEVE` made the server fail to start with `Code: 36 ... Unexpected value of FileCachePolicy: 'SIEVE' (BAD_ARGUMENTS)`, which surfaced as a `Start ClickHouse Server` failure in Bugfix validation. `SIEVE` is only implemented for the `CacheBase`-backed caches (mark and uncompressed caches in `cache_policy.xml`). Randomize the filesystem cache policy only across `LRU`/`SLRU`, using a separate variable from the mark and uncompressed cache policy (which keeps `LRU`/`SLRU`/`SIEVE`), in both `ci/jobs/functional_tests.py` and `tests/docker_scripts/stress_runner.sh`. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

…ix validation The install-time cache-policy randomization rewrote every `<cache_policy>LRU</cache_policy>` in `storage_conf*.xml` to the randomly chosen filesystem cache policy. This broke filesystem-cache tests that pin a specific policy: `02944_dynamically_change_filesystem_cache_size` (which has a dedicated `s3_cache_02944_lru` disk and tests both `LRU` and `SLRU` behaviour) and `03032_dynamically_resize_filesystem_cache_2` (which assumes `LRU` eviction sizes). Both fail with "result differs with reference" only on this PR and never on master. `SIEVE` is only implemented for the `CacheBase`-backed caches (mark, uncompressed and the index/page/query-condition caches in `cache_policy.xml`), not for the filesystem cache (`storage_conf*.xml`, backed by `FileCachePolicy`). Randomizing the filesystem cache policy therefore exercises nothing related to this feature while breaking the tests above. Stop randomizing the filesystem cache policy entirely and randomize only the mark and uncompressed cache policy across `LRU`/`SLRU`/`SIEVE`. In addition, during bugfix validation the install configs are used with downloaded master-side binaries that do not contain the `SIEVE` branch in `CacheBase`, so writing `<mark_cache_policy>SIEVE</mark_cache_policy>` would make the server fail to start before the validation test runs. Exclude `SIEVE` from the randomization when running bugfix validation. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

Adding `SIEVE` to the shared `CacheBase` constructor makes it accepted by every `CacheBase`-backed server setting, but only `mark_cache_policy`, `uncompressed_cache_policy`, `index_mark_cache_policy` and `index_uncompressed_cache_policy` listed the new value. The remaining `CacheBase`-backed policy settings (`unique_key_index_cache_policy`, `primary_index_cache_policy`, `iceberg_metadata_files_cache_policy`, `parquet_metadata_cache_policy`, `vector_similarity_index_cache_policy`, `text_index_tokens_cache_policy`, `text_index_header_cache_policy`, `text_index_postings_cache_policy`, `page_cache_policy` and `query_condition_cache_policy`) now also accept `SIEVE` but did not document it; `unique_key_index_cache_policy` even stated "(SLRU or LRU)". Update their descriptions to list the actual accepted values `LRU`, `SLRU`, `SIEVE`. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

`system.filesystem_cache_settings.cache_policy` describes the filesystem cache, which is backed by `FileCachePolicy`/`FileCache` and accepts only `LRU`/`SLRU` (and their overcommit variants), not `SIEVE`. Listing `SIEVE` here documented a value the server rejects, so revert the row to its previous wording. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

alexey-milovidov · 2026-06-18T17:49:25Z

Pushed fixes for the CI failures and the AI-review "Request changes" items (commits e95c2e15f3a, adabbfcdfeb, d5bb4f89a39, on top of a merge with master):

CI failures (02944_dynamically_change_filesystem_cache_size, 03032_dynamically_resize_filesystem_cache_2) — root cause: the install-time randomization rewrote every <cache_policy>LRU</cache_policy> in storage_conf*.xml to the randomly chosen filesystem cache policy. This broke tests that pin a specific filesystem cache policy (02944 has a dedicated s3_cache_02944_lru disk and tests both LRU and SLRU; 03032 assumes LRU eviction sizes). Both fail only on this PR and never on master (0 failures in 90 days). Since SIEVE is not implemented for the filesystem cache (FileCachePolicy) anyway, the filesystem cache policy is no longer randomized; only the mark and uncompressed cache policy is randomized across LRU/SLRU/SIEVE.

Bugfix validation — SIEVE is now excluded from the randomization when running bugfix validation, which uses downloaded master-side binaries that do not contain the SIEVE branch in CacheBase (writing <mark_cache_policy>SIEVE</mark_cache_policy> there made the server fail to start).

Documentation surface — SIEVE is now documented on all CacheBase-backed policy settings in ServerSettings.cpp (it is accepted by every CacheBase-backed cache, not only the four that were previously updated), and removed from the filesystem cache row in system.filesystem_cache_settings. The changelog entry no longer claims filesystem-cache support.

Earlier review threads — the algorithm correctness and the requested step-by-step eviction test are addressed by the reworked removeOverflow and SIEVECache.ComplexEvictTest, which passes under ASan/UBSan, MSan and TSan.

# Conflicts: # src/Core/ServerSettings.cpp

In `SIEVECachePolicy::set`, `removeOverflow` was always called with `ignore_last_element = true`, but `set` reaches this call for updates as well as insertions. The `ignore_last_element` flag protects the just-inserted tail entry from immediate eviction by rewinding the hand to `queue.begin`. On an update no new tail is appended, so passing `true` makes the policy skip whatever entry the hand currently points at (even an unrelated tail) and grant it the new-entry exemption, deviating from the canonical `SIEVE` algorithm. For example, with queue `{1, 3, 5, 7, 11}` and the hand at the tail `11`, an update of key `1` that overflows the cache evicted key `3`, while the canonical `SIEVE` hand inspects and evicts key `11` first. Pass `inserted` instead, so the tail is protected only when a new entry was actually appended. Add a unit test reproducing the scenario. Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>

alexey-milovidov · 2026-06-22T16:37:08Z

Merged master (resolving a conflict in ServerSettings.cpp: kept the new unique_key_bitmap_cache_* settings from master and, since DeleteBitmapCache is CacheBase-backed, documented SIEVE as a possible value for unique_key_bitmap_cache_policy to match the other cache-policy settings).

Addressed the open review finding on SIEVECachePolicy::set (4e41fa6ba27): removeOverflow was always called with ignore_last_element = true, but set also handles updates. On an update no new tail is appended, so the flag wrongly protected the entry the hand pointed at (an unrelated tail) and rewound the hand to queue.begin. It now passes inserted, so the new-entry exemption applies only on a real insertion. Added a unit test SIEVECache.UpdateDoesNotProtectUnrelatedTail reproducing the reported scenario.

The only red on the previous run was AST fuzzer (amd_debug, targeted) with Logical error: ... query tree node does not have valid source node after running ... pass. This is a pre-existing, master-wide analyzer/AST-fuzzer flake unrelated to the cache policy — it has hit 20+ unrelated PRs over the last 45 days (e.g. #98798 repeatedly, #107807, #106025, #104125, #88043, #108025). CI has been re-triggered on the new commit.

# Conflicts: # src/Core/ServerSettings.cpp

clickhouse-gh · 2026-06-27T18:46:44Z

LLVM Coverage Report

Full report

nikitamikhaylov added the can be tested Allows running workflows for external contributors label Apr 18, 2024

robot-ch-test-poll added the pr-improvement Pull request with some product improvements label Apr 18, 2024

kssenii self-assigned this Apr 18, 2024

kssenii reviewed Apr 18, 2024

View reviewed changes

Comment thread src/Common/SIEVECachePolicy.h Outdated

kssenii reviewed Apr 24, 2024

View reviewed changes

rschu1ze reviewed Apr 26, 2024

View reviewed changes

Comment thread src/Common/CacheBase.h Outdated

Comment thread src/Common/SIEVECachePolicy.h Outdated

Comment thread src/Common/SIEVECachePolicy.h Outdated

rschu1ze changed the title ~~Implemented SIEVE algorithm in cache framework (Issue #58910)~~ Implemented SIEVE eviction in cache framework Apr 26, 2024

Vectorshine closed this Jun 18, 2024

Vectorshine force-pushed the master branch from 393af65 to 22f6095 Compare June 18, 2024 12:50

Vectorshine reopened this Jun 18, 2024

robot-clickhouse added the submodule changed At least one submodule changed in this PR. label Jun 18, 2024

clickhouse-ci Bot added the manual approve Manual approve required to run CI label Jun 18, 2024

Vectorshine closed this Jun 18, 2024

Vectorshine reopened this Jun 18, 2024

Vectorshine closed this Jun 18, 2024

Vectorshine reopened this Jun 18, 2024

Vectorshine closed this Jun 18, 2024

Vectorshine force-pushed the master branch from 84997ca to 87b91c6 Compare June 18, 2024 14:00

reopen

9bf9a6a

Vectorshine reopened this Jun 18, 2024

robot-ch-test-poll3 removed the submodule changed At least one submodule changed in this PR. label Jun 18, 2024

Merge branch 'ClickHouse:master' into master

c6fafeb

clickhouse-gh Bot unassigned kssenii Mar 4, 2025

antonio2368 self-assigned this Oct 13, 2025

clickhouse-gh Bot unassigned antonio2368 Jun 1, 2026

alexey-milovidov and others added 2 commits June 16, 2026 00:59

Merge remote-tracking branch 'origin/master' into sieve-pr-62756

41995be

# Conflicts: # src/Common/CacheBase.h # tests/config/install.sh # tests/docker_scripts/stateless_runner.sh # tests/docker_scripts/stress_runner.sh

Fix -Wmissing-prototypes for assertQueue in SIEVE cache test

971fc70

Mark the `assertQueue` test helper as `static` so it does not trigger `-Werror,-Wmissing-prototypes`, and take `expected_keys` by const reference. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

clickhouse-gh Bot added pr-feature Pull request with new product feature and removed pr-improvement Pull request with some product improvements labels Jun 16, 2026