Живительная сортировка

lexa - 25/Ноя/2008 22:57

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

Задача

Некий код производит записи фиксированной длины:

  • 8-байт ключа
  • 20 байт данных на запись
Эти записи надо сложить в простую базу данных к которой другой код будет доступаться по ключу. Если несколько записей имеют один ключ, то в одну кучку надо сложить все эти записи.

В качестве хранилища используется BerkeleyDB, формат Btree. Исторически сложилось, не обсуждается, впрочем любые базы данных себя поведут примерно одинаково.

Кто виноват

  1. Ключей - много. В моем тестовом примере их 18 миллионов, а вообще может быть несколько сотен миллионов (на бОльшие размеры пока рассчитывать не надо).
  2. Ключ - это хороший хэш от строки, поэтому некий код практически является генератором случайных чисел.
  3. Дублирующих ключей (требующих аппенда записи) относительно мало, около 10%, правда есть ключи-рекордсмены, которые повторяются примерно в 0.3% случаев (60 тыс. повторов на 18M).

В результате, если не делать кэша размером хотя бы с половину базы данных (а делать его разумным, процентов 10-15) и просто писать данные в базу по мере образования, то все происходит довольно медленно: тестовые 18 млн. ключей пишутся в базу на моей тестовой машине около трех часов при размере кэша в 300 мегабайт и базе, дорастающей до 800M. Нет, 1800 транзакций в секунду - это неплохо, но хочется гораздо больше, ибо генерация тестовых данных занимает примерно 3 минуты.

Причина торможения понятна: если ходить в кэш с random-ключом, то вероятность cache hit примерно равна отношению размера кэша к размеру базы. Пока база маленькая - мы попадаем почти всегда, как только перерастаем кэш, так сразу начинаем изучать время HDD seek вместо более полезного занятия.

Решение, впрочем, довольно тривиальное.

Что делать

Давайте возьмем буфер, сколько не жалко (можно кусок кэша отъесть), будем накапливать в нем записи в порядке их порождения, затем сортировать то что накопили, склеивать то, что должно быть склеено ну и писать в базу в отсортированом порядке.

Не забываем, что BerkeleyDB рассматривает ключи как байтовую строку, поэтому сортировать надо в лексическом порядке.

Результат живителен. Для тестового примера в 18 млн записей и кэша БД в 100 мегабайт времена исполнения такие:

Размер буфера (записи)Время формирования базы hh:mm:ssРасход памяти на буфер для сортировки
18M00:01:06504Mb
10M00:01:30280Mb
7M00:02:36196Mb
5M00:03:18140Mb
2M00:09:5056Mb
1M00:31:4328Mb
103:12:1428 байт (но в данном случае кэш был 300Mb)

В этой таблице интереснее всего не верхняя строчка (хотя ускорение почти в 200 раз само по себе заслуживает внимания), а третья сверху. В случае с 196-мегабайтным буфером, общее использование памяти равно 300Mb т.е. столько же, сколько в последнем "тривиальном" случае (если быть точным, то BerkeleyDB аллоцирует кэши до 500Mb с 20% запасом, поэтому на третьей строчке общее потребление памяти даже меньше, чем на последней). Вместе с тем, правильное использование этих мегабайт позволяет ускориться в 75 раз ничего за это, по большому счету, не заплатив.

Comments

Алексей Иванов (not verified) - 25/Ноя/2008 23:25

> Не забываем, что BerkeleyDB рассматривает ключи как > байтовую строку, поэтому сортировать надо в
> лексическом порядке.

А это всегда так? Вроде, в BerkeleyDB можно подменить функцию сравнения ключей на свою - тогда в твоем случае можно пользоваться более быстрыми целочисленными сравнениями?

lexa - 26/Ноя/2008 07:30

В свое время в Top100 этот фокус не удался - что-то там падало и было криво. Разбираться тогда - не было сил.

Заметим, что при использовании qsort() целочисленные сравнения нифига не более быстрые, ибо строковое побайтовое сравнение в очень большой доле случаев срабатывает по первому или второму байту.

