Load Balancing: Round Robin, Najmniej Połączeń & Potęga Dwójki

Dlaczego jeden kolejna wąska przewaga nad wieloma

Load balancer znajduje się przed pulą serwerów z tyłu i decyduje, dla każdego przychodzącego żądania, który serwer go obsługuje. Cel wydaje się prosty – rozłożyć obciążenie – ale polityka, którą wybierzesz, zmienia opóźnienie końcowe o rząd wielkości nawet wtedy, gdy całkowity przepustowość wygląda identycznie na panelu sterowania. Główna zasada z teorii kolejek mówi, że jeden wspólny kolejna wąska podawana wielu serwerom przewyższa jedną prywatną kolejkę dla każdego serwera, ponieważ prywatna kolejka może być pusta w czasie, gdy wolne żądanie czeka za wolnym żądaniem. Większość rzeczywistych balancerów przybliża wspólną kolejnkę bez faktycznego budowania jej, kierując się na podstawie sygnałów na żywo z każdego serwera z tyłu.

Prosta kolejka 'round robin' jest najprostsza: żądanie 1 idzie do serwera A, żądanie 2 do B, żądanie 3 do C i z powrotem do A. Jest bezstanowa, tania i sprawiedliwa pod względem liczby – ale jest ślepa co do tego, jak długo trwa każde żądanie. Jeśli serwer B obsługuje wolne zapytanie o generowanie raportów, kolejka 'round robin' nadal wysyła mu nowe zadania według harmonogramu, a jego kolejna rośnie, podczas gdy A i C są względnie puste.

Najmniejsza liczba połączeń i warianty o ważeniu

Najmniejsza liczba połączeń koryguje tę ślepotę, kierując każdy nowy żądanie do serwera, który aktualnie ma najmniej aktywnych połączeń. Potrzebuje to, aby równoważnik monitorował liczbę aktywnych połączeń, ale efekt jest realny: wolne serwery naturalnie otrzymują mniej nowych zadań, ponieważ ich liczba połączeń pozostaje wysoka.

Ważona minimalna liczba połączeń rozszerza to na sprzęt heterogeniczny – serwer o podanej pojemności dwukrotnie większej otrzymuje wagę 2, a równoważnik skutecznie dzieli liczbę połączeń przez tę wagę przed porównaniem. score(serwera) = aktywności(serwera) / waga(serwera) następne żądanie -> argmin(score) dla wszystkich zdrowych serwerów Ważony okrągły ruchem jest odpowiednim rozwiązaniem dla okrągłego ruchu: serwer o wadze 3 otrzymuje trzy żądania na każde, które otrzymuje serwer o wadze 1, cyklicznie przechodząc w ustalonym wzorcu zamiast w oparciu o aktualne obciążenie. Jest to dobre rozwiązanie pośrednie, gdy z góry znane są względne pojemności, ale nie chcemy kosztów prowadzenia ewidencji dotyczących liczby połączeń.

score(server) = activeConnections(server) / weight(server)
next request -> argmin(score) over all healthy servers

Losowe i wybory o potęgach dwójki

Czysto losowe routowanie jest zaskakująco bliskie rundzie (zgodnie z prawem dużego liczby każdy serwer otrzymuje w długim okresie średnio około 1/N ruchu). Jednak ma gorszą zmienność krótkotrwałą – nic nie stoi na przeszkodzie, by pięć żądań pod rząd lądowało na tym samym serwerze. Ciekawe ulepszenie to wybory o potęgach dwójki: zamiast losowego wyboru jednego serwera, balanser losuje dwa serwery i kieruje żądanie do tego z mniejszą liczbą aktywnych połączeń. Analiza Michaela Mitzenmachera wykazała, że ta prosta modyfikacja redukuje maksymalne obciążenie na jakimkolwiek serwerze z O(log n / log log n) (losowe) do O(log log n) – ogromny wzrost wykładniczy – za niewielki nakład pracy administracyjnej, dlatego pojawia się ona w rzeczywistych systemach takich jak rozszerzenia least_conn w nginx oraz wielu service mesh.

Co właściwie robią kolejki, wpływając na opóźnienia

Każda z powyższych polityk dąży do osiągnięcia tego samego celu: utrzymanie krótkiej i w miarę równomiernej kolejki dla każdego serwera. Prawo Millsa, L = λW, wiąże długość kolejki L z natężeniem ruchu λ oraz średnim czasem spędzanym w systemie W — przy stałym natężeniu ruchu jedynym sposobem na skrócenie czasu oczekiwania jest skrócenie długości kolejki, a jedynym sposobem na skrócenie długości kolejki bez odrzucania żądań jest kierowanie pracy tam, gdzie kolejna jest faktycznie krótsza. To właśnie dlatego algorytmy minimalnego i maksymalnego obciążenia oraz wybieranie potęg dwójkowych przewyższają rundę roboczą w przypadku obciążenia szczytowego lub zróżnicowanego, ponieważ wykorzystują informacje o aktualnej długości kolejki, podczas gdy ta ostatnia je odrzuca.

// naive least-connections routing
function route(servers) {
  let best = null;
  for (const srv of servers) {
    if (!srv.healthy) continue;
    if (!best || srv.active / srv.weight < best.active / best.weight) best = srv;
  }
  best.active++;
  return best;
}

Kontrole stanu zdrowia, przyczepność sesji i awarie

Nic z tego nie ma znaczenia, jeśli obciążeniowie stale wysyłają ruch do martwego serwera. Kontrole stanu zdrowia – okresowe pingi lub żądania syntezowane – usuwają bezczynne backendy z rotacji i dodają je z powrotem po ich odzyskaniu, zazwyczaj z rampą wolnego startu, aby niedawno przywrócony serwer nie został natychmiast zaatakowany pełnym obciążeniem ruchu podczas rozgrzewania się jego pamięci podręcznych. Przyczepność sesji (przekierowywanie danego klienta konsekwentnie do tego samego backendu, często poprzez ciasteczko lub spójne haszowanie na adres IP klienta) wymienia jakość równoważenia obciążenia na prostotę, gdy backendy przechowują lokalne dane sesji; spójne haszowanie szczególnie minimalizuje liczbę klientów, którzy zostaną przepisani, gdy serwer zostanie dodany lub usunięty, co ma ogromne znaczenie dla współczynnika trafień w pamięci podręcznej.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Load Balancer i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.