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 тыс.

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

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



Последнее исправление: igloev (всего исправлений: 3)

индекс.

который хранит позицию и размер строки. решает п.1 и п.2. п.3 - удаление - будет создавать дыру. поскольку размер строки непредсказуем, создание индекса освободившихся блоков хранения в общем случае смысла не имеет.

olelookoe ★★★
()
Последнее исправление: olelookoe (всего исправлений: 1)
Ответ на: комментарий от anonymous

Это ни разу не задача на джуна. Это задача скорее на middle-senior database architect.

Какой бы сложности ни была задача, на лоре всегда найдется эксперт который будет говорить что эта задача для джуна, а то и вообще для школьника. Еще мудаком обзовут.

Тут и искать не надо. Чувак с мишкой в юзерпике назовет. Что-то про анал еще расскажет и про то, как бухал на физфаке. Фантазер знатный. ЧСВ еще имеет. В анал. Или оно его… ой простите…

ТС, memento noche, помни, у тебя всегда есть ночь, чтобы пересчитать индексы, а пока храни в tmp

anonymous
()
Ответ на: комментарий от igloev

Строки и ссылки на блоки ниже. Можешь строки хранить в отдельной структуре, а с дереве хранить ссылки на эту структуру. Но это потребует уже менеджмента этой отдельной структуры (это похоже на кучу, только с хранением на диске). Что-то упростит, что-то усложнит. Я бы хранил строки в самом дереве. Хотя если удаления редкие, можно и в «куче» хранить, которая из себя будет просто представлять эти строки одна за одной, без удаления (то бишь удалённые строки будут продолжать занимать место).

Legioner ★★★★★
()
Последнее исправление: Legioner (всего исправлений: 2)

Во-первых, в качестве ключей я бы советовал брать таймстампы, а не бесполезные порядковые номера. Во-вторых, с 2 бомже-гигами памяти ты не сможешь выйти на константное число сиков, только O(n log n) и мама-роди-меня-обратно во время любой major compaction. Если есть деньги хотя бы на пару десятков гигабайт, то, в принципе, можно добиться и O(1) с наперед заданной вероятностью за счет грамотно развернутых фильтров Блума[1]. С учетом того, что данных у тебя на 150 Тб, это довольно либерально. Сами же данные писать в LSM-дерево[2], как это делает любое распределенное хранилище, при этом скомпаченные блоки можно писать на диск в виде cache-oblivious B-деревьев[3].

[1] https://en.wikipedia.org/wiki/Bloom_filter
[2] https://en.wikipedia.org/wiki/Log-structured_merge-tree
[3] https://erikdemaine.org/papers/FOCS2000b/paper.pdf

anonymous
()
Ответ на: комментарий от Alve

Открыли. Что именно в SQL базах данных решает нашу задачу?

igloev
() автор топика
Ответ на: комментарий от anonymous

Структура данных в идеале должна быть такая, чтобы там как-бы не было ключа у каждой хранимой строки. Порядковый номер не бесполезен: юзкейс: показать страницу логов открытия ворот номер 8 млн (номер страницы). В странице - 100 событий, например. Сидит бабушка на вахте и листает страницы как на форуме.

igloev
() автор топика
Ответ на: комментарий от igloev

Ключи один хрен будут, потому что тебе в середину списка эффективно писать нужно, номера только что в таком случае в диапазоны сжимать можно. Но дело даже не в номерах, просто твой юзкейс «показать страницу логов открытия ворот номер 8 млн» это полный бред, вместо этого нужно «показать первые 100 записей от 2020-02-18T14:32:03.456Z».

anonymous
()

Вот предложение:

  • Каждая запись предваряется оригинальным номером записи, записи нумеруются с 0, в таком виде записываем на диск файл базы при ее инициализации.
  • Поиск: у записей есть средний размер, высчитываем смещение, по которому нужно начинать считывание, минус 2-3 стандартных отклонения, считываем блок сразу большой ( если храним на HDD, почти без разницы, 4К или 100к считываем ), ищем запись с нужным номером и все несколько нужных последующих.
  • Изменения: судя по всему, их немного. Оригинальный файл не меняется, а пишем в базу что такие-то номера удалены, и такие-то добавлены. Может лежать в оперативной памяти или на диске, в двоичном дереве. Назовем дельтой. Как используется: если собираемся искать запись с номером i, в дереве найдем все записи, меньшие i и вычислим эффективный i.
  • Когда изменений становится слишком много, делаем merge оригинального файла и дельты, после чего дельта становится пустой. Еще нужно подумать, что делать с дельтой во время merge – то есть, как обрабатывать запросы на изменения в то время, пока еще длится merge.
