Как Майкрософт делает эффективными гигабайтные сдвиги в связных списках?

Здесь опубликована часть будущей статьи для обсуждения. На данном форуме довольно часто подымались темы о достоинствах и недостатках Visual FoxPro , в частности о технологии Rushmore . Как выяснилось Рашмор использует преимущества древовидной структуры индексных CDX файлов. Поэтому интересно было бы научиться самим создавать эти файлы. Точнее говоря, добиться производительности их создания не хуже, чем это делает VFP-9 .

В интернете существуют несколько библиотек для работы с DBF файлами с открытым исходным кодом. Смотрите, например,
xHarbour Project – http://www.xharbour.org или http://sourceforge.net/projects/xharbour/files
Alexey Dolgachov – http://www.alxsoft.narod.ru
xbcdx.cpp – http://hk-classes.sourcearchive.com/documentation/0.8.3-4/xbcdx_8cpp-source.html
и т.д.

Однако просто взять и протестировать эти библиотеки на предмет эффективности создания дерева индексов проблематично, так как нужно глубоко вникать в их концепцию, а это время, причем нет уверенности, что оно будет потрачено с пользой. Гораздо лучше просто опубликовать алгоритм создания CDX файлов и пару картинок, поясняющих его работу. А вот с этим уже проблема. Поэтому здесь показан предполагаемый алгоритм вставки индекса в CDX файл и даны некоторые соображения по этому поводу. Тем не менее, некоторые вопросы все же остаются, поэтому хотелось бы их обсудить.


Тема эта достаточно интересна сама по себе, так наличие кругом калькуляторов не отменяет знание таблицы умножения. CDX файлы выбраны потому, что они связаны с DBF файлами, а те, наилучшим образом, по нашему мнению, подходят для работы с MFC списками – потомками CListCtrl .

Информацию о структуре компаундных индексных CDX файлов можно найти на сайте http://msdn.microsoft.com ( http://msdn.microsoft.com/en-us/library/k35b9hs2(VS.80).aspx ). Там же находим сопутствующие детали по компактным индексным файлам IDX ( http://msdn.microsoft.com/en-us/library/s8tb8f47(VS.80).aspx ) и обычным индексным файлам IDX ( http://msdn.microsoft.com/en-us/library/x0btabez(VS.80).aspx ). Здесь достаточно информации, чтобы построить структуры данных, но совершенно неясно, как вставлять новые индексы и удалять существующие. Видимо, с точки зрения Майкрософт , это знания не являются достаточно интересными :) . Поэтому, придется искать недостающие алгоритмы на просторах Интернет. Сделать это будет легче, если догадаться по рисункам последней ссылки (рис. 1), что речь идет о B+ деревьях .

