Мои проекты, как многие уже знают, подразумевают работу с реально большими объемами данных — сотни миллионов записей.
Причем это не просто «добавил-и-забыл», а регулярное их обновление, при этом работать на выборку они должны даже на достаточно слабых машинах. Пользователи моих продуктов скачивают и устанавливают базы себе на машину — так удобнее работать с большими выборками.
Меня часто спрашивают о движке, который я использую для организации данных, и сегодня я немного приоткрою завесу :)
Для начала — мои предыдущие эксперименты, чтобы вы не наступали на те же грабли:
1. MySQL — быстро импортирует, но нереально долго строит индексы. Подходит для случая «лучше один раз пару недель потратить, зато потом за пару минут долететь».
2. Firebird — более-менее быстро импортирует, но индексы строятся при первом использовании. Неожиданно, но неприятно :)
3. Готовые NoSQL-решения — не прижились, поскольку слишком «наворочены» для моих задач и создают дополнительные точки возникновения проблем в саппорте.
Решение появилось достаточно неожиданно: в потоке информации я «ухватился» за описание патента Google на BigTable:
ru.wikipedia.org/wiki/BigTable
Понятно, что использовать эту технологию я не имел права, но основные идеи — вполне.
Если вкратце, то подразумевается хранение практически неограниченного количества строк, причем скорость доступа обеспечивается многоуровневым разбиением. Допустим, строка 2,100,000 может находиться во 100-м блоке 2-й «таблетки». Каждый блок — 1000 записей, каждая таблетка — 1000 блоков.
Причем это должны быть именно строки, чтобы ты мог свободно их сортировать «подручными» средствами. Зачем «городить» свой код под каждый чих, когда есть куча готовых алгоритмов сортировки, в том числе и в памяти/многодисковые массивы.
Весь мой код основывается на следующей функции:
/// <summary> /// доступ к значениям /// </summary> /// <param name="key">ключ</param> /// <returns>значение</returns> public ValueType this[KeyType key] { get { // найдем ячейку int min = 0; int max = Cells.Count - 1; int mid = (min + max)/2; while (min <= max) { int compare = key.CompareTo(Cells[mid].Key); switch (compare) { case 1: min = mid + 1; break; case 0: // нашли, вернем значение return Cells[mid].Value; case -1: max = mid - 1; break; } mid = (min + max)/2; } // такой ячейки нет return Tablet.Database.NULL; } set { // найдем ячейку int min = 0; int max = Cells.Count - 1; int mid = (min + max)/2; while (min <= max) { int compare = key.CompareTo(Cells[mid].Key); switch (compare) { case 1: min = mid + 1; break; case 0: // нашли, выставим новое значение Cells[mid].Value = value; // изменилось Modified = true; // все, можно возвращаться return; case -1: max = mid - 1; break; } mid = (min + max)/2; } // такой ячейки еще нет, добавим Cells.Insert(min, new Cell<KeyType, ValueType> { Key = key, Value = value }); // изменилось Modified = true; } }
Как видно, он — не сложнее выеденного яйца (бинарный поиск и вставка), но его мощь — в экспериментах с разными параметрами: размерами блоков, алгоритмами сохранения/загрузки, форматом строки, сжатием/распаковкой содержимого блоков, алгоритмами размещения блоков на диске.
Неограниченность объема данных обеспечивается неограниченностью уровней вложенности: вы можете создавать блоки/подблоки/подподблоки и т.д. При этом они могут храниться в том числе и на разных винчестерах/разных машинах в сети. Все ограничено только вашей фантазией. Главное — понимать суть.
В приведенном мной примере можно работать не только со строками, главное чтобы KeyType поддерживал IComparable, а ValueType — сериализацию.
Один раз сделав что-то подобное, потом и не вспоминаешь о существовании каких-то чужих NoSQL-баз. Зачем, если ты можешь «играться» с параметрами, добиваясь нужной тебе производительности.
Пользуйтесь :)
Автор: MaxPastukhov