sappa (not verified) - 25/Ноя/2008 20:47

А если вообще отказаться от полной сортировки? У нас ведь задача попасть в кэш СУБД, а кэш СУБД может быть не таким уж и маленьким. Достаточно отсортировать по первому байту и иметь кэш размером в 1/256 от предполагаемого объема СУБД (несколько упрощенно) чтоб в кэш помещались все записи с ключом начинающимся на, скажем, 0x55. Вне зависимости от следующих за ним байтов. Они же все кучно расположены. Что это дает? Да удаление операции сортировки вообще. Достаточно иметь 256 односвязных списков в которые будут добавляться записи при генерации, в какой именно - вибирать согласно первому байту хэша. Операция очень быстрая, выбрать из 256-байтной таблицы адрес головы списка и два указателя поправить. Не чета настоящей сортировке. После заполнения буфера - выгружаем списки последовательно. Внятно у меня получилось изложить?

lexa - 26/Ноя/2008 01:37

Ну, в общем случае сделать ~50-60% сортировки (судя по числу срабатываний сравнений, см тут: http://blog.lexa.ru/2008/11/20/o_sortirovke_uzhasi_programmirovanija___2...) наверное не сильно хуже. Мне не сложно проверить (заменив функцию сравнения в сортировщике).

Но надо учитывать вот что
1) сортировка - штука быстрая, это где-то 2% от рантайма и 10% от user time
2) за счет полной сортировки получается заранее склеить записи с одинаковыми ключами, а это ~10% обращений в базу в моем случае
3) Списки дадут большой оверхед по памяти: 1 или 2 указателя (8 или 16 байт на 64-битной архитектуре), а размер записи с ключом у меня - 28. Можно, наверное, 256 динамически растущих массивов, но на реаллоках умрем (память будет сильно фрагментированной - а речь ведь идет о десятке мегабайт на список, скорее всего реальной памяти мы возьмем вдвое против потребного т.е сравнимо со списком).

Т.е. не все так просто :)

lexa - 26/Ноя/2008 04:50

Научные исследования показали, что если все отсортировать, то кэш вообще не нужен (больше некоторого минимального минимума).
Т.е. если есть память на кэш, то лучшее ее потратить на буфер сортировки.

http://blog.lexa.ru/2008/11/26/optimal_naja_zapis__v_btree_zhivitel_naja...

andy_scott (not verified) - 26/Ноя/2008 09:03

я бы, наверное, прежде всего проверил вариант "открыть файл нужной длины, mmap() его в память" и с ним и работать без всяких промежуточных DB как с массивом

lexa - 26/Ноя/2008 14:05

mmap-ed файл, естественно сортированный, это отличное хранилище, пока оно не очень большое. Там довольно очевидные недостатки
- очень дорогое удаление и вставка (в общем случае, половину файла надо подвинуть)
- 2-гигабайтное ограничение для 32-битных ОС
- вымывается кэш операционки.

Но для read-only storage не очень больших размеров (или в ситуации, когда можно побить на сегменты и одновременного доступа к разным сегментам немного) - отличная вещь, очень любим.

andy_scott (not verified) - 26/Ноя/2008 20:33

из описания у меня сложилось впечатление, что это именно R/O хранилище и вставок не нужно, значит ошибся (удаление дело такое, можно просто помечать удаленных)

32 бита это уже не то, чтобы и ограничение, по нынешним-то временам массовых 64-битных процессоров :) тем более 18 мегазаписей по 20 байт - не так и много

насчет кэша операционки не совсем понял, разве он не динамический? впрочем, я сильно отстал от нынешней ситуации, ту же fbsd пользую как юзер и в кишки настроек ядра не хожу, и так хватает

lexa - 27/Ноя/2008 03:07

18М записей - это в тесте. В жизни будет на порядок больше.
А 32 бита - требование, причем в него можно вписаться.

andy_scott (not verified) - 27/Ноя/2008 05:06

тогда 2q на желтые штаны :)

lamantyn (not verified) - 26/Ноя/2008 11:10

