Мои проекты, как многие уже знают, подразумевают работу с реально большими объемами данных — сотни миллионов записей.
Причем это не просто «добавил-и-забыл», а регулярное их обновление, при этом работать на выборку они должны даже на достаточно слабых машинах. Пользователи моих продуктов скачивают и устанавливают базы себе на машину — так удобнее работать с большими выборками.
Меня часто спрашивают о движке, который я использую для организации данных, и сегодня я немного приоткрою завесу :)
Для начала — мои предыдущие эксперименты, чтобы вы не наступали на те же грабли:
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
