聊聊FASTER和进程内混合缓存

时间:2022-11-15 10:11:35

最近有一个朋友问我这样一个问题:

我的业务依赖一些数据,因为数据库访问慢,我把它放在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,不过这已经够了,毕竟在缓存场景这些操作就足够了。
聊聊FASTER和进程内混合缓存

在它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字节:
聊聊FASTER和进程内混合缓存

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%的内存
    聊聊FASTER和进程内混合缓存

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那么快
    聊聊FASTER和进程内混合缓存

官方测试结果

由于我的测试结果不是很准确,我又继续查找有没有其它的性能评测的结果,并没有找到什么有价值的。于是从论文和Wiki中找到了一些数据,和大家解读一下我比较感兴趣的部分。

Faster论文

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

聊聊FASTER和进程内混合缓存
上图是单线程情况下,跑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和进程内混合缓存
在多线程的情况下,FASTER的读性能达到了惊人的1.6亿/s。

聊聊FASTER和进程内混合缓存
上图是在单核和双核的更新性能数据,可以看到FASTER蓝色的线是远超同类产品,特别是在线程数变多以后,其它都是下降趋势,它是程上升趋势。

聊聊FASTER和进程内混合缓存
上图是表示,分别在使用5GB~45GB内存加载27GB数据时的吞吐量,分别是50%的读写,和100%的写。可以看到写性能几乎不受内存大小的影响,这也佐证了我的测试结果。

C# FasterKV性能测试

这是翻阅微软Github项目时,看到专门针对于C#的FasterKV和ConcurrentDictionary的测试。不过它只有纯内存模式的测试,并不包含内存+硬盘混合模式。
https://github.com/microsoft/FASTER/wiki/Performance-of-FASTER-in-C%23#introduction

聊聊FASTER和进程内混合缓存
这里它使用了一台36核72线程的512GB服务器进行测试。分别测试大型数据集(2.5亿个键)和小型数据集(250万个键)进行实验。

大数据集场景

聊聊FASTER和进程内混合缓存
上图是大型数据集的加载速度,可以发现FASTER的加载速度确实很快,是ConcurrentDictionary的好10~50倍,性能还在上涨。

聊聊FASTER和进程内混合缓存
上图是100%写入时的场景,随着线程数量的增加还在上涨,远超ConcurrentDictionary,这和我们的测试结果相符合。

聊聊FASTER和进程内混合缓存
上图是分别进行50%读写的场景,可以发现吞吐量还是非常的不错的。

聊聊FASTER和进程内混合缓存
如果是100%纯度的场景,还是ConcurrentDictionary会更好。不过这也不是FASTER的适用场景,因为在这样的工作负载中不存在并发瓶颈,也不存在对内存的写操作。这两个系统都受到读取缓存失败次数的限制,并具有相似的性能。

聊聊FASTER和进程内混合缓存
上图显示了来自上面72个线程的数据,以 x 轴上的读取百分比表示。当您的工作负载中涉及到一小部分更新时,FASTER 提供了数量级更好的性能。随着非常高的读取百分比超过90% ,两个系统的性能开始像预期的那样趋于一致。

Int64类型的Key

因为ConcurrentDictionary对(Int32、Int64)类型有特殊的优化,所以将Key的类型替换为Int64做了下面的测试。

聊聊FASTER和进程内混合缓存

可以看到(Int32、Int64)类型确实让ConcurrentDictionary更快了,不过在有写入操作的场景,还是FASTER更胜一筹。

这也解释了一些我们上面的测试中,为什么ConcurrentDictionary在读场景那么快的原因之一,就是我们用了Int64作为Key。

小数据集场景

这个场景我就不解读了,和大数据集场景表现基本一致。

聊聊FASTER和进程内混合缓存
聊聊FASTER和进程内混合缓存
聊聊FASTER和进程内混合缓存

总结

通过对FASTER的测试和翻阅论文,从目前的结果来说,在以下单机场景比较适合使用FASTER:

  • 只需要简单的Read、Write和Read-Modify-Write的场景
  • 非100%读取操作的场景,这种场景由于没有锁争用,FASTER不如字典

另外FASTER也提供了Server版本,可以通过网络访问。另外在我的测试中,读取性能和官方测试有较大的出入,感觉是使用方法和参数上出了问题,因为FASTER整体还是比较复杂,笔者需要更多的时间去了解原理和测试。

回到最开始的那个问题,FASTER可以作为内存+磁盘进程内缓存使用吗?

我的答案是可以,它虽然比不上纯内存的ConcurrentDictionary,但是有着远超RocksDB等同类KV Store的性能。不过它不适合100%读的缓存,最好是那些既有读,又有写的场景;如果需要100%读,可能我们需要看看其它的工具是否能满足我们的需求。

参考文献及附录