聊聊FASTER和程序內混合快取

最近有一個朋友問我這樣一個問題：

我的業務依賴一些資料，因為資料庫存取慢，我把它放在Redis裡面，不過還是太慢了，有什麼其它的方案嗎？

其實這個問題比較簡單的是吧？Redis其實屬於網路儲存，我對照下面的這個表格，可以很容易的得出結論，既然網路儲存的速度慢，那我們就可以使用記憶體RAM儲存，把放Redis裡面的資料給放記憶體裡面就好了。

操作	速度
執行指令	1/1,000,000,000 秒 = 1 納秒
從一級快取讀取資料	0.5 納秒
分支預測失敗	5 納秒
從二級快取讀取資料	7 納秒
使用Mutex加鎖和解鎖	25 納秒
從主記憶體(RAM記憶體)中讀取資料	100 納秒
在1Gbps速率的網路上傳送2Kbyte的資料	20,000 納秒
從記憶體中讀取1MB的資料	250,000 納秒
磁頭移動到新的位置(代指機械硬碟)	8,000,000 納秒
從磁碟中讀取1MB的資料	20,000,000 納秒
傳送一個封包從美國到歐洲然後回來	150 毫秒 = 150,000,000 納秒

提出這個方案以後，接下來就遇到了另外一個問題：

但是資料比我應用的記憶體大，這怎麼辦呢？

筆者突然回想起來，似乎從來沒有考慮過資料比應用大是該怎麼處理，面對這種效能問題，最方便的方案就是直接擴容，在基礎設施完備的公司，一般只需要提交一個工單"8G->64G"就能解決這個問題，這種成本似乎不是該考慮的事情。

不過對於有一些朋友的公司，因為多個方面的原因（主要還是預算），沒有辦法擴容機器。或者體量非常大，每個範例擴容1GB記憶體，數萬個容器就是非常大的開銷。

於是我們可以採用一些記憶體+磁碟的快取方式，因為現在大多數都是SSD磁碟，伺服器NVME順序讀寫速度早已突破7GB/s，隨機讀寫早已突破100K IOPS，而且還可以通過RAID0進一步增加效能。

最簡單的就是我們在本地跑一個Sqlite，然後將資料快取到本地磁碟中，但是Sqlite並不是專業的KV Store，讀寫效能並不是特別好。KV-Store的話還有基於LSM-Tree的RocksDB、LevelDB等等。

不過那些KV都是C++的實現，在C#中整合需要Bind和P/Invoke，需要自己編譯比較麻煩；這讓我想起了多年前微軟開源FASTER專案。

FASTER

專案如其名，FASTER是目前藍星最快的KV-Store（開源的專案中），根據論文中的效能表現，它可以實現1.6億次操作/秒，當然這一切也是有代價的，就是它目前只支援簡單的幾種操作，Read、Upser、RMW和Delete，不過這已經夠了，畢竟在快取場景這些操作就足夠了。

在它2018年開源和論文發表時，我就有關注，不過當時它的API易用性不夠，另外C#版本存在一些問題，所以一直都沒有體驗它，現在它經過幾年的迭代，易用性得到了很大的提高，一些之前存在的問題也已經修復。

筆者簡單的體驗了一下它，可以說這是我使用過比較複雜的的KV-Store了，從它的API使用風格來說，它的設計的目的只有一個，那就是效能。

簡單體驗FASTER

具體的使用詳情大家可以直接看官方檔案，Github開源地址和檔案在文末給出，需要詳細瞭解的可以檢視檔案。首先就是安裝NuGet包：

<PackageReference Include="Microsoft.FASTER.Core" Version="2.0.22" />

然後下面簡單的幾行程式碼就可以把Demo執行起來了，它支援In-Memroy(記憶體模式)和混合模式。和對資料庫操作需要建立連結一樣，它的維度是session，注意這個session就代表一個執行緒對它進行讀寫，如果多執行緒場景，那麼每個執行緒對應的session應該要不一致，要單獨建立，當然我們也可以把它池化。

