Implement slots tracker for ASM - [MOD-12167]#7200
Conversation
…lly_available_overlap` plan
Codecov Report❌ Patch coverage is Additional details and impacted files@@ Coverage Diff @@
## master #7200 +/- ##
==========================================
- Coverage 85.49% 85.15% -0.35%
==========================================
Files 334 343 +9
Lines 51550 52674 +1124
Branches 11507 13601 +2094
==========================================
+ Hits 44071 44852 +781
- Misses 7300 7629 +329
- Partials 179 193 +14
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
| static void slots_tracker_set_local_slots(const RedisModuleSlotRangeArray *ranges) { | ||
| uint32_t version_before = atomic_load_explicit(&key_space_version, memory_order_relaxed); | ||
| uint32_t version_after = slots_tracker_set_local_slots_internal(ranges); | ||
| if (version_after != version_before) { | ||
| atomic_store_explicit(&key_space_version, version_after, memory_order_relaxed); | ||
| } | ||
| } |
There was a problem hiding this comment.
I assume this means you can't define this function in the Rust FFI layer?
There was a problem hiding this comment.
The goal is to avoid FFI overhead in the query execution path, which only requires reading the atomic variable.
With this trick, we can leave the atomic variable on the C side, giving very low overhead (everything is done with relaxed memory order), while still guarantee its maintenance by the FFI library (using static definition in the H file).
Any attempt to maintain the atomic variable from the FFI will give some overhead. This should be simplified once the pipeline execution is moved to Rust.
Alternativly, we could pass a pointer to the atomic variable to the FFI, and only have overhead when updating it (which is fine, as it's not the hot path). But it's an additional unsafety and will also require the caller to pass the right atomic variable, while with this solution the caller soen't have to explicitly know what's the right variable
There was a problem hiding this comment.
Okay, how many places in the code is expected to call this? If it is more than one then we'll have to rethink this (what will happen when one of the call sides are ported to Rust while the others are not)
There was a problem hiding this comment.
Each function will be called from a single component (the first from the coordinator, the second from a notification).
In any case, the atomic variable should be linked to the query result processor (where the access performance is critical). I believe we can handle any in-between state while we migrate
* initial component layout * layout `slots_tracker_set_local_slots` plan * layout `slots_tracker_set_partially_available_slots` plan * layout `slots_tracker_set_fully_available_slots` plan * layout `slots_tracker_remove_deleted_slots` and `slots_tracker_has_fully_available_overlap` plan * layout `slots_tracker_check_availability` plan * minimal refactor to the API * implement helpers for the version management * initial implementation of SlotsSet * another iteration * refine implementation * add some tests * formatting * group state parts and other cleanup * reuse functions * rename * set unit test module in slot_set.rs * formatting * move helpers * implement separately slots_tracker for safer API and easier testing * refactor API to use SlotsTracker * add some tests * tidy ups and fix lifetime * format * better struct exposure * better memory management in union_relation * add test * rewrite some comments * switch values anf six comments * allow empty SlotRangeArray input (not null) * Check complete state in tests with a custom PartialEq implementation * update comments * add promote_to_local_slots functionality * add tests * formatting * tests cleanup * add coverage_relation algorithm * refactor union_relation to use new coverage_relation * formatting * linting * an attempt to create an FFI correctly * address some review comments * another review comment fix * update ffi and header * fix cbindgen build * more idiomatic * add debug assert to promote_to_local_slots * remove tests for unexpected situations * refactor has_overlap to use "any" * minor improvement * reorder match cases for better readability * use thread_local to avoid unsafe sync * replace boolean assert with thread id validation * implement version enum for slots_tracker * address review comments * improve comments * rename value to version * optimize atomic access * simplify helpers * use assert * move atomic manipulations to the C side * improve tests * improve API comments (cherry picked from commit 742f192)
|
Successfully created backport PR for |
Implement slots tracker for ASM - [MOD-12167] (#7200) * initial component layout * layout `slots_tracker_set_local_slots` plan * layout `slots_tracker_set_partially_available_slots` plan * layout `slots_tracker_set_fully_available_slots` plan * layout `slots_tracker_remove_deleted_slots` and `slots_tracker_has_fully_available_overlap` plan * layout `slots_tracker_check_availability` plan * minimal refactor to the API * implement helpers for the version management * initial implementation of SlotsSet * another iteration * refine implementation * add some tests * formatting * group state parts and other cleanup * reuse functions * rename * set unit test module in slot_set.rs * formatting * move helpers * implement separately slots_tracker for safer API and easier testing * refactor API to use SlotsTracker * add some tests * tidy ups and fix lifetime * format * better struct exposure * better memory management in union_relation * add test * rewrite some comments * switch values anf six comments * allow empty SlotRangeArray input (not null) * Check complete state in tests with a custom PartialEq implementation * update comments * add promote_to_local_slots functionality * add tests * formatting * tests cleanup * add coverage_relation algorithm * refactor union_relation to use new coverage_relation * formatting * linting * an attempt to create an FFI correctly * address some review comments * another review comment fix * update ffi and header * fix cbindgen build * more idiomatic * add debug assert to promote_to_local_slots * remove tests for unexpected situations * refactor has_overlap to use "any" * minor improvement * reorder match cases for better readability * use thread_local to avoid unsafe sync * replace boolean assert with thread id validation * implement version enum for slots_tracker * address review comments * improve comments * rename value to version * optimize atomic access * simplify helpers * use assert * move atomic manipulations to the C side * improve tests * improve API comments (cherry picked from commit 742f192) Co-authored-by: GuyAv46 <47632673+GuyAv46@users.noreply.github.com>
Implement slots state machine as part of the ASM effort
Implements a C API for a state machine, as described in the design document.
The implementation has 3 levels:
SlotSet- Implement set operations sor a set of slots, represented as an array of ranges, represented by the start and end slot of each range. This is to be memory efficient (under unfragmanted topology), and to seamlessly work withRedisModuleSlotRangeArray, which is expected to be supplied by the notifications we are going to use it in.SlotsTracker- Implements the state machine as described in the design document, with functionalities according to the changes we want to track.Internally, it uses 3
SlotSets to track the different states of slots in the shard while the topology changes.SlotsTrackerinstance. It gives an unsafe access to the state machine, which is safe under the assumption only the main thread calls these functions, exceptslots_tracker_get_versionto atomically fetch the current version of theSlotsTracker, which can be called from any thread. The implementation is safe withthread_local!instanciation (so no thread can access the state machine managed by the main-thread), and the API remember the thread-ID that first called the API and panics if any other thread calls it, so we should never have more than a single state machineMain objects this PR modified
SlotSet- track slots (values[0-16383]) using vector of continuous ranges, represented by the start and end slot of the range, and implements Set operationsSlotsTracker- Implements the state machine as described in the design documentSlotsTrackerwith minimal synchronization overheadMark if applicable
Note
Introduces a Rust slots tracker and C FFI to manage cluster slot ranges with versioned state, plus an atomic version counter in result processing for future slot-based filtering.
slots_tracker: implementsSlotSet(range-based set ops) andSlotsTracker(local/fully/partially-available sets, wraparoundVersion, availability checks).c_entrypoint/slots_tracker_ffi: thread-local singleton tracker with owner-thread enforcement; exports C functions:slots_tracker_set_local_slots_internal,slots_tracker_mark_partially_available_slots_internal,slots_tracker_promote_to_local_slots,slots_tracker_mark_fully_available_slots,slots_tracker_remove_deleted_slots,slots_tracker_has_fully_available_overlap,slots_tracker_check_availability.headers/slots_tracker.hviacbindgenwith inline wrappers managing an atomic version andOptionSlotTrackerVersion.key_space_version(atomic_uint) declaration/definition inresult_processor.c.Cargo.tomland dependencies to includeslots_trackerand FFI crate; build script for header generation.Written by Cursor Bugbot for commit 88a4827. This will update automatically on new commits. Configure here.