• • • DRAFT * * *

Goals

Both InnoDB and MyRocks lock rows that the transaction is going to modify. However, InnoDB also locks the gaps between the rows.

This allows it to support SBR, although the gaps are locked even when tx_isolation=REPEATABLE-READ and log_bin=off.

The presence of Gap Locking removes certain concurrency anomalies (TODO: will post examples here).

The goal of this task is to get MyRocks to

• not exhibit these concurrency anomalies
• Support SBR

Gap Lock support in RocksDB

Current row Locking in RocksDB

InnoDB locks rows in the database and/or gaps between them.

In MyRocks, row locking is provided by RocksDB. One can have exclusive locks on keys, although there is no direct relationship between row locks and rows in the database.

Row locks are stored here: utilities/transactions/transaction_lock_mgr.cc:

  struct LockMapStripe {
    ...
    std::unordered_map<std::string, LockInfo> keys;
    ...
  }

  // Map of #num_stripes LockMapStripes
  struct LockMap {
    std::vector<LockMapStripe*> lock_map_stripes_;
  }

Row locks are held in several "stripes", the hash of the key determines which stripe holds the lock (see LockMap::GetStripe).
Access to the std::unordered_map is synchronized via a mutex. Due to striping, there are several mutexes instead of one.

Gap Locks vs Row Locks from RocksDB POV

• Gap locks are shared (multiple transactions can have locks at the same gap at
  the same time)

• Gap locks should allow ordered traversals

  • so striping and std::unordered_map will not work

When MyRocks should use the gap locks

Do like InnoDB does:

when a query takes SQL's write lock (*) on table T, it should lock the gaps for ranges it is is about to write to table T, it should lock the gaps when reading ranges from the table T.

(*) - DML statements take SQL write lock on the tables they are writing to, SELECT .. FOR UPDATE takes write locks too.

(TODO: InnoDB mentions it does not lock gaps when tx_isolation=READ-COMMITTED. Should we also do that?)

TODO: Is the following true:
Gap Locks should also lock secondary index records! Which at the moment we do not lock at all (except for unique secondary indexes)

Should MyRocks use Gap Locks or Range Locks?

InnoDB locks rows in the database, which means it always has a row where to lock a gap for.
If the query is reading a range and the range has no rows, it will attach a gap lock to the row after the range (or to the "supremum" pseudo-row if the table doesn't have real rows).

With MyRocks, it's different. Consider a query

  update t20 set a=1235 
   where 
     pk between 12 and 18 or 
     pk between 912 and 918

Suppose there are no pk values in the [12,18] range. No row locks will be taken, but we should prevent inserts in that range.

So, it looks like MyRocks should have

• Locking for gaps between row locks
• Also, range locks for the case when there are no row locks (e.g. for secondary keys, but for PKs sometimes too)

Should we just use Range locks instead of gap locks? (range locks will inhibit row locks so these two will be related)