Я чего-то не понял задачу задачи.

"Индекс должен помещаться в кеш" - это достаточно тривиально и известно сто лет.

У меня задача - принять 500 млн записей в день. Самая важная технология - partitioned table. СУБД работает с сегодняшним субсетом данных, в предыдущие дни лежат на диске не мешаются.

lexa - 26/Ноя/2008 14:11

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

А задача задачи, если переводить с языка ТЗ - это что-то в районе 100-500 тысяч лукапов в секунду по редко изменяемому стораджу в котором up to 200 mln записей. Памяти при этом не очень много т.к. на 32-битной ОС тоже должно работать. Правда там есть облегчающее обстоятельство - в подавляющем количестве случаев lookup будет failed.

lamantyn (not verified) - 26/Ноя/2008 15:01

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

lookup - это пользовательский запрос найти запись по ключу?
500 тыс пользователей в секунду где-то нажимают на кнопку и вытаскивают запись из этой базы? Это какая-то фантастическая нагрузка.

Время записи тебя волнует из-за downtime'а ? Записи генерятся и должны быть записаны в течении дня или один раз в конце дня?

Я тут попытался воспроизвести - 18млн 30 байтных записей.
bcp-in в неиндексированную таблицу заняло 88s (сейчас пойду вешать звезлюлей SAN-техникам) и построение индекса 9s.

lexa - 26/Ноя/2008 15:45

lookup - не пользовательский. Эта штука обрабатывает входные данные (неважно откуда взяты, просто поток данных), заявленная в требованиях скорость обработки приводит к указанной частоте лукапов (100k/sec - хороший случай, 500k/sec - плохой), при этом обработчик данных на самом деле может их жевать на одном ядре производя 2-3 миллиона ключей для лукапа в секунду, но этого уже не прожевать (а 500k на заявленных размерах - прожевать без проблем). Я, по всей видимости, не могу рассказывать более подробно (даже из какой конкретно области задача. ну обычная такая задача).

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

Интересно еще машинами померяться. Ты, небось, на настоящем сервере развлекался?

А скорость заливки меня интересует по той причине, что неприлично елозить диском и заливать три часа то, что заливается за минуту. Три часа - это в ситуации когда а) "индекс не влезает в кэш" б) решаем в лоб. Т.е. сам сторадж (Berkeley DB) - он хороший, там можно быстро поудалять-повставлять немножко, но с точки зрения обычной SQL-бд это в одной кучке и индекс и данные, индекс оторвать нельзя.

lamantyn (not verified) - 26/Ноя/2008 16:57

Ну я попробовал одним проходом - залил в таблицу с индексом, пакетами по 100k rows. Он перемены мест слагаемых сумма не изменилась. Раздельность же дает представление, что время теряется на фактической записи, а не сортировке.
Дисковые технологии демонстрируют удивительный прогресс в объеме и удивительное отсутствие прогресса в скорости.

Сервер настоящий, cpu-z:
http://www.dontsov.com/tmp/pc1.png
http://www.dontsov.com/tmp/pc2.png
http://www.dontsov.com/tmp/pc3.png
а вот что происходит на другом конце fiber'а (гигантский SAN) мне неподконтрольно.

lexa - 26/Ноя/2008 17:06

Во, а у меня быстрее на Core2Duo 1.86 с SATA-диском :)

Можешь повторить эксперимент, вписавшись в (например) 100 мегабайт памяти?

lamantyn (not verified) - 26/Ноя/2008 17:39

Может у Berkeley DB какой-нибудь lazy write и она репортает запись до фактического завершения? :-)

3 миллиона 22х байтовых записей, 114MB файл.
14s запись и 4s построение индекса.

Ключ, правда, у меня 8байтовый datetime, распределение почти уникальное.

lamantyn (not verified) - 26/Ноя/2008 17:55

Хотя надо заменить, что sp_spaceused показывает
92mb для данных и 57mb для индекса.
т.е. 4s это не просто сортировка ...

