微软并发Key-Value存储库FASTER引见

　　微软支撑并发的Key-Value 存储库有C++与C#两个版本。号称迄今为止最快的并发键值存储。下面是C#版本翻译：

FASTER C＃可在.NET Framework和.NET Core中运转，而且能够在单线程和并发设置中运用。经由测试，能够在Windows和Linux上运用。它公开了一种API，该API能够实行读取，盲更新（Upserts）和读取-修正-写入(RMW)操纵的夹杂。它支撑大于内存的数据，并接收IDevice将日记存储在文件中的完成。供应了IDevice当地文件体系的完成，也能够写入长途文件体系。或许将长途存储映射到当地文件体系中。FASTER能够用作传统并发数据结构相似ConcurrentDictionary的高性能替代品，而且还支撑大于内存的数据。它支撑增量或非增量数据结构范例的搜检点。

FASTER支撑三种基础操纵：

1. Read：从键值存储中读取数据
2. Upsert：将值自觉向上插进去到存储中（不搜检先前的值）
3. Read-Modify-Write：更新存储区中的值，用于完成“乞降”和“计数”之类的操纵。

构建

在实例化FASTER之前，您须要建立FASTER将运用的存储装备。假如运用的是可移植范例（byte、int、double）范例，则仅须要夹杂日记装备。假如运用对象，则须要建立一个零丁的对象日记装备。

IDevice log = Devices.CreateLogDevice("C:\\Temp\\hybridlog_native.log");

然后，按以下体式格局建立一个FASTER实例：

fht = new FasterKV<Key, Value, Input, Output, Empty, Functions>

  (1L << 20, new Functions(), new LogSettings { LogDevice = log });

组织函数的范例参数

有六个基础观点，在实例化FASTER时作为通用范例参数供应：

1. Key：这是键的范例，比方long。
2. Value：这是存储在FASTER中的值的范例。
3. Input：这是挪用Read或RMW时供应给FASTER的输入范例。它能够被视为读取或RMW操纵的参数。比方，关于RMW，但是增量累加到值。
4. Output：这是读操纵的输出范例，将值的相干部份复制到输出。
5. Context：操纵的用户定义上下文，假如没有必要运用Empty。
6. Functions：须要回调时，运用IFunctions<>挪用。

回调函数

用户供应一个实例化IFunctions<>。此范例封装了一切回调，下面将对其举行引见：

1. SingleReader和并发读ConcurrentReader：这些用于读取存储值并将它们复制到Output。单个读取器能够假定没有并发操纵。
2. SingleWriter和ConcurrentWriter：这些用于将值从源值写入存储。
3. Completion callbacks完成回调：种种操纵完成时挪用。
4. RMWUpdaters：用户指定了三个更新器，InitialUpdater，InPlaceUpdater和CopyUpdater。它们一同用于完成RMW操纵。
5. Hash Table Siz哈希表大小：这是分配给FASTER的存储行数，个中每一个行为64字节。
6. LogSettings 日记设置：这些设置与日记的大小、装备。
7. Checkpoint设置：这些是与搜检相干的设置，比方搜检范例和文件夹。
8. Serialization序列化设置：用于为键和值范例供应自定义序列化顺序。序列化顺序完成IObjectSerializer<Key>键和IObjectSerializer<Value>值。只要C＃类对象非可移植范例才须要这些。
9. Key比较器：用于为key供应更好的比较器IFasterEqualityComparer<Key>。

组织函数参数

FASTER的总内存占用量由以下参数掌握：

1. 哈希表大小：此参数（第一个组织函数参数）乘以64是内存中哈希表的大小（以字节为单元）。
2. 日记大小：logSettings.MemorySizeBits示意夹杂日记的内存部份的大小（以位为单元）。换句话说关于参数设置B，日记的大小为2 ^ B字节。假如日记指向类对象，则此大小不包括对象的大小，由于FASTER无法访问此信息。日记的较旧部份溢出到存储中。

Sessions (Threads)会话（线程）

实例化FASTER以后，线程能够运用Session来运用FASTER

fht.StartSession();

fht.StopSession();

当一切线程都在FASTER上完成操纵后，您终究烧毁FASTER实例：

fht.Dispose();

示例

以下是一个简朴示例，个中一切数据都在内存中，因而我们没必要忧郁挂起的I / O操纵。在此示例中也没有搜检点。

public static void Test()

{

  var log = Devices.CreateLogDevice("C:\\Temp\\hlog.log");

  var fht = new FasterKV<long, long, long, long, Empty, Funcs>

    (1L << 20, new Funcs(), new LogSettings { LogDevice = log });

  fht.StartSession();

  long key = 1, value = 1, input = 10, output = 0;

  fht.Upsert(ref key, ref value, Empty.Default, 0);

  fht.Read(ref key, ref input, ref output, Empty.Default, 0);

  Debug.Assert(output == value);

  fht.RMW(ref key, ref input, Empty.Default, 0);

  fht.RMW(ref key, ref input, Empty.Default, 0);

  fht.Read(ref key, ref input, ref output, Empty.Default, 0);

  Debug.Assert(output == value + 20);

  fht.StopSession();

  fht.Dispose();

  log.Close();

}

