Как я могу реализовать список в конечном итоге согласованной базы данных?

Question

Я хочу реализовать списки и очереди через Cassandra, Riak или любой другой, в конце концов, согласованный магазин. Возможно ли это и как я могу это сделать?

Я ищу алгоритм общего назначения.

Answer 1

Я не до конца понимаю. Какие списки / очереди? Вы можете создать (один / несколько) документ, который содержит каждую очередь / список в нем / них. Вы имеете в виду запросы или тому подобное (что немного похоже на мышление SQL)?

Очень хорошая статья о моделировании, а не о моделировании вещей может быть найдена здесь:

как НЕ сделать это http://ayende.com/blog/4465/that-no-sql-thing-the-relational-modeling-anti-pattern-in-document-databases

как это сделать http://ayende.com/Blog/archive/2010/04/21/that-no-sql-thing-modeling-documents-in-a-document-database.aspx

если я вас не так понял пожалуйста уточните:)

Answer 2

Не уверен, какие операции вы хотите поддерживать, и не знаком с Riak et. al., но здесь возможна реализация CouchDB, еще одной непротиворечивой БД.

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

Предполагая, что вы хотите поддерживать итерацию, push и pop, вы можете получить документ с

• идентификатор документа : это могут быть UUID или что-то еще, что имеет смысл, поэтому каждая запись получает уникальный идентификатор и не вызывает конфликтов во время слияния.
• ключ ранга : дает относительный порядок. Это может быть метка времени или глобальный счетчик. Дело в том, что порядок сортировки ключа такой же, как и относительный порядок в списке. Когда ключ ранга отличается от идентификатора документа, конфликты не имеют значения, и вы все равно получаете список / очередь в правильном порядке, сортируя по ключу. Если вы хотите уникальный заказ, добавьте идентификатор клиента или некоторые другие к ключу. Пример ключа: [123, "client1"] будет сортировать до [123, "client2"]. (Специфика здесь, вероятно, будет отличаться в зависимости от БД, но вы можете использовать этот трюк, даже если ключи являются просто строками.)
• значение : содержимое этого элемента списка

Операции

• list / iterate : вернуть все элементы, упорядоченные по ключу ранга, выполнить итерацию на клиенте. Если набор данных массивный, выполните итерации по ключевым поддиапазонам.
• head , tail : запросы, которые возвращают элемент с ключом наименьшего или наибольшего ранга.
• push : вставить новый документ с ключом ранга выше, чем самый высокий из существующих.
• pop : получить и затем удалить документ с ключом самого низкого ранга

Answer 3

Посмотрите на проект Клетки. Это может быть полезно для вашего случая использования. http://ria101.wordpress.com/2010/05/12/locking-and-transactions-over-cassandra-using-cages/

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

Answer 4

Отказ от ответственности: Я не знаком с Касандрой или Риаком.Это относится к общей «базе данных» (не обязательно реляционной, распределенной и т. Д.).

Я предполагаю, что вы можете хранить и получать доступ к «парам ключ-значение» (т. Е. К парезначения (a, b), где a - ключ к значению b).

Я также буду использовать эту запись для представления некоторого обобщенного «объекта» (структура данных, объект, словарь, ..): Person[name: "John Doe" age: 49].

Реализация связанного списка

Предполагается, что у вас есть пара ключ-значение (ключ, значение) и объект Object [fields: values...], связанный список может быть реализован в базе данных путем

1. добавления «следующего» поля к объекту путем определения Object [fields: values ​​... next] ИЛИ
2. создание нового «объекта-держателя», определенного как (ключ, значение) = Holder [Object [fields: values ​​...] next]

Это также может быть идеей для храненияпервое значение связанного списка в некоторой специальной паре ключ-значение, например (first, ...).

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

При извлечении значения из пары ключ-значение, чтобы получить следующее значение, просто найдите поле «next» в Holder или Object, чтобы перейти к списку до следующего значения,и т. д.

Пример алгоритма связанного списка

Поиск:

def find(first, node):
    if node = first[next]:
        return first[next]
    else:
        find(first[next], node)

Поиск предшественника:

def find_pred(first, node):
    if node = first[next]:
        return first
    else:
        find_pred(first[next], node)

Вставкаперед конкретным узлом:

def insert_at_front(node, inserted_node):
    find_pred(node)[next] = inserted_node
    inserted_node[next] = node

Реализация очереди

В этом случае очередь может быть просто связанным списком, в котором два конкретных значения автоматически известны (вероятно, хранятся в базе данных):

1. первый элемент (или заголовок), который может быть сохранен с помощью специальной пары ключ-значение (head, ...)
2. последний элемент (или хвост), который можетхраниться в специальной паре ключ-значение (tail, ...)

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

Answer 5

Вы можете пойти другим путем и использовать Lucene для хранения своего «списка», и просто добавить в Lucene столбец для «индекса разговора» или чего-либо еще, что вы делаете.

См. Lucandra проект для получения дополнительной информации. Кроме того, в блоге Sematext есть хорошая рецензия.