если делать кластерный индекс, то таблица занимает 116mb.
Времени это берет те же 4s (на пересортировку и перезапись таблицы).

lexa - 27/Ноя/2008 01:18

8 mb/sec - позорно для мегадорогого SAN :)

Anonymous (not verified) - 27/Ноя/2008 02:04

Зато честно. :-) Ты на reset нажми сразу после "записи" в Berkeley DB и посмотри сколько записей на диске останется. :-)

lexa - 27/Ноя/2008 03:00

Там на закрытии fsync() делается - т.е. все будет на диске.

А время я считаю вместе с close()

tanelorn (not verified) - 27/Ноя/2008 03:15

Чтобы прогресса в скорости было нужно что-то кардинально менять в консерватории (технологии). А сегодняшные технологии ничего нового не предлагают - количество оборотов на дисках остаеться тот-же самым 7.2К, 10К, 15К. Растет только обьем данных на площади. В результате этого поднимается seek time что тоже не способствует тому чтобы скорость поднялось.

Хотя если заменить диск на SSD то можно поднять скорость _чтения_ раз в десять и больше, при этом обсолютно не важно где хрянятся данные, т.е. понятия sequential/random read осувствуют. Ну и быть готовых выложить 30 раз больше за гигабайт.

Правильная организация tired storage - буфер/кеш в памяти tier1, SSD для хранения индексов - tier2, SAN FC 15K Disk - tier3 с базами/логами и так далее с целю чтобы как можно больше запросов обслуживались как можно быстрым выдом памяти. Естественно это не дешего.

lexa - 27/Ноя/2008 03:25

Многие (например, Петя Зайцев) говорят, что если transaction log класть на SSD, то общая стоимость дискового хранилища при тех же транзакциях в секунду - падает.

И это при сохранении старой парадигмы, а вообще под SSD нужно иначе программировать.

tanelorn (not verified) - 27/Ноя/2008 04:03

Интересно было бы послушать обоснование про падение стоимости хранилища если класть transaction log на SSD. Если ничего в мире баз данных и storage за последный месяц не случилось, то transaction log - это всегда sequential writes of data. Т.е. хренилище для TL должно быть оптимизировано для _записи_, а не для чтения.

Все учебники советуют класть TL на RAID10 или по крайней мере на RAID1. Не забываем что write time у SSD диска _ниже_ чем у SATA 7.2k диска. Поэтому при условиях держания TL на SSD производительность дисковой подсистемы (и в результате - баз данных) должно падать.

Полностью согласен с тем, что хорошо оптимизированная база должна строится под storage performance and type а не наобарот. Это я время от времени пытаютсь довести до клиентов. Не все понимают с первого раза. Подай им 10000 транзакции (IOPS) в секуду и когда они слышат во столько это обойдется....

lexa - 27/Ноя/2008 04:35

Следите за руками.
15k-rpm диск вращается со скоростью 4 миллисекунды на оборот. Т.е. даже без seek средняя дисковая транзакция будет 2 ms просто запись и 6ms с read-after-write. C random - хуже, нужно еще seek time добавить (еще 3-4ms для лучших дисков).
Итого, в лучшем из лучших случаев мы будем иметь 500 Write IOPS, а скорее чуть меньше (в тестах намеривают под 400).

Для разумного SSD из текущей линейки - Intel X25-E (быстрый, относительно дорогой но без наворотов вроде DRAM с батарейкой) - интел врет про 3300 4-килобайтных random write в секунду, причем random и stream отличаются, понятно, очень мало (для stream - 4k с хвостом получается).

У предыдушего поколения (MTRON-ов всяких) несколько хуже, но все еще много лучше чем у дисков.

Понятно, что на SLC flash не так много дисков делается, ибо дорого, но в ряде узких мест они окупаются.

tanelorn (not verified) - 27/Ноя/2008 05:08

Это только в том случае если принять что у SSD 4K IOPS _действительно_ существует в природе. Пока-что то что _сейчас_ есть, даже для single layer SSD write performance на уровне SATA дисков.

