Explore possibility of sharding the keyspace for reducing lock scope

[the123saurav]

Issue

Currently we are taking a global lock for every request so as to guarantee the order of execution for commands.

Possible Solve

CM uses segments under the hood just like ConcurrentHashMap for parallel access.
If we can use the same hashing mechanism and just take a lock on the segment, we can guarantee ordering for same key.

[tuhuynh27]

So let's say if we do this in order:

• Get shard for key and take lock K on that
• Generate a monotonic number atomically which decides the order of command, write this number along with the command to AOF under a global lock G.
• Release the lock G now
• Process for key
• Release lock K

So basically limit the global lock scope(barring Tx)
The number that we persisted would be used for sorting at boot
CM uses this function XxHash_r39 which they have adapted, we can also adapt that and if we specify the number of segments when constructing CM, we can know what segment a key hash would fall in (https://github.com/OpenHFT/Chronicle-Algorithms/blob/ea/src/main/java/net/openhft/chronicle/algo/hashing/XxHash_r39.java)

Suggested flow by @the123saurav

[haphananhtuan]

Just a quick thought, if we gonna support sharding by putting a lock for each shard then we could remove the global lock. Because with shard level lock we have already guarantee the order of command within that shard.

[tuhuynh27]

Yes @haphananhtuan, ChronicleMap already has an internal shard lock to handle concurrency, but we (from outside) can't access that lock thus don't know the command order to write to the AOF log / replication log