Garnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.
[x] Add unit tests to validate cluster redirect functionality.
[x] Implement key level access control.
[x] Benchmark standalone cluster and main
Overview of Migration
The process of slot migration involves several stages which are designed to manage data access, ensuring both data integrity and high availability as the corresponding keys are being transferred from the source node to the target node.
The MIGRATE command supports two transfer options, specifically MIGRATE KEYS and MIGRATE SLOTS.
Both options use a common data access control interface, that is logically divided into the following categories:
Slot level access control
Used to orchestrate migration by changing the state of the associated slot accordingly (i.e. MIGRATING, IMPORTING) at the corresponding source and target nodes
Key level access control
Used to control access to individual keys in order to ensure high availability and data integrity.
Key level access control
Each migrate session maintains a dictionary of <keys, KeyMigrationStatus> pairs.
This dictionary is used to control access to keys that are actively being managed by a single running migrate session.
When a slot is in the process of migration and there are no active migration sessions managing a specific key, any requests for that key are handled under the assumption that the key exists. If it doesn’t, a redirect -ASK is created, which points to the endpoint of the target node.
The KeyMigrationStatus will affect individual session readers and writers as follows:
QUEUED (QD)
Key owned by a specific MigrateSession but is not actively being migrated.
Reads and writes can be served if the keys exist.
MIGRATING (MG)
Key is actively being migrated by a specific MigrateSession.
Writes will be delayed until status goes back to QUEUED or MIGRATED.
Reads can be served without any restriction.
DELETING (DL)
Key is being deleted after it was sent to the target node.
Reads and writes will be delayed.
We need to delay reads to avoid the scenario where a key exists during validation but was deleted before read executes.
MIGRATED (MD)
Key owned by a specific MigrateSession and has completed all the steps to be MIGRATED to target node.
This does not mean that key existed or has not expired, just that all the steps associated with MIGRATED have completed.
This can happen for a key that was provided as an argument in MIGRATE command but did not exist or expired for both main and object stores.
Key Transfer State Machine Algorithm
Add keys to dictionary and initialize KeyMigrationStatus to QUEUED
Perform for main and object store separately
Transition keys from QUEUED to MIGRATING state
Await for status change propagation using epoch protection.
For every key in MIGRATING state perform the following:
Lookup for key at given store.
If key is found send it (do it in batch) to the target node.
If key is not found change state back to QUEUED to unblock any writers.
If copy option is disabled perform the following:
Transition keys from MIGRATING to DELETING.
Await for status change propagation.
For every key in DELETING state, delete it and change its state to MIGRATED.
If copy option is enabled transition keys from MIGRATING to MIGRATED state.
This PR resolves issue #354.
Tasks:
Overview of Migration
The process of slot migration involves several stages which are designed to manage data access, ensuring both data integrity and high availability as the corresponding keys are being transferred from the source node to the target node. The MIGRATE command supports two transfer options, specifically MIGRATE KEYS and MIGRATE SLOTS. Both options use a common data access control interface, that is logically divided into the following categories:
Key level access control
Each migrate session maintains a dictionary of <keys, KeyMigrationStatus> pairs. This dictionary is used to control access to keys that are actively being managed by a single running migrate session. When a slot is in the process of migration and there are no active migration sessions managing a specific key, any requests for that key are handled under the assumption that the key exists. If it doesn’t, a redirect -ASK is created, which points to the endpoint of the target node.
The KeyMigrationStatus will affect individual session readers and writers as follows:
Key Transfer State Machine Algorithm
RespClusterBench - Slot in STABLE state
Main
PR #474
Diff (%)
RespClusterMigrateBench - Slot in MIGRATING state
Main
PR #474
Diff (%)