Go stosuje tri-kolorowy współbieżny zbieracz śmieci, w którym obiekty przechodzą z koloru białego (nierozpoznane) do szarego (w kolejce) a następnie do czarnego (całkowicie zeskanowane). Fundamentalna zasada podczas oznaczania mówi, że czarne obiekty nigdy nie mogą zawierać wskaźników do białych obiektów, ponieważ mogłoby to doprowadzić do błędnego zwolnienia osiągalnej pamięci przez zbieracz. Aby wymusić to bez zatrzymywania świata, Go używa barier zapisu – haczyka wstawionego przez kompilator, który jest wywoływany przy każdym zapisie wskaźnika do sterty. Kiedy gorutyna modyfikująca wykonuje zapis wskaźnika, bariera sprawdza, czy obiekt docelowy jest biały; jeśli tak, od razu koloruje obiekt docelowy na szaro przed zakończeniem zapisu, atomowo zachowując inwariant.
Obserwowaliśmy poważne opóźnienia w analizie w czasie rzeczywistym w pipeline'ie przetwarzającym miliony zdarzeń na sekundę. System używał skomplikowanej struktury grafowej, w której węzły często aktualizowały odniesienia do węzłów podrzędnych w oparciu o dane strumieniowe, co powodowało ogromny obrót wskaźników w cyklach GC Go.
Pierwsze rozważane rozwiązanie: Próbowaliśmy to złagodzić przez zwiększenie GOGC do 200%, aby opóźnić zbieranie śmieci. Zalety: Zmniejszenie częstotliwości cykli GC, co obniżyło całkowitą liczbę wykonania bariery w czasie. Wady: To dramatycznie zwiększyło maksymalny rozmiar sterty, co narażało nasze ograniczone pamięciowo kontenery na awarie OOM, i jedynie odwlekało szczyty opóźnienia, zamiast je rozwiązać.
Drugie rozwiązane rozwiązanie: Eksperymentowaliśmy z pulowaniem obiektów przy użyciu sync.Pool, aby ponownie używać struktur węzłów i zmniejszyć alokacje. Zalety: Zmniejszyło to presję alokacyjną oraz tempo powstawania nowych białych obiektów. Wady: Przeciążenie bariery zapisu pozostawało wysokie, ponieważ nadal modyfikowaliśmy wskaźniki w istniejących (często już zeskanowanych) czarnych obiektach w tym samym tempie; pulowanie nie rozwiązało kosztów wykonania bariery podczas aktualizacji wskaźników.
Trzecie rozważane rozwiązanie: Przebudowaliśmy graf, aby używać indeksów całkowitych w dużym prowadzie zamiast bezpośrednich wskaźników do relacji między węzłami. Zalety: Przypisania całkowite nie są zapisami wskaźników, całkowicie omijając mechanizm bariery zapisu i eliminując związane z tym koszty CPU podczas oznaczania. Wady: To wymagało wdrożenia ręcznego zarządzania pamięcią dla prowadzenia (obsługa luk, kompaktowanie) i sprawiło, że kod stał się mniej idiomatyczny oraz trudniejszy do utrzymania.
Wybrane rozwiązanie: Przyjęliśmy podejście oparte na indeksach dla rdzenia grafu o dużym obrocie, zachowując wskaźniki dla statycznych metadanych. To bezpośrednio wyeliminowało gorącą ścieżkę bariery zapisu, jednocześnie zachowując semantykę spójności grafu.
Wynik: Opóźnienia w ogonie podczas GC spadły o 90%, z 15ms do 1.5ms, a całkowita przepustowość wzrosła o 40% z powodu zmniejszonej pracy asystującej GC, kradnącej CPU od modyfikatorów.
Dlaczego bariera zapisu koloruje obiekt, do którego się wskazuje, a nie obiekt, który jest modyfikowany?
Kandydaci często błędnie zakładają, że bariera powinna oznaczać obiekt źródłowy (ten, do którego się pisze) jako wymagający ponownego skanowania. Jednak źródło jest już albo szare, albo czarne; jeśli jest czarne, ponowne skanowanie go byłoby kosztowne i wymagałoby śledzenia wszystkich jego wychodzących wskaźników. Z drugiej strony, pokrycie docelowego obiektu (nowa wartość wskaźnika) na szaro natychmiast spełnia inwariant tri-kolorowy: jeśli źródło jest czarne, a cel był biały, krawędź staje się czarna-na-szarą, co jest bezpieczne. To rozróżnienie jest kluczowe, ponieważ minimalizuje pracę (tylko nowy cel jest w kolejce) zamiast wymagać potencjalnie dużych obiektów źródłowych do ponownego skanowania.
Jak bariera zapisu współdziała z alokacjami stosu i dlaczego stosy mogą wymagać ponownego skanowania?
Podczas gdy bariery zapisu głównie przechwytują zapisy wskaźników do sterty, Go musi również obsługiwać wskaźniki ze stosów do sterty. Jeśli gorutyna zapisuje wskaźnik do białego obiektu na stercie w czarnej ramce stosu, bariera zapisu wykonuje się, aby pokolorować cel. Jednak ponieważ stosy mogą rosnąć, kurczyć się i być kopiowane, utrzymanie precyzyjnych stanów czarnego/białego dla każdego slotu stosu jest skomplikowane. Go rozwiązuje to, traktując stosy jako korzenie, które mogą wymagać ponownego skanowania na końcu fazy oznaczania, jeśli były aktywne podczas oznaczania. Kandydaci często umykają, że ponowne skanowanie stosu jest koniecznym planem awaryjnym, gdy bariery zapisu na stosach nie mogą zapewnić inwariantu z powodu równoległego wykonywania, a ta finalna faza stop-the-world jest zazwyczaj krótka, ale niezbędna dla poprawności.
Jaka jest różnica między barierą zapisu Dijkstry a barierą zapisu Yuasa i którą stosuje Go?
Bariera Dijkstry koloruje obiekt docelowy, gdy wskaźnik jest instalowany (czarny modyfikator, biały cel), zapobiegając wystąpieniu krawędzi czarno-białej. Bariera Yuasa natomiast rejestruje stary wartość wskaźnika, która jest nadpisywana i koloruje ją, zachowując właściwość „snapshot-na-początku”. Go używa hybrydowej bariery Dijkstry, ponieważ jest prostsza i zapewnia silny inwariant tri-kolorowy natychmiast, chociaż może spowodować unoszące się śmieci, jeśli biały obiekt stanie się osiągalny zaraz po pokolorowaniu. Kandydaci często mylą te pojęcia lub wierzą, że Go używa Yuasa z powodu swojej konserwatywnej obsługi stosów, ale zrozumienie wyboru Dijkstry wyjaśnia, dlaczego bariera Go jest synchroniczna z zapisem, a nie oparta na logowaniu.