// 記憶體模式
using var fasterKvSetting = new FasterKVSettings<string, string>(null);

// 混合模式
using var fasterKvSetting = new FasterKVSettings<long, byte[]>("./faster-query");

// 建立fasterKv Store
using var fasterKv = new FasterKV<long, byte[]>(fasterKvSetting);


var session = fasterKv.For(new SimpleFunctions<long, byte[]>()).NewSession<SimpleFunctions<long, byte[]>>();

// 準備一個utf-8字元
var str = "yyds"u8.ToArray();

// 寫入
session.Upsert(1024, str);

// 讀取
var result = session.Read(1024);

Console.WriteLine($"{Encoding.UTF8.GetString(result.output)}");

輸出結果就是yyds。

另外也有豐富的引數可以調整記憶體佔用，以下列出了幾個相關的記憶體佔用引數,當然，更低的記憶體使用，意味著更多的使用磁碟空間，效能也就會下降的越多：

• IndexSize: 主Hash索引的大小，以位元組為單位(四捨五入為2的冪)。最小大小為64位元組。
• MemorySize: 表示混合紀錄檔的記憶體部分的大小(四捨五入為2的冪)。注意，如果紀錄檔指向類鍵或值物件，則此大小僅包括對該物件的8位元組參照。紀錄檔的舊部分溢位到儲存中。
• LogSettings: 這些是幾個與紀錄檔相關的設定，例如頁面大小的 PageSize。
• ReadCacheEnable: 是否為儲存提供並啟用了單獨的讀快取。
• ReadCacheMemorySize: 讀快取記憶體佔用大小，
• ReadCachePageSize: 讀快取頁面大小

跑個分試試

那麼FASTER到底有多強呢？筆者構建了一個測試，和我們常用的ConcurrentDictionary做比較，那是我能找到在.NET平臺上差不多的東西，按道理來說我們應該和RocksDB、LevelDB來比較。

ConcurrentDictionary應該是.NET平臺上效能最好的純記憶體KV Store了，嚴格來說它和FASTER並不是不能相提並論，而且受制於筆電的效能，無法做大數量的測試，要知道FASTER的場景是大型資料集。

為了方便的統計記憶體佔用，我構建了一個結構體型別，如下所示，它應該佔用32位元組：

Add測試

我分別構建了不同的場景來測試Add效能，測試的構建如下所示：

• ConcurrentDictionary 單執行緒模式
• FasterKV 記憶體+磁碟混合 10~100%記憶體佔用模式
• FasterKV 純記憶體模式
• 以上模式的6個執行緒並行存取模式

程式碼如下所示：

[GcForce]
[Orderer(SummaryOrderPolicy.FastestToSlowest)]
[MemoryDiagnoser]
[HtmlExporter]
public class AddBench
{
    private const int ThreadCount = 6;
    private const int NumCount = 200_0000;

