Microsoft Garnet

The FASTER project provides two primary artifacts for managing large application state with high performance and resilience:

• 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 and can saturate disk bandwidth. It supports both synchronous and asynchronous interfaces, handles disk errors, and includes 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. It supports datasets larger than available memory by leveraging fast external storage (local or cloud) and provides consistent recovery via a fast non-blocking checkpointing technique, allowing users to trade off performance for commit latency.

Azure Cosmos DB Garnet Cache is a fully managed, high-performance caching service built on the Garnet remote cache-store. It is designed for enterprise-grade reliability, security, and scalability.

Unlike traditional single-threaded caches, Garnet uses a shared-everything architecture within nodes, where all threads directly access a single shared memory space. This allows for:

• Ultra-Low Latency: Median (P50) latency < 1 ms; 99th percentile (P99) latency at 3 ms.
• High Throughput: Supports millions of operations per second with linear scalability.
• Scalability: Supports vertical and horizontal scaling, and configurable replication.
• Data Persistence: Optional durability via non-blocking append-only file (AOF) logging and Redis Database (RDB) snapshots.

Tsavorite is the storage layer for Garnet. It is a fork of the FASTER project and provides high-performance database features designed for scalability and durability.

Key features include:

• Thread Scalability: Optimized for high-concurrency workloads.
• Tiered Storage: Support for multiple storage tiers including memory, SSD, and cloud storage.
• Durability & Recovery: Includes fast non-blocking checkpointing, recovery mechanisms, and operation logging.
• Concurrency Control: Supports multi-key locking and transaction support.
• Resource Management: Improved memory management and space reuse capabilities.

Garnet is a high-performance, cross-platform remote cache-store built on .NET. It supports a wide range of operations:

• Raw Strings: GET, SET, and key expiration.
• Analytical Operations: HyperLogLog and Bitmap.
• Object Operations: Sorted Sets, Lists, Sets, Hashes, and Geo.
• Transactions: Supports client-side RESP transactions and server-side stored procedures/modules written in C#.
• Scripting: Supports Lua scripts.
• Advanced Features (Preview):
  • Vector Sets: Approximate nearest-neighbor search using the DiskANN algorithm.
  • Range Index: Secondary range and equality indexes over keys using Bf-Tree.

Garnet provides a comprehensive API surface compatible with common key-value store patterns, including:

• Raw Strings: Support for Get and Set variants, including key expiration.
• Data Structures: Support for List, Hash, Set, Sorted Set, and Geo types.
• Analytics: Specialized APIs for Hyperloglog and Bitmap operations.
• Transactions: Client-side transaction API using MULTI/EXEC.
• Messaging: Publish/Subscribe capabilities.
• Management: Admin operations and Access Control List (ACL) features.

Azure Cosmos DB Garnet Cache is compatible with Redis clients and supports a subset of Redis data types and commands.

Key Constraints:

• Maximum Key-Value Size: 32MB.
• Performance Recommendation: For the lowest latency, aim to keep key-value pairs around 1KB.

The implementation follows the open-source Garnet command set, covering various categories including CLIENT, CLUSTER, HASH, STRING, and more.

Garnet provides compatibility with a large subset of the Redis REST API surface. While the supported command list is continuously expanding, you can check the current support status for specific commands in the api-compatibility.md documentation.

Beyond standard Redis commands, Garnet features a custom operator framework. This allows you to register custom C# data structures and read-modify-write operations directly on the server, which can then be accessed via an extension of the RESP (Redis Serialization Protocol).

Garnet provides partial support for Vector Sets, which are implemented using the DiskANN project.

Mental Model

A Vector Set consists of:

1. An Index Key: A single key that stores metadata and a pointer to the underlying DiskANN data structure. This is the only key visible to the user.
2. Element Keys: Multiple keys that store the actual vectors, quantized vectors, attributes, etc.

To prevent user commands from accidentally overwriting element data, Garnet stores element keys in different namespaces derived from the index's Context value. This allows standard commands like SET to work on the same key names without interfering with the Vector Set's internal storage.

The FreeList mechanism is organized into a three-tier hierarchy designed for high-concurrency reuse of deleted records:

1. FreeRecordPool: The top-level manager that maintains multiple bins and uses a size index (a cache-aligned vector of integers) to quickly determine which bin should handle an Enqueue or Dequeue request.
2. FreeRecordBins: Multiple bins corresponding to the RevivificationBin definitions in your settings. Each bin manages a specific range of record sizes. Bins use a segmented circular buffer approach to balance search efficiency and concurrency.
3. FreeRecord: The individual units stored within bins. Each FreeRecord contains a free log address and the epoch in which it was freed. The record's data is stored as a long containing the 48-bit address and 16-bit size (for records $\le 2^{16}$ bytes).

Clients can connect to any node in the cluster. The node receiving the request calculates the relevant hashlot and responds based on the following logic:

• Slot owned by receiving node: Performs the operation normally.
• Slot owned by another node: Responds with -MOVED <slot> <address> <port>.
• Receiving node is a replica: Serves read requests for its primary's slots; redirects write requests via -MOVED.
• Slot is migrating:
  • If the key exists: Reads are normal; writes return -MIGRATING.
  • If the key does not exist: Both reads and writes return -ASK <slot> <address> <port>.
• Target of migration: If the receiving node is the target of a migration, requests are only served if the client previously issued an ASKING command. Note that using ASKING does not ensure write safety; clients must handle this with care.