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

Question

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

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

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

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

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

Answer 1

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

Для простой очереди "первым пришел - первым обслужен" вы можете использовать несколько магазинов с кэВ-значениями, например:

{
     oldestIndex:5,
     newestIndex:10
}

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

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

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

Answer 2

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

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

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

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, которые могут заставить вас обновлять ключ или значение отдельно и безопасно выполнять поток. Однако эта реализация является проблемой алгоритма, а не структурой ключ-значение.