Кожен PoP володіє власною клітиною площини
Теселяція Вороного
Розмістіть N точок (PoP: точки присутності) на площині. Проведіть межі регіонів так, щоб кожна точка площини призначалася до найближчого PoP. Результатом є діаграма Вороного: площина розбивається на N клітин, по одній на кожен PoP, кожна з яких містить усі точки, що ближче до її PoP, ніж до будь-якого іншого.
Геометрія CDN: запит кожного користувача маршрутизується до найближчого PoP. Кожен PoP обслуговує клітину географічної площини. Межі клітин є перпендикулярними бісектрисами ліній між сусідніми PoP.
Геометрична інтерпретація:
- Додавання PoP зменшує комірки його сусідів (& створює нову комірку)
- Видалення PoP змушує його комірку перерозподілитися між сусідами (сплеск навантаження на сусідів)
- Користувач, який перебуває поруч із межею комірки, може перемикатися між PoP, коли змінюється балансування навантаження
- Збій одного PoP збільшує ефективну комірку кожного сусіда протягом періоду простою
Операційний наслідок: коли збій PoP, його навантаження не зникає; воно мігрує до сусідніх PoP. Якщо сусіди розраховані лише на їхнє нормальне навантаження, сплеск зламає їх наступними (каскадний збій PoP). Досвідчені провайдери CDN розраховують кожен PoP, враховуючи сплеск навантаження при збої сусіда.
Нерівність трикутника, від якої неможливо ухилитися
Фізика встановлює нижню межу
Світло рухається зі швидкістю ~300 000 км/с у вакуумі. У оптичному волокні — приблизно 200 000 км/с через показник заломлення. Це означає:
- ~1 000 км волокна = ~5 мс у один бік = ~10 мс у обидва боки
- Від узбережжя до узбережжя США (~5 000 км) = мінімум ~50 мс RTT
- США до Європи (~8 000 км) = мінімум ~80 мс RTT
- Антіподальна точка (напівкола навколо світу) = мінімум ~200 мс RTT
Це нижня межа. Реальний RTT завжди більший (переходи через маршрутизатори, комутація, черги, затори). Жодна програма не може працювати швидше, ніж дозволяє фізика.
Нерівність трикутника
Для трьох вузлів A, B, C нерівність трикутника стверджує, що d(A,C) <= d(A,B) + d(B,C): прямий шлях коротший (або дорівнює) будь-якому непрямому шляху.
Мережеве тлумачення: якщо ваша служба маршрутизує трафік A -> B -> C замість прямого A -> C, затримка становить принаймні суму затримок двох відрізків. Часто вона більша через обробку на вузлі B.
Архітектурне читання: кожне посередництво (проксі, балансировач навантаження, хоп CDN) додає принаймні один відрізок кругового походу до сприйнятої користувачем затримки. Перевага CDN полягає в тому, що відрізок користувача стає коротшим (точка присутності PoP ближча до вихідного сервера, ніж сам вихідний сервер), навіть якщо загальна кількість хопів зростає.
Пастки багатореґіональності: сервіс, який читає з регіону A, але записує в регіон B, несе затримку A-до-B при кожному записі. Якщо відстань між A та B становить 100 мс, то кожен запис займає мінімум >= 100 мс. Розширені бази даних платять цю «підлогу» щоразу.
Оплата «підлоги»
Сервіс працює в двох регіонах: US-East (us-east-1) та EU-West (eu-west-1). Відстань між цими регіонами становить приблизно 5 500 км. У сервісі є основна база даних у US-East. Запити користувачів з ЄС обслуговуються бекендами в EU-West, але кожен запис вимагає виклику до основної бази даних у US-East.
Географічне проєктування пропускної здатності
Синтез
Тепер ви можете інтерпретувати комірки Вороного як зони збору PoP, обчислювати нижні межі затримки за швидкістю світла та застосовувати криву черги на рівні проксі.
Застосуйте всі три.
Команда планує покриття CDN для сервісу з користувачами на трьох континентах: Північна Америка (60% користувачів), Європа (30%), Азія (10%). У них є бюджет на 6 PoP. Кожен PoP може обслуговувати стабільну комірку з використанням 70% без перетину коліна кривої чергування.
Завершення супутнього курсу
Завершення супутнього курсу
Ви завершили всі п'ять супутніх уроків з геометрії:
- Проксі та джерела: орієнтовані графи, кількість стрибків, вхідний/вихідний ступінь, непряме посилання
- Безстанове горизонтальне масштабування: закон Літтла як площа, крива чергування та її «коліно»
- Розділення вхідного та вихідного трафіку: дводольна структура, усунення розділюючих вершин, толерантність до розбиття
- Режими збоїв та радіус ураження: центральність проміжного положення, мінімальний розріз, діаметр
- Спостережуваність та пропускна здатність (цей урок): комірки Voronoi для точок присутності (PoP), нижня межа трикутника затримки, географічний дизайн пропускної здатності
Головна ідея: розподілені системи мають геометричну структуру. Кожна архітектура — це граф. Кожна нижня межа затримки — це нерівність трикутника. Кожне рішення щодо пропускної здатності — це крива та її «коліно». Щойно ви побачите цю геометрію, операційні рішення випливають із неї.
Разом із п'ятьма основними уроками (cs_distsys_*) ви маєте робочу ментальну модель веб-масштабної розподіленої системи та графову дисципліну для міркувань про неї.
Молодець.