я бы добавил эту дату в value, проверял бы при доступе и вдобавок периодически (зависит от объёма данных) запускал бы чистку. Схема хорошая, в реляционках использовал, но тут разнесение одного куска логики на два куска кода получается. Обычно приемлемо.
ну фигня в том, что периодически придется проходиться по всему хранилищу. по ссылке http://programmers.stackexchange.com/que... предложил структуры данных, чтоб этого не делать :) но хз, может и проходиться тоже норм.
Я бы складывал в отдельное дерево: ключ — время, когда этот объект нужно удалить значение — указатель на объект, который мы хотим удалять опционально, у удаляемого элемента можно сделать поле со ссылкой на соответствующий элемент этого дерева, чтобы можно было изменять TTL. Периодически пробегаем дерево и удаляем из него элементы, у которых дата истечения меньше текущей
ага, у меня тоже сначала был этот вариант. но у него сложность логарифмическая. а у варианта с бакетами (который по ссылке, что я постил, где я вопрос задавал есть), вариант с O(1).
А вот изменение TTL у алгоритма с корзинками — O(n). В принципе, в случае in-memory storage вроде Redis можно использовать AVL-дерево с указателем на минимальный элемент и тогда удаление элемента будет константным, а изменение TTL — логарифмическим.
Хотя... Я гоню. Вариант с корзинками — самый оптимальный и при правильной реализации константа по всем операциям. Особенно если у нас нет требования о моментальном удалении элемента по истечении указанного промежутка времени и сильно ограничен максимальный TTL (количество корзинок).
13 comments
recommend
bookmark
subscribe
Самое очевидное решение — это пары время => список ключей.
я бы добавил эту дату в value, проверял бы при доступе и вдобавок периодически (зависит от объёма данных) запускал бы чистку. Схема хорошая, в реляционках использовал, но тут разнесение одного куска логики на два куска кода получается. Обычно приемлемо.
ну фигня в том, что периодически придется проходиться по всему хранилищу. по ссылке http://programmers.stackexchange.com/que... предложил структуры данных, чтоб этого не делать :) но хз, может и проходиться тоже норм.
В моём варианте по всему хранилищу проходиться не надо — чистятся только те ключи, которые есть в списке.
а тут надо смотреть на конкретику. Конечно, в общем случае хуёво это, про всему хранилищу бегать. И более культурные решения тоже интересны.
ну вот по ссылке я предложил структуру данных. интересно, можно ли лучше.
Вполне нормальное решение.
яхз. интересно, как оно у редисов и прочих. http://stackoverflow.com/questions/86523...
Я бы складывал в отдельное дерево:
ключ — время, когда этот объект нужно удалить
значение — указатель на объект, который мы хотим удалять
опционально, у удаляемого элемента можно сделать поле со ссылкой на соответствующий элемент этого дерева, чтобы можно было изменять TTL.
Периодически пробегаем дерево и удаляем из него элементы, у которых дата истечения меньше текущей
ага, у меня тоже сначала был этот вариант. но у него сложность логарифмическая. а у варианта с бакетами (который по ссылке, что я постил, где я вопрос задавал есть), вариант с O(1).
А вот изменение TTL у алгоритма с корзинками — O(n).
В принципе, в случае in-memory storage вроде Redis можно использовать AVL-дерево с указателем на минимальный элемент и тогда удаление элемента будет константным, а изменение TTL — логарифмическим.
А использование корзинок — очевидная оптимизация, применимая к любому алгоритму. Ну или почти к любому.
Хотя... Я гоню. Вариант с корзинками — самый оптимальный и при правильной реализации константа по всем операциям. Особенно если у нас нет требования о моментальном удалении элемента по истечении указанного промежутка времени и сильно ограничен максимальный TTL (количество корзинок).