Когда архитектор Да Лю увидел работу стажера Сяо ЛиВнеочередной учетКогда дело дошло до проблемы, он понял, что был прав: на этот раз Да Лю снова использовал старого приятеля последовательного хеширования, чтобы решить эту проблему.
Что ж, последовательное хеширование, необходимое лекарство для распределенных архитекторов, давайте попробуем вместе.
1. Глаза полны того, как я выглядел 20 лет назад, начнем с хэша
N лет назад распределённая архитектура Интернета была на подъеме. В связи с потребностями бизнеса компания Да Лю представила бизнес-архитектуру, разработанную командой IBM.
Эта архитектура использует распределенную идею и обменивается данными через промежуточное программное обеспечение сообщений RabbitMQ. Эта архитектура в эпоху того времени считалась архитектурой черных технологий с передовым мышлением и редкими технологиями.
Однако из-за того, что распределенная технология не была широко внедрена в то время, есть много мест, которые еще не созрели. Поэтому при использовании этой архитектуры с годами постепенно стали заметны некоторые проблемы. Среди них наиболее типичными проблемами являются две:
-
RabbitMQ — это единая точка, как только она сломается, вся система будет полностью парализована.
-
Бизнес-система приема и отправки сообщений также является единой точкой. Если в какой-то момент возникнет проблема, сообщения в соответствующей очереди либо не будут потребляться, либо будет накапливаться большое количество сообщений.
Независимо от того, какая проблема, в конце концов, вся распределенная система не может быть использована, а последующая обработка очень хлопотна.
Для одноточечной проблемы RabbitMQ, поскольку кластерная функция RabbitMQ была очень слабой в то время, а в обычном режиме была одноточечная проблема самой очереди, мы, наконец, использовали Keepalived с двумя несвязанными RabbitMQ для достижения высокой доступности.
Для одноточечной проблемы бизнес-системы были перипетии, когда она решалась с самого начала. Вообще говоря, мы хотим решать одноточечные задачи, и метод состоит в том, чтобы складывать машины и приложения в кучу. Отправка и получение — это одна точка, мы можем просто развернуть еще несколько приложений напрямую. С технической точки зрения это не что иное, как то, что несколько приложений, отправляющих и получающих сообщения, конкурируют за размещение сообщений в MQ для получения сообщений.
Однако именно после кластеризации приложений, отправляющих и получающих сообщения, в системе возникают проблемы.
Сама архитектура системы будет применяться к различным видам бизнеса компании, а некоторые бизнесы предъявляют строгие требования к порядку сообщений.
Например, приложение для обмена мгновенными сообщениями внутри компании, будь то одноранговый чат или сообщение группового чата, требует, чтобы сообщения разговора были строго упорядочены. И когда мы кластеризуем приложения, которые производят и потребляют сообщения, возникает проблема:
История чата не в порядке
Когда A и B разговаривают, некоторые сообщения не будут получены B в строгом соответствии с порядком, отправленным A, поэтому вся последовательность чата превращается в беспорядок.
После расследования было установлено, что основная причина проблемы кроется в кластере приложений. Поскольку в кластере приложений нет специальной обработки для отправки и получения сообщений, когда A отправляет сообщение чата B, сообщение, отправленное RabbitMQ, будет зашифровано потребителем в B. Если A отправляет несколько сообщений за короткий промежуток времени, они могут быть перехвачены различными приложениями в кластере.
В это время появляется проблема выхода из строя. Хотя бизнес-логика приложений одинакова, приложения в этих кластерах все же могут иметь различия в скорости обработки информации, что в конечном итоге приведет к путанице в информации чата, которую видят пользователи.
Проблема найдена, какое решение?
Как мы уже говорили выше, неупорядоченность порядка сообщений вызвана тем, что разные приложения в кластере перехватывают сообщения и затем обрабатывают их с разной скоростью. Если мы можем гарантировать, что сеансы A и B будут использоваться только одним и тем же приложением в потребляющем приложении кластера сообщений, где B находится от начала до конца сеанса, тогда мы можем гарантировать порядок сообщений. Таким образом, мы можем ставить захваченные сообщения в очередь в приложении, которое их потребляет, а затем последовательно обрабатывать их.
Так как же достигается эта гарантия?
Сначала мы создаем очереди в RabbitMQ с тем же префиксом, за которым следует номер очереди. Затем разные приложения в кластере будут прослушивать эти две очереди с разными номерами соответственно. При отправке сообщения в A мы делаем простой хэш сообщения:
m = hash(id) mod n
Здесь id — это идентификатор пользователя. n — количество развертываний бизнес-систем, где B находится в кластере. Последнее m — это номер очереди назначения, в которую нам нужно отправить сообщение.
Предположим, что результат hash(id) равен 2000, n равно 2 и m = 0 после вычисления. В этот момент A отправит информацию о разговоре между ним и B в очередь chat00. После того, как B получит сообщение, оно, в свою очередь, будет показано конечному пользователю. Таким образом решается проблема беспорядка в чате.
Итак, это конец дела? Идеально ли это решение?
2. Похоже, нам нужно увеличить количество приложений
С развитием компании резко увеличилось количество людей в компании, также увеличилось количество пользователей IM внутри компании, появились новые проблемы.
Основная проблема в том, что люди стали медленнее отправлять сообщения в чате. Причина тоже очень проста, не хватает машин кластера для сбора информации чата. Решение может быть простым и понятным, просто добавьте еще одну машину.
Однако, поскольку в кластер, получающий сообщение, была добавлена новая машина, в настоящее время нам нужно сделать еще несколько вещей:
-
Нам нужно добавить дополнительную очередь chat02 для недавно добавленного приложения на этом компьютере.
-
Нам также нужно изменить наши правила рассылки сообщений, изменив исходный хэш(id) mod 2 на хеш(id) mod 3.
-
Перезапустите проект, отправив сообщение, чтобы измененные правила вступили в силу.
-
Разверните приложение для приема сообщений на новом компьютере.
Пока все еще под контролем. Разработчикам нужно только добавить новую очередь, когда это необходимо, а затем внести небольшие изменения в наши правила распределения.
Но чего они не знали, так это того, что приближается буря.
3. Приходят новые проблемы, может это и есть жизнь
Поскольку многие люди внутри компании используют этот инструмент обмена мгновенными сообщениями. Иногда для удобства этим ИМ пользуются и клиенты компании, и некоторые партнеры. Это все усложняет. Сначала разработчики работали как обычно, добавляя машину каждый раз, когда люди жаловались, что сообщения замедляются.
Хуже всего то, что клиенты компании жаловались на то, что IM иногда был полностью недоступен. Это немаловажно. Проблемы внутри компании также могут быть решены через внутреннюю коммуникацию. Но к проблеме клиентов компании не стоит относиться легкомысленно, ведь она связана с репутацией продукции компании.
Итак, что, черт возьми, здесь происходит?
Получается, что первопричиной является перезапуск службы после каждой модификации правил конфигурации. Каждый раз, когда вы изменяете правила конфигурации, вам необходимо планировать соответствующее время простоя для повторного запуска проекта.
Однако этот подход не работает, когда клиенты компании также используют IM. Потому что многие клиенты компании находятся за границей. Тем не менее, вполне вероятно, что кто-то всегда использует IM, днем или ночью.
Это вынуждает разработчиков при добавлении машин координировать и сообщать время запуска нескольким сторонам, затем публиковать объявление и выходить в сеть. Такое повторное общение, повторный запуск, повторное общение и повторный запуск напрямую подбрасывали разработчиков на полпути.
Часто после общения онлайн-время сразу переводится на полмесяца позже. И за эти полмесяца разработчикам приходится терпеть слюну бесчисленного количества внутренних IM-пользователей. Кропотливое общение, хриплое объяснение, недосып и недосып, все это подталкивает разработчиков к внесению изменений в стоящее перед ними техническое решение.
4. Идея свернута, очередь обведена
Суть спроса на новые технические решения заключается в следующем:
Независимо от того, меняют ли правило сообщения сообщения или добавить кластерную машину, нельзя выключить, чтобы остановить службу
В этой ситуации хорошим решением будет выполнение динамического определения времени для профиля проекта и обновление правил конфигурации при обнаружении изменений.
Все выглядит хорошо.После использования динамического определения времени всякий раз, когда нам нужно добавить машины в кластер, нам нужны только следующие три шага:
-
добавить очередь
-
Изменение правил назначения сообщений
-
Развернуть новую машину
Клиенты ничего не знают, а разработчикам не нужно координировать свои действия и общаться с пользователями для принятия специальных мер по запуску. Однако есть некоторые проблемы с этим решением:
-
Поскольку мы развертываем все больше и больше систем, нам нужно все больше и больше систем для ручного изменения правил.
-
Если машина-потребитель выйдет из строя, нам нужно удалить очередь, и в то же время нам нужно удалить и изменить правила распределения сообщений, когда машина восстановится, нам нужно изменить правила распределения сообщений обратно.
Правила рассылки сообщений действительно раздражают, каждый раз, когда происходят изменения, приходится обращать внимание на правила рассылки сообщений. Есть ли способ сделать это назначение более автоматическим?
Если предположить, что в MQ есть 100 очередей для отправки и получения сообщений чата (100: это невозможное число для нашего IM), нам нужно только настроить в правиле конфигурации:
m = hash(id) mod 100
Затем, после запуска нашего приложения для отправки сообщений, оно динамически определяет всю реальную информацию об очереди для отправки и получения сообщений чата.
Когда мы обнаружим, что реальной соответствующей очереди по числу, вычисляемому по хэшу, нет, мы по определенным правилам найдем реальную очередь, в которую мы хотим отправлять сообщения.
Если мы это сделаем, то каждый раз, когда очередь изменится, увеличится она или уменьшится, нам больше не нужно думать о правилах распределения, нам нужно будет просто удалить проблемную очередь или увеличить очередь с соответствующими потребителями.
Эта идея — идея последовательного хеширования.
Как это сделать?
На первом этапе мы предполагаем, что существует 100 очередей для отправки и получения сообщений чата, и эти очереди находятся в кольце.
На втором шаге мы получаем реальное количество очередей на отправку и получение сообщений чата, предположим, что их 5.
На третьем шаге мы сопоставляем реальную очередь с кольцом, которое мы предполагали на первом шаге.
На четвертом шаге мы вычисляем соответствующий номер очереди, назначая хэш (идентификатор) правила mod 100.
Если результат hash(id) равен 2000, то рассчитанный номер очереди m = 0. В это время мы проверяем и обнаруживаем, что очередь chat00, соответствующая номеру 0, действительно существует, затем отправляем сообщение прямо в chat00.
Если результат нашего хеша(id) равен 1999, то вычисленный номер очереди m = 99. На этом этапе мы проверили отношение сопоставления очередей и обнаружили, что номер 99 не имеет соответствующей реальной очереди. Что нам делать в это время? Очень просто, продолжаем искать по часовой стрелке, кого мы нашли? 0 соответствует реальной очереди chat00.В это время мы отправляем сообщение в очередь chat00.
Вышеупомянутые четыре шага представляют собой базовый последовательный алгоритм хеширования.
Итак, отвечает ли этот набор согласованных алгоритмов хеширования потребностям нас, не желающих постоянно обновлять правила рассылки сообщений? Давайте проверим:
-
Предположим, нам нужно добавить машину в кластер на стороне информации о потребителе.
Если мы хотим добавить машину, то нам также нужно добавить очередь в MQ. В настоящее время нашим правилом распределения является hash(id) mod 100. После добавления очередей предполагается, что фактическое количество очередей равно 6. В это время, если результат hash(id) mod 100 меньше 6, то правила распределения те же, что и при отсутствии машин: какая очередь была выделена раньше и какая очередь выделена сейчас. Но для случая, когда результат равен 6, что-то меняется. Сообщения автоматически назначаются на chat05. При назначении на chat05 новый потребитель автоматически начнет работать в обычном режиме, нам не нужно делать какое-либо ручное вмешательство, и нам не нужно учитывать изменения в правилах назначения.Перед добавлением машин:
После добавления машин:
-
Предположим, что машина в кластере потребительской информации не работает.
Чтобы смоделировать время простоя, мы уменьшим очередь на этом этапе. Фактическое количество очередей после сокращения равно 5, что прямо противоположно увеличению очередей.При m = 5 не будет изменений в поведении, какая очередь назначена раньше или какая очередь назначена. Если m = 6, поскольку реальной очереди нет, он выполнит поиск по часовой стрелке и найдет chat00, а тот, который ранее был назначен для chat05, будет назначен для chat00. В это время у chat00 есть потребители, поэтому пользователи системы ничего не знают, и мы можем сосредоточиться на ремонте наших машин. Когда машина будет восстановлена, она будет такой же, как только что добавленная машина, а информация, результат расчета которой равен 6, будет перераспределена обратно в чат05.
В настоящее время мы видим, что когда мы вводим последовательное хеширование, независимо от того, добавляем ли мы новую машину или кластерная машина не работает, мне нужно только следить за состоянием машины и выполнять одну операцию: увеличивать или уменьшать очередь в MQ. . Все упрощено.
Итак, есть ли еще проблема с этим планом?
5. Неуравновешенное кольцо может стать той соломинкой, которая сломает верблюда.
Предположим, у нас в настоящее время есть 5 очередей, и наше правило распределения: m = hash(id) mod 100. Ну, в этот момент возникает проблема.
Если значение m больше 5, поскольку соответствующей реальной очереди нет, система будет искать по часовой стрелке вдоль созданного нами хеш-кольца и, наконец, найдет очередь chat00.
Затем вы обнаружите, что если идентификатор со значением m больше 5 соответствует сообщению, отправленному пользователем, оно в конечном итоге попадет в очередь chat00.
В крайних случаях, если большое количество информации попадает в очередь chat00, потребитель, соответствующий чат00, может не справиться с ней, что может привести к краху потребителя.
Тогда, после удаления очереди, по правилам, в последующую очередь чат01 чата 00 потечет большое количество информации, что приведет к краху приложения, соответствующего чат01, и в конечном итоге к краху всего кластера. это лавинный эффект.
Нам нужен более разумный способ решить эту проблему.
6. От реального к виртуальному, может быть, нам стоит осмелиться подумать больше
После приведенного выше обсуждения мы обнаружили, что при распределении очередей причина дисбаланса заключается в том, что распределение наших очередей на кольце не сбалансировано.
Все наши реальные очереди расположены на кольце по часовой стрелке. В приведенном выше сценарии у нас есть только 5 очередей. На данный момент мы предполагаем, что будет 100 очередей. Тогда m = hash(id) mod 100 в этой формуле:
Существует вероятность 95%, что m больше 5
Так как наши 5 очередей расположены последовательно по порядку номеров. Это означает, что все сообщения, m которых больше 5, будут сопоставлены с несуществующей очередью, и, наконец, согласно правилам, они будут перемещены по часовой стрелке в очередь chat00, соответствующую 0.
Если мы сможем сделать так, чтобы реальные очереди были равномерно распределены по кольцу, повторится ли этот серьезный дисбаланс снова?
Из приведенного выше рисунка видно, что если мы сможем сделать реальную очередь равномерно распределенной по кольцу, то этот серьезный дисбаланс будет значительно уменьшен.
Так как же сделать так, чтобы эти очереди были равномерно распределены в этом кольце? Помните, когда мы мучились постоянным пересмотром правил рассылки сообщений и смело предполагали номер очереди, до которого наша система обмена мгновенными сообщениями никогда не дотянется?
Мы предполагаем, что в MQ 100 очередей, а затем идем выяснять, существуют ли эти очереди на самом деле. Если она не существует, мы просто скользим по часовой стрелке, пока не найдем настоящую очередь.
Если мы будем немного смелее и тайно еще больше оптимизируем наши предположения и сопоставим некоторые очереди, которые должны оцениваться как несуществующие, с теми, которые на самом деле существуют, то сможем ли мы распределить эти реальные очереди равномерно по принципу «Включено ли это кольцо?»
Как и на картинке выше, метод сопоставления небольшого количества существующих очередей с несколькими гипотетическими очередями — это метод согласованного хеширования виртуальных узлов.
Что касается того, как отобразить небольшое количество очередей на несколько гипотетических очередей, существуют различные алгоритмы реализации.
Например, мы можем добавить к реальным именам очередей какие-то числа, чтобы хэшировать их отдельно, например, хэш(чат00) мод 100, хэш(чат00#1) мод 100, а затем по полученному остатку перейти в реальную очередь chat00 и на карте позиций в ринге, соответствующем остатку.
Если hash(chat00) mod 100 = 31, то позиция 31 соответствует chat00, и все последующие сообщения, соответствующие m = 31 в m = hash(id) mod 100, будут отправлены прямо в очередь chat00.
И hash(00#1) mod 100 = 56, сообщение, соответствующее m = 56, также будет отправлено прямо в очередь chat00.
Таким образом, мы косвенно равномерно распределяем реальные очереди в MQ, тем самым значительно уменьшая явление дисбаланса информации.
7. Понимание идеи алгоритма лучше, чем реализация алгоритма
Что ж, идея последовательного хеширования здесь временно проанализирована с помощью реальных сценариев.
Как очень классическая идея алгоритма, последовательное хеширование широко используется в крупных распределенных проектах для решения различных проблем фрагментации и проблем распределения задач.
Однако здесь я хочу исправить один момент: многие люди в Интернете говорят, что Redis использует согласованное хеширование. Это неправильно, Redis просто использует идею последовательного хеширования. Например, кольцевое распределение при согласованном хешировании и идея о том, что виртуальные узлы соответствуют реальным узлам.
Однако Redis не использует хеш-алгоритм для расчета распределения.Если вам интересно, вы можете внимательно прочитать соответствующий контент. На примере redis мы видим, что только поняв идею алгоритма, мы можем более легко и гибко декомпозировать, модифицировать и улучшать алгоритм в соответствии с локальными условиями, чтобы алгоритм можно было более реалистично интегрировать. в наши проекты.
В этой статье мы начнем с хэширования и перейдем к распределению виртуальных узлов с использованием согласованного хеширования.Как вы относитесь к хорошему лекарству последовательного хеширования?
Я впервые написал графическую статью, давайте приспособимся к эстетике натуралов!
Это был мой первый раз, когда я писал иллюстрированную статью, и я действительно устал брать кровь! Пожалуйста, прочитайте все этоотличный.