Сеть с адресацией по содержимому

CAN — это распределённая система, реализующая хеш-таблицу: пространство идентификаторов разбивается между участниками сети, и каждый узел отвечает лишь за свою, небольшую часть пространства. Каждый узел — это своего рода сервер, предоставляющий содержимое, хранящееся у него, в виде пар (ключ, значение). Для маппинга ключа в пространство координат используется хеш-функция (например, SHA-1), после чего полученная зона будет закреплена за соответствующим узлом. Хеш от ключа назначается тому узлу, чей идентификатор максимально близок к значению хеша. Если хеш больше всех идентификаторов, используется модуль по 2^n.

Базовая архитектура сети — виртуальное d-мерное декартово пространство, циклическое по всем измерениям. CAN реализует топологию гиперпрямоугольников («зон»): каждому узлу соответствует уникальная зона. Пространство виртуальных координат не связано с физическим расположением или соединениями узлов.

Вся система состоит из множества узлов, каждый из которых хранит часть хеш-таблицы. Зоны могут быть разного размера, но должны быть квадратными. Каждый узел предоставляет доступ к зоне содержимого для всех клиентов, но, как правило, необходимая информация находится на другом узле, к которому клиент не подключён непосредственно. Для таких запросов нужен пересыл запросов соседям. Соседями считаются узлы, у которых совпадают все координаты, кроме одной; в результате формируется виртуальная сеть, опосредующая пересылку запросов между зонами. Каждый узел поддерживает таблицу соседей с указанием их IP-адресов и координат зон. Передача сообщения происходит по алгоритму: пересылка на соседний узел, координаты которого ближе всех к целевой точке. Каждый пересылаемый пакет содержит конечный адрес и промежуточный узел. Если сообщение пришло не владельцу зоны, оно пересылается ближайшему соседу по координатам. Количество соседей у узла определяется размерностью пространства и равно 2*d.

Алгоритм маршрутизации определяет время реагирования на запрос. В качестве метрики выбирается декартово расстояние. Пользователь отправляет запрос — добавление, удаление или поиск данных — на свой подключённый узел, тот хеширует ключ и определяет точку в пространстве. Если зона, куда попал ключ, принадлежит этому узлу, происходит немедленный обмен, иначе — пересылка ближайшему соседу. Необходимо проверять доступность соседей перед пересылкой, так как сбой ближайшего по координатам узла может привести к ошибке. В этом случае кратчайший путь может быть недоступен.

Для оценки эффективности рассчитывается средняя длина маршрута. Пусть d — размерность пространства, n — всего зон. Тогда наибольшая длина пути по каждой координате — \sqrt[d]{n}/2, и максимальная общая длина пути — d·\sqrt[d]{n}/2. Следовательно, средняя длина маршрута $O(d·\sqrt[d]{n})$.

Для первого подключения участников в P2P-систему CAN реализует механизм инициализации: существуют специальные bootstrap-узлы, поддерживающие частичный список активных узлов. С помощью DNS имя домена CAN разрешается в IP-адрес одного из таких узлов, после чего подключение к сети происходит через любой из доступных bootstrap-узлов.

CAN поддерживает три базовых операции: вставку, удаление и поиск.

Для поиска ключа K его идентификатор определяет зону пространства, где он хранится. Узел X, получивший запрос на поиск, проверяет, отвечает ли он за нужную зону; если нет — пересылает запрос ближайшему соседу, и так далее, пока не найдётся владелец данного ключа. Сложность поиска: $O(d·n^{1/d})$ (где d — размерность, n — число узлов).

Подключение нового участника требует перестроения структуры: новый узел X перед подключением связывается с одним из узлов-участников (через алгоритм bootstrapping), выбирает произвольную точку P пространства, после чего с помощью алгоритма маршрутизации находит узел J, ответственный за эту координату. Узел J делит свою зону пополам: одну половину оставляет себе, вторую передаёт новому участнику X. Затем J информирует X о своих соседях, что позволяет X составить собственную таблицу соседей. Информация о новых связях распространяется среди всех затронутых соседей. Вставка нового узла влияет только на конкретную зону и её ближайших соседей.

Если узел X покидает сеть (или выходит из строя), требуется восстановить структуру координатного пространства. Для этого работает специальный протокол реструктуризации: один из соседей берёт на себя контроль над освободившейся зоной (если возможно, объединяет зоны; если нет — выбирается временно ближайший сосед с наименьшей зоной). После переназначения зоны каждое изменение доводится до всех соседей для синхронизации таблиц маршрутизации.

При плановом выходе из сети узел передаёт свою зону и таблицу маршрутизации выбранному соседу. Если зоны можно объединить — формируется новая зона; если нет — выбранный сосед временно обслуживает обе зоны.

В случае отказа (аварийного выхода) возникает «мертвая» зона и возможна потеря данных (ключ-значение). Для предотвращения этого используется периодическая пересылка обновлений координат и таблиц соседей между участниками. Если какой-то узел не отвечает в течение заданного времени, остальные инициируют протокол takeover (реструктуризации), распределяя управление зоной между соседями. Этот протокол может одновременно инициироваться разными соседями и гарантирует, что зона не останется без владельца.

Порядок реструктуризации:

1. Узел запускает таймер;
2. По истечении времени отправляет сообщение takeover соседям узла, который вышел из строя;
3. Соседи сравнивают размер своей зоны с бывшей зоной неактивного узла, и, если их зона меньше, пересылают takeover и участвуют в распределении.

Преимущества протокола: равномерное распределение зон между узлами и отсутствие централизованного управления.

Возможны одновременные сбои смежных узлов, что может привести к несогласованности данных; для корректного восстановления применяется кольцевой обход и реконструкция структуры.

В ходе реструктуризации одному участнику может быть временно назначено несколько зон, что нежелательно с точки зрения фрагментированности пространства. Для равномерного распределения зон используется отдельный алгоритм перераспределения.

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

Дальнейшее улучшение — поддержка нескольких независимых пространств координат («реальностей»). При подключении новый узел выбирает r случайных координат (одна — на каждую реальность) и поддерживает r отдельных таблиц соседей. Это повышает отказоустойчивость и уменьшает среднюю длину маршрута (в r раз).

Для избежания перегрузки популярных зон используются методы кэширования и репликации.

• Кэширование

CAN поддерживает кэш последних востребованных ключей. Перед пересылкой запроса сначала проверяется локальный кэш, и если ключ найден — пересылка не требуется. Чем выше востребованность ключа — тем чаще он оказывается в кэше разных узлов, что ускоряет доступ. Кэшированные значения имеют ограниченное время жизни.

• Репликация

Если узел перегружен запросами к определённому ключу, он может передать копии этого значения каждому соседу. Таким образом, доступ к этим данным обеспечивается несколькими узлами одновременно, равномерно распределяя нагрузку. Реплики имеют ограниченное время жизни.

Для повышения доступности данных можно использовать k различных хеш-функций, размещая один и тот же ключ на k разных точках пространства (и, соответственно, у k разных узлов). Это увеличивает объём базы, но снижает задержку и повышает вероятность найти ближайший к клиенту узел.

Равномерное разбиение пространства — важнейшее условие эффективности: средняя длина маршрута минимальна, если все зоны одинаковы по размеру. В базовом CAN новый узел выбирает случайную зону, делит её пополам (владелец зоны знает размеры соседних зон). Для улучшения разбиения целесообразно отдавать предпочтение соединению с соседом, чья зона максимальна по размеру.