Хранение объектов, адресуемых по идентификатору и отсортированных по метке времени

Question

Я создаю приложение, и мне нужна помощь в поиске структуры данных, чтобы делать то, что я хочу.

Фон

, который получает около 100 событий в секунду.Эти события состоят из трех частей: строкового сеанса uuid, длинной метки времени (время Unix) и, возможно, строки json.Сессия uuid используется, чтобы связать события из одного и того же сеанса вместе.Первое событие, которое мы получаем с данным набором TTL для сеанса.

Требования

Я пытаюсь сохранить эти сеансы, которые, по сути, являются отсортированными коллекциямисобытия, которые отсортированы по времени их события.Два критерия, с которыми я сталкиваюсь при одновременной проблеме:

1. Мне нужно иметь возможность быстро найти сеанс на основе его UUID.
2. Мне нужно иметь возможностьопределить, какие сеансы истекли, основываясь на их метке TTL, которая является атрибутом сеанса.

Я имею в виду карту, на которой я могу отключить UUID, но значения хранятся в отсортированном порядке.Я могу сделать объекты EventSession сопоставимыми по времени, но похоже, что SortedMap только сортирует ключи.Я не уверен, есть ли фундаментальные проблемы с тем, что я прошу, но я открыт для идей.

Answer 1

Похоже, вам нужны две структуры: Map для поиска объектов Session по UUID и PriorityQueue для хранения тех же объектов Session, упорядоченных по TTL.

Answer 2

Я сделал то же самое. Вам нужно 2 структуры данных:

• a Список, содержащий time-sessionID-pair, сохраняйте указатель на начало и конец, чтобы вы могли вставлять и удалять в постоянное время.

• Карта sessionID-> JSonString, реализованная в виде красно-черного дерева отсортированных sessionIDs

Красно-черное дерево автоматически уравновешено, проще реализовать этот AVL и даст вам log (n) вставок, поисков и удалений. Поэтому при удалении из списка вы берете идентификатор, который там хранится, и запись на карте в лог (n) времени.