Jaka technika stojąca za tym, że **Go** może przenieść cały stos goroutines do nowej lokalizacji pamięci, zachowując poprawność wszystkich wskaźników odnoszących się do danych przydzielonych na stosie?

Odpowiedź na pytanie

Historia

Wczesne implementacje Go przydzielały stosy o stałej wielkości (1KB na goroutine), co albo wyczerpywało pamięć przy dużej konkurencji, albo przepełniało się podczas głębokiej rekurencji. Język przeszedł ewolucję od stosów segmentowanych (połączonych fragmentów) we wczesnych wersjach do kopiowania sąsiednich stosów w Go 1.3+, aby poprawić lokalność pamięci podręcznej i uprościć zarządzanie wskaźnikami.

Problem

Gdy goroutine wyczerpuje swój aktualny segment stosu, runtime musi przydzielić większy obszar pamięci i przenieść wszystkie istniejące dane stosu. To przeniesienie naraża na unieważnienie wskaźników, które odnoszą się do zmiennych stosowych, ponieważ ich adresy pamięci zmieniają się podczas transportu, co może potencjalnie spowodować uszkodzenie pamięci lub awarie.

Rozwiązanie

Kompilator wstawia preambułę do sprawdzania stosu przy każdym wejściu do funkcji, porównując wskaźnik stosu z stroną ochronną. Jeśli miejsce jest niewystarczające, wywołuje runtime.morestack, który przydziela nowy stos (zwykle podwajając jego rozmiar), kopiuje starą zawartość i wykorzystuje generowane przez kompilator mapy wskaźników, aby znaleźć i dostosować wszystkie wskaźniki wewnątrz stosu, które wskazują na inne lokalizacje stosu.

Przykład kodu

Poniższa funkcja demonstruje, jak wskaźniki do zmiennych stosowych pozostają ważne nawet gdy stos rośnie podczas rekurencji:

func Calculate(depth int, prev *int) int {
    if depth == 0 {
        return *prev
    }
    // current jest przydzielone na stosie
    current := depth * 100
    
    // &current może wskazywać na starą lokalizację stosu
    // Jeśli stos rośnie tutaj, runtime aktualizuje wskaźnik
    return Calculate(depth-1, &current) + *prev
}

Wykonanie wznawia się na nowym stosie z zaktualizowanymi rejestrami, zapewniając, że wszystkie wskaźniki wskazują na poprawne nowe adresy.

Sytuacja z życia

Scenariusz

Silnik dopasowywania finansowego przetwarzający rekurencyjne obliczenia książki zamówień napotkał sporadyczne awarie podczas zdarzeń rynkowych o dużej zmienności, gdy głębokość rekurencji przekraczała początkowy przydział 2KB stosu. System potrzebował rozwiązania, które utrzymałoby czytelność algorytmów rekurencyjnych bez kompromitowania milionów lekkich goroutines obsługujących równoległe połączenia.

Problem

Algorytm dopasowywania używał głębokiej rekurencji do przeszukiwania drzewa o kształcie głębokości zamówień, co powodowało paniki związane z przepełnieniem stosu, gdy wolumen handlowy osiągał swoje maksimum. Rozwiązanie musiało zapewnić bezpieczne zarządzanie nieograniczoną rekurencją, nie marnując gigabajtów pamięci na wstępnie przydzielone duże stosy dla w większości bezczynnych goroutines.

Rozwiązanie 1: Stałe Duże Stosy

Wstępnie przydzielone duże stosy dla wszystkich goroutines z użyciem debug.SetMaxStack lub modyfikując domyślne ustawienia runtime. Zalety: całkowicie eliminuje koszty wzrostu i ryzyko przepełnienia. Wady: zużywa nadmierną pamięć dla nieaktywnych obsługujących połączenia, naruszając obietnicę lekkiej goroutine i zmniejszając maksymalną wykonalną konkurencję.

Rozwiązanie 2: Iteracyjna Konwersja