Опять-же, если за последный месяц что-то кардинально поменялось во вселенной, я не знаю.

lexa - 27/Ноя/2008 05:21

Времена доступа порядка 0.1ms - они реально существуют. И тому же интелу я не вижу оснований не верить. Если X25-E на рождественских распродажах подешевеют разумно - возьму на пробу (пока жду Micron P200)

tanelorn (not verified) - 27/Ноя/2008 05:26

Если получится по пожалуйста прогони на нем iometer с размерами 1, 2, 4, 8, 16, 64, 128, & 1024kb, seq/random при queue depth от 2-х до 32-х.

Очень интересно было бы посмотреть на результаты.

lexa - 27/Ноя/2008 05:38

Это не вполне то, потому что паттерн немножко другой, но смысл тот же.
В рамках нашей дискуссии можно смотреть на Database

http://techreport.com/articles.x/15931/9

lexa - 27/Ноя/2008 03:30

Да, у обычных HDD seek time потихоньку падает, transfer довольно быстро растет за счет увеличения плотности. Но не на порядки, конечно.

С RAM та же фигня - объемы растут быстро, bandwidth - медленно, latency - вообще почти не растет. И в отличие от дисков, прорывных технологий вовсе не видно.

tanelorn (not verified) - 27/Ноя/2008 04:10

С RAM ситуация другая. Если с дисками ничего за последные 20 лет не менялось - те же блины которые крутятся, то с RAM-ом мы проходили FP-RAM, EDO, SDRAM, DDRAM, FB-RAM и вот DDR3 на подходе. Причем каждый раз новый вид памяти стоет 2-3 дороже по сравнению с предыдущим поколением.

Насчет обьема - 64GB FB-RAM (8x8GB) сейчас стоет как хорошая used car...

lexa - 27/Ноя/2008 04:18

А с RAM - те же микросхемы, может только ножек побольше :)
С дисками мы прошли GMR, перпендикулярную запись и прочие страшные слова - и это только за последние лет 10, раньше я не следил или уже забыл

А эффект близкий - рост bandwidth (мне за 20 лет сложно оценить, могу за 15 - у дисков примерно на 2 порядка, у памяти - тоже), падение latency (у памяти раз в 6 за те же 15 лет, у дисков - раза в 4 минимум).
Я же помню эти серверные диски 93-го года - 700 мегабайт, 5 дюймов, полная высота, мегабайт 6-10 в секунду на чтение в хорошую погоду, десятки миллисекунд avg seek, когда много seek-s - корпус big tower трясется как уазик на ухабах.

Ну и с ценой - пик цены 92-93 года на память - 30 доларов за мегабайт, помню как я 16Mb за $600 покупал. SCSI-диск в 92-м - доллар за мегабайт.

tanelorn (not verified) - 27/Ноя/2008 04:35

Ну да, обьемы выросли на порядки, цены понизились, стали класть диски в массивы, а вот bit error rate для диска осталься тем-же самым.

В результате тот, который строет 10-ти терабайтный RAID 5 массив из 1ТБ consumer SATA дисков (предлагают-же блин) или идиот или неуч....
http://en.wikipedia.org/wiki/RAID_5#RAID_5_disk_failure_rate

lexa - 27/Ноя/2008 04:38

BER кстати упал. Я помню цифры в районе 10^-13, а сейчас 10^-15.

И надежность, по ощущениям, выросла. В 2000-2001-м годах в Рамблере падеж дисков был в районе 1% в месяц, сейчас у нас - много меньше.

Что касается массивов - читали про гугловую петабайтную сортировку на 48 тысячах дисков? Ну типа да, за время теста диски отваливаются, тройное дублирование спасает.

tanelorn (not verified) - 27/Ноя/2008 05:20

Гугл может тройное дублирование себе позволить, но это не значит что многие могут позволить для себя то-же самое.

