LINUX.ORG.RU

Эффективно хранить список строк на диске. Длина списка - 100 млрд. Длина строки - рандом. Дешево удалять/вставлять в середину.

 


0

3

Надо сохранить массив (список) строк. В массиве может лежать крайне дохрена таких элементов (строк), т.е. например 100 млрд строк. Длина одной строки - рандом, но уже разумный - например 1…2000 символов. Т.е. наш массив имеет такой вид: [‘ab’, ‘zuzuzu’, ‘S’, …, ‘hehebububu’] (и это всё длиной 100 млрд).

Хочется:

  1. Быстрый доступ по индексу, т.е. по смещению: «дай 5-млрдный элемент». Доступ как к 1 элементу, так и к подмассиву («дай 100 элементов со смещения 52 млрд»).
  2. Быстрая, но можно уже чуть медленнее, вставка в любое место. В середину, например. Не перезапись, а именно вставка - т.е. если вставил в середину, то значит подвинул всё после места вставки на 1 и вставил в новое место, а длина списка выросла на 1.
  3. Быстрое удаление из любого места. Почти то же, что (2).

Требования (2) и (3) как-бы подразумевают, что если я воткнул строку по индексу «5 млрд», то все элементы, лежавшие после него должны теперь переехать в следующие по нумерации квартиры на единицу. ВСЕ ПЕРЕЕХАТЬ! Т.е. элемент, лежавший ранее по индексу 10 млрд теперь будет лежать по индексу (10 млрд + 1). За идею «давайте сделаем 95 млрд изменений в памяти или на диске» - сразу расстрел.

В память оно не влезет. Памяти у нас 2 гига, хаха. Т.е. надо как-то хранить всю эту байду на диске. На длинах массива порядка миллиардов цена доступа к любому элементу такого массива должна быть не выше чем 3-4 движения головы диска, т.е. это число обращений к нему. Т.е. всё должно лежать на диске не хуже, чем бы оно лежало в B+-Tree, если бы мы все элементы списка положили в виде key=value пар виде (elem1=string, elem2=string). С вариантом «куча key=value» не взлетит потому, что вас расстреляют при попытке переименовать все 95 млрд ключей, поменяв у них циферку в конце при вставке на позицию «5 млрд». Положить кучу key=value так, чтобы value было блоком строк - уже лучше, но всё равно на порядках сотен миллиардов придётся переименовывать овердофига ключей, трогая явно не 3-4 блока.

Варианты?

P.S.:

Пример применения: хранить очень длинный чатик или лог открытия ворот. Просматривалка с доступом через пагинацию. Нас не интересует время события, нас интересуют все 50 событий на странице номер 500 тыс.

Удаление или вставка в середину иногда нужна, но редко. Например дропнуть пачку флуда или добавить некий служебный евент.

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

Прошу прощения за некропостинг. И заодно за то, что выше уже в чуть других словах писали похожие вещи. Но все же напишу, что думаю.

Требование быстрого произвольного доступа совместно со вставкой-удалением сразу намекает на использование деревьев - у них O(log N).

Чтобы константа при O(log N) была хорошей (чтобы реже двигать головки дисков), надо использовать какое-то сильно ветвящееся дерево - например, B-Tree или какую-то вариацию на его тему.

Как на деревьях реализовать быстрый доступ по индексу: можно в каждом узле дерева хранить его «ранг» - количество записей в нем и его субдеревьях. Тогда при поиске по номеру просто идем в ту ветку, для которой выполняется два условия: левее нее меньше узлов, чем искомый номер, а если к количеству узлов левее прибавить ранг этой ветки - то получается больше или равно искомому номеру. Обновление при вставке/удалении весьма простое: просто надо при перебалансировке исправлять ранг затронутых перебалансировкой узлов.

Разумеется, дерево должно поддерживать работу без ключей, с операциями вида «найти по индексу» (вышеописанным способом), «найти следующий/предыдущий узел после/до ранее найденного», «удалить найденный ранее узел», «вставить новый узел перед или после ранее найденного узла». По сути, от дерева остаются только его правила перебалансировки - ключей нет, но все еще есть отношения порядка между узлами, и поэтому перебалансировка делается точно так же, как в классическом варианте дерева того же вида. Насколько понимаю, любой алгоритм деревьев можно относительно несложно вывернуть таким боком (например, для всяких красно-черных, андерссоновских и прочих подобных деревьев это вроде бы тривиально, для B-Tree - на первый взгляд тоже).

Если хочется поменьше программировать, а побольше использовать стандартные инструменты, то можно сделать так: отдельно хранить, например в СУБД с полным кэшированием в ОЗУ, упорядоченный список «чанков» (на самом деле все равно не список, а дерево) с их текущими размерами и уникальными идентификаторами, а сами хранимые строки размещать пачками в телах «чанков», которые хранить в отдельном хранилище (да хоть в MongoDB, чтобы на халяву шардинг с репликацией поиметь). При добавлении/удалении элемента ищем чанк, к которому этот элемент будет принадлежать или принадлежит (зная список чанков и количества узлов в каждом), читаем его тело, добавляем в/из него интересующие нас строки, пишем обратно. При этом при разрастании чанка выше какого-то размера делим его на два чанка, а при сжатии ниже какого-то размера сливаем с соседним.

Если характерный размер чанка сделать достаточно большим, можно будет понадеяться, что если нижележащее хранилище будет хранить чанк непрерывно, то перемещения головок дисков будут происходить в основном на границах чанков. Также характерный размер чанка должен быть таким, чтобы упорядоченный список чанков можно было полностью кэшировать в ОЗУ. Для двух гигов ОЗУ и 10e11 записей получаем чанки размером в несколько десятков тысяч записей (очень грубая прикидка, плюс-минус десятичный порядок).

При таком хранении можно заодно положиться на шардирование (чтобы не хранить все данные на одном узле - шасси на сотню накопителей не бывает, значит, по любому нужно какое-то распределенное хранилище) и обеспечение надежности (репликацию?) средствами выбранного хранилища (той же монги). Для первого прототипа/proof-of-concept я бы взял в качестве хранилища для списка чанков что-то вроде SQLite, ну или даже PostgreSQL с репликацией (причем можно даже этот список чанков не сильно реплицировать и бакапить - оно все восстановимо за разумное время, если в телах или метаданных чанков хранить еще и их положение в цепочке, например, описанным кем-то выше способом с ключами, поддерживающими операцию генерации ключа между любыми двумя другими ключами), а в качестве хранилища для собственно тел чанков - да хоть ту же MongoDB. Если при чтении/записи/удалении важно не только количество перемещений головок дисков, но и объем прочитанного, то реализация работы с чанками будет уже сложнее, сами чанки тоже должны будут выглядеть как деревья, и вместо тупого хранения в MongoDB придется придумать что-то еще.

vap77 ()