追記型ストレージFasterLogについて

# 始めに

Microsoftは、ローカルで使えるストレージライブラリの[FASTER](https://github.com/microsoft/FASTER)というものを開発している。
このFASTER、最初はキーバリューストアであるFasterKVのみ提供していた。しかし、バージョン2019.10.31.1より、FasterLogという、データの追記に特化した機能が追加された。
少し触ってみると、今自分が実現したい機能を丁度良くカバーしてそうなので、使い方や注意点を書いておく。

FasterKVは論文も発表されているので、特徴や理論的な裏付け等が知りたければそちらも参照のこと。

* [論文(PDF)](https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf)
* [日本語解説](https://scrapbox.io/nikezono/FASTER)

今回紹介するFasterLogは、FasterKVで使用しているストレージ機能のベース部分を利用した、追記と範囲検索に特化したものとなる。

なお、FasterLogは今もなおインターフェイスの更新が行われており、この記事で書かれていることと微妙に差異があるかもしれないので注意が必要。
この記事では1.9.5をベースに解説を行う。

# 特徴

* データはディスクに保存される
    * ドライバを書けばローカルディスク以外にも対応可能
        * 例: [Azure Blobをストレージとして使うライブラリ](https://www.nuget.org/packages/Microsoft.FASTER.Devices.AzureStorage/)
* 扱えるデータ型はバイト配列のみ
* 以下の操作が可能
    * 追記
    * データの範囲検索
    * 過去のある時点までのレコード削除
* 特定レコードの削除は不可
* 途中にデータを挿入することは不可

# 使い方

## プロジェクトへの導入

普通に[nugetパッケージ](https://www.nuget.org/packages/Microsoft.FASTER.Core/)として公開されているので、PackageReference等で追加すればOK。

他に、[Microsoft.FASTER.Server](https://www.nuget.org/packages/Microsoft.FASTER.Server/)や、[Microsoft.FASTER.Client](https://www.nuget.org/packages/Microsoft.FASTER.Client/)も存在するが、これは [FasterKVをクライアントサーバー形式で利用したい場合に使うフレームワーク](https://microsoft.github.io/FASTER/docs/remote-basics/) なので、今回は導入しない。

## ストレージデバイスインスタンスを作成する

まず、以下のコードでログを格納するディスク領域を作成する。

```csharp
// using FASTER.core;
// 独自ストレージを使用する場合、FASTER.core.IDeviceを実装したインスタンスを代わりに生成する
// ファイルパスのみ必須。
// 基本的に同じフォルダに複数ファイルを作る設計なので、複数のログファイルを扱いたい場合、別フォルダに分けるのが良い
IDevice logDevice = Devices.CreateLogDevice("[格納するファイルのパス]");
```

なお、`deleteOnClose`というオプション引数が使用可能だが、これを使用すると、後でデータを開こうとした時に挙動がおかしくなるので、検証またはテスト目的以外では設定しないこと。
また、オプション引数で`preallocateFile=true`とすると、後でFasterLogを生成する時に最初から`2^SegmentSizeBits`のファイルを確保してから、そこに書き込むという動作になる。
パフォーマンスを重視する場合はtrueにするのも手だが、その場合突然大きなファイルが作成されることになるため、注意が必要となる。

ここで生成した`IDevice`は、必ずプログラム終了時に`logDevice.Dispose()`するか、または`using`で囲むこと。

他のIDeviceの実装として、`LocalMemoryDevice`というものもあるが、[コンストラクタにConsole.Write等が仕込まれている](https://github.com/microsoft/FASTER/blob/a31b52b29e952827b4ad464674df57d9e230020a/cs/src/core/Device/LocalMemoryDevice.cs#L46-L78)等、テスト目的で作ったような印象なので、リファレンス実装あるいはテストのためのデバイスと思った方が良い。

また、[Azure Storage(page blob)を使うIDeviceの実装もある](https://www.nuget.org/packages/Microsoft.FASTER.Devices.AzureStorage/)。ただし、こちらの性能等は未検証

## FasterLogインスタンスを生成する

ストレージデバイスインスタンスを生成したら、以下のようにして、FasterLogインスタンスを生成する。

```csharp
// using FASTER.core;
// LogDeviceのみ必須
var fls = new FasterLogSettings()
{
    LogDevice = logDevice
};
using(var fl = new FasterLog(fls))
{
    // 処理
    // flインスタンスはプロセス内で使い回すこと
}
```

### FasterLogSettingsのその他項目について

FasterLogSettingsのその他項目は以下のようになる。

* PageSizeBits
    * 格納データページの基本単位
    * 各レコードは、メタデータと実データが必ず同じページに収まるように格納される
        * つまり、一レコード当たりの最大サイズがこの値に依存して決定される
        * ファイルの空間効率にも影響するので、サイズ設定は慎重に
    * 単位は**何ビット使用するか**なので、例えば8を指定したら`2^8 = 256(bytes)`となる
    * 初期値は22(`2^22 ≒ 4MB`)
* MemorySizeBits
    * オンメモリに乗せる最大データ容量
    * 単位はPageSizeBitsと同じ
    * 初期値は23(`2^23 ≒ 8MB`)
    * 最低でもPageSizeBits+1必要で、下回るとFasterLogインスタンス生成時にエラーが出る
* SegmentSizeBits
    * オンメモリに乗らないデータを格納するファイルのサイズ
    * 初期値は30(=1GB)
* LogCommitManager
    * トランザクションを管理する
    * リカバリ等も担当
    * 以前は [LocalLogCommitManager](https://github.com/microsoft/FASTER/blob/v1.9.5/cs/src/core/Index/FasterLog/LocalLogCommitManager.cs) がデフォルトだったが、今は [DeviceLogCommitCheckpointManager](https://github.com/microsoft/FASTER/blob/v1.9.5/cs/src/core/Index/CheckpointManagement/DeviceLogCommitCheckpointManager.cs) が使われている(旧来のバージョンを使うことも可能)
* LogCommitFile
    * **1.9.5時点では使われていない**
    * 出力先を変えたい場合、LogCommitManagerのインスタンスを作る必要がある
* GetMemory
    * データ読出しの時に呼ばれるコールバック関数
* LogChecksum
    * ログ整合性のためのチェックサムをどのように追加するか
    * ファイルが壊れた場合に検知ができるため、データの重要度に応じてオンにしておく
    * [本体データ+メタデータのXORを集計しているため、オーバーヘッドはそれなりに大きいと思われる](https://github.com/microsoft/FASTER/blob/ff51d3c973634d043df08cd79e6ba5a0e1ffa6c1/cs/src/core/Index/FasterLog/FasterLog.cs#L1001-L1014)
    * None=チェックサム追加をしない、PerEntry=レコードごとにチェックサムを取得する
    * デフォルト=None

### 生成されるファイル

FasterLogをnewした時点で、以下のファイルが生成される

* ログセグメントデータ: `[CreateLogDeviceで指定したファイル].[0始まり数字]`
    * データ本体が格納される
    * `preallocateFile=true`の場合、`2^[SegmentSizeBits]`bytesのサイズをアロケートしようとするので注意(デフォルト1GB)
    * ログデータが`2^[SegmentSizeBits]`を超えるたびに、新しくセグメントファイルを作成する
* トランザクションファイル: デフォルトは `log-commits/commit.0.0`
    * 論理的なアドレスの開始点、終点が書き込まれる
    * サイズは概ね一定
    * 複数のログデータで共有するとおかしなことになるので、同じディレクトリに複数ログデータを作成する場合は、デフォルト値から変更した方が良い
    * DeviceLogCommitCheckpointManager を作る場合、`log-commits`ディレクトリのベースパスを指定することができる

## データを追加する

データの追加は以下のように行う

```csharp
// FasterLog fl;
// byte[] data;
// ReadOnlySpan<byte>でも可
// Enqueueの時点ではまだ永続化はされない
long recordAddress = fl.Enqueue(data);
// ここで返ってくるaddress値は、WaitForCommit系のAPIでuntilAddressとして使用する
// コミットデータの永続化
fl.Commit(true);
```

`Commit`した時点でディスクに書き出される。
戻り値として、追加したデータの論理アドレスが取得できる。

例ではEnqueueを使用したが、これは内部的にEnqueueを成功するまで繰り返すという挙動のため、タイミングが悪いと時間がかかる場合もある。
一定回数追加を試みて、だめならエラーを出すか後でやり直すという挙動をしたい場合、`bool FasterLog.TryEnqueue(byte[] data, out var logicalAddress)`というAPIを使用する。
[Enqueueも実は内部的にTryEnqueueを使っている](https://github.com/microsoft/FASTER/blob/32b3f6e40aa500a11cc2f92f7df8ded5345c1d61/cs/src/core/Index/FasterLog/FasterLog.cs#L228-L234)。

## データを読み出す

データの読み出しは、C#8.0とそれより前でやり方が異なる。

### 共通事項

下記のように、`FasterLog.Scan([開始アドレス], [終端アドレス])`を使用する。

```csharp
// FasterLog fl;
// fl.Scan([論理開始アドレス], [論理終端アドレス])という風にして指定する
using(FastLogScanIterator iter = fl.Scan(fl.CommittedBeginAddress, fl.CommittedUntilAddress))
{
    // enumeratorで走査
}
```

ここでいう開始アドレスと終端は、コミット済みの全てのログを見るなら`FasterLog.CommittedBeginAddress`と`FasterLog.CommittedUntilAddress`をそれぞれ指定すると良い。
全てのログを見たくない場合は、終端アドレスに、`[開始アドレス] + [適当なバイト数]`を指定する。

走査中に、現在見ているログの論理アドレスを知りたい場合は、`FastLogScanIterator.CurrentAddress`、次のエントリのアドレスを知る場合は、`FastLogScanIterator.NextAddress`を使用する。

### 非同期(C#8.0)

`IAsyncEnumerable`を使用する。

```csharp
// FasterLog fl;
// fl.Scan([論理開始アドレス], [論理終端アドレス])という風にして指定する
using(FastLogScanIterator iter = fl.Scan(fl.CommittedBeginAddress, fl.CommittedUntilAddress))
{
    // dataの型はbyte[]
    // lenはデータ長(bytes)
    // 2019.11.18では二つだけだが、最新ソースでは更に long currentAddress も追加になる模様
    // https://github.com/microsoft/FASTER/commit/bf657635374873958d96b31db1299b58ef9a17b1
    await foreach(var (data, len, currentAddress, nextAddress) in iter.GetAsyncEnumerable())
    {
        // データの参照
    }
}
```

`FastLogScanIterator.GetAsyncEnumerable(CancellationToken ct = default)`では、foreachの要素に単純にnewされた`byte[]`を受け取るが、代わりに`System.Buffers.MemoryPool<byte>`のインスタンスを渡すと、メモリプール経由でバッファの確保を行うため、アロケーションが減らせる。
ただし、`IMemoryOwner<byte>`自体のアロケーションは避けられないため、ゼロではない。
また、使い終わった`IMemoryOwner<byte>`はDisposeを行わないと、メモリリークの原因になる。

### 非同期(C#7.x以前)

`FastLogScanIterator.[GetNext,NextAddress,WaitAsync]`等を駆使する

```csharp
// FasterLog fl;
using(FastLogScanIterator iter = fl.Scan(fl.CommittedBeginAddress, fl.CommittedUntilAddress))
{
    // 終端ではnextAddressが-1になる
    while(iter.NextAddress >= 0)
    {
        await iter.WaitAsync();
        // データを取り出すまでループと待機を行う
        // 引数は、データ本体、データ長、現在のアドレスの三つ
        while(iter.GetNext(out var entry, out var length, out var currentAddress, out var nextAddress))
        {
            // データの参照
        }
    }
}
```

## データの削除

データの削除には、`FasterLog.TruncateUntil(long untilAddress)`または`FasterLog.TruncateUntilPageStart(long untilAddress)`を使用する。

### TruncateUntil

`TruncateUntil`は**データの開始アドレス(BeginAddress)から、指定されたアドレス直前までのデータを削除する**という挙動である。
注意点として、**レコード境界ではない中途半端なアドレスを指定すると、次回のScan時にエラーが出る**という仕様がある。

* [関連github issue](https://github.com/microsoft/FASTER/issues/191#issuecomment-548833464)

回避するには、末尾アドレス(FasterLog.TailAddress)を指定するか、下記のようにScanの途中で得たNextAddressで、正確なレコード境界を取得して指定するというやり方がある

```csharp
// FasterLog fl;
long untilAddress = 0;
using(var iter = fl.Scan(fl.BeginAddress, [終端]))
{
    await foreach(var x in iter.GetAsyncEnumerable())
    {
        // 処理
        untilAddress = iter.NextAddress;
    }
}
fl.TruncateUntil(untilAddress);
// 最後にCommitすると変更が反映される
fl.Commit(true);
```

より安全に、かつ大雑把に消したい場合は、後述の`TruncateUntilPageStart`を使用する

### TruncateUntilPageStart

`TruncateUntilPageStart`は**データの開始アドレスから、指定されたアドレスに紐づくページの直前までを消去する**という挙動である。
レコードはページをまたぐことは仕様上ないため、`TruncateUntil`で起こったような問題は起きない。
ただし、正確な消去はできないため、大雑把にログローテーション等をしたい場合に使うと良いだろう

# パフォーマンス上の注意点

追記、削除する時は、操作後にコミットを行い永続化する必要があるが、コミットはFasterLogの中で最もコストのかかる処理だという事を念頭に置いた方が良い。しかし、コミットしないとデータが永続化されないので、信頼性が下がる。悩ましいところである。
つまり、より高速にデータを処理したい場合は、**信頼性を下げずにいかにコミット回数を減らすか**ということを考える。

ではどうすればいいか。以下のようなやり方を一例として示そうと思う。

## Commitタスクを独立させる

箇条書きにすると以下のような動作になる

* 追記タスクを並列化する
* 追記タスクは、自分の書き込みが完了するまでWaitForCommitAsyncで待機する
    * 要件による
* 追加で、一つだけひたすらコミットだけするタスクを作成する
* 追記タスクは、コミットタスクに自分が追記したレコードのアドレスを渡す
* コミットタスクは、現在のコミット済み終端アドレスと受け取ったレコードアドレスを比較して、未コミットと判断したら、コミットを行う

タスク間のデータ受け渡しは、`System.Threading.Channels`が使えると思う。

### 追加されたデータが永続化されるまで待機する

さて、このやり方では、追記とコミットが別タスクで行われる状態になる。しかし、要件によっては、データ消失を可能な限り避けるため、自分で追加したデータが、確実に永続化されたかどうか確認する必要が出てくる。
そこで、`FasterLog.WaitForCommitAsync(long address, CancellationToken ct)`を使用する。
引数には`FasterLog.Enqueue`で得たアドレスを指定する。
これを使うと、指定されたアドレスがコミットされたと判断されるまで(`address <= CommittedUntilAddress`になるまで)待機が発生する。

### コード例

具体的には、少々長くなるが以下のようなコードになる。

```csharp
using System;
using System.Threading;
using System.Threading.Tasks;
using System.Threading.Channels;
using FASTER.core;
using System.IO;
using System.Linq;

namespace fasterlabs
{
    static class FasterLogCommitTest
    {
        static long EnqueueData(long value, FasterLog fl)
        {
            Span<long> data = stackalloc long[1];

            if (fl.TryEnqueue(System.Runtime.InteropServices.MemoryMarshal.AsBytes(data), out var logicalAddress))
            {
                return logicalAddress;
            }
            else
            {
                return -1;
            }
        }
        public static async ValueTask DoTest(int TaskNum)
        {
            const long TotalCount = 100000;
            // ensure using cleared data 
            if (File.Exists("logcommittest.log.0"))
            {
                File.Delete("logcommittest.log.0");
            }
            if (Directory.Exists("log-commits"))
            {
                Directory.Delete("log-commits");
            }
            var log = Devices.CreateLogDevice("logcommittest.log");
            var channel = Channel.CreateUnbounded<long>();
            using (var fl = new FasterLog(new FasterLogSettings() { LogDevice = log }))
            {
                var sw = new System.Diagnostics.Stopwatch();
                sw.Start();
                using (var csrc = new CancellationTokenSource(1000 * 240))
                {
                    await Task.WhenAll(
                        Task.WhenAll(Enumerable.Range(0, TaskNum).Select(async idx =>
                        {
                            // データを追加するタスク
                            long logicalAddress = 0;
                            try
                            {
                                for (int i = 0; i < TotalCount / TaskNum; i++)
                                {
                                    logicalAddress = EnqueueData(i + idx * TotalCount, fl);
                                    await channel.Writer.WriteAsync(logicalAddress, csrc.Token).ConfigureAwait(false);
                                    await fl.WaitForCommitAsync(logicalAddress, csrc.Token).ConfigureAwait(false);
                                    // Console.WriteLine($"{idx}, {i}, {logicalAddress}");
                                }
                            }
                            catch (Exception e)
                            {
                                Console.WriteLine($"producer error({idx}, {logicalAddress}, {fl.CommittedUntilAddress}, {fl.TailAddress}): {e}");
                            }
                            // Console.WriteLine($"exit producer({idx}, {sw.Elapsed})");
                        })).ContinueWith(t => channel.Writer.Complete()),
                        Task.Run(async () =>
                        {
                            // コミットする方のタスク
                            int commitCount = 0;
                            try
                            {
                                while (true)
                                {
                                    if (!await channel.Reader.WaitToReadAsync(csrc.Token).ConfigureAwait(false))
                                    {
                                        break;
                                    }
                                    while (channel.Reader.TryRead(out var untiladdr))
                                    {
                                        if (fl.CommittedUntilAddress != fl.TailAddress)
                                        {
                                            fl.Commit(true);
                                            // await fl.CommitAsync(csrc.Token).ConfigureAwait(false);
                                            commitCount++;
                                        }
                                    }
                                }
                            }
                            catch (Exception e)
                            {
                                Console.WriteLine($"consumer error:{e}");
                            }
                            Console.WriteLine($"exit consumer({commitCount})");
                        }).ContinueWith(t =>
                        {
                            if(fl.CommittedUntilAddress != fl.TailAddress)
                            {
                                Console.WriteLine($"last commit");
                                fl.Commit(true);
                            }
                        })
                    ).ConfigureAwait(false);
                    sw.Stop();
                    Console.WriteLine($"Multi({TotalCount}, {TaskNum}): {sw.Elapsed}, iops = {(TotalCount * 1000) / sw.Elapsed.TotalMilliseconds}");
                }
            }
            log.Close();
        }
    }
}
```

バージョン2019.11.18.1より前のバージョンでは、`CommitAsync`すると`WaitForCommitAsync`とスレッドプールの消費が競合して、デッドロック状態になる場合があるので注意すること。([該当github issue](https://github.com/microsoft/FASTER/issues/199))

# 終りに

今回はログ向けストレージ機能を持つFasterLogを紹介した。実際制約もあるので、あらゆる場面で使用できるわけではないが、それでも他には無い特徴を持っているため、役に立つ場面では役に立つと思われる。
機会があれば、コミット回数や並列数を変えて性能テスト等を行ってみたい。

また、データ検索についてはComplete周り等、もう少し掘り下げられそうな所があるので、別記事にするか、あるいはこの記事に追記したい。

## 参考リンク

* [githubプロジェクトページ](https://github.com/microsoft/FASTER)
* [github.ioページ](https://microsoft.github.io/FASTER/)
* [MSによる調査報告ページ](https://www.microsoft.com/en-us/research/project/FASTER/)
* [FasterKV論文についての日本語解説](https://scrapbox.io/nikezono/FASTER)