FASTER: How Does Microsoft KV Store Achieve 160 Million OPS?

Introduction

  • The Epoch Protection Framework: It realizes global modification on concurrent systems, defers synchronization in all threads, and simplifies concurrency design. FASTER threads require no synchronization and run independently.
  • Highly Concurrent Latch-free Hash Indexing: It is the key to achieving high throughput.
  • HybridLog: It uses logical addresses to unify memory and secondary storage. If written data exceeds the memory size, the data is flushed to the disk to support scenarios with a larger-than-memory data volume.

Epoch Protection Framework

Epoch Basics

Trigger Actions

Using

  • Acquire reserves an entry for T and sets Et to E.
  • Refresh updates Et to E.
  • BumpEpoch(action) increases c to c+1.
  • Release removes the entry of T from the epoch table.

The FASTER Hash Index

Index Format

Index Operations

  • Finding and Deleting an Entry: When finding an entry, the thread locates the entry in the bucket based on the key value. The thread locates the corresponding bucket based on the offset and then traverses to find the entry that matches the tag. When deleting an entry, the thread uses the CAS atomic operation to replace the matching entry with zero. Zero indicates the entry is null and can be written to.
  • Inserting: A thread inserts a new entry when the tag does not exist. Figure 3(a) shows the typical operation mode. In this mode, entries in the bucket are traversed to find the empty entry, and the new tag is inserted with CAS. However, there is a chance that two threads concurrently write the same tag, which is problematic. As shown in Figure 3(a), T1 traverses the entries from left to right in order to find the fifth entry and writes g5. At the same time, T2 deletes g3 and then traverses the entries from left to right in order to find the third entry and writes g5.

In-memory, Log-Structured, and HybridLog

In-memory

  • Read: A read operation locates the hash index entry based on the key and traverses the entry list to find the entry that matches the key value.
  • Update and Insert: The blind update and RMW update modes are supported, which are in-place update modes. Under epoch protection, threads securely perform in-place updates. If the entry does not exist, the thread writes the entry based on the two-phase approach of the hash index. If the entry cannot be found in the list, the thread performs the CAS operation to write the new entry to the end of the list atomically.
  • Delete: A delete operation removes an entry from the list by performing the CAS operation. When the entry is deleted, it is set to zero to indicate that the entry is null. After the entry is deleted, memory deallocation cannot be done immediately, as concurrent updates may exist. FASTER uses epoch protection to solve this problem, in which each thread maintains a thread-local space that is released only when the corresponding epoch becomes secure.

Log-Structured

HybridLog

Recovery

Test

Original Source:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alibaba Cloud

Alibaba Cloud

Follow me to keep abreast with the latest technology news, industry insights, and developer trends. Alibaba Cloud website:https://www.alibabacloud.com