NoSQL своими руками: код для работы с нереально большими объемами данных

Мои проекты, как многие уже знают, подразумевают работу с реально большими объемами данных — сотни миллионов записей.

Причем это не просто «добавил-и-забыл», а регулярное их обновление, при этом работать на выборку они должны даже на достаточно слабых машинах. Пользователи моих продуктов скачивают и устанавливают базы себе на машину — так удобнее работать с большими выборками.

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

Для начала — мои предыдущие эксперименты, чтобы вы не наступали на те же грабли:

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-баз. Зачем, если ты можешь «играться» с параметрами, добиваясь нужной тебе производительности.

Пользуйтесь 🙂