DOCSEARCHbyAlgolia
Submit Docs

FASTER Documentation

repository·main·Indexed 27 days ago

https://github.com/microsoft/faster

A high-performance state management project providing FASTER Log (a concurrent persistent recoverable log) and FASTER KV (a concurrent key-value store and cache). Designed to handle data larger than memory with low latency and high throughput, it is available in C# and C++. The project includes tools for YCSB benchmarking and a C++ port with built-in recovery capabilities.

Tokens
27.4K
Snippets
44
Records
150
Agent score
91%

What's inside FASTER

  1. Overview of FASTER Log and FASTER KV

    main

    FASTER provides two primary high-performance artifacts for managing large application state:

    • FASTER Log: A high-performance concurrent persistent recoverable log, iterator, and random reader library written in C#. It is designed for frequent commit operations at low latency, can saturate disk bandwidth, and supports both sync and async interfaces, disk error handling, and checksums.
    • FASTER KV: A concurrent key-value store and cache available in both C# and C++. It is optimized for point lookups and heavy updates, supporting data larger than memory by leveraging local or cloud external storage. It features consistent recovery via a fast non-blocking checkpointing technique.

  2. Overview of FasterKV C# capabilities

    main

    FasterKV is a high-performance key-value store and cache for .NET Framework and .NET Core, compatible with both Windows and Linux.

    Key features include:

    • Concurrency: Supports both single-threaded and highly concurrent settings.
    • Operations: Provides APIs for Reads, Blind Updates (Upserts), and atomic Read-Modify-Write operations.
    • Scalability: Supports data larger than available memory.
    • Storage: Uses IDevice implementations for log storage. Built-in implementations exist for the local file system and Azure Page Blobs, with support for custom devices and meta-devices (sharded/tiered configurations).
    • Persistence: Supports both incremental and non-incremental checkpointing.
    • Async Support: Operations can be issued synchronously or asynchronously using the C# async interface.
    • Use Case: Can serve as a high-performance replacement for ConcurrentDictionary when larger-than-memory data or checkpointing is required.

  3. Overview of FASTER C++

    main
    FASTER C++ is a C++ port of the FASTER C# key-value store. It provides a full key-value store implementation along with its built-in recovery capabilities. For complete building instructions and detailed documentation, refer to the official FASTER C++ documentation site.

  4. Overview of F2Kv Two-Tier Storage

    main

    F2Kv is an extension of FasterKv that implements a two-tier storage architecture to manage data movement between hot and cold stores automatically.

    Key features include:

    • Hot Store: Optimized for fast access and frequent updates with a larger in-memory mutable region. Supports optional read-caching.
    • Cold Store: Optimized for storage efficiency for less active data.
    • Two-Level Indexing: Uses a cold-index that spans memory and disk to reduce indexing overhead to approximately 1 byte per key by grouping hash buckets into hash chunks.
    • Automatic Data Migration: Data moves between tiers based on access patterns via multi-threaded lookup-based compaction.
    • Consistency: Guarantees system consistency across multiple threads operating on the same records.

  5. Understand FasterKV Record Locking via LockTable

    main

    FasterKV uses a LockTable to manage locks for records that are not currently in memory (e.g., evicted due to memory pressure) or have not yet been added to the log. The LockTable acts as if the key were present on the log and in memory, ensuring lock consistency even for non-resident keys.

    Key concepts:

    • LockTable: The mechanism for recording locks for non-resident or new keys.
    • InMemKV: An optimized in-memory key/value store used by the LockTable to minimize GC overhead and optimize bucket-level locking.
    • RecordInfo: The value type stored in the LockTable which contains the actual lock state and metadata (like ExclusiveGeneration and Tentative bits).

  6. Variable-Length (Varlen) Remote FASTER

    main

    For scenarios requiring arbitrary byte sequences (similar to standard KV stores), use the variable-length implementation:

    • Server Side: Uses the SpanByte concept to store variable-length keys and values inline in the hybrid log. The wire format is [ 4 byte payload length | payload ].
    • Client Side: The session API uses Memory<byte>, allowing clients to read and write arbitrary byte sequences that are binary compatible with the server.

  7. Understand FASTERKV Record Locking and ReadCache structure

    main

    In FASTERKV, when ReadCache is enabled, records in the ReadCache (identified by the ReadCache bit in their RecordInfo header) are inserted into the hash chain before any main log records.

    Chain Structure:

    • Without ReadCache: HashTable -> m#### (main log) -> m#### ...
    • With ReadCache: HashTable -> r#### (ReadCache prefix chain) -> r#### -> m#### (main log) -> m#### ...

    In FASTER v2, ReadCache records may be locked. To prevent losing these locks during updates or evictions, FASTER uses specific transfer mechanisms:

    1. On updates: The specific ReadCache record being updated is spliced out and transferred to a CopyToTail on the main log, preserving its locks.
    2. On eviction: ReadCache records are removed from the prefix chain, and any records holding locks are transferred to the LockTable.

  9. Understand FasterKV locking levels

    main

    FASTER provides two distinct levels of locking:

    1. Ephemeral Locking: Automatically managed during data operations like Upsert, RMW, Read, or Delete. These locks operate under epoch protection to prevent eviction. If an ephemeral lock cannot be acquired within a limited spin count, the operation fails, and the caller should retry.
    2. Manual Locking: Managed by the user via Lockable*Context instances obtained from a ClientSession. These allow for long-lived locks that can persist even when pages are evicted from memory to the LockTable due to memory pressure.

  10. Upsert Locking Flow

    main

    An Upsert is a blind update. The locking behavior depends on the record's location:

    • ReadCache: The record is exclusively locked, a new record is added, and then it is unlocked.
    • Mutable Region: The record is read-locked, IFasterSession.ConcurrentReader is called, and then it is unlocked.
    • Immutable Region: The record is read-locked, IFasterSession.SingleReader is called. If CopyToTail is enabled, the lock transfer logic for immutable regions applies.

  11. Configure F2Kv with Advanced Settings

    main

    For fine-grained control, you can specialize the F2Kv class and configure separate hot_faster_store_config_t and cold_faster_store_config_t objects. This allows you to define specific compaction policies, memory sizes, and hash chunk sizes for the cold index.

    Key configuration components:

    • Index Configuration: Set table_size, in_mem_size, and mutable_fraction.
    • Hybrid Log (Hlog) Configuration: Set in_mem_size, mutable_fraction, and pre_allocate.
    • Compaction Configuration: Control check_interval, trigger_pct, compact_pct, max_compacted_size, and hlog_size_budget.
    • Read Cache: Enable/disable via ReadCacheConfig.
    // Define your types
