предисловие

Я помню, как делился статьей год назад«Анализ согласованного алгоритма хеширования», на тот момент только анализировал принцип реализации этого алгоритма, какие задачи он решал и так далее.

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

задний план

Видимый«Создайте для себя распределенную систему обмена мгновенными сообщениями»друзья должны быть впечатлены логикой входа в систему.

Кратко познакомить с новыми друзьямиcimЧто оно делает:

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

Процесс выбора — это процесс стратегии загрузки; первая версия относительно проста и по умолчанию поддерживает только опрос.

Хотя достаточно, это недостаточно элегантно 😏.

Поэтому мой план состоит в том, чтобы создать множество стратегий маршрутизации, чтобы пользователи могли выбирать их в соответствии со своими собственными сценариями, и предоставить простой API, чтобы пользователи могли настраивать свои собственные стратегии маршрутизации.

Давайте взглянем на некоторые характеристики согласованного алгоритма хеширования:

построить0 ~ 2^32-1кольцо размера.
Сервисный узел сохраняет себя в индексе в кольце после хеширования.
Клиент также находит это кольцо после хеширования некоторых своих данных.
Найдите ближайший к нему узел по часовой стрелке, который является служебным узлом этого маршрута.
Учитывая количество сервисных узлов и проблему алгоритма хэширования, виртуальные узлы вводятся при неравномерном распределении данных в кольце.

Заказная карта

В соответствии с этими объективными условиями мы можем легко думать о настройкеаккуратныймассив для имитации этого кольца.

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

Инициализировать массив длины N.
Здесь хранится положительное целое число, полученное сервисным узлом с помощью алгоритма хеширования, и собственные данные узла (хэш-код, ip, порт и т. д.).
После сохранения узлов весь массив сортируется (существует множество алгоритмов сортировки).
Когда клиент получает узел маршрутизации, он хэширует себя, чтобы получить положительное целое число;
Просматривайте этот массив до тех пор, пока не будут найдены данные, большие или равные хеш-значению текущего клиента, и текущий узел используется в качестве узла, маршрутизируемого клиентом.
Если данных больше, чем клиент, не найдено, вернуть первый узел (удовлетворяющий характеристикам кольца).

Не учитывая время, затрачиваемое на сортировку, просто посмотрите на временную сложность этого маршрута:

Лучше всего найти его с первого раза, а временная сложностьO(1).
Худшее обнаруживается после обхода массива, а временная сложность равнаO(N).

После того, как теория закончена, давайте посмотрим на конкретную практику.

Я настроил класс:SortArrayMap

Его использование и результаты следующие:

Видно, что финалkeyСортировать по размеру, при этом переходя вhashcode = 101будет найден по часовой стрелкеhashcode = 1000Этот узел возвращается.

Рассмотрим конкретную реализацию.

Переменные-члены и конструкторы следующие:

Ядром которого являетсяNodeМассив, который используется для хранения сервисного узлаhashcodeа такжеvalueценность.

внутренний классNodeСтруктура выглядит следующим образом:

Способ записи данных следующий:

Я верю, что виделArrayListИсходный код должен создавать впечатление, что логика написания здесь очень похожа на него.

Перед записью определите, требуется ли расширение, и при необходимости скопируйте массив в 1,5 раза больше исходного размера для хранения данных.
После этого массив записывается, и размер массива равен +1.

Однако память хранится в порядке записи и, естественно, не упорядочена при обходе, поэтомуSortметод, данные могут бытьkeyНа самом деле, этоhashcodeСортировать.

Сортировка также относительно проста, используяArraysЭтот инструмент массива сортирует, он на самом деле используетTimSortАлгоритм сортировки более эффективен.

Наконец, вам нужно найти соответствующий узел по часовой стрелке в соответствии со стандартом согласованного хэша:

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

Таким образом, требования согласованного хэша в основном достигаются.

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

Реализация TreeMap

SortArrayMapХотя функция согласованного хеширования реализована, эффективность недостаточно высока, что в основном отражается наsortСортировочное место.

На следующем рисунке показана временная сложность текущего основного алгоритма сортировки:

лучшее этоO(N).

Здесь вполне можно изменить идею, нет необходимости сортировать данные, вместо этого выстраивается порядок при записи, но это снизит эффективность записи.

Такие как бинарное дерево поиска, такая структура данныхjdkЕсть готовые реализации, т.е.TreeMapОн реализован с использованием красно-черного дерева, которое по умолчанию выполняет естественный порядок ключей.

Давайте посмотрим, как использоватьTreeMapКак добиться такого же эффекта.

результат операции:

127.0.0.1000

Эффекты и использование вышеSortArrayMapсогласуется.

Используются только некоторые API TreeMap:

При записи данных,TreeMapЕстественный порядок ключей гарантирован.
tailMapВы можете получить некоторые данные больше, чем текущий ключ.
Когда этот метод возвращает данные, первым является первый узел в направлении по часовой стрелке.
Если нет возврата, просто возьмите всеMapПервый узел также реализует кольцевую структуру.