anymouse
()
Ответ на: комментарий от anonymous

Насчёт O(n log n). Откуда множитель N перед log, если мы оцениваем поиск только 1 ключа? Во-вторых основание можно сделать не 2, а сильно больше: получается почти константа, в том смысле, что такой логарифм очень медленно растёт при росте N. Block size = 32768, item_size = 160 bytes:

>> import math
>> math.log(1024*1024*1024 * 100) / math.log((32768/160))
4.776045977184937

В общем, в районе 4..5 обращений к диску, учитывая что много блоков верхнего уровня будет у оперативе - ну 2..3 обращения. В целом, это был краткий пересказ лекции про B+-tree и вот хочется подобного поведения.

igloev
() автор топика
Ответ на: комментарий от igloev

Откуда множитель N перед log, если мы оцениваем поиск только 1 ключа?

Да, я описался, O(log n) там, конечно.

В общем, в районе 4..5 обращений к диску

Это охренеть как дофига. Та же HBase показывает, что вполне реально достичь 1.

учитывая что много блоков верхнего уровня будет у оперативе

У тебя оперативы 2 гига, о чем тут может быть речь? Тебя могут спасти только очень тонко настроенные Блум-фильтры, только памяти все равно нужно на порядок больше.

пересказ лекции про B+-tree

Нет, тебе нужны варианты LSM-деревьев, они именно для этого и были придуманы. А как ты на диске физически хранить будешь это уже другая история, я рекомендую любую cache-oblivious структуру данных для эффективных range query. Только потом у тебя окажется, что на одну машину данные не влезают плюс хочется отказоустойчивости, а с пулом машин и консистентности, то есть нужен Paxos, поверх него какой-нибудь PubSub, грамотно шардить каким-нибудь согласованным хешированием и так далее. Не страдай фигней, бери уже готовое и проверенное временем распределенное хранилище.

anonymous
()
Ответ на: комментарий от anonymous

Нет, тебе нужны варианты LSM-деревьев, они именно для этого и были придуманы.

Для чего «этого»? LSM были придуманы в первую очередь для «инсертов сильно больше, чем селектов».

igloev
() автор топика
Ответ на: комментарий от anonymous

Не страдай фигней, бери уже готовое и проверенное временем распределенное хранилище.

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

igloev
() автор топика
Ответ на: комментарий от anonymous

Это охренеть как дофига. Та же HBase показывает, что вполне реально достичь 1.

Положить на диск кучи SSTable-файлов, в памяти держать первый ключ от каждого? Ок, но вопрос о хранении key=value данный тред не поднимает.

igloev
() автор топика

Redis предлагали?

anonymous
()

Быстрая, но можно уже чуть медленнее, вставка в любое место. В середину, например. Не перезапись, а именно вставка - т.е. если вставил в середину, то значит подвинул всё после места вставки на 1 и вставил в новое место, а длина списка выросла на 1.

Экспромтом.
Двух связный список + что-нибудь типа B-tree, хранящее в узлах диапазоны номеров узлов списка.

Владимир

anonymous
()
Ответ на: комментарий от anonymous

Двух связный список + что-нибудь типа B-tree, хранящее в узлах диапазоны номеров узлов списка.

Можно и без списка.
Используем B-tree, хранящее в узлах диапазоны номеров узлов, а лист будет содержать array с адресами узлов.

Владимир

anonymous
()

