Supporting CAS operations in Badger

Users
1

We like to support operations like CASPut(key, val, casCounterCheck) where the value for key is updated only if casCounterCheck matches the key’s current casCounter. casCounter is a random nonzero uint16. We could also call this casValue or something, but for now, let’s call it a casCounter.

One immediate application is the value log GC. For value log GC, we iterate entries in the value log. For each key we see, we check against KV[key]. If the value offset is different, we can drop the entry. Otherwise, we want to keep the entry, by appending it to another vlog file and updating the value offset for that key. The problem is that between the get and put of the value offset, the key-value might be updated. In this case, the CAS counter will allow us to realize that the key-value is not what we “get” just now, and avoid doing the update.

Question: When is the CAS counter computed? Firstly, the user is not allowed to specify the CAS counter for an operation. It is randomly generated. And it is generated BEFORE writing to value log, for every operation. In addition, for CAS operations, we will also store to value log CASCounterCheck.

During value log replay (say after a crash), we will use the same CAS counters as recorded in the value log. For CAS operations, we will do the check using CASCounterCheck in the value log. Note: You have to store these in value log. Otherwise, after a crash, you will get different CAS counters and CAS operations might not be executed correctly.

Question: When do we Get the CAS counter to compare against the user-specified CAS counter check? This is done in WriteToLSM. Just before we Put an entry, we do this Get. Note that all writes go into a channel and processed sequentially. So between this Get and Put, this key cannot be modified. We have to be careful not to change this.

Here is some pseudocode to summarize the order of these steps.

writeRequests(entries):
  for each entry,
    compute random CAS counter and store in entry
  write entries to value log. This includes CAS counters and CAS counter checks.
  writeToLSM

writeToLSM(entries)
  for each entry,
    if entry.CASCounterCheck != 0:
      casCounter=kv.Get(entry.Key)
      if casCounter != entry.CASCounterCheck, continue
    insert entry to memtable
2

This topic was automatically closed 30 days after the last reply. New replies are no longer allowed.