Введение
В распределённом хранении данных P-Grid — это самоорганизующаяся структурированная одноранговая сеть, способная обрабатывать произвольные распределения ключей (и, следовательно, поддерживать лексикографический порядок ключей и запросы по диапазону), при этом обеспечивающая балансировку нагрузки на хранилище и эффективный поиск с использованием рандомизированной маршрутизации.
Выдающиеся черты
Хороший баланс нагрузки на хранилище, несмотря на произвольное распределение нагрузки по ключевому пространству. P Grid может естественно поддерживать и эффективно обрабатывать запросы диапазона, поскольку P Grid абстрагирует структуру префиксного дерева и поддерживает практически любое распределение ключей, как это наблюдается в реальных сценариях. Фактически, на каждом узле хранится несколько записей для каждого уровня, чтобы обеспечить отказоустойчивость (а также потенциально для управления нагрузкой запросов). По различным причинам, включая отказоустойчивость и балансировку нагрузки, за каждый листовой узел в дереве P Grid отвечают несколько узлов. Эти узлы называются репликами. Узлы-реплики поддерживают независимую подсеть реплик и используют протокол обмена данными для поддержания актуальности группы реплик. Избыточность как в репликации разделов ключевого пространства, так и в сети маршрутизации в совокупности называется структурной репликацией. На рисунке выше показано, как запрос разрешается путем пересылки на основе сопоставления префиксов.
Спросы диапазона в P-Grid
P Grid разделяет ключевое пространство с гранулярностью, адаптирующейся к нагрузке в данной части ключевого пространства. Следовательно, возможно реализовать сеть наложения P Grid, в которой каждый узел имеет схожую нагрузку на хранение даже при неравномерном распределении нагрузки. Эта сеть, вероятно, обеспечивает поиск ключей столь же эффективно, как и традиционные распределенные хэш-таблицы (DHT). Важно отметить, что в отличие от P Grid, DHT эффективно работают только при равномерном распределении нагрузки. Таким образом, мы можем использовать функцию, сохраняющую лексикографический порядок, для генерации ключей и при этом реализовать P Grid с балансировкой нагрузки, поддерживающую эффективный поиск точных ключей. Более того, благодаря сохранению лексикографического порядка, запросы по диапазону могут выполняться эффективно и точно в P Grid. Три-структура P Grid позволяет использовать различные стратегии запросов по диапазону, обрабатываемые последовательно или параллельно, с компромиссом между объемом передаваемых сообщений и задержкой разрешения запроса. Простые архитектуры хранения данных, основанные на векторах, также подвержены ограничениям, зависящим от типа запроса, в среде P Grid.