Вариант для лога/чата: Храним на диске кучу файлов в любом формате, позволяющем отделять записи друг от друга. Имена файлов выбираем так, чтобы их порядок соответствовал порядку индексов строк в них. В памяти храним структуру, содержащую количество строк в каждом файле и всех предыдущих. Способ разделения строк по файлам выбираем исходя из баланса размера файлов и их количества (чтоб структура влезла в память). Например, в одном файле все записи за день. Требование не перемещать все данные при вставке в середину и требование строкам с соседними индексами лежать рядом явно противоречат друг другу, оставляем только первое (ну или дефрагментировать ФС перед запуском машин лернинга). Далее под размером файла подразумевается количество строк в нем.

  1. Поиск по индексу: идем по структуре бинарным поиском пока не найдем нужный файл. Идем по файлу, пока не найдем нужный индекс. Сложность - логарифм от количества файлов + линейная от размера файла.
  2. Вставка по индексу - идем по структуре, пока не найдем нужный файл, идем по файлу, пока не найдем нужную позицию, сдвигаем хвост, вставляем строку. Обновляем структуру в памяти. Сложность линейная от количества файлов плюс линейная от размера файла.
  3. Удаление аналогично вставке.

Поиск по файлу можно ускорить, если дополнительно генерировать индекс, но это замедлит вставку.

roof ★★
()
Последнее исправление: roof (всего исправлений: 1)
Ответ на: комментарий от igloev

Бинго

Ну и как ты добьёшься последовательного расположения данных на диске? Свои же требования из головы вылетают?

anonymous
()
Ответ на: комментарий от slovazap

Так от кандидата требуется порассуждать.

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

WitcherGeralt ★★
()
Ответ на: комментарий от bvn13

Ну так то да. Но я хз. Логично подумать. «Сделать таблицу (отдельный файл) в которой соотнести файлы(пути) к интексу» и тогда двигать индексы не двигая реальные файлы. Получим при просто доступе просто доступ, при перемещении (вставке) перещаписываем индексы, а файлы как лежали так и лежат мы их вообще никак не трогаем, но позиция у них уже иная. Ноооо эта табличка тоже будет эммм здоровенной. Короче не знаю

LINUX-ORG-RU ★★★★★
()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)
  1. Вам нужно key-value, потому что:

    • Удаление из середины требует либо дерева, либо перемещения данных.
    • Вставка в середину в середину требует либо какого-нибудь варианта открытой адресации, либо перемещения данных.
    • Единственным пересечением вариантов без перемещения данных будет key-value с переменным размером ключа.
  2. В простейшем случае подойдет любая SQL-баз, т.е. работать будет. Если хочется быстрее и/или без лишних расходов, то нужно смотреть в сторону минималистических key-value хранилищ.

  3. В качестве key-value для одного хоста (т.е. не распределенных, без шардирования и/или репликации) выбирать стоит примерно между LSM и B+Tree:

    • LSM даст быстрый доступ к свежим данным, но с провалами скорости (с микросекунд до нескольких секунд, иногда десятков секунд) в остальных случаях. Я бы взял RocksDB.
    • B+Tree даст относительно ровную стоимость всех операций Olog(N). Я бы взял libmdbx.
    • LSM будет идеален если много записей с короткой жизнью (добавили - удалили, добавили - изменили - удалили), но создаст фоновую нагрузку на диск из-за слияний внутри LSM.
    • B+Tree суммарно будет меньше читать/писать, но доступ будет более случайным.
  4. Если не на одном хосте, то нужно вдумчиво выбирать по массе критериев. Я бы смотрел на Tarantool, ScyllaDB, Mongo.

Не за что :)

anonymous
()
Ответ на: комментарий от anonymous

Вам нужно key-value, потому что:

Не учтена вставка в середину списка. Как в key=value я сдвину все индексы на 1 после вставляемого элемента?

igloev
() автор топика
Ответ на: комментарий от igloev

Не учтена вставка в середину списка. Как в key=value я сдвину все индексы на 1 после вставляемого элемента?

Я же специально написал про переменный размер ключа:

Было: aaa1->x, aaa2->y

После вставки в середину: aaaA->x, aaaAB->z, aaaB->y

Т.е. ключи как координаты/адреса записей, должны допускать вставку значения между двумя любыми соседними. Иначе придется «перемещать» данные по адресам, через которые они доступны (вне зависимости от того какие именно это адреса). Это примерно математический закон.

anonymous
()
Ответ на: комментарий от anonymous

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