    private ConcurrentDictionary<long, Data> _concurrent;
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static async Task FasterInternal(double percent, bool inMemory = false, bool multi = false)
    {
        FasterKVSettings<long, Data> kvSetting;

        if (inMemory)
        {
            kvSetting = new FasterKVSettings<long, Data>(null);
        }
        else
        {
            // 總計記憶體大小 總數 * (key + 每個Data需要佔用的記憶體)
            var dataByte = NumCount * (Unsafe.SizeOf<Data>() + 8 + 8);
        
            // 計算memorySize 計劃只使用{percent * 100}%的記憶體 需要是2的次冪
            var memorySizeBits = (int) Math.Ceiling(Math.Log2(dataByte * percent));
        
            // 根據數量計算IndexSize 需要是2的次冪
            var numBucketBits = (int) Math.Ceiling(Math.Log2(NumCount));
            kvSetting = new FasterKVSettings<long, Data>("./faster-add", deleteDirOnDispose: true)
            {
                IndexSize = 1L << numBucketBits,
                MemorySize = 1L << memorySizeBits
            };
        
            // 不分頁
            kvSetting.PageSize = kvSetting.MemorySize;
        }

    
        using var fkv = new FasterKV<long, Data>(kvSetting);
        if (multi)
        {
            await FasterMultiThread(fkv);
        }
        else
        {
            FasterSingleThread(fkv);
        }
        
        kvSetting.Dispose();
    }
    
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static void FasterSingleThread(FasterKV<long, Data> fkv)
    {
        using var session = fkv.For(new SimpleFunctions<long, Data>()).NewSession<SimpleFunctions<long, Data>>();
        for (int i = 0; i < NumCount; i++)
        {
            session.Upsert(i, new Data());
        }

        session.CompletePending(true);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static async Task FasterMultiThread(FasterKV<long, Data> fkv)
    {
        const int perCount = NumCount / ThreadCount;
        var tasks = new Task[ThreadCount];
        for (var i = 0; i < ThreadCount; i++)
        {
            var i1 = i;
            var session = fkv.For(new SimpleFunctions<long, Data>())
                .NewSession<SimpleFunctions<long, Data>>();
            tasks[i] = Task.Run(() =>
            {
                var j = i1 * perCount;
                var length = j + perCount;
                for (; j < length; j++)
                {
                    session.Upsert(j, new Data());
                }
                session.CompletePending(true);
            });
        }

        await Task.WhenAll(tasks);
    }

    [Benchmark]
    public async Task Faster_Hybrid_10per_Memory_Add()
    {
        await FasterInternal(0.10);
    }

    [Benchmark]
    public async Task Faster_Hybrid_25per_Memory_Add()
    {
        await FasterInternal(0.25);
    }

    [Benchmark]
    public async Task Faster_Hybrid_50per_Memory_Add()
    {
       await FasterInternal(0.50);
    }

    [Benchmark]
    public async Task Faster_Hybrid_90per_Memory_Add()
    {
       await  FasterInternal(0.90);
    }

    [Benchmark]
    public async Task Faster_Hybrid_100per_Memory_Add()
    {
       await FasterInternal(1.0);
    }

    [Benchmark]
    public async Task Faster_Default_InMemory_Add()
    {
        await FasterInternal(0, true);
    }
    
    [Benchmark]
    public async Task Faster_Hybrid_10per_Memory_Multi_Add()
    {
        await FasterInternal(0.10, multi: true);
    }

    [Benchmark]
    public async Task Faster_Hybrid_25per_Memory_Multi_Add()
    {
        await FasterInternal(0.25, multi: true);
    }
    
    [Benchmark]
    public async Task Faster_Hybrid_90per_Memory_Multi_Add()
    {
        await  FasterInternal(0.90, multi: true);
    }

    [Benchmark]
    public async Task Faster_Hybrid_100per_Memory_Multi_Add()
    {
        await FasterInternal(1.0, multi: true);
    }
    
    [Benchmark]
    public async Task Faster_Hybrid_50per_Memory_Multi_Add()
    {
        await FasterInternal(0.50, multi: true);
    }
    
    [Benchmark]
    public async Task Faster_Default_InMemory_Multi_Add()
    {
        await FasterInternal(0, true, true);
    }
    
    [Benchmark]
    public void Concurrent_Add()
    {
        _concurrent = new ConcurrentDictionary<long, Data>(1, NumCount);
        for (long i = 0; i < NumCount; i++)
        {
            _concurrent.TryAdd(i, new Data());
        }
    }
    
    [Benchmark]
    public async Task Concurrent_Multi_Add()
    {
        const int perCount = NumCount / ThreadCount;
        var tasks = new Task[ThreadCount];
        _concurrent = new ConcurrentDictionary<long, Data>(1, NumCount);
        for (var i = 0; i < ThreadCount; i++)
        {
            var i1 = i;
            tasks[i] = Task.Run(() =>
            {
                var j = i1 * perCount;
                var length = j + perCount;
                for (; j < length; j++)
                {
                    _concurrent.TryAdd(j, new Data());
                }
            });
        }

        await Task.WhenAll(tasks);
    }
}

結果如下所示：

• FASTER的多執行緒寫入效能非常不錯，而且似乎使用記憶體的多少對寫入效能影響不是很大
• 單執行緒的話FASTER整體是不如ConcurrentDictionary的
• FASTER確實是能節省記憶體，設定混合模式時，相較ConcurrentDictionary節省60%的記憶體
  

Query測試

Query測試我一共建立了100W條記錄，然後測試瞭如下場景:

• 單執行緒讀取
• 多執行緒讀取

[GcForce]
[Orderer(SummaryOrderPolicy.FastestToSlowest)]
[MemoryDiagnoser]
[HtmlExporter]
public class QueryBench
{
    public const int Threads = 6;
    public const int NumCount = 100_0000;