Вероятно это название произошло путем сокращения словосочетания «бинарные B деревья + двухсвязный список» . Как бы там ни было это обычные бинарные деревья , все листья которого находятся на одном уровне, т.е. дерево сбалансировано (за счет сдвигов элементов листовых узлов ) и все узлы (в том числе, листья ) каждого уровня связанны в двухсторонний список , причем каждый узел имеет собственный ограниченный (фиксированного размера) массив пар «ключ – указатель» . Здесь указатель это либо номер записи ключа в файле (для листа), либо адрес структуры индекса . Эти данные уже легко позволяют найти описание и способ работы с B+ деревьями . Смотрите, например (по-русски), «Методы сортировки и поиска» by С.Д. Кузнецов ( http://www.citforum.ru/programming/theory/sorting/sorting2.shtml#5_1_1 ). Для англоязычных читателей можно предложить статью «B+ tree» в Wikipedia ( http://en.wikipedia.org/wiki/B+_tree ). Правда, там показан пример одностороннего списка вместо двухстороннего.

По крайней мере, на основании этой информации можно представить себе алгоритм работы с B+ деревьями . Однако практическая реализация этих алгоритмов может быть различной. Поэтому для экспериментальной проверки процесса вставки листьев в B+ дерево индексов CDX файлов, реализованного Майкрософт . пришлось воспользоваться утилитой IDXVeiw ( http://wareseeker.com/freeware/idxview-1.0/100675366/ ). Полученный алгоритм представлен на рис. 2 – 6.

Данный способ вставки элементов в B+ дерево , используемый Майкрософт для CDX файлов Visual FoxPro 9 сразу вызывает недоуменные вопросы. Неужели этот алгоритм является эффективным? Ведь очевидно, что происходит глобальный сдвиг элементов массивов на всех уровнях . Допустим, у нас уже имеются миллионы записей и происходит вставка пары «ключ – номер записи» в начало списка. Это означает что мы должны двигать миллионы элементов (мегабайты и гигабайты данных) для каждой новой вставки. Согласитесь, что этот способ нельзя признать эффективным. Может быть Майкрософт использует этот алгоритм только в начале, когда элементов еще мало и на сдвиги не тратятся много системных ресурсов? Для этого придется провести еще один эксперимент, подсчитывающий производительность работы используемых алгоритмов, так как логично предположить, что разные алгоритмы будут давать разную производительность. Для проверки мы использовали DBF файл, в котором всего одно символьное поле Key длиной 71 символ . Эта длина выбрана таким образом, чтобы массив пар «ключ – указатель» состоял только из шести элементов (для удобства демонстрации алгоритма). Записи этого файла представляют собой случайно сгенерированных 70 цифр и 1 букву (для построения рис. 3 – 7 брались 3 случайных цифры и 68 нулей ). Затем для определенного количества таких индексов замерялось время индексации затрачиваемое Visual FoxPro 9 и вычислялась производительность как отношения количества данных индексов (длиной 71 символ ) ко времени их создания. На рис. 7 продемонстрирована функциональная зависимость скорости построения индексов от количества таких индексов. Естественно, что на разных компьютерах производительность создания индексов будет различной, однако характерный вид показанных кривых сохраняется, с точностью до случайных флуктуаций, связанных с работой компьютера.

Демонстрация этих рисунков наглядно показывает, что CDX файлы создаются, как минимум , с помощью двух алгоритмов. Тем самым, стало ясно что Майкрософт использует алгоритм «глобальных сдвигов» (назовем его так) только для относительно малого количества индексов, до 10 – 20 тысяч или в пересчете на полный размер CDX файла, до 1 – 2 MB . Последним, похоже, используется алгоритм вставки индексного узла в двухсвязный список , который уже очень слабо зависит от общего количества индексов (наиболее вероятна логарифмическая зависимость). Можно предположить, что для большого количества индексов используется классический алгоритм вставки в B+ дерево , связанный с расщеплением узлов и «переливанием» элементов пар «ключ – указатель» таким образом, чтобы в индексном узле содержалось не менее целой части половины элементов.

К нашему огромному удивлению , оказалось, что это не совсем так или совсем не так :) . При расщеплении узла, новые уже не заполнены на 100% и если в этот момент пройтись по цепочке индексов, то можно обнаружить, что их количество не постоянно. Мы проделали подобные эксперименты для индексного файла размером до 1.5 ГБ . Во всех индексных узлах было ровно 6 уникальных индексов (длиной 71 символ ) и только в самом последнем узле их было ровно столько, сколько нужно, чтобы обеспечить суммарное их количество (задаваемое заранее). Для справки заметим, что если индексы не уникальны, то в индексном узде их могло поместиться 7, 8, 9 и более за счет сжатия VFP элементов «ключ – указатель» в индексных узлах.

Но как же тогда это сочетается с графиком производительности создания индексов? Как можно двигать локально элементы в списках, чтобы не образовывалось пустоты? Или алгоритм вставки в CDX список за счет глобальных сдвигов достаточно эффективен вплоть до двух гигабайтных DBF таблиц ?

Сейчас я пытаюсь реализовать на C++ представленный алгоритм глобальных сдвигов , но нет уверенности, что он будет также эффективен, как и у VFP-9 …

Рис. 1. Схема Майкрософт для структуры индексного файла.

Рис. 2. Вставка первых 6 ключей индекса в B+ дерево.

Рис. 3. Вставка 7, 8 и 9 ключей индекса в B+ дерево.

Рис. 4. Вставка 12 и 13 ключей индекса в B+ дерево.

Рис. 5. Вставка 36 ключа индекса в B+ дерево.

Рис. 6. Вставка 37 ключа индекса в B+ дерево.

Рис. 7. Скорость создания индексов в файле CDX Visual FoxPro 9 до 5000 и 250000 индексов.

Creation (insertion) algorithm of Visual FoxPro CDX files

Похоже, что Майкрософт не делает никаких глобальных сдвигов в связных списках . Более того, мало того что ключи в списках представлены «непрерывно» , так ведь они еще и упорядочены . Фактически мы имеем дело с внешней сортировкой индексных ключей по отношению к DBF файлу. А это уже совершенно другая «песня». Отсюда можно сделать вывод, что все это совершенно не обязательно делать с помощью глобальных сдвигов, достаточно просто воспользоваться классическим алгоритмом вставки элемента (пары «ключ – указатель») в листовой узел B+ дерева или каким-нибудь усовершенствованным аналогом а затем, если возникнет такая необходимость, сделать разовую переупаковку CDX файла (подобно сжатию DBF файла). Если бы индексный ключ всегда был бы один, то можно было бы вообще отказаться от дерева и ограничиться только связным списком, а поиск нужного элемента вести методом деления пополам, или подобным методом, тогда была бы достигнута еще большая компактификация индексных файлов. Но, видимо, чтобы не плодить множество индексных файлов для одного DBF файла, была введена дополнительная структура бинарного дерева.

Правда, остается пока отрытым вопрос об эффективности переупаковки индексного CDX файла в случае однократного изменения индекса. Тогда время переупаковки индексного файла может быть существенно большим по сравнению с временем изменения индекса. Возможно вопрос об эффективности переупаковки нужно будет решать отдельно для каждого особого случая.

Однако сейчас нам важнее определиться с общим алгоритмом вставки в B+ дерево который вполне может быть и единственным и даже вести себя подобно функциональной зависимости на рис. 7, левую часть которой вполне можно объяснить и краевыми эффектами . Детали можно будет уточнять уже в процессе реализации данного алгоритма.

Предлагаемый классический алгоритм вставки в B+ дерево в части вставки первых шести элементов будет точно таким же как и на рис. 2. Следующие этапы вставки продемонстрированы на рис. 8 – 11. Затем по идее должна быть переупаковка индексного CDX файла, по крайней мере, после полной индексации DBF файла (команда INDEX ON в Visual FoxPro ).

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

Рис. 8. Вставка 7 и 8 ключей индекса в B+ дерево в классическом алгоритме.

Рис. 9. Вставка 25 ключа индекса в B+ дерево в классическом алгоритме.

Рис. 10. Вставка 26 ключа индекса в B+ дерево в классическом алгоритме.

Рис. 11. Вставка 27 ключа индекса в B+ дерево в классическом алгоритме.

Уточнение алгоритма вставки индексных ключей в CDX файлы Visual FoxPro.

Итак, мы отказались от идеи глобальных сдвигов в связных списках B+ деревьев . То, что мы видим в результате применения команды VFP INDEX ON к некоторому DBF файлу на самом деле есть, скорее всего, результат вставки в индексное дерево уже упорядоченного ранее индексного ключа. Т.е. индексируемое поле DBF файла мы предварительно сортируем в некоторый буфер (оперативной или виртуальной памяти) путем внутренней или (для больших объемов данных) внешней сортировки и уже затем отсортированные ключи вставляем в B+ дерево . В этом случае, процесс вставки элементов пар «ключ – указатель» в индексные узлы становиться абсолютно тривиальным и полностью сохраняет «непрерывность» данных, их физическую и логическую упорядоченность. Тем самым он становиться похожим на алгоритм вставки, продемонстрированный на рис. 2 – 6, при условии, что ключи поступают не в произвольном а в уже упорядоченном порядке . Таким образом, снимается противоречие экспоненциального роста времени глобальных сдвигов от суммарного объема сдвигаемых данных . Ибо вставка элемента в индексный узел всегда происходит в последнюю свободную позицию последнего индексного узла (в силу своей предварительной упорядоченности).

В принципе, можно сразу ориентироваться на внешнюю сортировку , как более универсальную. Так, в общем-то, устроены и обычные базы данных. Если объем базы не большой, то в принципе все операции мы можем делать в оперативной памяти, а если уже такой памяти не хватает, то использовать файловую, виртуальную память. Таков подход был характерен для DOC-овских времен, смотрите, например, исходный код Object Professional, v. 1.22 . Однако сейчас более популярен подход сразу иметь дело с файловой памятью базы данных при любых объемах данных этой базы. Это упрощает алгоритмы и повышает надежность работы с данными. Тем более что физические диски современных компьютеров достаточно ёмкие и «шустрые», что работать с ними таким образом. Поэтому мы должны выбрать себе алгоритм внешней сортировки индексных полей DBF файлов, ибо Майкрософт вряд ли опубликует подобную информацию. Но это не должно нас сильно смущать, так как алгоритмы сортировок, хоть внутренней, хоть внешней, гораздо лучше представлены в Интернете и литературе, чем практические алгоритмы вставок в B+ деревья . А при нахождении более эффективного алгоритма внешней сортировки можно будет без проблем старый алгоритм заменить на новый.

Сортировка слиянием

Для того чтобы начинать программирование, для начала можно будет воспользоваться сортировкой слиянием , описание которой опубликовано в Википедии http://ru.wikipedia.org/wiki/Сортировка_слиянием . Далее мы процитируем обширный кусок оттуда, слегка адаптируя его к нашим условиям.

http://ru.wikipedia.org/wiki/Сортировка_слиянием Сортировка слиянием (англ. merge sort) – алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например – потоки) в определённом порядке. Эта сортировка – хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Для решения задачи сортировки индексируемого поля DBF файла эти три этапа выглядят так:

1. Сортируемое поле разбивается на две половины примерно одинакового размера;
2. Каждая из получившихся половин сортируется отдельно, например – этим же алгоритмом;
3. Два упорядоченных буфера половинного размера соединяются в один.

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

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

Псевдокод на C++ подобном языке:

Алгоритм был изобретён Джоном фон Нейманом в 1945 году.

Время работы алгоритма порядка O(n*log(n)) при отсутствии деградации на неудачных случаях, которая есть больное место быстрой сортировки (тоже алгоритм порядка O(n*log(n)) , но только для лучшего случая). Расход памяти выше, чем для быстрой сортировки, при намного более благоприятном паттерне выделения памяти – возможно выделение одного региона памяти с самого начала и отсутствие выделения при дальнейшем исполнении.

Популярная реализация требует однократно выделяемого временного буфера, равного размеру сортируемого поля, и не имеет рекурсий. Шаги реализации:

1. InputArray = сортируемое поле, извлеченное во внешний массив, OutputArray = временный буфер.

2. Над каждым отрезком входного массива InputArray[N * MIN_CHUNK_SIZE . . (N + 1) * MIN_CHUNK_SIZE) выполняется какой-то вспомогательный алгоритм сортировки, например, сортировка Шелла или QSort .

3. Устанавливается ChunkSize = MIN_CHUNK_SIZE .

4. Сливаются два отрезка InputArray[N * ChunkSize . . (N + 1) * ChunkSize) и InputArray[(N + 1) * ChunkSize . . (N + 2) * ChunkSize) попеременным шаганием слева и справа (см. выше), результат помещается в OutputArray[N * ChunkSize . . (N + 2) * ChunkSize] , и так для всех N , пока не будет достигнут конец массива.

5. ChunkSize удваивается.

6. Если ChunkSize стал >= размера массива – то конец, результат в OutputArray , который (ввиду перестановок, описанных ниже) есть либо сортируемый массив, либо временный буфер, во втором случае он становиться конечным отсортированным массивом.

7. Иначе меняются местами InputArray и OutputArray перестановкой указателей, и все повторяется с пункта 4.

Такая реализация также поддерживает размещение сортируемого массива и временного буфера в дисковых файлах, т.е. пригодна для сортировки огромных объемов данных. Реализация ORDER BY в СУБД MySQL при отсутствии подходящего индекса устроена именно так (источник: filesort.cc в исходном коде MySQL ).

Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:

Есть несколько вариантов функции merge() , наиболее простой вариант может выглядеть как:


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

Общая идея всего этого такая, если индексируемое поле DBF файла уже упорядочено, например, внешней сортировкой слиянием , то построение упорядоченного индексного CDX файла уже не представляет никаких трудностей.

Однако некоторые вопросы все же остаются.

1. Одновременная сортировка множества индексов.
2. Разделение доступа к индексному файлу.
3. Изменение дерева индексов при однократной вставке записи в индексированный большой DBF файл.

По первому пункту можно предложить «параллельную» сортировку. По второму использование возможностей MMF плюс логическая оптимизация программы и структуры базы данных. А по третьему пункту самая интересная ситуация. Экспериментальная проверка показывает, что при вставке в гигабайтный индексированный DBF файл записи, которая логически должна быть в начале, она, как и положено, записывается физически в конец DBF файла и, самое удивительное , что соответствующий индексный ключ записывается в физическое начало индексного CDX файла практически мгновенно . Майкрософт не перестает нас удивлять и задал еще одну задачку. Применять данный алгоритм сортировки / индексации для одной записи на огромных файлах абсолютно не выгодно! Ибо это займет очень много времени. Я бы просто записал этот индексный ключ в конце CDX файла, по аналогии с DBF файлом, тем более что деревья и связные списки это позволяют. И периодически делал бы переиндексацию базы данных в удобное для себя время, как периодически должна делаться переупаковка DBF файлов (не исключено, что автоматически с переиндексацией).

Короче говоря, пока это неразрешимая загадка. Как Майкрософт удается вставлять физически упорядоченные индексы в гигабайтные CDX файлы практически мгновенно? Это уже что-то из области мистики. Может быть, это и есть один из секретов Rushmore

Vowk1-й варант - отпадает, потому что слишком сложная система. Вряд ли там обойдешься изучением 2-3 файлов на C++.
2-й варант - платный
3-й варант - какие-то классы, тоже вероятно для Linux. Не очень конкретно.
У мну есть импортная библиотечка на Паскале для NTX и NDX, я ее под Delphi и Free Pascal планирую переделать. Ну еще десяток научных статеек надыбал по вопросам создания больших индексов. Больше ничего не попалалось.
Если реально сам пишешь код для работы с dbf / cdx файлами, то очень часто возникают различные вопросы. Иногда смотришь, что наваяли другие, чтобы сравнить со своим «шедевром». Вывод, в общем такой. Особого смысла в этих библиотеках нет, потому что структуры достаточно хорошо прописаны в msdn.microsoft.com, а что касается алгоритмов работы, то все авторы изобретают собственные или берут общеизвестные, так как MS не публикует такие вещи. А поскольку практические алгоритмы работы с B+ деревьями весьма сильно различаются по производительности и ресурсоемкости, то глупо слепо переписывать их из других источников, в которых нет анализа эффективности этих алгоритмов. Поэтому ваши «научные статейки» было бы весьма интересно прочитать. А так меня интересуют только cdx файлы версии VFP-9 в реализации на С++. В своих публикациях я пытаюсь нащупать нужный алгоритм работы с ними, но пока остаются еще несколько нерешенных вопросов, хотя для собственно программирования информации уже достаточно.

ИзопропилEmery,

Как блокировки реализуются при обновлении индекса в многопользоватеском режиме?
Пока никак. Еще сама индексация до конца не реализована. Так что многопользовательская «вкуснятина» нам еще предстоит :) .
\

