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

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

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

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

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

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

2. Firebird — более-менее быстро импортирует, но индексы строятся при первом использовании. Неожиданно, но неприятно :)

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

Решение появилось достаточно неожиданно: в потоке информации я «ухватился» за описание патента Google на BigTable:
ru.wikipedia.org/wiki/BigTable ^[1]

Понятно, что использовать эту технологию я не имел права, но основные идеи — вполне.

Если вкратце, то подразумевается хранение практически неограниченного количества строк, причем скорость доступа обеспечивается многоуровневым разбиением. Допустим, строка 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

Источник ^[2]