Orthogonal Key Value Locking (OKVL). More...

Classes
struct	okvl_mode
	Represents a lock mode of one key entry in the OKVL lock manager. More...

Variables
const uint32_t	OKVL_PARTITIONS = 2
	The number of partitions in OKVL. More...

const uint32_t	OKVL_MODE_COUNT = (OKVL_PARTITIONS + 1 + 1)

Detailed Description

Orthogonal Key Value Locking (OKVL).

Overview

OKVL is a more concurrent and simple lock mode design compared to ARIES KVL (Key Value Locking), Lomet's KRL (Key Range Locking), and Graefe's OKRL (Orthogonal Key Range Locking). It combines techniques from those previous work with partitioning of the key. In addition to the key lock mode, OKVL has k partition lock modes.

So, it consists of k element lock modes (e.g., S and X) for individual partitions, 1 element lock mode for key, and 1 element lock mode for the gap between the key and the next key. For example, suppose k=4 and a transaction (Xct-A) locks only the 2nd partition with S; 1st=N, 2nd=S, 3rd=N, 4th=N, key=IS, gap=N. Even when another transaction (Xct-B) wants to lock the key with X, the locks are compatible unless Xct-B ends up hitting 2nd partition.

We determine the partition to lock based on the uniquefier of the key-value entry. Thus, if the index is a unique index, OKVL behaves exactly same as OKRL. However, for non-unique indexes with lots of duplicate keys this will dramatically increase the concurrency.

Note that sometimes we have to lock the entire key with absolute lock mode (e.g., S) rather than intent mode (e.g., IS). For example, a scanning transaction has to protect all entries under the key.

Uniquefier in non-unique indexes

It depends on the implementation of non-unique indexes. Some database appends uniquefiers to keys (so, physically making it a unique index except lock manager behavior) while other stores uniquefiers as data (thus, "value" is a list). We employ the former approach, so uniquefier is the tail of each key.

How To Use

Include w_okvl.h. This file declares the most basic enums/structs/functions for the locking module based on OKVL (Orthogonal Key Value Locking). All of them are header-only to be easily used across all modules.

Note: Inline functions and global constants are defined in w_okvl_inl.h to make this file easier to read. Include it if you need them.

References

For further understanding, you are strongly advised to read the full document about OKVL under publications/papers/TBD. Or, search "Orthogonal Key Value Locking" on Google Scholar. It's a full-length paper, but it must be worth reading (otherwise punch us).

Variable Documentation

§ OKVL_MODE_COUNT

const uint32_t OKVL_MODE_COUNT = (OKVL_PARTITIONS + 1 + 1)

Number of partitions, +1 for key, and +1 for gap.

§ OKVL_PARTITIONS

const uint32_t OKVL_PARTITIONS = 2

The number of partitions in OKVL.

Must be 1 or more. If the value is 1, it behaves just like OKRL. In the OKVL paper, this parameter is denoted as "k".

Note: When this value is more than 1, it should be a prime number because we currently divide hashes by this number to determine the partition. A simple number, say "256", would result in horrible hash collisions (yes, I actually hit the issue). Also, it's a good idea to keep OKVL_MODE_COUNT within some multiply of 16 (for example, 61+1+1=63, which would fit in one cache line). Finally, this number should be reasonably small, say at most hundreds. We tested even larger numbers and observed slow downs. See our paper for more details.

Classes

Variables