Кэширование — Как LRU-кешировать многочисленные объекты из тяжелых структур C ++ STL?
У меня есть большие структуры данных C ++ / STL (myStructType) со списками и картами. У меня много объектов такого типа, я хочу к LRU-кешу с ключом. Я могу перезагрузить объекты с диска, когда это необходимо. Более того, его необходимо использовать в многопроцессорном высокопроизводительном приложении, работающем на платформе BSD.
Я вижу несколько решений:
- Я могу рассмотреть пожизненный отсортированный список
pair<size_t lifeTime, myStructType v>плюс карта для o (1) доступа к индексу нужного объекта в списке по его ключу, я могу использовать shm и mmap для хранения всего, и блокировку для управления доступом (см. Вот). - Я могу использовать сервер redis, сконфигурированный для LRU, и перепроектировать мои структуры данных, чтобы перерисовать пары ключ / значение и ключ / списки.
- Я могу использовать сервер redis, настроенный для LRU, и сериализовать мои структуры данных (myStructType), чтобы иметь простой ключ / значение для управления с помощью redis.
Конечно, могут быть и другие решения. Как бы вы это сделали или, что лучше, как успешно это сделали, имея в виду высокую производительность?
Кроме того, я хотел бы избежать тяжелых зависимостей, таких как Boost.
Решение
Я на самом деле недавно построил кэши (не только LRU).
Варианты 2 и 3, скорее всего, не быстрее, чем повторное чтение с диска. Это фактически не кеш вообще. Кроме того, это будет гораздо более тяжелая зависимость, чем Boost.
Вариант 1 может быть сложным. Например, вы предлагаете «замок». Это было бы довольно утверждал замок, так как она должна защищать каждое обновление срок службы, а также все операции LRU. Поскольку ваши объекты уже тяжелые, возможно, стоит иметь уникальную блокировку для каждого объекта. Существуют промежуточные варианты этого решения, где имеется более одной блокировки, но также более одного объекта на блокировку. (Вам все еще нужен ключ для защиты всей карты, но это только для замены)
Вы также можете подумать, действительно ли вам нужен строгий LRU. Эта стратегия предполагает, что вероятность повторного использования объекта со временем уменьшается. Если это не совсем так, то случайная замена так же хороша. Вы также можете рассмотреть возможность удаления более одного элемента одновременно. Одна из проблем заключается в том, что когда элемент должен быть удален, это будет так из всех потоков, но достаточно, если один поток удалит его. Вот почему пакетное удаление помогает: если поток пытается взять блокировку для пакетного удаления, и это терпит неудачу, он может продолжаться при условии, что кэш-память скоро будет иметь свободное место.
Один быстрый выигрыш — не обновлять время LRU последнего использованного элемента. Это было уже самое новое, сделать его новым не поможет. Это, конечно, имеет эффект, только если вы часто снова используете этот элемент, но (как отмечено выше) в противном случае вы просто используете случайное выселение.
Другие решения
Других решений пока нет …