Что происходит у гугла в датацентрах я знаю не понаслышке, у меня двое друзей в их storage division работают. У них датацентры в среднем раз в 9 месяцев сгорают. В букавальном смысле. Для FEC и восстановления данных у них альгоритмы (адаптированные для них turbo codecs) встроены на уровне application, и data redundancy на уровне storage controllers не используется. Т.е. у них дисковая подсисема построена на уновне JBOD (в основном используется HP DL180/185/320s) чтобы запаковать как можно больше ТБ (они используют 7.2К 1TB SATA) в 1U.

lexa - 27/Ноя/2008 05:36

Но тройное дублирование на дешевых SATA - оно дешевле мега-SAN-ов. Даже с учетом рабочих рук, которые должны быть квалифицированными, конечно. Ну и начиная с каких-то объемов, если нужно всего 10 терабайт, то ситуация может быть другой.

Вообще, забавный разговор. Году в 2001-м ответить на фразу "терабайтное хранилище" было только "уууу!", а у меня сейчас 2 терабайта под столом, еще три над столом и пара терабайт офлайн в шкафу лежит.

lamantyn (not verified) - 27/Ноя/2008 16:09

<q> Но тройное дублирование на дешевых SATA - оно дешевле мега-SAN-ов. </q>

Неочевидно.

<q> у меня сейчас 2 терабайта под столом </q>

1.5TB - $120

http://www.newegg.com/Product/Product.aspx?Item=N82E16822148337

lexa - 27/Ноя/2008 16:17

Да очевидно.
Посмотри на тех, у кого в сторадже реальный бизнес. Ну вот гугл (или амазон S3, хотя про них меньше известно). Сторадж, очевидно, самый толстый в мире, если бы SAN был бы дешевле - не было бы у них этих мульенов писюков.

lamantyn (not verified) - 27/Ноя/2008 16:29

99% того, что хранит гугл - это мусор, пропажа которого не отразится на бизнесе компании. Это не "реальный бизнес", а все еще наколеночный стартап.

lexa - 27/Ноя/2008 16:47

То что SAN - это такая job security и никого не накажут за покупку самой крутой дисковой полки/шкафа, ибо там дохрена девяток и вообще сервис-инженер приезжает через час после звонка - это все понятно. То же самое и с базами данных - то, что Oracle может просто давать неправильный ответ на запрос (при том, что по маленьким данным все тесты отличные) - никого не ипет, это Oracle, если они не смогли, то кто же?

Но это не имеет отношения к "дешевле".

А так - тебе EMC с удовольствием продаст тот же терабайтный Seagate ES.2 за 700 баксов вместо 150. Все будут довольны.

lamantyn (not verified) - 27/Ноя/2008 17:30

Ты просто не осознаешь масштаб стоимости переделки базы софта на "встроенное писание на три диска" с distributed transaction.
Ну представь, что тебе нужно писать код, работающий на multicore cpu. который может произвольно посчитать 2*2=5, поэтому тебе нужно параллельно делать вычисления на разных ядрах и сравнивать результаты.

А геморрой с синхонизацией данных после замены битого диска?
А сколько времени займет переставить эти три диска в лругой сервер, если материнка сдохла?

<q> это Oracle, если они не смогли, то кто же? </q>

И кто же? Фрилансер с MySQL, от голода фантазирующий как Мюнхгаузен?

lexa - 28/Ноя/2008 03:15

Масштаб переделок там большой.
Но все там будем - нет никаких шансов прожить в рамках старой парадигмы (без распределенной конструкции) в ближайшие 10-20 лет.

И таки да - историй про MySQL, оптимизации которого приводят к неверным результатам что-то не слышно.

lamantyn (not verified) - 27/Ноя/2008 11:31

Набрать нужные мне терабайты сегодняшними SSD по 80GB - это будет сиотреться порнографично. :-)

Скорее всего проблема в размере записи и кластера. SQL записывает 8k страницу физически записывая 32k кластер.

lexa - 27/Ноя/2008 11:55

между тем, на фоне Savvio 15K новые SSD не выглядят безобразно дорогими.

andy_scott (not verified) - 26/Ноя/2008 20:39

вообще если я правильно помню, прямо в доке по BDB было сказано, что заливать btree оптимальнее всего предсортированными записями, оно так изначально заточено