此示例的函数：

public class Funcs : IFunctions<long, long, long, long, Empty>

{

  public void SingleReader(ref long key, ref long input, ref long value, ref long dst) => dst = value;

  public void SingleWriter(ref long key, ref long src, ref long dst) => dst = src;

  public void ConcurrentReader(ref long key, ref long input, ref long value, ref long dst) => dst = value;

  public void ConcurrentWriter(ref long key, ref long src, ref long dst) => dst = src;

  public void InitialUpdater(ref long key, ref long input, ref long value) => value = input;

  public void CopyUpdater(ref long key, ref long input, ref long oldv, ref long newv) => newv = oldv + input;

  public void InPlaceUpdater(ref long key, ref long input, ref long value) => value += input;

  public void UpsertCompletionCallback(ref long key, ref long value, Empty ctx) { }

  public void ReadCompletionCallback(ref long key, ref long input, ref long output, Empty ctx, Status s) { }

  public void RMWCompletionCallback(ref long key, ref long input, Empty ctx, Status s) { }

  public void CheckpointCompletionCallback(Guid sessionId, long serialNum) { }

}

更多例子

搜检点和恢复

FASTER支撑基于搜检点的恢复。每一个新的搜检点都邑保存（或使之耐久）其他用户操纵（读取，更新或RMW）。FASTER许可客户端线程跟踪已耐久的操纵和未运用基于会话的API的操纵。

追念一下，每一个FASTER线程都邑启动一个与唯一的Guid相干联的会话。一切FASTER线程操纵（读取，Upsert，RMW）都带有单调序列号。在任何时候点，都能够挪用Checkpoint以启动FASTER的异步搜检点。在挪用以后Checkpoint，（终究）向每一个FASTER线程关照一个序列号，如许能够确保直到该序列号之前的一切操纵以及在该序列号以后没有任何操纵被保存为该搜检点的一部份。FASTER线程能够运用此序列号来消灭守候实行的操纵的任何内存缓冲区。

在恢复时期，线程能够运用继承运用雷同的Guid举行会话ContinueSession。该函数返回线程当地序列号，直到恢复该会话哈希为止。从那时起，新线程能够运用此信息来重播一切未提交的操纵。

下面一个单线程的简朴恢复示例。

public class PersistenceExample

{

  private FasterKV<long, long, long, long, Empty, Funcs> fht;

  private IDevice log;

  

  public PersistenceExample()

  {

    log = Devices.CreateLogDevice("C:\\Temp\\hlog.log");

    fht = new FasterKV<long, long, long, long, Empty, Funcs>

    (1L << 20, new Funcs(), new LogSettings { LogDevice = log });

  }

  

  public void Run()

  {

    IssuePeriodicCheckpoints();

    RunSession();

  }

  

  public void Continue()

  {

    fht.Recover();

    IssuePeriodicCheckpoints();

    ContinueSession();

  }

  

  /* Helper Functions */

  private void RunSession()

  {

    Guid guid = fht.StartSession();

    System.IO.File.WriteAllText(@"C:\\Temp\\session1.txt", guid.ToString());

    

    long seq = 0; // sequence identifier

    

    long key = 1, input = 10;

    while(true)

    {

      key = (seq % 1L << 20);

      fht.RMW(ref key, ref input, Empty.Default, seq);

      seq++;

    }

    // fht.StopSession() - outside infinite loop

  }

  

  private void ContinueSession()

  {

    string guidText = System.IO.File.ReadAllText(@"C:\\Temp\session1.txt");

    Guid sessionGuid = Guid.Parse(guidText);

    

    long seq = fht.ContinueSession(sessionGuid); // recovered seq identifier

    seq++;

    

    long key = 1, input = 10;

    while(true)

    {

      key = (seq % 1L << 20);

      fht.RMW(ref key, ref input, Empty.Default, seq);

      seq++;

    }

  }

  

  private void IssuePeriodicCheckpoints()

  {

    var t = new Thread(() =>

    {

      while(true)

      {

        Thread.Sleep(10000);

fht.StartSession();

        fht.TakeCheckpoint(out Guid token);

        fht.CompleteCheckpoint(token, true);

fht.StopSession();

      }

    });

    t.Start();

  }

}

FASTER支撑两种搜检点观点：“快照”和“折叠”。前者是将内存中的完全快照复制到一个零丁的快照文件中，而后者是自上一个搜检点以来变动的增量搜检点。折叠有效地将夹杂日记的只读标记移到尾部，因而一切数据都作为统一夹杂日记的一部份保存（没有零丁的快照文件）。一切后续更新均写入新的夹杂日记尾部位置，这使Fold-Over具有增量性子。

项目途径：

https://github.com/Microsoft/FASTER/tree/master/cs