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)

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

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

забавно, вспоинил анекдот: как распить 800мл водки на троих? элементарно: сначала надо бахнуть по 100 грам после чего задача сводится к стандартной))

Anoxemian ★★★★★
()

то значит подвинул всё после места вставки на 1 и вставил в новое место, а длина списка выросла на 1.

Ты с ума сошёл, так быстро работать не будет.

Тебе уже ответили правильно, используй субд.

anonymous
()

ИМХО, тебе не это нужно.

anonymous
()

На правах вакханалии

Субд. Или если хочется эдакого то прям файловую систему юзать как базу и манипулятивное средство. ext4 вроде умеет 4 миллиарда файлов все твои данные это 100 гигов в максимуме тогда взять штук 30 винтов по 100 гигов (с запасом ибо, ибо бо) в них поочерёдно вписывать строки в файлы под индексами 1,2,3,4,5,6… в соотвецтвии с положением в изначальном массиве. в софте обращатся просто к файлам, а жёсткие диски будут смотрированны в 1 корневой каталог и воспинимаются как просто чанки тут от 1 до 3000000000 следующий от 3000000000 до 6000000000. Всю работу свести просто к работе с «большой» ФС. Всё. Ядро будет кешировать часто используемое на автомате. Будет быстрее любой бд (которую также один хрен придётся разбивать на диски и партицировать) ибо никакого тебе индексирования,поиска и прочего, вот те инода вот те файл. Можно ещё 30 витов рядом вствить в рейде для зеркала.

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

Ну или ещё как извратиться =) ФС это хорошая БД сама по себе. =)

А лучше купить 256 гогов оперативки, загнать все данные в двумерный массив или двусвязный список и вертеть этими миллиардами на своём шаловливом со скоростью калибри

LINUX-ORG-RU ★★★★★
()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)

Короче суть в том что у тебя 2 гига памяти для тог что бы обработать например просто прочитать все данные в потоке по символу это 50 раз полностью перезаписать всю оперативку. Даже тупо операция чтения всех данных будет оочень долгой. Так что разделяй и властвуй. А что за данные сейсмический датчик стоит и постоянно выплёвывает CSV простыню?

LINUX-ORG-RU ★★★★★
()

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

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

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

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

Ну требования вроде понятные - дисковое хранилище с доступом по индексу и вставкой/удалением в случайное место. Но честно говоря не могу придумать под это юзкейс - если из-за модификаций индексы меняются, то в них нет никакого смысла: добавили-удалили элементов в начало, значит стомиллиардный элемент уже не стомиллиардный - где он мы уже не знаем, а стомиллиардным будет другой элемент. Значит на самом деле тут не нужен доступ по индексу, а нужен либо доступ «куда-то примерно в начало/конец/середину/6.66%» что можно сделать проще, либо никакие индексы не нужно сдвигать и нужен обычный map. Ну либо это задача с собеса или лабы - тогда в job.

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

В редисе есть List, вот пусть его и юзает. Быстрейшая субд, как раз строки хранит. ТС хочет дёшево решить свою больную задачу, словно на тракторе в Антарктиду уехать

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

*Между 100 и 10, а также 9 и 2000 знак умножения

anonymous
()

3-4 движения головы диска

Покупаешь терабайтный SSD для «индекса»– и у тебя 1 движение на собственно достать данные.

В память оно не влезет

man mmap и это теперь задача ядра.

Требования

Звучит, как реклама верёвок, но это просто последнее, о чём я читал, скорее всего там их таких много.

DonkeyHot ★★★★★
()

Памяти у нас 2 гига, хаха.

Ну вы и бомжи, хаха.

anonymous
()

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

это классика

anonymous
()

днс-велосипед или acl ?

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

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

Какой вы умный, это что-то. А теперь пожалуйста произвольный доступ по индексу, как хочет ТС после вставки в список.

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

но LinkedHashMap формально под оба этих условия подходит.

Такое ощущение, что вы хотите блеснуть знаниями «умных слов». Ещё раз, у ТСа всё разложено по 3 пунктам. Как LinkedHashMap тут поможет? У него же не было пункта поиска по содержимому.

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