Предварительные итоги по алгоритму вставки индексных ключей в CDX файлы Visual FoxPro

На основе наших исследований просматриваются два способа работы с индексными файлами .

1. Работаем с B+ деревьями по классическому методу , когда данные вставляются в дерево в порядке их поступления. В случае необходимости физически переупорядочиваем индексы (наряду с логическим порядком). Сделать это несложно, например, используя логический порядок ключей старого индексного файла для записи их в новый , тем самым, добавляя к логическому порядку еще и физический. Старый индексный файл затем удаляется. Это можно делать также автоматически при переупаковке (сжатии) DBF файла.

2. Сразу создаем физический и логический порядок индексов путем предварительной внешней сортировкой «естественным слиянием» в файловые буфера ( natural merge sort ) при полной индексации / переиндексации индексного файла. При разовой вставке / модификации записи в DBF файле физический порядок индексного файла не поддерживаем (т.е. новый индексный ключ пишем в конец файла, если нет места в середине). И опять же при необходимости делаем физическое переупорядочивание индексов.

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

Мы уже писали, что «Майкрософт умудряется сохранять физический порядок в индексном файле при разовой вставке / модификации записи без его явного физического переупорядочивания . Однако, более тщательные исследования этого вопроса, показали, что это не так . Похоже, на мистику нет даже намека :) . Все, до банального, просто. Тот же «классический метод вставки в B+ дерево» у Майкрософт , как и должно быть по логике вещей, при любом количестве индексных ключей или размере индексного файла. Однако, при создании индексного файла с «нуля», физический порядок создается, наряду с логическим, чего легко можно достичь предварительной внешней сортировкой индексных ключей или перезаписью индексного файла, используя его логическую структуру. Тем самым, из наших двух способов работы естественным образом вытекает один.

При создании индексного CDX файла или при полной переупаковке / переиндексации DBF файла индексные ключи предварительно сортируются , а затем на их основе создается B+ дерево по классическому алгоритму . А при модификации индексного файла (файла базы данных), предварительная сортировка не используется , только обычная вставка.

Поскольку физический порядок при интенсивных разовых вставках (модификации БД) постепенно теряется, то, очевидно, следует рекомендовать периодически делать полную переупаковку / переиндексацию DBF файла, например, во время простоя программы. Понятно также, что и периодическая дефрагментация жесткого диска будет сказываться благоприятно на скорости работы с нашей базой данных.

Внешняя сортировка «естественным слиянием»

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

Оно состоит из основных двух операций.

1. Разделение (расщепление) данной сортируемой последовательности S на множество локально упорядоченных (по возрастанию или убыванию) подпоследовательностей {s1, s2, s3, . . . , sK}, где все подпоследовательности, кроме, быть может, последней содержат более одной записи (ключа).

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

Эти две операции повторяются до тех пор, пока вся последовательность S не будет состоять из одной только подпоследовательности, т.е., пока она не станет упорядоченной.

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

АСУ ТПшникВ чем рисовали?
В Excel.