    private static readonly Random Random = new(NumCount);
    private static readonly long[] RandomIndex =
        Enumerable.Range(0, 1000).Select(i => Random.NextInt64(0, (int)(NumCount * 0.10))).ToArray();

    private static readonly ConcurrentDictionary<long, Data> Concurrent;
    
    private static readonly FasterKV<long, Data> FasterKvHybrid;
    private static readonly FasterKV<long, Data> FasterKvInMemory;
    
    private static readonly ClientSession<long, Data, Data, Data, Empty, SimpleFunctions<long, Data>> HybridSession;
    private static readonly ClientSession<long, Data, Data, Data, Empty, SimpleFunctions<long, Data>> InMemorySession;

    static QueryBench()
    {
        // 初始化字典
        GC.Collect();
        var heapSize = GC.GetGCMemoryInfo().HeapSizeBytes;
        Concurrent = new ConcurrentDictionary<long, Data>(Threads, NumCount);
        for (long i = 0; i < NumCount; i++)
        {
            Concurrent.TryAdd(i, new Data());
        }
        Helper.PrintHeapSize("Concurrent", heapSize);


        // 初始化混合FasterKv
        heapSize = GC.GetGCMemoryInfo().HeapSizeBytes;
        // 總計記憶體大小 總數 * (key + 每個Data需要佔用的記憶體)
        var dataByte = NumCount * (Unsafe.SizeOf<Data>() + 8 + 8);
        
        // 計算memorySize 計劃只使用50%的記憶體 需要是2的次冪
        var memorySizeBits = (int) Math.Ceiling(Math.Log2(dataByte * 0.5));
        
        // 根據數量計算IndexSize 需要是2的次冪
        var numBucketBits = (int) Math.Ceiling(Math.Log2(NumCount));
        var kvHybridSetting = new FasterKVSettings<long, Data>("./faster-query", deleteDirOnDispose: true)
        {
            IndexSize = 1L << numBucketBits,
            MemorySize = 1L << memorySizeBits
        };
        
        // 32分頁
        kvHybridSetting.PageSize = kvHybridSetting.MemorySize / 32;
        
        Console.WriteLine($"memorySizeBits:{memorySizeBits},numBucketBits:{numBucketBits},{kvHybridSetting}");
        FasterKvHybrid = new FasterKV<long, Data>(kvHybridSetting);

        HybridSession = FasterKvHybrid.For(new SimpleFunctions<long, Data>()).NewSession<SimpleFunctions<long, Data>>();
        for (long i = 0; i < NumCount; i++)
        {
            HybridSession.Upsert(i, new Data());
        }

        HybridSession.CompletePending(true);
        Helper.PrintHeapSize("Faster Hybrid", heapSize);
        
        
        // 初始化In Memory
        GC.Collect();
        heapSize = GC.GetGCMemoryInfo().HeapSizeBytes;
        var inMemorySetting = new FasterKVSettings<long, Data>(null);
        FasterKvInMemory = new FasterKV<long, Data>(inMemorySetting);
        InMemorySession = FasterKvInMemory.For(new SimpleFunctions<long, Data>()).NewSession<SimpleFunctions<long, Data>>();
        for (long i = 0; i < NumCount; i++)
        {
            InMemorySession.Upsert(i, new Data());
        }
        InMemorySession.CompletePending(true);
        Helper.PrintHeapSize("Faster In Memory", heapSize);
    }
    