lexa - 27/Ноя/2008 03:03

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

Anatoly Skoblov (not verified) - 27/Ноя/2008 18:04

Решение задачи принципиально зависит от соотношения доступной памяти и максимального размера БД.

Если говорить о задаче типа "счетчика", с 8-байтным ключем и 20-байтными данным на современной машине, 100М записей :), то мое решение такое:

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

статически выделенная таблица указателей на "страницы", размером в величину хеша * на размер указателя. Тут у нас не возникает никакого дефицита.

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

Тут у нас уже дефицит памяти и адресного пространства в 32 битах становится существенным. Но с 64 битами на современной машине мы прекрасно вписываемся.

при изменении данных они маркируются и фоновый процесс сливает все в БД. Таким образом производительность дисков не влияет на производительность самой системы.

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

Я так делал еще в DOS :), где дефицит памяти был куда как более суровым. Программирования тут - на несколько часов, обсуждать дольше.

lexa - 27/Ноя/2008 18:19

Анатолий,

к несчастью 32-бита (т.е. реальные 2Gb на процесс с учетом портабельности) являются требованием. И в этих 2 гигабайтах 5-6 гигабайтная база возникает, увы.

Помимо этого, уметь работать с данными, которых несколько больше чем имеется RAM - это такое очень хорошее пожелание, которое позволит использовать девелопемый софт более широко. Если на машине с 64 битами и 64 гигабайтами получится работать с полутерабайтной базой - отлично. Если с четвертьтерабайтной (что получится с гарантией) - ну просто хорошо, это значит в стойку можно впихнуть обработку десятка терабайт.

Ну а считать битики - мы умеем.

Anatoly Skoblov (not verified) - 27/Ноя/2008 21:08

Я выдал решение той задачи, что сформулирована. Там не было упоминанй о дефиците памяти и 32 битах :) Любые лишние свойства, выходящие за рамки поставленнйо задачи и усложняющей решение, являются той самой болезнью "супердвижка", о которой мы месяц назад говорили.

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

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

lexa - 27/Ноя/2008 21:23

В первоначальном посте сформулирована задача "сложить в BTree". Ее ты вообще не обсуждаешь. Там же написано (хотя и косвенно), что в память не влезаем.

Если ты взял (реальную) задачу из комментов, то там и про размер и про 32 бита тоже написано, дочитай комменты до конца.

Anatoly Skoblov (not verified) - 28/Ноя/2008 01:13

Нет, задача сформулирована не так - "сложить в БД и иметь доступ по ключу" + "в качестве хранилища используется btree". Вот я и увидел задачу "собрать в памяти и использовать, а хранить в битри"

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

lexa - 28/Ноя/2008 12:32

Единственное, что представляет интерес - если объем даных заведомо больше размера памяти, то как и в какой момент сливать данные в БД.

И ровно этот вопрос и обсуждается в данном посте, если ты не заметил....

Anatoly Skoblov (not verified) - 28/Ноя/2008 16:41

С трудом заметил, с третьей попытки, прочитав внимательно комментарий к табличке.

А в середине заметил, что нам нужны лукапы, а не просто оптимизация заливки в БД, о чем в посте.

И заметил оценку максимального объема данных, позволяющую задуматься о случае "памяти хватит на все".

Отсюда и раздвоение в моем комментарии

"Когда сливать", на самом деле не очевидно. У нас есть (применительно к моему описанию) 3 момента для записи:

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

если все влезает в память, то нас интересует вариант 1, а вот если не влезает - не очевидно.

Ну и ключевой момент, который ты пропустил - большой индекс-массив с размерностью "количество ключей/N" и маленькие растущие массивы "страниц" совсем не страшны, зато очень эффективны. Реаллоки там не нужны, на самом деле, там просто нужна оптимизация выделения памяти под работу с записями известного размера. У меня это стандартно в любых реалтаймовых задачах. Это с одной стороны приводит к некоторому оверхеду, но очень небольшому. Вред от реаллоков больше.