Skip to content
Branch: master
Go to file
Code

Latest commit

sillycross committed 88d7282 Jul 3, 2020
New API for clean handling of VariantLengthKey (#282)
In this diff, we propose the new API for clean handling of VariantLengthKey.
Previously, handling VariantLengthKey is extremely tricky and fragile (if possible at all),
and requires writing code that any project with reasonable code quality standards would not tolerate.
This is even causing bugs in our own codebase (e.g. Compaction contexts, and even the test that tests VariantLengthKey is buggy itself).

We propose a backward-compatible new API to handle VariantLengthKey cleanly.
We add a new concept -- ShallowKey. This class is required to provide the same APIs
as the Key class (size(), GetHash() and operator==()), but unlike Key class,
which raw contents (interpreted as a uint8_t* string) is directly written into the log,
ShallowKey's internal representation does not matter.
In addition to the existing APIs, a new API with prototype
   void write_deep_key_at(Key* dst) const
is required, which should write the bytestream-representation of the Key into address 'dst'.

In order to use the new API, all you need to do is to change the key() API in Context to return
ShallowKey type, instead of key_t type. Example:

struct UpsertContext
{
	using key_t = Key;

	// uncomment below to use new API
	// ShallowKey key();

	// uncomment below to use old API
	// key_t key();
};

Files

Permalink
Failed to load latest commit information.

README.md

NuGet Build Status Gitter

Introduction

Managing large application state easily, resiliently, and with high performance is one of the hardest problems in the cloud today. The FASTER project offers two artifacts to help tackle this problem.

  • 🆕 FASTER Log is a high-performance concurrent persistent recoverable log, iterator, and random reader library in C#. It supports very frequent commit operations at low latency, and can quickly saturate disk bandwidth. It supports both sync and async interfaces, handles disk errors, and supports checksums. Learn more about the FASTER Log here or here.

  • FASTER KV is a concurrent key-value store + cache (available in C# and C++) that is designed for point lookups and heavy updates. FASTER supports data larger than memory, by leveraging fast external storage (local or cloud). It also supports consistent recovery using a new checkpointing technique that lets applications trade-off performance for commit latency.

Some key differentiating features of FASTER KV and FASTER Log include:

  1. Latch-free cache-optimized index, in FASTER KV.
  2. A fast persistent recoverable append-only log based on fine-grained epoch protection for concurrency, in FASTER Log.
  3. Unique “hybrid record log” design in FASTER KV, that combines the above log with in-place updates, to shape the memory working set and retain performance.
  4. Architecture as a component that can be embedded in multi-threaded cloud apps.
  5. Asynchronous recovery model based on group commit (called CPR).
  6. A rich extensible storage device abstraction called IDevice, with implementations for local storage, cloud storage, tiered storage, and sharded storage.

For standard benchmarks where the working set fits in main memory, we found FASTER KV to achieve significantly higher throughput than current systems, and match or exceed the performance of pure in-memory data structures while offering more functionality. See the SIGMOD paper for more details. We also have a detailed analysis of C# FASTER KV performance in a wiki page here. The performance of the C# and C++ versions of FASTER are very similar. FASTER Log is also extremely fast, capable of saturating modern NVMe SSDs using less than a core of CPU, and scaling well in a multi-threaded setting.

🆕 We now support C# async in FASTER KV (and FASTER Log). See the detailed guide at this link for more information. Also, check out the samples in the playground located here.

Getting Started

Visit our research website for technical details and papers. For FASTER usage and getting started information, head over to our GitHub Pages website. A detailed guide to getting started with FASTER KV C# is also available in the repository at this link. FASTER C# binaries are available via NuGet.

You can take a look at the project roadmap here.

Build and Test

For C#, click here.

For C++, click here.

Recovery in FASTER KV

Both the C# and C++ version of FASTER KV support asynchronous checkpointing and recovery, based on a new recovery model called Concurrent Prefix Recovery (CPR for short). You can read more about CPR in our research paper here (to appear in SIGMOD 2019). Briefly, CPR is based on (periodic) group commit. However, instead of using an expensive write-ahead log (WAL) which can kill FASTER's high performance, CPR: (1) provides a semantic description of committed operations, of the form “all operations until offset Ti in session i”; and (2) uses asynchronous incremental checkpointing instead of a WAL to implement group commit in a scalable bottleneck-free manner.

CPR is available in the C# and C++ versions of FASTER. More documentation on recovery in the C# version is here. For C++, we only have examples in code right now. The sum-store, located here, is a good example of checkpointing and recovery.

Contributing

This project welcomes contributions and suggestions. Most contributions require you to agree to a Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us the rights to use your contribution. For details, visit https://cla.microsoft.com.

When you submit a pull request, a CLA-bot will automatically determine whether you need to provide a CLA and decorate the PR appropriately (e.g., label, comment). Simply follow the instructions provided by the bot. You will only need to do this once across all repos using our CLA.

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.

You can’t perform that action at this time.