    [Benchmark]
    public async Task Faster_Hybrid_Multi_Query()
    {
        var tasks = new Task[Threads];
        for (int i = 0; i < Threads; i++)
        {
            var session = FasterKvHybrid.For(new SimpleFunctions<long, Data>())
                .NewSession<SimpleFunctions<long, Data>>();
            tasks[i] = Task.Run(() =>
            {
                Data data = default;
                for (int j = 0; j < RandomIndex.Length; j++)
                {
                    session.Read(ref RandomIndex[j], ref data);
                }
            });
        }

        await Task.WhenAll(tasks);
    }
    
    [Benchmark]
    public void Faster_Hybrid_1Thread_Query()
    {
        Data data = default;
        for (long j = 0; j < RandomIndex.Length; j++)
        {
            HybridSession.Read(ref RandomIndex[j], ref data);
        }
    }
    
    [Benchmark]
    public async Task Faster_InMemory_Multi_Query()
    {
        var tasks = new Task[Threads];
        for (int i = 0; i < Threads; i++)
        {
            var session = FasterKvInMemory.For(new SimpleFunctions<long, Data>())
                .NewSession<SimpleFunctions<long, Data>>();
            tasks[i] = Task.Run(() =>
            {
                Data data = default;
                for (int j = 0; j < RandomIndex.Length; j++)
                {
                    session.Read(ref RandomIndex[j], ref data);
                }
            });
        }

        await Task.WhenAll(tasks);
    }
    
    [Benchmark]
    public void Faster_InMemory_Query()
    {
        Data data = default;
        for (long j = 0; j < RandomIndex.Length; j++)
        {
            InMemorySession.Read(ref RandomIndex[j], ref data);
        }
    }
    
    [Benchmark]
    public void Concurrent_Query()
    {
        for (long j = 0; j < RandomIndex.Length; j++)
        {
            Concurrent.TryGetValue(RandomIndex[j], out _);
        }
    }

