Реализация кэша LRU в Go

задняя часть Go gRPC
Реализация кэша LRU в Go

предисловие

Я писал об этом несколько лет назадLRU cacheстатья:Сестра crossover.top/2018/04/07/…

В то время он был реализован на Java, и недавно я над ним работал.ptgКак раз тогда, когда вам нужна наименее недавно использованная структура данных для хранения истории.

ptg: инструмент тестирования производительности (Go), инструмент отладки клиента gRPC, реализованный в Go.

В официальной библиотеке Go нет родственной реализации, учитывая простоту программы, я не планирую полагаться на стороннюю библиотеку и писать ее самостоятельно, сама сложность невелика, а строк всего несколько кода.

С этой структурой данных у меня естьptgФункция истории запросов реализована в:

Храните каждую запись запроса в кэше lru, самые последние использованные исторические записи ранжируются первыми, а также предоставляют соответствующие функции поиска; подробности см. на рисунке ниже.

выполнить

О принципе реализации и говорить нечего.Javaтакой же как:

  • Порядок, в котором двусвязный список хранит данные
  • Одинmapхранить окончательные данные
  • Когда данные достигают верхнего предела, удалите хвостовые данные связанного списка.
  • будет использоватьсяNodeПерейти к головному узлу связанного списка

Хотя Go относительно лаконичен, хорошая новость заключается в том, что базовая структура двусвязного списка все еще существует.

Итак, исходя из этого, мы определяемLruCache:

Согласно предыдущему анализу:

  • sizeРазмер кэша хранилища.
  • Связанный список хранит порядок данных.
  • mapХранение данных.
  • lockИспользуется для управления безопасностью параллелизма.

image.pngСледующее внимание уделяется двум функциям: записи и запроса.

При записи оценивайте, достигнут ли верхний предел емкости, и удаляйте хвостовые данные после его достижения, в противном случае записывайте данные в голову.

При выборке данных это переместит запрошенный узел на головной узел.

Эти операции с узлами инкапсулируются в List.

Так удобнее в использовании.

наконец через этоLruCacheЭффект вышеприведенной картинки достигнут.Если вы хотите узнать больше деталей, вы можете обратиться к исходному коду:

GitHub.com/crossover J я…

Категории