Блог

В настоящее время у нас есть система, в которой метаданные будут храниться в кластере хранения kv. Мы храним его просто путем сериализации метаданных приложения с помощью protobuf, а затем отправляем в кластер kv. По мере того как система становится все больше и больше, извлечение метаданных само по себе становится дорогостоящим. Поэтому мы разрабатываем компонент мета-кэша в памяти, просто кэш LRU, а кэшированные элементы являются объектами protobuf. В последнее время мы столкнулись с некоторыми проблемами:

• Одновременное чтение-запись кажется большой проблемой: когда мы добавляем новые данные в нашу систему, нам также необходимо обновить кэш, поэтому нам нужно будет частично заблокировать часть кэша, чтобы обеспечить повторяемость чтения, это приводит к очень высокой конкуренции за блокировку кэша.
• Со временем кэш становится все больше и больше.

Я думаю, что, возможно, наш дизайн кэша недостаточно хорош, и рассматриваю возможность использования сторонней библиотеки, такой как Facebook Cachelib (наша система написана на C ). Может ли кто-нибудь, у кого есть опыт в этом вопросе, дать мне несколько советов? Должны ли мы использовать стороннюю библиотеку или нам следует улучшить нашу собственную? Если мы улучшим наши собственные, что мы сможем сделать?

Большое спасибо :).

Если вы кэшируете в памяти только на одном узле сервера и если вы можете хэшировать все ключи (для индексации метаданных) в уникальные положительные целые числа, и если вам подходит ~75 м запросов в секунду на старом процессоре, существует многопоточная многоуровневая реализация кэша для чтения и записи:

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 */,
        [amp;](int key){ return data[key]; } /* cache-miss function to get data from backingstore into cache */,
        [amp;](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 медленнее и разделен, но лучше при попадании в кэш, хотя и не так хорош, как perfect-LRU.

Если в приложении есть часть, доступная только для чтения (например, просто распределение значений по потокам из резервного хранилища, доступного только для чтения), есть еще один способ повысить производительность до 2,5 миллиардов запросов в секунду:

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

     backingStore[key] = value;
});

#pragma omp parallel num_threads(8)
{
        // each thread builds its own lockless L1amp;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 и наборами, существует другая реализация, производительность которой зависит от количества ключей, запрашиваемых одновременно из потока:

 // 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,[amp;](int key){ return data[key]; },[amp;](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,amp;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;
 

это не является полностью согласованным, и потоки отвечают за правильное упорядочение объектов/наборов между собой.

Если индексирование метаданных является двух-или трехмерным, существуют многопоточные кэши с прямым отображением 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,
        [amp;](int x, int y){ return backingStore[x][y]; },
        [amp;](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;
 

он имеет лучшее соотношение попаданий в кэш, чем обычный кэш с прямым отображением, если вы выполняете обработку плиток.