ps: Здесь также нет хеш-метода и виртуального узла (см. ниже конкретную реализацию), потому что в качестве базовых структур данных используются TreeMap и SortArrayMap.

Сравнение производительности

Для того, чтобы вам было проще выбрать структуру данных, я используюTreeMapиSortArrayMapДля сравнения был записан миллион фрагментов данных.

первыйSortArrayMap:

Это заняло 2237 мс.

Карта дерева:

Это заняло 1316 мс.

Результат почти в два раза быстрее, поэтому рекомендуется использоватьTreeMapдля реализации ведь не требуется дополнительная сортировка потерь.

Практическое применение в cim

Давайте посмотрим наcimКак он используется в этом приложении, включая упомянутые выше виртуальные узлы и алгоритмы хеширования.

Метод шаблона

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

AbstractConsistentHash, основные методы этого абстрактного класса следующие:

addМетод естественно записывает данные.
sortМетод используется для сортировки, но подклассы не обязательно должны переопределяться, напримерTreeMapТаким образом, контейнер с собственной сортировкой не нужен.
getFirstNodeValueПолучить узел.
processОн ориентирован на клиента, и, наконец, нужно только вызвать этот метод, чтобы вернуть узел.

Давайте посмотрим на использованиеSortArrayMapа такжеAbstractConsistentHashкак это достигается.

Это реализация нескольких абстрактных методов.Логика такая же, как и выше, но она извлекается в разные методы.

Просто добавил несколько виртуальных узлов в методе добавления, я думаю, все могут понять.

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

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

Таким образом, вAbstractConsistentHashМетод хеширования определен в .

Алгоритм здесь взят из xxl_job, и в Интернете есть другие различные реализации, такие какFNV1_32_HASHд.; реализация разная, но цель та же.

Это очень просто для пользователя:

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

то же самое для тех, кто хочет пройтиTreeMapЧтобы добиться той же рутины:

Здесь ему не нужно переопределять метод сортировки, потому что он уже отсортирован при записи.

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

Эффект от операции тот же.

Таким образом, когда вы хотите настроить свой собственный алгоритм, вам нужно только наследоватьAbstractConsistentHashВы можете переопределить соответствующие методы,Код клиента менять не нужно.

Расширяемость алгоритма маршрутизации

Но на самом деле дляcimНастоящая масштабируемость — для алгоритма маршрутизации, например, он должен поддерживать опрос, хэш, непротиворечивый хеш, случайный, LRU и т. д.

Просто существует несколько реализаций согласованного хэша, и их взаимосвязь такова:

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

Итак, интерфейс определен:RouteHandle

public interface RouteHandle {

    /**
     * 再一批服务器里进行路由
     * @param values
     * @param key
     * @return
     */
    String routeServer(List<String> values,String key) ;
}

Существует только один метод — метод маршрутизации; входными параметрами являются список услуг и информация о клиенте.

Для согласованного алгоритма хеширования необходимо только реализовать этот интерфейс и выбрать его одновременное использование.SortArrayMapConsistentHashвсе ещеTreeMapConsistentHashВот и все.

Вот еще одинsetHashвходным параметром является AbstractConsistentHash; он используется для указания клиентом конкретной структуры данных, которую необходимо использовать.

То же самое верно и для стратегии опроса, существовавшей ранее.RouteHandleинтерфейс.

Здесь я просто переместил предыдущий код.

Далее давайте посмотрим, как его использует клиент и как выбрать, какой алгоритм использовать.

Чтобы клиентский код оставался почти неподвижным, я поместил этот процесс выбора в файл конфигурации.

Если вы хотите использовать исходную стратегию опроса, настройте ееRouteHandleПолное имя политики опроса для интерфейса.
Если вы хотите использовать согласованную стратегию хеширования, вам нужно только настроить реализацию.RouteHandleПолное имя согласованного алгоритма хеширования для интерфейса.
Конечно, существует также несколько реализаций текущего согласованного хэша, поэтому после настройки в качестве согласованного хэша вам нужно добавить другую конфигурацию, чтобы принять решение об использовании.SortArrayMapConsistentHashвсе ещеTreeMapConsistentHashИли другие индивидуальные программы.
То же самое требуется и для настройки наследованияAbstractConsistentHashПолное имя .

Независимо от того, как здесь меняется политика, она остается неизменной там, где она используется.

Просто введитеRouteHandle, который называет этоrouteServerметод.

@Autowired
private RouteHandle routeHandle ;
String server = routeHandle.routeServer(serverCache.getAll(),String.valueOf(loginReqVO.getUserId()));

Поскольку используется инъекция, процесс переключения этой стратегии фактически создаетRouteHandle beanзавершено, когда.

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

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

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

Суммировать

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

Я считаю, что в процессе собеседования золото, серебро и серебро, это еще может заставить глаза интервьюера заблестеть.Ведь судя по процессу интервью, который я слышал за этот период времени, только несколько человек слышали этот термин😂 ( также может быть в 1 с кандидатами ~ 3 года на этом уровне).

Весь приведенный выше исходный код:

GitHub.com/crossover J я…

Если эта статья оказалась для вас полезной, пожалуйста, перешлите ее.