Ценно замечание.

Но все-же, где видите что нельзя индексы? и потом, мало-ли чего захотелось …

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

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

Да ничего ни в чём нет. В пятый раз говорю, что ТС хочет сделать нечто невразумительное, только в космических масштабах. Есть подозрение, что ему вообще очередь нужна.

anonymous
()

Т.е. элемент, лежавший ранее по индексу 10 млрд теперь будет лежать по индексу (10 млрд + 1).

Тогда, никакого смысла в этом «индексе» нет. Это даже и не индекс вообще, это хрень какая-то. Индекс ценен тем, что одному и тому же индексу всегда соответствует один и тот же элемент, вне зависимости от того, сколько данных добавилось.

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

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

Да лана. Берем выборку по индексам, добавляем туда что-то новое, не обязательно в конец, и получаем новую таблицу и уже её индексируем. А теперь предположим, что выборка вдруг состоит из всей имеющейся таблицы, но вот так вышло...

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

Вы увидели бред? Это проекция?

Вы решили замусорить топик бредовыми сообщениями с личными наездами не по делу в надежде, что заодно снесут и те сообщения, где вы обосрались?

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

но вот так вышло...

шизофазия какая-то

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

честно говоря не могу придумать под это юзкейс

«Очередь» спризвольным доступом с вставкой в произвольное место.

Ранговая система с произвольной вставкой и просмотром с произвольного места. «Дайте мне список лузеров, начиная с 100500 места»

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

Индекс ценен тем, что одному и тому же индексу всегда соответствует один и тот же элемент

Не всегда. Иногда индекс нужен не ради содержимого элемента, а ради номера элемента.

anonymous
()

У Berkeley DB есть такая фича: https://docs.oracle.com/cd/E17276_01/html/api_reference/C/dbget.html#dbget_DB_SET_RECNO

К записи в btree можно получить доступ по «логическому номеру». Но у них ограничение в 2**32 номеров, т.е. 100 млрд (если тебе действительно столько нужно) он не сможет.

Если хочешь писать сам, то скорее всего нужно будет хранить в промежуточных узлах какие-то дополнительные метаданные. Ну и из общих соображений доступ «по номеру» будет медленнее чем по ключу, нужно будет читать с диска больше узлов.

Deleted
()

Сортируй и сохраняй в мелких файлах. Название - индекс. В каждом файле не более N строк. То есть типа такого

db
├── a
│   ├── 0
│   ├── 1
│   └── 2
└── b
    ├── 0
    ├── 1
    └── 2
dnb ★★★★
()

Зачем вы все сдаете за него собеседование? Это стандартная задача на собеседованиях на Джуна.

DELIRIUM ☆☆☆☆☆
()

задача элементарная, задавали на собеседовании лет 5 назад. Никаких субд не нужно. нужно знать структуры данных и чуть чуть думать башкой. решай сам.

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

Зачем вы все сдаете за него собеседование? Это стандартная задача на собеседованиях на Джуна.

Чтобы собеседование превратить в абсурд при равных условиях.

Раз собеседующий может пользоваться придуманными толпой задачами, то и собеседуемый может пользоваться придуманными толпой ответами.

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

и в итоге занимаемся нон-стоп переиндексацией

В каком таком итоге? Выбирайте выражения. Если задача вот такая с бесконечными вставками — то да. А вы что предлагаете?

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

Ты значит не пройдешь, это задача не на конкретный ответ, как «чему равно два+два?» Твой ответ: спросить на ЛОРе. Ты не прошёл.

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

сделать нечто невразумительное

Тебя уже опровергли. Вразумительное.

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

а цена вопроса какая? и почему не в job

anonymous
()

B-дерево. Все операции за логарифм. На диске хранить не проблема, алгоритмы давно известны.

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

твой ответ: спросить на ЛОРе. Ты не прошёл.

Как по мне, так отличный ответ.

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

Иногда индекс нужен не ради содержимого элемента, а ради номера элемента.

Номер и индекс - разные вещи.

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

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

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

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