    [Benchmark]
    public async Task Concurrent_Multi_Query()
    {
        var tasks = new Task[Threads];
        for (int i = 0; i < Threads; i++)
        {
            tasks[i] = Task.Run(() =>
            {
                for (long j = 0; j < RandomIndex.Length; j++)
                {
                    Concurrent.TryGetValue(RandomIndex[j], out _);
                }
            });
        }

        await Task.WhenAll(tasks);
    }
    
}

結果如下所示，這裡是100%讀的場景：

• 似乎記憶體不足對於FASTER的讀效能影響挺大的，這也是必然的結果，畢竟SSD再快也沒有記憶體快
• 另外根據我的測試結果來說，FASTER純記憶體模式在100%純讀取的場景沒有Concurrent那麼快
  

官方測試結果

由於我的測試結果不是很準確，我又繼續查詢有沒有其它的效能評測的結果，並沒有找到什麼有價值的。於是從論文和Wiki中找到了一些資料，和大家解讀一下我比較感興趣的部分。

Faster論文

這是在Faster 2018年的論文中提到的一些，如下所示：
https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf

上圖是單執行緒情況下，跑YCSB-A(uniform)資料集和YCSB-A(Zipf)資料集的結果。可以看到在單執行緒的場景，FASTER速度遠超於同類Intel TBB、MassTree、RocksDB等資料庫。

文中的0:100、50:50、100:0是代表全寫、50%寫50讀、全讀的場景。另外FASTER支援Read-Modify-Write，RMW就是代表進行這個操作的效能。

Yahoo! Cloud Serving Benchmark (YCSB) 是一個Java語言實現的主要用於雲端或者伺服器端的資料庫效能測試工具，其內部涵蓋了常見的NoSQL資料庫產品，如Cassandra、MongoDB、HBase、Redis等等。

在多執行緒的情況下，FASTER的讀效能達到了驚人的1.6億/s。

上圖是在單核和雙核的更新效能資料，可以看到FASTER藍色的線是遠超同類產品，特別是線上程數變多以後，其它都是下降趨勢，它是程上升趨勢。

上圖是表示，分別在使用5GB~45GB記憶體載入27GB資料時的吞吐量，分別是50%的讀寫，和100%的寫。可以看到寫效能幾乎不受記憶體大小的影響，這也佐證了我的測試結果。

C# FasterKV效能測試

這是翻閱微軟Github專案時，看到專門針對於C#的FasterKV和ConcurrentDictionary的測試。不過它只有純記憶體模式的測試，並不包含記憶體+硬碟混合模式。
https://github.com/microsoft/FASTER/wiki/Performance-of-FASTER-in-C%23

這裡它使用了一臺36核72執行緒的512GB伺服器進行測試。分別測試大型資料集(2.5億個鍵)和小型資料集(250萬個鍵)進行實驗。

巨量資料集場景

上圖是大型資料集的載入速度，可以發現FASTER的載入速度確實很快，是ConcurrentDictionary的好10~50倍，效能還在上漲。

上圖是100%寫入時的場景，隨著執行緒數量的增加還在上漲，遠超ConcurrentDictionary，這和我們的測試結果相符合。

上圖是分別進行50%讀寫的場景，可以發現吞吐量還是非常的不錯的。

如果是100%純度的場景，還是ConcurrentDictionary會更好。不過這也不是FASTER的適用場景，因為在這樣的工作負載中不存在並行瓶頸，也不存在對記憶體的寫操作。這兩個系統都受到讀取快取失敗次數的限制，並具有相似的效能。

上圖顯示了來自上面72個執行緒的資料，以 x 軸上的讀取百分比表示。當您的工作負載中涉及到一小部分更新時，FASTER 提供了數量級更好的效能。隨著非常高的讀取百分比超過90% ，兩個系統的效能開始像預期的那樣趨於一致。

Int64型別的Key

因為ConcurrentDictionary對(Int32、Int64)型別有特殊的優化，所以將Key的型別替換為Int64做了下面的測試。

可以看到(Int32、Int64)型別確實讓ConcurrentDictionary更快了，不過在有寫入操作的場景，還是FASTER更勝一籌。

這也解釋了一些我們上面的測試中，為什麼ConcurrentDictionary在讀場景那麼快的原因之一，就是我們用了Int64作為Key。

小資料集場景

這個場景我就不解讀了，和巨量資料集場景表現基本一致。

總結

通過對FASTER的測試和翻閱論文，從目前的結果來說，在以下單機場景比較適合使用FASTER：

• 只需要簡單的Read、Write和Read-Modify-Write的場景
• 非100%讀取操作的場景，這種場景由於沒有鎖爭用，FASTER不如字典

另外FASTER也提供了Server版本，可以通過網路存取。另外在我的測試中，讀取效能和官方測試有較大的出入，感覺是使用方法和引數上出了問題，因為FASTER整體還是比較複雜，筆者需要更多的時間去了解原理和測試。

回到最開始的那個問題，FASTER可以作為記憶體+磁碟程序內快取使用嗎？

我的答案是可以，它雖然比不上純記憶體的ConcurrentDictionary，但是有著遠超RocksDB等同類KV Store的效能。不過它不適合100%讀的快取，最好是那些既有讀，又有寫的場景；如果需要100%讀，可能我們需要看看其它的工具是否能滿足我們的需求。

參考文獻及附錄

• https://microsoft.github.io/FASTER/docs/fasterkv-basics/
• https://github.com/microsoft/FASTER/wiki/Performance-of-FASTER-in-C%23
• https://www.microsoft.com/en-us/research/uploads/prod/2018/03/faster-sigmod18.pdf
• https://blog.csdn.net/weixin_43705457/article/details/123133324