SQL Server

SQL Server i algorytmy wymiany stron? WTF?

Jakiś czas temu miałem przyjemność uczestniczyć w szkoleniu Performance Management Oracle Database 12c Instance: Monitoring and Diagnostics. Szkolenie prowadził Maciej Zakrzewicz. Jedno z lepszych szkoleń, w jakich w ogóle brałem udział.

Mimo, że, na co dzień to nie moja działka to z przyjemnością słuchałem jakie Oracle ma niuanse. Podczas szkolenia poruszone były między innymi kwestie związane z buffer cache oraz algorytmami wymiany stron. Konkretnie mowa była o Least Recently Used (LRU) i jego następcy – LRU Touch-Count.

Jako osoba z obszaru RDBMS z obozu konkurenta byłem odbiorcą lekkich drwin. Wszystko na szczęście w granicach dobrego smaku:)

Zostałem zapytany jaki u „nas” z wygląda wymiana stron z buffer cache. Powiem szczerze, zostałem zaskoczony. Po prostu nie wiedziałem. Krótko po szkoleniu zacząłem interesować się tematem. Jak to robi SQL Server? Zacząłem czytać, mimo, że tematyka nie należy do tych z pierwszych stron.

Pierwsze informację, do których dotarłem, informowały, że w SQL Server mechanizm, który jest odpowiedzialny za zapis zmienionych stron na dysk (czyli checkpoint) również odpowiedzialny jest za oznaczanie, jako wolnych tych stron do których nie było odwołań przez pewien czas. SQL Server utrzymuję listę adresów do tych stron i każdy proces potrzebujący stron bufora korzysta z tej listy.

Każdy bufor ma nagłówek, który zawiera informacje o ostatnich dwóch odwołaniach do strony i niektóre informacje o statusie, zawierające czy strona jest dirty. Według publikacji SQL Server 2008 Internals odwołania te wykorzystywane są do implementacji zasady zastępowania stron z pamięci podręcznej danych.

Konkretnie to implementacja algorytmu LRU-K, który został wprowadzony przez Elizabeth O’Neil, Patrick O’Neil i  Gerhard Weikum (The LRU-K Page Replacement Algorithm For Database Disk Buffering). Algorytm LRU-K zachowuję ślad ostatnich K odwołań do strony i potrafi rozróżnić rodzaje stron. Strony indeksu i danych. To potrafi symulować efekty przypisywania stron do różnych buforów. W implementacji SQL Server, K równe jest, 2 co oznacza, że zachowuję informację o dwóch ostatnich dostępach do strony w buforze.

Następnie wygooglowałem prezentacje Bob Dorr, który jest główny inżynier oprogramowania SQL Server. W tej prezentacji (Jan 2008) w znajduję się notatka.

The latest builds of SQL Server have moved to Time of Last Access (TLA) algorithms to determine which buffers to eject from cache.  The older algorithms were based on a reference counting scheme and TLA has been found to be more efficient.

Co można rozumieć, że najnowsza wersja SQL Server została przeniesiona na algorytm Time of Last Access (TLA), aby określać bufory, które mają zostać wyrzucone z pamięci podręcznej. Starsze algorytmy opierały się na schemacie liczenia odwołań i stwierdzono, że TLA jest bardziej wydajny.

Szukałem dalej, aby znaleźć rzetelną i jednoznaczną informację. Natknąłem się na interesujący komentarz, w którym Jonathan Kehayias łączy pojęcia TLA z LRU-K pisząc.

The buffer pool uses the LRU-K algorithm to track the last K times a page was referenced. In SQL Server K = 2, so it knows the last two times a page was used in the buffer pool and it compares the TLA (time of last access) against the system wide threshold that is based on the current workload and demand for memory and that determines if a page is going to be evicted from the buffer pool or not. If the workload is stable and no data is being read from disk, there is no adjustment of the system wide threshold for TLA and pages will remain until the buffer pool needs BUF structures on the free list and begins removing stale (unused) pages based on the TLA and current threshold.

Rozumiem to w ten sposób, że TLA (time of last access) to nic innego jak czas ostatniego dostępu strony z algorytmu LRU-K. To TLA jest porównywane z progiem całego systemu, który jest oparty na bieżącym obciążeniu pracą i zapotrzebowaniu na pamięć.

Wtedy SQL Server określa czy strona ma zostać wyrzucona lub nie. Jeśli obciążenie jest stabilne, a dane nie są odczytywane z dysku,  system dostosowuje szeroki próg TLA i strony pozostają aż nie będzie potrzeby usuwania nieaktualnych / nieużywanych stron opartych na TLA i bieżącym progu.

Ma to jakiś sens? Może tak, ale nie jestem przekonany. Na pewno postaram się jeszcze zgłębić wiedzę i podzielić się z Tobą. Na tą chwilę poddaję się i w tym temacie pewien jestem tylko, że Oracle korzysta z LRU Touch-Count.

 

How It Works: Bob Dorr’s SQL Server I/O Presentation

Finding what queries in the plan cache use a specific index