从kv存储器缓存元数据的最佳方法

Question

目前，我们有一个系统，元数据将存储在一个kv存储集群中。我们只需通过使用protobuf序列化应用程序元数据来存储它，然后发送到kv集群。随着系统变得越来越大，获取元数据本身就变得非常昂贵。因此，我们开发了一个内存元缓存组件，简单地说是一个LRU缓存，缓存的项就是protobuf对象。最近，我们面对一些挑战：

• 并发读写似乎是一个大问题:当我们向系统中添加新数据时，我们也需要更新缓存，因此我们需要部分锁定缓存的一部分，以确保可重复读取，这会给缓存带来很高的锁争用。

• 缓存随着时间的推移越来越大。

我在想，也许我们的缓存设计不够好，并考虑使用第三方库，比如Facebook (我们的系统是用C++编写的)。有经验的人能给我一些建议吗？我们应该使用第三方库，还是应该改进自己？如果我们改进我们自己，我们能做些什么？

非常感谢:)。

Answer 1

如果您仅在单个服务器节点上进行内存缓存，并且可以将所有键(用于元数据索引)散列为唯一的正整数，并且如果在旧的CPU上每秒~75M查找对您来说是可以的，则有一个多线程多级读-写缓存实现：

https://github.com/tugrul512bit/LruClockCache/blob/main/MultiLevelCache.h

它的工作方式如下：

int main()
{
    std::vector<int> data(1024*1024); // simulating a backing-store
    
    MultiLevelCache<int,int> cache(
        64*1024 /* direct-mapped L1 cache elements */,
        256,1024 /* n-way set-associative (LRU approximation) L2 cache elements */,
        [&](int key){ return data[key]; } /* cache-miss function to get data from backingstore into cache */,
        [&](int key, int value){ data[key]=value; } /* cache-miss function to set data on backging-store during eviction */
    );
    cache.set(5,10); // this is single-thread example, sets value 10 at key position of 5
    cache.flush(); // writes all latest bits of data to backing-store
    std::cout<<data[5]<<std::endl;
    auto val = cache.getThreadSafe(5); // this is thread-safe from any number of threads
    cache.setThreadSafe(10,val); //    thread-safe, any number of threads
    return 0;
}

它由两个缓存组成，L1是快速和切分的，但是在缓存命中时很弱，L2是较慢和切分的，但是在缓存命中方面更好，尽管不如完美的LRU。

如果应用程序中存在只读部分(例如只将值分发到只读备份存储中的线程)，则还有另一种方法可以提高性能，达到每秒25亿次查找。

// shared last level cache (LRU approximation)
auto LLC = std::make_shared<LruClockCache<int,int>>(LLCsize,
  [ & ](int key) {   
      return backingStore[key];
  },
  [ & ](int key, int value) {

     backingStore[key] = value;
});

#pragma omp parallel num_threads(8)
{
        // each thread builds its own lockless L1&L2 caches, binds to LLC (LLC has thread-safe bindings to L2)
        // building overhead is linearly dependent on cache sizes
        CacheThreader<LruClockCache,int,int> cache(LLC,L1size,L2size);

        for(int i=0;i<many_times;i++)
            cache.get(i); // 300M-400M per second per thread

}

性能取决于访问模式预测。对于用户输入依赖的访问顺序，由于流水线效率低，性能较低.对于编译时已知的索引，它具有更好的性能.对于真正的随机访问，由于缓存丢失和缺乏矢量化，其性能较低.对于顺序访问，它具有更好的性能。

如果您需要在get/set调用期间异步使用主线程，并且仍然需要get和set之间(弱的)缓存一致性，则还有另一个实现，它的性能依赖于每次从线程请求的键数：

// backing-store
std::vector<int> data(1000000);

// L1 direct mapped 128 tags
// L2 n-way set-associative 128 sets + 1024 tags per set
AsyncCache<int,int> cache(128,128,1024,[&](int key){ return data[key]; },[&](int key, int value){ data[key]=value; });

// a variable to use as output for the get() call
int val;

// thread-safe, returns immediately
// each set/get call should be given a slot id per thread
// or it returns a slot id instead
int slot = cache.setAsync(5,100);  

// returns immediately
cache.getAsync(5,&val,slot);

// garbage garbage
std::cout<<data[5]<<" "<<val<<std::endl;


// waits for operations made in a slot
cache.barrier(slot);

// garbage 100
std::cout<<data[5]<<" "<<val<<std::endl;

// writes latest bits to backing-store
cache.flush();

// 100 100
std::cout<<data[5]<<" "<<val<<std::endl;

这并不是完全一致的，线程负责对彼此之间的gets/集合进行正确的排序。

如果元数据索引是二维/三维的，则有2D/3D直接映射的多线程缓存：

https://github.com/tugrul512bit/LruClockCache/blob/main/integer_key_specialization/DirectMapped2DMultiThreadCache.h

https://github.com/tugrul512bit/LruClockCache/blob/main/integer_key_specialization/DirectMapped3DMultiThreadCache.h

int backingStore[10][10];
DirectMapped2DMultiThreadCache<int,int> cache(4,4,
        [&](int x, int y){ return backingStore[x][y]; },
        [&](int x, int y, int value){  backingStore[x][y]=value; });
for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
        cache.set(i,j,0); // row-major

cache.flush();

for(int i=0;i<10;i++)for(int j=0;j<10;j++)
    std::cout<<backingStore[i][j]<<std::endl;

它有更好的缓存命中率比正常的直接映射缓存，如果你做平铺处理。