Что-то редактор глюкнул.

Имелось в виду: Вставка в середину требует либо какого-нибудь варианта открытой адресации (например расширение ключа), либо перемещения данных.

anonymous
()
Ответ на: комментарий от anonymous

Т.е. ключи как координаты/адреса записей, должны допускать вставку значения между двумя любыми соседними. Иначе придется «перемещать» данные по адресам, через которые они доступны (вне зависимости от того какие именно это адреса). Это примерно математический закон.

Приведите конкретный пример таких ключей.

igloev
() автор топика
Ответ на: комментарий от igloev

Т.е. ключи как координаты/адреса записей, должны допускать вставку значения между двумя любыми соседними. Иначе придется «перемещать» данные по адресам, через которые они доступны (вне зависимости от того какие именно это адреса). Это примерно математический закон.

Приведите конкретный пример таких ключей.

Пример был выше, для ключей с «традиционным» упорядочиванием (memcmp).

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

anonymous
()
Ответ на: комментарий от igloev

Нужен пример в контексте вопроса - т.е. про индексы массива.

Это примерно тупиковый путь, т.е. не получится.

Например: у вас есть массив X[0..99] и вы хотите вставить элемент между 9 и 10. У вас есть варианты:

  1. Просто раздвинуть элементы, т.е. переместить элементы 10..99 на одну позицию дальше. Сложность Olog(N).

  2. Дописать новый элемент в конец массива и в отдельном «словаре» пометить что 10-й элемент находиться в 100 ячейке. Однако при этом нужно также перенумеровать старые элементы после вставленного.

    • если это делать «в лоб», то сложность также будет Olog(N).
    • если строить индекс, то в конечном счете вы придете к структуре подобной дереву, со сложностью Olog(N).
    • при удалении вам придется как-то решать проблему сборки мусора и/или удаления дырок. Какие-нибудь skiplist конечно помогут, но в итоге получится либо почти LSM, либо почти B+Tree.
  3. Придумать открытую адресацию, так чтобы при вставке между 9 и 10 получался элемент с логической координатой/адресом 9½. Тогда вы сможете использовать готовые решения key-value. Это то о чем я писал исходно.

anonymous
()
Ответ на: комментарий от anonymous

Опечатался: если это делать «в лоб», то сложность также будет O(N).

Руки автоматом пишут Olog(N) вместо O(N) :)

anonymous
()
Ответ на: комментарий от anonymous

Похоже кто-то действительно тупой.

Тот, кто не предоставил решения задаче? Или «это примерно тупиковый путь, т.е. не получится.» - это такое решение?

igloev
() автор топика
Ответ на: комментарий от igloev

Тот, кто не предоставил решения задаче? Или «это примерно тупиковый путь, т.е. не получится.» - это такое решение?

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

anonymous
()
Ответ на: комментарий от igloev

Судя по предыдущим вопросам (1, 2, 3) вам достаточно разобраться с открытой адресацией и задействовать любой подходящий key-value. Если чтений будет больше чем апдейтов, то подойдет libmdbx, иначе какой-нибудь LSM.

anonymous
()
Ответ на: комментарий от igloev

Линейные не требовалось. Можно порубать на блоки и хитрить с ними.

Это называется ROPE.

Если оптимизировать для хранения и обновления на диске, то получится B+tree, либо LSM.

anonymous
()

Список с пропусками (Skip list).

Вставка/доступ/удаление — O(log N) в среднем. Ключей нет, вместо них номер элемента.

monk ★★★★★
()

Декартово дерево по неявному ключу. Вместо ключа хранится размер поддерева. Получение поддиапазонов дерева по индексам, вставка в любое место и удаление за O(log N).

gorky ★★
()

Твой объем данных это в лучшем случае 10 ТБ. Для манипуляции таким объемом данных нужна СУБД. Иначе ты просто напишешь свою. В качестве индексов строк используй timestamp’ы. Идея со сдвигом — идиотизм. Для того что бы сдвинуть хотя бы 1 млн элементов — нужно обратиться к 1 млн элементов. Каждое обращение это минимум 100 нс.

Сделай прототип с 1% объема данных от необходимого объема. И попробуй прогнать пару тестов.

brualan
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.