мне нужен простая структура кэша (в питоне, но это на самом деле не имеет значения), с некоторыми специфическими требованиями:Оптимальный алгоритм кэша с истекает
- до нескольких миллионов мелких объектов (100 байт в среднем)
- Скорость является ключевым (как ставить и получить), я бы ожидать, время срабатывания при температуре около нескольких микросекунд
- только один поток доступа к этому - так это может быть всего лишь в памяти (не требуется настойчивость)
- Ключами являются хеширование MD5 (если это имеет значение)
- Там в момент истечения срока действия, глобальный для кэша - каждый ключ должен быть удален из кэша после истечения времени, считая с момента первым положить
Теперь дело в том, как реализовать истечение срока - как и все другие могут осуществлен используя простой словарь. Простейшее решение - регулярно перебирать все данные и удалять истекшие ключи - может слишком долго блокировать весь кеш. Его можно было бы улучшить, повторяя части данных с каждым процессом очистки, но все равно потребуется некоторое время (или не будет достаточно быстро очистить его). Также удаление ключей один за другим выглядит как трата процессора - поскольку они могут быть удалены партиями (их не нужно удалять сразу же после истечения срока действия - мы можем позволить себе дополнительную ОЗУ для хранения истекших ключей немного дольше).
Проверка ключей во время извлечения недостаточно (хотя это должно быть сделано, тем не менее, чтобы не возвращать истекшие ключи) - так как многие ключи не могут быть извлечены, а затем они останутся навсегда (или слишком долго).
Большинство ответов на эту проблему предлагают использовать memcached, но я думаю, что это будет пустой тратой процессора, тем более, что я сохраняю объекты, которые могут быть помещены в словарь по ссылке, но с использованием memcached они должны быть (de) сериализованная.
У меня есть идея, как реализовать это: разделите данные на временные фрагменты, имея на самом деле несколько словарей - например, если время истечения составляет 60 секунд, то у нас есть (самое большее) 4-е изд. И каждые 20 секунд мы добавляем новые один - где кладут новые ключи и удаляют четвертый - где у нас будут ключи, добавленные более 60 секунд назад. Это делает очистку очень быстро за счет времени восстановления, когда вам нужно искать в 4 словарях вместо одного (а использование ОЗУ - на 33%).
Итак, наконец-то вопрос - что есть: есть ли лучшее решение? Или, может быть, я ошибаюсь, и некоторые из упомянутых решений (удаление ключей один за другим) будут лучше и быстрее? Я не хочу изобретать велосипед, но не нашел хорошего решения в сети.
Как я уже говорил, это один поток, и добавление другого для удаления ключей даст как много проблем с синхронизацией - также это было бы намного хуже, чем просто их последовательная обработка и удаление один за другим. – kompas
в общем опросе гораздо менее эффективен, чем уведомление. в этом случае вы не только опросите один объект за его истечение, но и будете опросить все население. удачи! – necromancer
, и вы можете использовать уведомление таймера без синхронизации в самом кэше. просто вставьте в него уведомления, а один поток один раз в то же время сбрасывает очередь и удаляет из очереди уведомленные объекты. я не вижу, как периодически проверять 1000 000 объектов, чтобы найти, что 1000 истекших объектов могут быть более эффективными, чем обработка 1000 удалений из очереди. вздох ... – necromancer