Przepisanie rekurencyjnego przeszukiwania drzewa jako algorytmu iteracyjnego z wyraźnym przydzielonym na stosu kawałkiem pamięci sterty do śledzenia stanu przeszukiwania. Zalety: przewidywalne zużycie pamięci i brak ryzyka przepełnienia stosu. Wady: zwiększona złożoność kodu, utrata czytelności algorytmu oraz dodatkowa presja na zbieranie śmieci z powodu częstych przydziałów kawałków pamięci podczas obrotów handlowych o dużej objętości.

Rozwiązanie 3: Dynamiczny Wzrost Stosu

Zachowanie rekurencyjnego projektu, ale poleganie na ciągłym wzroście stosu Go, zapewniając, że kompilator optymalizuje ramki funkcji z dokładnymi mapami wskaźników. Zalety: zachowuje czystą logikę rekurencyjną, używa pamięci proporcjonalnie do rzeczywistych potrzeb i obsługuje szczyty ruchu automatycznie bez zmian w kodzie. Wady: mikrosekundowe przerwy podczas kopiowania stosu, chociaż są one łagodzone przez małe domyślne stosy i efektywne kopiowanie.

Wybrane podejście

Wybrano rozwiązanie 3, ponieważ 100-nanosekundowy koszt kopiowania stosu okazał się nieistotny w porównaniu do opóźnienia sieciowego, a także zachowało matematyczną przejrzystość rekurencyjnego algorytmu dopasowywania. Dodaliśmy limity głębokości rekurencji jako zabezpieczenie, aby zapobiec nieskończonym pętlom pochłaniającym 1GB stosów.

Rezultat

System zrealizował 50 000 równoległych obliczeń rekurencyjnych podczas testów stresowych rynku bez awarii. Wykorzystanie pamięci pozostało poniżej 300MB dla 100 000 goroutines, a opóźnienie p99 wzrosło o mniej niż 2 mikrosekundy podczas zdarzeń wzrostu stosu, spełniając surowe wymagania handlu wysokiej częstotliwości.

Co kandydaci często pomijają

Dlaczego kopiowanie stosu nie narusza wskaźników do zmiennych na stosie, gdy stos przemieszcza się do nowego adresu w pamięci?

runtime polega na mapach stosu (mapach bitowych) generowanych przez kompilator dla każdej funkcji. Te mapy identyfikują, które sloty w ramce stosu zawierają wskaźniki. Podczas runtime.copystack, runtime iteruje przez te mapy, znajduje każdy wskaźnik wskazujący na stary zakres stosu i aktualizuje go na odpowiadający przesunięcie w nowym stosie. To zapewnia, że nawet po zmianie fizycznego adresu pamięci, wszystkie odniesienia pozostają ważne i wskazują na odpowiednie nowe lokalizacje.

Jak Go radzi sobie z rosnącym stosem podczas wywołań CGO, które mogą mieć wskaźniki do danych stosu Go?

Wykonanie CGO zawsze przełącza się na stos systemowy (g0) przed wejściem do kodu C. runtime zapewnia, że żadne wskaźniki stosu goroutine nie są ujawniane w funkcjach C. Jeśli wzrost stosu występuje podczas wykonywania kodu C (poprzez oddzielną goroutine), stos C pozostaje nietknięty. Po powrocie z C do Go, runtime przełącza się z powrotem na (potencjalnie przeniesiony) stos goroutine za pomocą zaktualizowanego wskaźnika stosu zapisanym podczas przejścia runtime.entersyscall.

Co powoduje błąd krytyczny "runtime: goroutine stack exceeds 1000000000-byte limit" i jak różni się to od normalnego wzrostu?

W przeciwieństwie do normalnego rozszerzenia stosu, które kopiuje do większego sąsiedniego obszaru, ten błąd występuje, gdy runtime.morestack wykrywa, że żądany wzrost przekracza twardy limit (1GB w systemach 64-bitowych). Taki stan sygnalizuje nieograniczoną rekurencję lub niekontrolowany przydział. Podczas gdy normalny wzrost jest przejrzysty i oparty na kopiowaniu, osiągnięcie tego limitu wywołuje natychmiastową panikę, ponieważ runtime nie może zaspokoić żądania pamięci bez ryzyka ausschowaniu systemu, a kontynuowanie wykonania byłoby niebezpieczne.