struct Key { /* ... */ };
struct Value { /* ... */ };

// Hot Index class
using HI = MemHashIndex<Disk>;
// Cold Index class: Use 2^6 (=64 byte) sized hash chunks
using CI = ColdIndex<Disk, ColdLogHashIndexDefinition<6>>;
// F2Kv specialized class
using store_t = F2Kv<Key, Value, Disk, HI, CI>;

// Create hot store configuration
typename store_t::hot_faster_store_config_t hot_config;
// ... configure hot_config.index_config, hot_config.hlog_config, etc.

// Create cold store configuration
typename store_t::cold_faster_store_config_t cold_config;
// ... configure cold_config.index_config, cold_config.hlog_config, etc.

// Create F2Kv instance
store_t store{ hot_config, cold_config };

  12. Understand FasterKV Record Locking Flows

    main

    FasterKV uses different locking flows for Read operations versus Updaters (RMW, Upsert, Delete) depending on where the record resides in memory.

    For In-Memory Records:

    • Read: Locks the record and calls the appropriate IFunctions method.
    • Updaters: Lock the record for the entire lifetime of the operation.
      • If the record is in the mutable region, the update is performed in-place and the lock is released immediately.
      • If the record is elsewhere, a new record is created. The existing record acts as the 'source'. For RMW, the 'source' data is used to create the new record; for Upsert and Delete, the 'source' data is ignored. Once the new record is written, the 'source' record is unlocked.

    For On-Disk Records:

    Read operations involve pending-read processing. The system first checks for an existing source record (which might have been added to the log, readcache, or LockTable by another session) and locks it before calling IFasterSession.SingleReader.