Использует ли HBase первичный индекс?

Question

Как HBase выполняет поиск и получает запись? например, каков эквивалент в HBase для B-деревьев СУБД?

[РЕДАКТИРОВАТЬ]

Я понимаю, как HBase разрешает -ROOT- и.META. таблицы, чтобы узнать, в каком регионе хранятся данные. Но как выполняется локальный поиск?

Чтобы лучше проиллюстрировать, вот пример:

1. Я начинаю поиск (получить или отсканировать) запись с помощью ключа 77.
2. Клиент HBase считает, что ключ находится в 50-100 регионах, которые хранятся в RegionServer X.
3. Клиент HBase связывается с RegionServer X для получения данных.

Как RegionServer X узнает местоположение записи 77?

Использует ли RegionServer какую-либо таблицу соответствия (например, B-деревья СУБД?) Для ключей региона? Или нужно читать все содержимое StoreFiles, для записей от 50 до 77?

Answer 1

TL;DR: похоже, что HBase (как BigTable), использует как структуру, похожую на дерево B+, для поиска. Таким образом, ключ строки является первичным индексом (и единственным индексом любого вида в HBase по умолчанию).

Длинный ответ: Из этого сообщения в блоге Cloudera о пути записи HBase похоже, что HBase работает следующим образом:

Каждая таблица HBase размещается и управляется наборами серверов, которые подразделяются на три категории:

• Один активный главный сервер
• Один или несколько резервных главных серверов
• Много региональных серверов

Региональные серверы способствуют обработке таблиц HBase. Поскольку таблицы HBase могут быть большими, они разбиты на разделы, называемые регионами. Каждый сервер региона обрабатывает один или несколько из этих регионов.

В следующем параграфе есть некоторые подробности:

Поскольку ключ строки отсортирован, легко определить, какой сервер региона управляет каким ключом. ... Каждый ключ строки принадлежит определенному региону, который обслуживается сервером региона. Таким образом, основываясь на ключе put или delete, клиент HBase может найти нужный сервер региона. Сначала он находит адрес сервера региона, на котором расположен регион -ROOT-, из кворума ZooKeeper. От корневого сервера региона клиент узнает местоположение сервера региона, на котором расположен регион -META-. На сервере мета-региона мы, наконец, определяем фактический сервер региона, который обслуживает запрашиваемую область. Это трехэтапный процесс, поэтому местоположение региона кэшируется, чтобы избежать этого дорогостоящего ряда операций.

Из другого сообщения в блоге Cloudera, похоже, что точный формат, используемый для сохранения HBase в файловой системе, постоянно меняется, но описанный выше механизм поиска ключей строк должен быть более или менее согласованным.

Этот механизм очень и очень похож на поиск в Google BigTable (подробности вы найдете в Разделе 5.1, начиная с конца страницы 4 в PDF), который использует трехуровневую иерархию для запроса местоположения ключа строки: Chubby -> Root tablet -> планшеты METADATA -> актуальный планшет

ОБНОВЛЕНИЕ: чтобы ответить на вопрос о поисках внутри самого Сервера Региона: я точно не знаю, но так как ключи строк отсортированы, а HBase знает ключи начала и конца, я подозреваю, что он использует двоичный поиск или интерполяционный поиск, оба из которых действительно быстрые - log(n) и log(log(n)) соответственно. Я не думаю, что HBase когда-либо нужно будет сканировать строки от начального ключа строки до того, который ему нужно найти, поскольку поиск по отсортированным ключам - это хорошо известная проблема, которая имеет несколько эффективных решений.