We expect kvrocks to support MVCC

[xinhua5]

Why do we need MVCC

We have introduced a cache layer between kvrocks and client, which supports multi-point writing in the cache layer. like this:

flowchart TB
    client-->cache1
    client-->cache2
    cache1 <--> kvrocks0_0
    cache1 <--> kvrocks1_0
    cache2 <--> kvrocks0_0
    cache2 <--> kvrocks1_0
    
    kvrocks0_0 --- kvrocks0_1
    kvrocks0_0 --- kvrocks0_2
    kvrocks1_0 --- kvrocks1_1
    kvrocks1_0 --- kvrocks1_2

Loading

There is such a scenario：

sequenceDiagram
client ->> cache1: set k=10
cache1 ->> cache1: write WAL and buffer, k=10
cache1 ->> cache1:  failed
client ->> cache2: set k=12
cache2->> cache2: write WAL and buffer, k=12
cache2 ->> kvrocks: flush k=12
cache1 ->> cache1: recovery and load WAL
cache1->>kvrocks: flush k=10
client ->> cache1: get k
cache1->> kvrocks: get k
kvrocks->>cache1: return k
cache1->>client: return k

Loading

We want k=12, but in fact k=10, that's why we expect kvrocks to support mvcc.

[git-hulk]

@xinhua5 Thanks for your feedback. EVAL_RO also needs the MVCC feature to guarantee the data consistency, but this should be a big change and need to design carefully first. I have a rough idea
is to allow passing version into connection, then all read operations should use this version instead of latest if exists.

[git-hulk]

I misunderstood @xinhua5 meaning, what he needs is written order NOT the read version. So just disregard the above comment.

[mapleFU]

Intrdocuing mvcc is hard, especially when you have multiple kvrocks instance, for simplest case, if we want to implement single key mvcc, we need:

1. Generating a new version for k in kvrocks. Apart from RocksDB's sequence_id, it should be encoding to RocksDB's key, and generated by a incr like operation.
2. Calling set with the mvcc key.
3. Get a key with version, if the key with version doesn't exists, the query should fallback to the previous version, so version might be encoded in big endian.
4. Garbage collection the useless version, which should be set by your cache client.

1-3 using set and get is impossible, so new command should be created. If you want multi-key transaction, it would be much more complex, because version generating would depending on a centralized sequncer or clock-si, and garbage collecting them should be much more hard.

I think the key reason in your design is never mvcc, is transaction. Maybe a key service like zk or redlock is required when calling set, and getting a key should goto the right server.

[mapleFU]

And seems that your cache is not a cache, is just like a BufferPool in RDBMS or write buffer in memory system. Writing different cache server is may have lots of confusing actions, for example:

client 1 write cache 1 with version 5
client 1 write cache 2 with version 6
--> what will happen if client 1 queries cache 1?

I recommend using hash or range partitions to partition the cache server, and using a zk-liked server to manage the partition. Although still some problems like aba would happens, it will greatly decrease your problems.

Or you can write with a version, before flushing, you can check the version in that key or write with a lua script when flushing to kvrocks.

[git-hulk]

Yes, Kvrocks also supported the CAS command, so it's ok to check the version before set.

[xinhua5]

Thanks, as you say, The cache actually is Customized Computing Node, like BufferPool, cache operators and merge it, then flush BatchResult to kvrocks. Writing the same server that using hash to partition the server. But unable to ensure that all data is written accurately kvrocks, that's what we're worried about.

[mapleFU]

Thanks, as you say, The cache actually is Customized Computing Node, like BufferPool, cache operators and merge it, then flush BatchResult to kvrocks. Writing the same server that using hash to partition the server. But unable to ensure that all data is written accurately kvrocks, that's what we're worried about.

Google MapReduce has a process to assign task and check status, seems that you can recover from WAL in your compute node, so I think you can either write the response to kvrocks straiforward, or caching with a caching policy (like lru / max caching time ) and flushing them. If a server crashs, you can force recover and using max caching time to flush them

[tanruixiang]

I think the key reason in your design is never mvcc, is transaction. Maybe a key service like zk or redlock is required when calling set, and getting a key should goto the right server.

I agree. I think your design needs to do more at the cache layer. This will be much less work than modifying kvrocks.