Как эффективно смоделировать очередь поверх хранилища ключевых значений?

Предположим, что у меня есть база данных ключ-значение, и мне нужно построить очередь поверх нее. Как я мог бы достичь этого, не получая плохой производительности?

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

Я также могу реализовать связанный список со случайными ключами, и есть один фиксированный ключ который выступает в качестве отправной точки для элемента 1. В зависимости от того, предпочитаю ли я быстрое чтение или быстрый доступ к записи, я могу позволить указать фиксированный элемент на первую или последнюю запись в очереди (поэтому мне приходится перемещать его вперед / назад).

Или, чтобы продолжить это - я мог бы также иметь два фиксированных указателя: один для первого, on для последнего элемента.

Какие-либо другие предложения о том, как сделать это эффективно?

2 2
queue key-value-store

2 ответа:

Я думаю, что это зависит от типа очереди, которую вы хотите реализовать, и никакое решение не будет идеальным, потому что хранилище ключей-значений не является правильной структурой данных для такого рода задач. Там будет всегда какую-то халтуру, участвующих.

Для простой очереди first in first out вы можете использовать несколько магазинов значений кэВ, таких как: 

{
     oldestIndex:5,
     newestIndex:10
}

В этом примере в очереди будет 6 элементов (5,6,7,8,9,10). Пункты от 0 до 4 уже выполнены, в то время как пункта 11 или около того пока нет. Рабочий-производитель увеличит newestIndex и сохранит свой товар под ключом 11. Потребитель берет товар под ключ 5 и увеличивает oldestIndex.

Обратите внимание, что этот подход может привести к проблемам, если у вас есть несколько потребителей/производителей и если очередь никогда не бывает пустой, поэтому вы не можете сбросить индекс.

Но проблема многопоточности также справедлива для связанных списков и т. д.

1

Изначально структура ключ-значение очень похожа на исходное хранилище памяти, где физический адрес в памяти компьютера играет роль ключа. Таким образом, любой тип структуры данных может быть смоделирован на основе хранения значений ключей, включая связанный список.

Первоначально связанный список - это список узлов, включающий индексную информацию предыдущего узла или следующего узла. Затем узел его собственной, следует также рассматривать как ключ-значение суб структуры. С дополнительным префиксом к ключу, информация в узле может храниться отдельно в плоской таблице пар ключ-значение.

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

pilot-last-index: 5
pilot-0: Rei Ayanami
pilot-1: Shinji Ikari
pilot-2: Soryu Asuka Langley
pilot-3: Touji Suzuhara
pilot-5: Makinami Mari
Я думаю, что соответствующий альгритм также можно себе представить. Если бы у вас был поток демона для манипулирования этими ключами, pilot-5 можно было бы переименовать в pilot-4 в приведенном выше примере. Даже если, это не позволено иметь дополнительный поток в какой-то особой ситуации на результат очереди он сам не влияет. Просто некоторые накладные расходы будут существовать для точки разрыва в последовательности.

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

Потокобезопасность-это именно проблема, однако древняя проблема. Так же, как и класс, реализующий интерфейс ConcurrentMap в JDK, атомарная операция над данными ключ-значение также предусмотрена идеально. В некоторых промежуточных программах типа memcached есть аналогичные методы, которые могут заставить вас обновлять ключ или значение отдельно и безопасно для потока. Однако эта реализация является проблемой альгритма, а не ключевой ценностной структуры, которую он сам.

1