Як послідовне хешування вирішує проблеми масштабованості
Консистентне хешування – це метод, який робить масштабування розподілених систем набагато плавнішим та надійнішим. На відміну від старих методів хешування, які ламаються під час додавання або видалення серверів, консистентне хешування зменшує перебої, перерозподіляючи лише невелику частину даних. Такий підхід гарантує:
- Мінімальне переміщення даних: Під час додавання або видалення сервера перепризначається лише приблизно 1/n ключів, що дозволяє уникнути збоїв у роботі всієї системи.
- Кращий розподіл навантаженняВіртуальні вузли рівномірно розподіляють робоче навантаження між серверами, запобігаючи утворенню гарячих точок та забезпечуючи ефективне використання ресурсів.
- Покращена відмовостійкість: Якщо сервер виходить з ладу, лише його безпосередні сусіди беруть на себе додаткове навантаження, забезпечуючи стабільність системи.
- Стабільність кешуБільшість кешованих даних залишаються недоторканими під час масштабування, що зменшує навантаження на базу даних та підтримує продуктивність.
Послідовне хешування широко використовується в сучасних системах, таких як Amazon DynamoDB, CDN від Netflix та Discord, для обробки непередбачуваних піків трафіку та забезпечення надійної роботи. Розміщуючи сервери та дані на круговому хеш-кільці, воно оптимізує масштабованість та надійність у розподілених архітектурах.
Узгоджене хешування в розподілених системах | Просте пояснення + Демонстрація
sbb-itb-59e1987
Як працює послідовне хешування
Послідовне хешування проти традиційного хешування: порівняння переміщення даних
Хеш-кільце та призначення ключа
Послідовне хешування використовує a циклічний хеш-простір, яке часто називають хеш-кільцем, замінює простий підхід за модулем. Це кільце представляє хеш-значення в діапазоні від 0 до 2^32-1. Як сервери, так і ключі даних хешуються за допомогою однієї й тієї ж функції та розміщуються на кільці.
Коли запитується ключ, система хешує ключ у певному місці на кільці. Звідти він переміщується за годинниковою стрілкою, доки не досягне першого маркера сервера, який потім відповідає за зберігання та керування цим ключем. Це правило за годинниковою стрілкою визначає, який сервер обробляє яку частину хеш-простору.
На відміну від традиційного хешування, консистентне хешування не прив'язує систему до загальної кількості серверів. Кожен сервер займає певну точку на кільці та володіє сегментом між собою та попереднім сервером проти годинникової стрілки.
Додавання та видалення вузлів
Коли додається новий сервер, його дані хешуються в певну позицію на кільці та перебирає ключі від свого наступного сусіда за годинниковою стрілкою. Важливо, що решта системи залишається незмінною. Наприклад, у системі зі 100 вузлами, додавання ще одного вузла вимагатиме лише 0.90% ключів даних перемістити. На противагу цьому, традиційне хешування вимагатиме переміщення 99.01% даних.
Процес аналогічний під час видалення сервера. Якщо сервер вимикається з мережі або виходить з ладу, його ключі переміщуються на наступний сервер за годинниковою стрілкою. Такий цілеспрямований перерозподіл мінімізує перебої, уникаючи широкомасштабного переміщення даних та промахів кешу, які можуть виникати за допомогою традиційних методів. Забезпечуючи перерозподіл лише невеликої частини ключів, послідовне хешування підтримує масштабовані та надійні системи хостингу.
Завдяки ефективній складності часу пошуку O(log N) при використанні двійкового дерева пошуку для зберігання позицій вузлів, послідовне хешування забезпечує безперебійну роботу навіть по мірі зростання системи. Таке оптимізоване переміщення даних також закладає основу для оптимізації розподілу навантаження між віртуальними вузлами.
Використання віртуальних вузлів для кращого розподілу навантаження
Щоб покращити балансування навантаження, віртуальні вузли (VNodes) вступають у гру. Якщо фізичний сервер знаходиться лише в одній позиції на кільці, це може призвести до нерівномірного розподілу навантаження. Віртуальні вузли вирішують цю проблему, призначаючи кожному фізичному серверу кілька позицій на кільці.
Ця стратегія розподіляє робоче навантаження більш рівномірно. Коли сервер виходить з ладу, його завдання розподіляються між кількома серверами, а не обтяжують лише одного сусіда. Віртуальні вузли також дозволяють зважування на основі потужності, що означає, що сервери з більшими ресурсами (наприклад, більше процесора або оперативної пам'яті) можуть обробляти більшу частку запитів, маючи більше віртуальних вузлів.
Зазвичай системи призначають близько 100 віртуальних вузлів на сервер, що забезпечує точний контроль над балансуванням навантаження. Навіть у масштабних розгортаннях потрібна пам'ять мінімальна. Наприклад, хеш-кільце, що підтримує 60 000 фізичних серверів з 6 мільйонами віртуальних вузлів, потребуватиме лише близько від 12 до 27 мегабайт пам'яті для зберігання відображення. Таке поєднання ефективності та гнучкості робить віртуальні вузли життєво важливим інструментом для узгоджених систем хешування.
Як послідовне хешування вирішує проблеми масштабованості
Менше переміщення даних під час масштабування
Одна з видатних переваг послідовного хешування полягає в тому, як воно мінімізує переміщення даних під час масштабування вгору або вниз. У традиційному модулярному хешуванні навіть невелике коригування, таке як додавання одного сервера до великого кластера, може вимагати перепризначення майже всіх ключів. З іншого боку, послідовне хешування перерозподіляє лише близько 1/n ключів, коли вводиться новий сервер. Це значно зменшує обсяг перетасовування даних по мережі. Наприклад, у тесті з 1500 елементами, розподіленими по 80 машинах (деякі з яких зазнали змін), послідовне хешування призвело лише до збільшення перепризначених пар на 25%, тоді як традиційне хешування вимагало б переміщення майже всіх ключів. Ця ефективність має вирішальне значення для запобігання перевантаженню мережі та перебоям у роботі, особливо в середовищах, де переміщення великих обсягів даних може бути руйнівним. Обмежуючи переміщення даних, послідовне хешування забезпечує стабільнішу роботу системи навіть під час збоїв вузлів.
Краща продуктивність та надійність
Послідовне хешування також покращує продуктивність і надійність, обмежуючи вплив збоїв вузлів. У традиційних системах на основі модуля відмова одного вузла може вимагати повторного хешування до 90% ключів, що призводить до потоку запитів на повторне обчислення до вихідних серверів. Завдяки послідовному хешуванню перебої локалізовані – лише сусідні вузли на хеш-кільці беруть на себе додаткове навантаження. Ранні реалізації показали, що незначні додаткові накладні витрати від проходження хеш-кільця були незначними порівняно з часом, витраченим на передачу даних по мережі.
Помітним застосуванням консистентного хешування є компанія Akamai Technologies, яка використовувала його у своїй мережі доставки контенту (Content Delivery Network) для розподілу трафіку між обертовими веб-серверами. Цей підхід допоміг вирішити проблему "слешдотування" (або «слешдотування») 1990-х років, коли раптові сплески трафіку призводили до збоїв серверів. Тім Бернерс-Лі навіть вважав це рішення ефективним за вирішення цих сплесків трафіку.
Підтримка ефективності кешу
Ефективне кешування є критично важливим як для продуктивності, так і для управління витратами, а послідовне хешування відіграє ключову роль у підтримці цілісності кешу. Обмежуючи перепризначення даних невеликою частиною ключів, послідовне хешування допомагає зберегти "теплі" кеші, які зберігають часто використовувані дані. Це важливо, оскільки промахи кешу можуть призвести до дороговартісних запитів до бази даних і збільшення навантаження на серверні системи. Зберігаючи більшість кешованих даних недоторканими під час масштабування, послідовне хешування мінімізує ризик поширеної недійсності кешу.
"Мінімізуючи недійсність кешу, послідовне хешування покращує взаємодію з користувачем завдяки швидшому завантаженню та зменшенню витрат на пропускну здатність". – Наїм Уль Хак, експерт з проектування систем
Реальний приклад цього можна побачити в зусиллях Discord щодо масштабування в липні 2017 року. Для підтримки 5 000 000 одночасних користувачів Discord використав послідовне хешування в рамках своєї архітектури на основі Elixir. Це дозволило ефективно зіставити певні чати з потрібними вузлами хоста, забезпечуючи плавне масштабування та надійну продуктивність. Окрім збереження ефективності кешу, послідовне хешування також допомагає ефективно розподіляти робочі навантаження, навіть коли можливості сервера різняться.
Робота з різними потужностями серверів
У середовищах з різноманітним серверним обладнанням, послідовне хешування використовує віртуальні вузли для балансування навантаження на основі кожного віртуальні приватні сервери потужність. Наприклад, серверу з вдвічі більшою потужністю, ніж інший, можна призначити вдвічі більше віртуальних вузлів, що дозволить йому обробляти пропорційно більшу частку робочого навантаження. Призначаючи віртуальні вузли відповідно – наприклад, 100 вузлів для стандартних серверів і 200 для високопродуктивних – система досягає збалансованого розподілу навантаження з мінімальними коливаннями. Такий підхід гарантує повне використання потужніших серверів, тоді як менш потужні обробляють робочі навантаження, що відповідають їхній потужності. Результатом є збалансована та ефективна конфігурація хостингу, яка безперешкодно адаптується до різних можливостей обладнання.
Міркування щодо впровадження для узгодженого хешування
Тепер, коли ми розглянули переваги, давайте заглибимося в практичні деталі ефективного впровадження послідовного хешування.
Вибір хеш-функції
Обрана вами хеш-функція відіграє вирішальну роль у продуктивності та розподілі ключів. Для більшості хостингових середовищ, некриптографічні хеш-функції Такі функції, як MurmurHash, xxHash або MetroHash, ідеально підходять, оскільки вони швидкі та не навантажують процесор непотрібними витратами на безпеку. Криптографічні хеш-функції (наприклад, MD5, SHA-1) є надмірними для цієї мети та можуть уповільнити вашу систему.
"Оптимальна хеш-функція для послідовного хешування повинна бути швидкою та видавати рівномірний результат". – Нео Кім
Гарна хеш-функція забезпечує рівномірний розподіл ключів по хеш-просторі, уникаючи гарячих точок, де окремий вузол перевантажується. 32-бітна хеш-функція пропонує близько 4,29 мільярда можливих позицій на віртуальному кільці, чого достатньо для зменшення колізій. Для підтримки узгодженості всі клієнти та вузли повинні використовувати та сама хеш-функція, забезпечуючи їхню згоду щодо того, як ключі відповідають вузлам. Крім того, використання хеш-виходів, що є степенями двійки, дозволяє виконувати швидші побітові операції, які є ефективнішими, ніж обчислення за модулем.
Керування змінами вузлів
Обробка змін у кластері, таких як приєднання або вихід вузлів, є ще одним критичним аспектом послідовного хешування. Хеш-кільце повинно динамічно налаштовуватися без порушення роботи сервісів. Використання самобалансуюче бінарне дерево пошуку (BST) Зберігання позицій вузлів гарантує, що операції пошуку залишаються ефективними, зі складністю O(log N), навіть по мірі розвитку кільця. Така структура дозволяє легко та швидко знаходити "наступний вузол за годинниковою стрілкою" для будь-якого заданого ключа.
Для безпечного керування оновленнями використовуйте блокування читання-запису для синхронізації змін у BST під час додавання або видалення вузлів. протокол пліток також може допомогти, дозволяючи вузлам періодично обмінюватися інформацією про стан у форматі peer-to-peer. Це дозволяє уникнути необхідності центрального контролера, який може стати вузьким місцем. Щоб запобігти перевантаженню одного сусіда у разі збою вузла, рандомізуйте початкові розподіли розділів, щоб навантаження рівномірно розподілилося по всьому кластеру. Після того, як ці механізми будуть впроваджені, постійний моніторинг допоможе підтримувати баланс.
Моніторинг та налаштування розподілу навантаження
Навіть за наявності добре спроектованого хеш-кільця, стеження за розподілом навантаження є важливим для запобігання дисбалансу під час виконання. Регулярно відстежуйте кількість ключів, якими володіє кожен вузол щоб виявити потенційні проблеми на ранній стадії. Зверніть пильну увагу на кількість віртуальних вузлів, призначених кожному фізичному вузлу – призначення близько 100 віртуальних вузлів на фізичний вузол є гарною відправною точкою для виявлення та усунення дисбалансів.
"Гарним правилом, якого варто дотримуватися, може бути обчислення 100 віртуальних вузлів для кожного реального вузла з максимальною потужністю. Це дозволить вам змінити навантаження на будь-який вузол на 1%". – Грег Холт
Для систем зі змішаними апаратними можливостями можна призначити більше віртуальних вузлів серверам з більшими ресурсами процесора або пам'яті, гарантуючи, що вони оброблятимуть пропорційно більшу частку робочого навантаження. Щоб запобігти перевантаженню будь-якого окремого вузла, реалізуйте обмежені навантаження – якщо вузол перевищує свою пропускну здатність, перенаправляти вхідні запити на резервний вузол.
Реальним прикладом дії цього принципу є OpenStack Swift. У лютому 2011 року вони продемонстрували, що зі 100 вузлами та 10 000 000 ідентифікаторами даних, додавання одного вузла з послідовним хешуванням та 1000 віртуальних вузлів призвело до переміщення лише 90 423 ідентифікаторів (0,90%). На противагу цьому, традиційне модулярне хешування вимагало переміщення 9 900 989 ідентифікаторів (99,01%). Це ілюструє, як послідовне хешування може зробити масштабування набагато ефективнішим, мінімізуючи перебої, одночасно мінімізуючи перебої.
Висновок
Ключові переваги послідовного хешування
Послідовне хешування – це революційний спосіб для розподілених систем, пропонуючи ефективний спосіб масштабування шляхом переміщення лише частки (1/n) ключів під час додавання або видалення серверів. На відміну від традиційного модулярного хешування, цей метод зберігає стабільність більшості ключів, забезпечуючи високий рівень звернень до кешу та запобігаючи перевантаженню серверів.
Ще однією видатною особливістю є її відмовостійкість. Якщо вузол виходить з ладу, лише ключі, призначені цьому вузлу, перерозподіляються на наступний у хеш-кільці, залишаючи решту системи незмінною. Віртуальні вузли ще більше покращують цей процес, рівномірніше розподіляючи дані між серверами та дозволяючи потужнішим серверам обробляти більший трафік. Разом ці функції створюють основу для стійких та високопродуктивних інфраструктур.
"Послідовне хешування робить розподіл ключів незалежним від кількості серверів, що використовуються системою. Таким чином, ми можемо масштабувати систему вгору або вниз, не впливаючи на загальну систему". – Анімеш Гайтонде, технічний керівник Amazon
Приклади з реального світу підкреслюють ці переваги. Наприклад, DynamoDB від Amazon покладається на послідовне хешування для управління масивними піками трафіку, такими як ті, що відбувалися в Чорну п'ятницю, без будь-яких збоїв. Аналогічно, Netflix використовує його у своїй CDN Open Connect для ефективного зіставлення контенту з периферійними серверами по всьому світу.
Послідовне хешування в сучасному хостингу
Завдяки своїй ефективності та надійності, послідовне хешування стало наріжним каменем сучасних хостингових рішень. Хостинг-провайдери використовують цей метод для легкого масштабування та балансування трафіку між глобальними центрами обробки даних. Можливість додавати або видаляти потужності без необхідності широкого перерозподілу даних гарантує стабільна продуктивність та надійність.
Цей метод ідеально вписується в сучасні архітектури хостингу, які повинні обробляти динамічні робочі навантаження та працювати в кількох регіонах. З часом пошуку до 20 мікросекунд а також здатність підтримувати ефективність кешу під час змін інфраструктури, послідовне хешування дозволяє рішенням хостингу надавати стабільні послуги в міру розвитку систем. Serionion, ми застосували послідовні принципи хешування, щоб забезпечити гнучкий та високопродуктивний хостинг у наших розподілених центрах обробки даних.
поширені запитання
Як послідовне хешування допомагає зменшити переміщення даних під час масштабування розподілених систем?
Консистентне хешування працює шляхом розташування вузлів і даних у круговому хеш-кільці. Коли вузол приєднується до системи або виходить з неї, перепризначаються лише дані, пов'язані з цим конкретним вузлом та його найближчим сусідом. Цей метод значно зменшує обсяг даних, які потрібно перемістити, впливаючи лише на невелику частину загального набору даних.
Така конструкція мінімізує перебої під час масштабування, забезпечуючи плавніший та ефективніший процес. Вона особливо добре підходить для розподілених систем, які керують постійно змінними робочими навантаженнями.
Як віртуальні вузли допомагають розподіляти навантаження при послідовному хешуванні?
Віртуальні вузли, або віртуальні вузли, відіграють життєво важливу роль у послідовному хешуванні, допомагаючи рівномірніше розподіляти навантаження в розподілених системах. Замість того, щоб прив'язувати кожен сервер лише до однієї позиції на хеш-кільці, серверам призначається кілька віртуальних позицій. Це розділяє простір ключів на менші, легші в обробці секції, забезпечуючи рівномірніший розподіл трафіку та сховища між усіма серверами.
Ось як це працює: коли ключ хешується, він призначається найближчому віртуальному вузлу, рухаючись за годинниковою стрілкою на хеш-кільці. Завдяки кільком віртуальним вузлам на сервері система уникає перевантаження будь-якого окремого сервера, підтримуючи збалансоване навантаження. Додавання або видалення сервера впливає лише на ключі, пов'язані з його віртуальними вузлами, зменшуючи обсяг даних, які потрібно переміщувати. Така конструкція підтримує плавне масштабування та забезпечує надійну продуктивність, що є критично важливим для таких інфраструктур, як Serionion’хостингова платформа, де ефективне управління ресурсами є важливим для досягнення стабільних результатів.
Як послідовне хешування підвищує відмовостійкість у розподілених системах?
Послідовне хешування підвищує відмовостійкість, розподіляючи дані між вузлами таким чином, що мінімізує перебої в роботі, коли вузол виходить з ладу. Воно працює через кругове хеш-кільце, яке відображає як дані, так і сервери. Коли вузол виходить з ладу, лише дані, пов'язані з цим конкретним вузлом, перепризначаються його найближчому сусіду в кільці. Такий підхід значно зменшує переміщення даних, забезпечуючи при цьому безперебійну роботу решти системи.
Цей метод не лише забезпечує високу доступність, але й підтримує масштабованість. Додавання або видалення вузлів призводить до мінімальних збоїв у роботі системи. Завдяки ефективному керуванню збоями вузлів, послідовне хешування стає наріжним каменем для створення надійних розподілених систем.
