Google BigTable - это система, которая использует LSM-дерево в качестве основной структуры данных для хранения. LSM-дерево может использовать разные стратегии слияния. Двумя наиболее распространенными являются (1) уровневое объединение, которое более оптимизировано для чтения, и (2) многоуровневое объединение, которое более оптимизировано для записи. Эти стратегии слияния могут быть дополнительно настроены путем настройки соотношения размеров между соседними уровнями.
Я нигде не смог найти, каково поведение BigTable по умолчанию в этих отношениях, и можно ли его настроить или нет. В результате трудно понять, как это свойства производительности по умолчанию и как адаптировать их к различным рабочим нагрузкам.
При многоуровневом объединении уровень сборок LSM-деревьев выполняется до тех пор, пока не достигнет своей емкости. Затем он объединяет эти прогоны и сбрасывает результирующий прогон на следующий больший уровень. На каждом уровне выполняется не более O (T * log_T (N)), а стоимость записи составляет O (log_T (N) / B), где N - размер данных, B - размер блока и T - размер. соотношение между уровнями.
При выровненном объединении на каждом уровне LSM-дерева выполняется один прогон. Слияние происходит, как только новый уровень входит в уровень, и если уровень превышает емкость, результирующий цикл сбрасывается на следующий больший уровень. На каждом уровне выполняется не более O (log_T (N)), а стоимость записи составляет O ((T * log_T (N)) / B).
В результате эти схемы имеют разные характеристики производительности чтения / записи. Однако мне не удалось найти источники информации о том, использует ли BigTable Google многоуровневое или многоуровневое объединение, и каково соотношение размеров по умолчанию T? Кроме того, исправлены ли эти аспекты системы или они настраиваются?