Przegląd

Kilka miesięcy temu rozpocząłem pracę nad prototypem relacyjnej bazy danych w Metalu. Firma Apple właśnie wypuściła M1 Max i M1 Ultra kilka miesięcy wcześniej z aż 128 GB zunifikowanej pamięci (w Mac Studio).

Postrzegałem to jako okazję do zrobienia czegoś z bardzo dużym przetwarzaniem, które wymagało dużej ilości pamięci GPU: przetwarzanie dużych tabel relacyjnych na GPU.

Nie ja pierwszy pomyślałem o napisaniu relacyjnej bazy danych na GPU. Bazy danych, takie jak BlazingSQL , relacyjna baza danych GPU oparta na Rapids.AI . Rapids.AI to biblioteka Pythona firmy NVIDIA, która odzwierciedla funkcjonalność wielu popularnych bibliotek Pythona, takich jak Pandas, ale uruchamia równoważne funkcje na GPU. Firma NVIDIA dużo inwestuje w centra danych i pomaga w opracowywaniu większej liczby narzędzi działających na ich kartach, zwłaszcza w zakresie uczenia maszynowego i przetwarzania dużych ilości danych.

Oglądając ostatnio konferencje Apple, czułem, że istnieje wiele potencjalnych wydajności, które tak naprawdę nie są wykorzystywane. Z tego, co widziałem, programiści wykorzystują nowe możliwości graficzne nowych układów. Po stronie obliczeniowej brakowało wersji demonstracyjnych i oprogramowania open source zbudowanego przy użyciu Metalu. Apple wykonał przykładowy projekt symulacji cząstek, przypuszczam, że pokazuje odpowiednik próbki CUDA. Pokazują, jak można korzystać z obliczeń w CUDA i renderowania w OpenGL na GPU bez konieczności powrotu do procesora pomiędzy nimi. Innym miejscem, w którym Apple intensywnie korzysta z GPU, są zadania AI. Za każdym razem, gdy Neural Engine nie obsługuje operacji w modelu, CoreML automatycznie przełącza się na GPU w celu zwiększenia wydajności. Chociaż jest to bardzo przydatne i fascynujące,

Wybrałem relacyjną bazę danych, ponieważ tak się składa, że ​​naprawdę kocham bazy danych i myślałem o wielu projektach dla nich, z których niektóre budowałem prototypy przez lata. Relacyjne bazy danych są również interesujące, ponieważ używają ciągów znaków i wartości pustych. Zarówno przykład sztucznej inteligencji, jak i symulator cząstek, choć bardzo imponujące, używają tylko liczb zmiennoprzecinkowych i liczb całkowitych.

Implementację, którą zbudowałem, można znaleźć tutaj: MetalDB Github

Projektuj pomysły

Nie pamiętam, czy było to na samym początku, czy gdzieś w połowie procesu, jednak zainspirowała mnie dokumentacja z BigQuery Query Plans , która mówiła o grafie etapów zapytania składających się na plan wykonania zapytania.

Jednym z głównych ograniczeń konstrukcyjnych Metalu jest to, że cała pamięć musi być statycznie zwymiarowana w czasie kompilacji. Stanowiło to wyzwanie, ponieważ nie mogłem skopiować ciągu, ponieważ nie wiedziałem, ile ciągów znajduje się w wierszu bazy danych ani jak długi będzie każdy ciąg w czasie kompilacji.

Doszedłem do wniosku, że użycie algorytmu sumy prefiksów do wydajnego kopiowania wszystkich danych z GPU do procesora byłoby najprostsze, gdyby każdy wątek przetwarzał jeden wiersz. Musiałem też użyć największego dostępnego synchronizowalnego bloku, którym w Metalu jest ThreadGroup.

Częściowo jako optymalizacja, a częściowo jako osobiste wyzwanie, chciałem zmaksymalizować ilość pracy wykonanej na GPU. Z tych powodów zdecydowałem się zacząć od odczytu plików CSV na CPU i parsowania CSV na GPU.

Podczas implementacji chciałem również móc przetestować bazę danych na procesorze, aby testy jednostkowe można było przeprowadzić w debuggerze. Z tego powodu skonfigurowałem potok kompilacji, aby wszystkie moje metalowe jądra były zapisane jako nagłówki. W rezultacie mogłem je uwzględnić w plikach jądra Metal, ale także w testach w C++. Ten projekt pozwoliłby mi również zdefiniować stałe i typy w nagłówkach Metal i zagwarantować, że będą one zawsze takie same w kodzie C++, który by to wywołał.

Tło dotyczące grup wątków i koncepcji metalowych

Jako tło dla dalszych pomysłów i wyjaśnień, wykonanie metalowe jest zorganizowane w siatki. Siatka to 1D, 2D lub 3D grupa ThreadGroups. ThreadGroup to grupa, którą można zsynchronizować w tej siatce. Wątki wewnątrz ThreadGroup są dzielone i wykonywane na dalsze grupy, zwane wypaczeniami.

Wątek jest najbardziej podstawowym blokiem w programowaniu GPU i z grubsza przekłada się na model wątku na rdzeniu procesora. Jest to pojedyncze, liniowe, uporządkowane wykonanie instrukcji. Wątek ma rejestry, do których ma bezpośredni dostęp, a także odczyt i zapis w pamięci współdzielonej. Jest to inny model pamięci niż w przypadku procesora, ale wykracza to poza zakres tego artykułu.

Osnowa (nazywana SIMD w dokumentacji Metal) to często grupa 16 lub 32 wątków. Ta sama instrukcja musi być wykonana w tym samym czasie na wszystkich wątkach w osnowie, chociaż potencjalnie na różnych danych (SIMD, pojedyncza instrukcja, wiele danych). Jeśli niektóre wątki obiorą inną ścieżkę w kodzie, wszystkie wątki w tej warpie muszą czekać, aż wszystkie gałęzie wykonają się szeregowo. Prowadzi to do projektowania kodu GPU z jak najmniejszą liczbą rozgałęzień, tak aby wszystkie wątki w osnowie były jak najbardziej zajęte.

Inne systemy, takie jak CUDA i OpenCL, mają podobne koncepcje, tylko pod różnymi nazwami.

Realizacja

Link do realizacji:https://github.com/mattpaletta/metaldb

Moim zdaniem najbardziej sensowne jest mówienie o wdrożeniu w kolejności przepływu danych przez system. Jest to jednak prawie idealne odwrotność tego, jak zabrałem się za wdrażanie tego.

Dwójkowy

Końcowy wynik, który jest produkowany jest bardzo prosty. Jest to plik binarny o nazwie metaldbi ma w sobie tylko główną funkcję. Sprawiłem, że aplikacja jest bardzo lekka, abym mógł, podobnie jak inni, łatwo ponownie wykorzystać wewnętrzne biblioteki jako część innych bibliotek i aplikacji w przyszłości.

Silnik

Silnik to miejsce, w którym koordynowana jest większość logiki systemu. Silnik współpracuje z QueryPlannermodułem , który jest zaimplementowany w bibliotece QueryPlanner, a także z modułem Scheduler, który odpowiada za uruchomienie i koordynację wykonania wygenerowanego planu zapytań.

Analizator zapytań

Parser zapytań to komponent odpowiedzialny za przekształcenie zapytania podobnego do SQL w AST, który może być łatwiej analizowany przez resztę systemu.

Ta pierwsza wersja bazy danych nie zawiera implementacji parsera zapytań. Zamiast tego zakodowałem na stałe AST dla różnych zapytań, które chcę przetestować. Napisanie parsera i utworzenie AST, choć brzmi to bardzo interesująco, jest czymś, co zrobiłem w innym projekcie i nie było celem tego projektu.

Nie zamierzałem również, aby ten projekt był gotową do produkcji bazą danych. Dlatego w tej chwili nie potrzebuje parsera zapytań, ale wszystkie kody pośredniczące są dostępne, abym mógł je zaimplementować w późniejszym momencie, jeśli tak zdecyduję.

Oprócz systemu akceptującego ciągi zapytań, planuję docelowo zaimplementować Dataframe API, podobnie jak w Pandach, ale w C++. Z mojego punktu widzenia ten rodzaj API byłby prostszy w obsłudze dla innych bibliotek. Oszczędza to również krok innej biblioteki, która musi wygenerować ciąg zapytania tylko po to, aby mógł on zostać natychmiast ponownie przeanalizowany przez parser. Ten interfejs API ramek danych jest również pozostawiony jako przyszłe prace.

Jako zestaw danych testowych po raz pierwszy użyłem publicznie dostępnego zestawu danych Iris . Wybrałem ten zestaw danych, ponieważ jest stosunkowo mały, w formacie CSV i zawiera głównie liczby, bez wartości pustych.

Po uruchomieniu tego zestawu danych chciałem wypróbować znacznie większy zestaw danych z wieloma plikami. W tym celu użyłem New York Taxi Dataset . Ten większy zbiór danych okazał się interesującym wyzwaniem, którego się nie spodziewałem, więcej na ten temat później.

Planer zapytań

Po wygenerowaniu AST przez Parser zapytań, następnym komponentem jest Query Planner. Odpowiada to za przekształcenie AST w zoptymalizowany plan wykonania.

Pierwszym krokiem do stworzenia zoptymalizowanego planu wykonania jest w ogóle sporządzenie planu. Zainspirowany odniesieniem do BigQuery , spodobał mi się pomysł podzielenia planu wykonania na wykres „etapów”. W BigQuery każdy etap składa się z co najmniej jednego kroku. Każdy krok może być odczytem lub zapisem, agregacją lub łączeniem itp. Nie chciałem zagłębiać się w szczegółowość kroków, ale mam podobną koncepcję, którą nazywam „częściową”.

Aby przejść od AST do wykresu etapów, najpierw wyświetlam listę plików na dysku dla tabeli (tabel). Następnie idę do liści AST i dla każdego z nich tworzę nowy etap, który odczyta ten plik.

Idąc z powrotem w górę drzewa, decyduję, czy utworzę nową częściową część istniejącego etapu, czy utworzę nowy etap. Kluczową kwestią jest to, że kiedy muszę przejść z GPU do CPU lub odwrotnie, tworzę nowy etap. Oznacza to, że GPU może przetwarzać jak najwięcej danych, jednocześnie minimalizując czas transferu między CPU a GPU. Jest to szczególnie istotne w przypadku urządzeń, które nie mają ujednoliconej pamięci.

Każdy etap ma pojedynczą listę części do uruchomienia. Zostaną one później przetłumaczone jako instrukcje dla GPU na tym etapie, ponieważ omówimy więcej w sekcji dotyczącej harmonogramu.

Za każdym razem, gdy tworzę nowy etap, wstawię „instrukcję losowania”, która mówi GPU, aby skopiował informacje z powrotem do procesora.

W przyszłości napisałbym również optymalizator, który mógłby przepisać zapytania, aby zminimalizować ilość danych odczytywanych z każdego pliku i kopiowanych z powrotem do procesora po odczytaniu.

Planista

Harmonogram jest odpowiedzialny za równoległe wykonanie zapytania. Kusiło mnie, aby napisać własną wielowątkową bibliotekę, aby to zrobić. Skończyło się na tym, że napisałem swoją implementację na szczycie TaskFlow , otwartej biblioteki wykresów zadań C++.

Na wysokim poziomie tworzenie wykresu zadań następuje po wykresie etapów. Każdy etap jest zadaniem na grafie i zależy od jego dzieci.

W ramach etapu każda część, lista kroków do wykonania na CPU lub GPU, jest rozwijana w kolejności. Gdy każda część jest rejestrowana, ma kilka zadań na grafie zadań, do których może się podłączyć.

Głównym zadaniem, do którego można się podłączyć, jest zadanie kodowania poprzedniego zadania. Część powinna utworzyć nowe zadanie, które jest zależne od nadrzędnego częściowego zadania kodowania. Używa przekazanego Encoder do zakodowania się w serializowanej reprezentacji, którą można wysłać do procesora GPU. W przypadku większości zadań to wszystko, co jest konieczne, a implementacja częściowa odbywa się na GPU w Metalu.

Drugim dostępnym zadaniem jest zadanie robocze. Istnieje to w przypadku, gdy częściowe chce zastąpić coś w sposobie wykonywania pracy dla tej częściowej zamiast zachowania domyślnego.

Większość zadań odczytuje bufory z jednego lub większej liczby etapów potomnych i zapisuje do ich bufora wyjściowego. Instrukcja read jest unikalna, ponieważ musi czytać z dysku, a nie z buforów podrzędnych.

Instrukcja read ustawia łańcuch zadań, które odczytują plik CSV (jedyny obecnie zaimplementowany typ pliku), który został mu przypisany i wczytuje go do bufora. Podczas wczytywania do bufora śledzi przesunięcie bieżącego wiersza i przechowuje je jako część RawTableobiektu opisanego poniżej.

Po odczytaniu pliku GPU może rozpocząć przetwarzanie wierszy. Projekt bazy danych wymaga jednego wątku na wiersz. Metal ma limit liczby wątków, które można przypisać do ThreadGroup. Dlatego najpierw podzieliliśmy wiersze na wiele buforów, z których każdy będzie niezależnie wysyłany do GPU.

TaskFlow umożliwia dynamiczne podzadania w ramach zadania. Kiedy otrzymuję RawTable, sprawdzam liczbę wątków, które Metal pozwala mi zaplanować i rozbić oryginalne wiersze na kawałki o takim rozmiarze.

Każdy fragment jest następnie wysyłany do GPU równolegle.

Po przetworzeniu wszystkich fragmentów uruchamiam zadanie scalania, które kopiuje wszystkie OutputRowobiekty z GPU i łączy je w jednego giganta OutputRow, aby następny etap mógł je razem odczytać.

W przyszłości chciałbym zoptymalizować podział wielu partii. Gdy tylko partia zostanie podzielona, ​​można ją wysłać do GPU. Gdy tylko ta porcja wróci, można ją skopiować do końcowego bufora, podczas gdy inne zadania są przetwarzane asynchronicznie.

Ponadto chciałbym zwolnić oryginał RawTable, gdy wszystkie wiersze zostaną podzielone na części, z których każda przechowuje kopię. Ponadto powinienem być w stanie zwolnić bufor wyjściowy z fragmentu, gdy tylko zostanie on skopiowany do bufora końcowego, zmniejszając całkowitą ilość wymaganej pamięci.

Instrukcja ParseRow

Zaczyna się ParseRowInstructionod prostego założenia. Mając listę indeksów na początku każdego wiersza oraz informacje o liczbie wierszy i typach kolumn, przeanalizuj wartości dla określonego wiersza, rzutując na ich poprawne typy.

Najprostszym typem kolumny jest łańcuch. W przypadku wiersza N możemy przeskoczyć na początek tego wiersza, wyszukując jego indeks zapisany przez procesor podczas odczytu pliku z dysku. Możemy wtedy uzyskać wskaźnik do tego indeksu. To jest początek rzędu. Koniec dowolnej kolumny to pozycja przed następnym przecinkiem (oznaczającym następną kolumnę), gdy przesuwamy się o jeden znak do przodu lub o jeden przed początkiem następnego wiersza (jeśli jest to ostatnia kolumna wiersza) lub o jeden przed końcem bufora (jeśli jest to ostatnia kolumna ostatniego wiersza).

Instrukcja odczytuje najpierw każdą kolumnę jako łańcuch. Analizuje kolumnę dokładnie tak, jak opisano i odczytuje ją jako ciąg znaków, znak po znaku. Teraz, aby przeczytać następną kolumnę, zaczynamy od początku rzędu. Kiedy dochodzimy do pierwszego przecinka, zaznaczamy go jako początek i przechodzimy do następnego przecinka. Proces powtarza się dla kolejnych kolumn.

Jeśli mamy liczbę całkowitą, przekazujemy wskaźniki na początek i koniec łańcucha do stoifunkcji niestandardowej. Jest to podobne do tego ze standardowej biblioteki C, która konwertuje łańcuch na reprezentację całkowitą. Napisałem też własną wersję stof.

Jak możesz sobie wyobrazić, czytanie każdej kolumny od początku wiersza za każdym razem jest bardzo powolne i jest dużo podwójnej pracy. Możemy zrobić lepiej, dużo lepiej.

Pierwszą rzeczą, o której należy pamiętać podczas optymalizacji znajdowania początku kolumny, jest to, że często występuje niewielka liczba kolumn. Wybrałem 16 jako dowolną liczbę kolumn do buforowania.

Przy tym pierwszym poziomie pamięci podręcznej, jeśli czytam kolumnę w pierwszych 16 kolumnach, próbuję odczytać poprzednio zapisany w pamięci podręcznej wskaźnik dla tej kolumny. Jeśli nie jest null, mam już wartość. Wiersze są niezmienne, więc wskaźnik musi być prawidłowy, a proces jest zakończony!

Jeśli wskaźnik ma wartość NULL, mogę iterować po mojej pamięci podręcznej wstecz od indeksu 16. kolumny, aż znajdę kolumnę wcześniej zapisaną w pamięci podręcznej lub dostanę się do pierwszego wpisu.

Gdziekolwiek się zatrzymam, mogę iterować przez wiersz w naiwny sposób, po jednej postaci na raz. Za każdym razem, gdy znajduję przecinek, zapisuję wskaźnik na początek tej kolumny w mojej pamięci podręcznej, aby kolejne zapytania mogły przeskakiwać prosto tam.

Oznacza to, że losowy dostęp do pierwszych 16 kolumn powinien być w zasadzie bezpłatny, ponieważ staje się prostym wyszukiwaniem wskaźnika. Wyklucza to pierwszy dostęp, którym jest O(n) .

A co z wierszami zawierającymi więcej niż 16 kolumn? Wiem już, gdzie jest piętnasta kolumna (zaczynając od 0), więc mogę od razu przejść do piętnastej kolumny, a następnie interweniować w naiwny sposób. Jeśli nie wiem, gdzie jest piętnasta kolumna, mogę ją szybko obliczyć i zapisać w pamięci podręcznej.

To całkiem nieźle, z wyjątkiem jeszcze jednej optymalizacji, którą można wykonać. Inną realizacją jest to, że w ramach ParseRowInstruction podczas konstruowania wiersza wyjściowego uzyskuje dostęp do kolumn w kolejności. Oprócz losowej pamięci podręcznej o stałym rozmiarze dla pierwszych 16 kolumn, możemy zachować dodatkowy wskaźnik, który przechowuje początek ostatniej dostępnej kolumny oraz indeks tej kolumny. Pozwala to na proste wyszukiwanie wskaźników dla sekwencyjnych dostępów dla dowolnej liczby kolumn, bez konieczności przechowywania nieskończonej liczby wskaźników, jak na pierwszym poziomie buforowania. Oczywiście te dwie warstwy buforowania współpracują ze sobą. Gdy aktualizujemy pierwsze 16 wartości, aktualizujemy również last_accessedwskaźnik.

Podczas pracy na GPU każdy wątek odpowiada za pojedynczy wiersz. Tak więc każdy wątek ma swoją własną wielowarstwową pamięć podręczną zgodnie z opisem. Pamięć podręczna śledzi również, który wiersz buforujemy. Jeśli różni się od żądanej, resetujemy pamięć podręczną, dzięki czemu wiemy, że pamięć podręczna jest zawsze aktualna. Możliwe jest rozszerzenie tego, aby objąć przypadki użycia odczytywania wielu wierszy lub udostępniania pamięci podręcznej między wątkami, ale wykraczało to poza zakres początkowej implementacji.

Instrukcja projekcji

W ProjectionInstructionporównaniu jest to bardzo proste. Otrzymuje listę indeksów kolumn do pobrania. Tworzy nowy obiekt TempRow i kopiuje te kolumny z ostatniego TempRow, aktualizując metadane w nowym obiekcie TempRow.

Instrukcja filtra

Podstawowa implementacja FilterInstructionjest zaprojektowana wokół oceny jakiegoś wiersza względem jakiegoś wyrażenia, które zwraca albo truealbo false.

Zostało to zaimplementowane jako maszyna wirtualna oparta na stosie. Przydział stosu jest ustalany w czasie kompilacji i dlatego zawsze przydzielany jest jego maksymalny rozmiar.

Stos był dość interesujący do wdrożenia. Zdecydowałem się zaprojektować kod bajtowy dla maszyny wirtualnej, aby zawierał typy, a także instrukcje dotyczące rzutowania jednego typu na inny. Implementacja stosu pozwala na heterogeniczne dane, ale wywołujący jest odpowiedzialny za dostarczenie typów.

W normalnym stosie możesz tworzyć pudełka dla obiektu, a pudełko będzie przechowywać typ rzeczy, a także wskaźnik do rzeczy. W takim przypadku kompilator (jeszcze nie zaimplementowany) jest odpowiedzialny za napisanie kodu bajtowego w celu uwzględnienia wszystkich niezbędnych rzutowań. Pozwala to środowisku uruchomieniowemu na umieszczenie liczby całkowitej na stosie, który jest xbajtami, a później, gdy odczytuje liczbę całkowitą, może xzdjąć bajty ze stosu i uzyskać tę samą liczbę całkowitą. Nie są wymagane żadne pudełka ani dynamiczne odlewanie. To nakłada na kompilator obowiązek poprawienia wszystkich typów, ale pozostawia to do przyszłej implementacji.

Instrukcja wyjściowa

Służy do OutputInstructionłączenia wszystkich danych z poszczególnych wątków w grupie ThreadGroup i usuwania wszystkich zduplikowanych danych, których potrzebuje każdy wątek, ale tak naprawdę wystarczy to tylko raz skopiować do procesora i skutecznie umieścić w jednym dużym buforze .

Pierwszym krokiem jest to, że każdy wiersz (każdy wątek) oblicza swój własny rozmiar. Następnie uruchamiamy sumę prefiksów rozmiarów. To daje nam indeks, w którym wiemy, że możemy zacząć zapisywać nasze dane.

Suma przedrostków to algorytm często używany w obliczeniach GPU, w którym dana tablica liczb całkowitych zwraca nową tablicę, w której dla każdego indeksu i zawiera sumę wszystkich elementów mniejszych niż i . Jeśli suma zawiera pozycję i dla pozycji i , nazywana jest sumą inkluzywną, w przeciwnym razie nazywana jest sumą wyłączną. Użyłem ekskluzywnej sumy do mojej realizacji.

Zanim zaczniemy zapisywać dane, wątki muszą koordynować pisanie nagłówka pliku OutputRow. Aby to zrobić, pierwszy wiersz, odpowiedzialny za zapisanie nagłówka, dodaje również rozmiar nagłówka do własnego rozmiaru. Po wykonaniu sumy prefiksów uruchamiamy również redukcję rozmiarów wierszy, aby pierwszy wątek mógł zapisać całkowitą liczbę bajtów w nagłówku.

Gdy to się zakończy, każdy wiersz może przeskoczyć do swojego przesunięcia z wyjścia sumy prefiksów i skopiować swoje bajty do bufora, zaczynając równolegle od tego punktu, i mamy gwarancję, że nie będzie żadnych kolizji.

TempRow

Jest TempRowto struktura danych, która jest przekazywana podczas przetwarzania danych w Metalu. Idealnie byłoby, gdybyśmy przydzielili zmienny rozmiar TempRowna stercie, aby zminimalizować zużycie pamięci, ale ponieważ Metal nie obsługuje dynamicznej alokacji pamięci. Każdy TempRowjest buforem o stałym rozmiarze. Wybrałem 1024 bajty, czyli 1 kilobajt. Pierwsza sekcja TempRowto nagłówek, po którym następują dane.

Pierwsza wartość w nagłówku to jego długość. Jest to ważne, ponieważ dane rozpoczynają się bezpośrednio po nagłówku, a nagłówek ma zmienną wielkość w zależności od liczby kolumn i ich typów.

Następny bajt to liczba kolumn. Ponieważ jest to tylko 1 bajt, maksymalna liczba kolumn wynosi 256. Wydaje mi się, że jest to wystarczająca ilość dla większości przypadków użycia.

Następne N bajtów to typy kolumn. Kolumny mogą być jednymi z: Integer, Floatlub Stringich odpowiednikami dopuszczającymi wartość null. Wartość logiczna jest po prostu wyrażona jako liczba całkowita.

Liczba całkowita i liczba zmiennoprzecinkowa mają zawsze stały rozmiar, więc nie musimy przechowywać ich rozmiaru w nagłówku, chyba że jest to kolumna dopuszczająca wartość null. Natomiast łańcuch może mieć dowolną liczbę znaków. Dlatego przechowujemy rozmiar wszystkich kolumn o zmiennej długości (łańcuchów i kolumn opcjonalnych) w kolejnych bajtach. Ponownie, ponieważ rozmiar kolumny to tylko 1 bajt, maksymalna długość łańcucha wynosi 256 znaków.

Po nagłówku wszystkie dane dla kolumn są dołączane jeden po drugim.

Aby uprościć konstrukcję TempRow, istnieje klasa pomocnicza, TempRowBuilderw której wywołujący może zapisać wszystkie typy i rozmiary kolumn itp. W osobnych tablicach. Następnie TempRowmożna w prosty sposób skonstruować z konstruktora, kopiując wartości.

Dane z kolumn można następnie dołączać w kolejności. Istnieją metody pomocnicze ułatwiające kopiowanie ciągów znaków, liczb całkowitych i zmiennoprzecinkowych oraz zapisywanie ich bajt po bajcie.

Kiedy następna metoda przechodzi następnie do odczytu TempRow, istnieją metody pomocnicze, które odczytują z nagłówka w celu określenia indeksów początkowych i końcowych w buforze dla tej kolumny i rzutują bajty z powrotem na odpowiedni typ. Osoba dzwoniąca jest odpowiedzialna za zapytanie ColumnTypekolumny, którą jest zainteresowany, przed odczytaniem jej jako tego typu.

Ponieważ TempRowodczytuje wszystkie dane bezpośrednio z bufora o stałym rozmiarze, można go w prosty sposób dostosować do constexprklasy dla innych aplikacji.

wiersz wyjściowy

Jest OutputRowtworzony przez OutputRowInstruction(opisany powyżej) i służy do przenoszenia wielu wierszy, które mają ten sam schemat. Bezpośrednie kopiowanie wszystkich pojedynczych obiektów byłoby marnotrawstwem, TempRowponieważ każdy wiersz ma ten sam schemat, więc istnieje wiele zduplikowanych metadanych. Zamiast tego kopiujemy wszystkie dane do pojedynczej struktury, tak że w razie potrzeby możemy TempRowpóźniej skopiować je do osobnych obiektów lub w razie potrzeby podzielić na dwa lub więcej OutputRowobiektów.

Podobnie jak TempRow, OutputRowma definicję nagłówka, choć różni się nieco od TempRow. Pierwsza wartość, jak wyjaśniono wcześniej, to rozmiar nagłówka, ale ta wartość jest większa, z przydzielonymi 2 bajtami zamiast 1. Następna wartość to liczba bajtów w OutputRow, i jest to 32-bitowa liczba całkowita bez znaku. Po tym następuje liczba kolumn, a to tylko jeden bajt. Następnie następują typy kolumn, podobne do TempRow.

Po nagłówku dołączane są wszystkie dane. Ponieważ OutputRowzawsze jest tworzony z jednego lub więcej TempRowlub z innego OutputRow, możemy równolegle obliczyć rozmiar danych każdego wiersza za pomocą algorytmu sumy prefiksów i równolegle zapisywać do bufora danych.

Podczas pracy w Metal, OutputRowstatycznie przydzielany jest stały rozmiar 1 000 000 bajtów. Na procesorze możemy być bardziej wydajni i używać a std::vectordo przydzielania tylko potrzebnej nam ilości miejsca.

Aby lepiej ułatwić OutputRowrównoległe odczytywanie i zapisywanie każdego wątku, zamiast zapisywania rozmiarów kolumn o zmiennej wielkości w nagłówku, tak jak w TempRow, zamiast tego są one dołączane do danych dla tej kolumny na wiersz. Na przykład wiersz z 2 liczbami całkowitymi, po których następuje ciąg 3 znaków „abc”, miałby format: <integer><integer>3abc. Czytnik OutputRow(obecnie zaimplementowany tylko na procesorze) wie, że kolumna jest ciągiem znaków i dlatego może przeskoczyć na początek łańcucha, aby przeczytać jego zawartość. Rozmiary każdego wiersza nie są zapisywane wOutputRow. Zamiast tego czytnik iteruje po buforze i rejestruje początek każdego wiersza oraz rozmiary każdej kolumny o zmiennej wielkości dla każdego wiersza. Zrobiono to, aby zaoszczędzić miejsce, ale można je zoptymalizować tak, aby były zapisywane w nagłówku lub w wierszu, tak aby odczyt OutputRowbył bardziej wydajny, a zatem szybszy. Szczegóły odczytywania, dzielenia i scalania OutputRowobiektów w procesorze zostały pokrótce omówione wcześniej w sekcji dotyczącej pliku Scheduler.

Przyszła praca

Pracowałem nad tym projektem jako eksperymentem, aby sprawdzić, czy jest to możliwe. Jest wiele rzeczy, które chciałbym wdrożyć, gdybym miał przygotować go do produkcji, a nawet po prostu spędzić więcej czasu nad prototypem, niż mam.

Ten jeden błąd

Pierwszym problemem, który chciałbym rozwiązać, jest (co uważam za błąd w Xcode 13), gdzie wielu wątkom przypisywany jest wątek 0 w grupie wątków. Daj mi znać, jeśli masz jakieś pomysły. Powoduje to, że wiele wątków próbuje napisać nagłówek. Powoduje to, że nagłówek zostaje częściowo zgnieciony danymi, w zależności od kolejności wątków. Próbowałem googlować na ten temat, ale nie mogłem znaleźć żadnych źródeł, które byłyby szczególnie pomocne. Myślę, że miało to związek z ilością pamięci, którą próbowałem przydzielić każdemu wątkowi. Niestety oficjalna dokumentacja Apple nie mówi nic na ten temat, co mogłem znaleźć.

Silnik zapytań + parser

Kolejnym dużym zadaniem jest zaimplementowanie parsera i silnika zapytań, aby baza danych mogła akceptować zapytania podobne do SQL i przekształcać je w plany zapytań i wykonywać je. To zadanie obejmuje również implementację DataFrame API lub zapisywanie na dysku w wielu formatach, które mają być używane przez inne biblioteki i programy.

Dołącz + Grupuj według

Rozwijając specyfikację SQL, fajnie byłoby móc obliczyć sprzężenie i klauzulę Group By. Pomyślałem, że naiwnym sposobem zaimplementowania łączenia jest równoległe obliczenie każdego nieprzetworzonego wiersza na GPU, a następnie wykonanie łączenia mieszającego na procesorze, raz na porcję. Jednak zamiast tego bardziej wydajne może być znalezienie sposobu na przesłanie jednej porcji z 2 różnych tabel, do których chcesz dołączyć w tym samym czasie, i zwrócenie przez GPU połączonych wierszy.

W przypadku opcji Grupuj według można to zrobić na procesorze lub wykonać częściową agregację na GPU. Lub możesz wykonać kombinację, w której wykonujesz wstępne przetwarzanie surowe na GPU, a następnie wykonujesz inne jądro, w którym dany zestaw wierszy oblicza grupę dla każdego wiersza w zestawie. Umożliwiłoby to szybkie gromadzenie wierszy na procesorze, w których można przydzielić więcej danych do przechowywania wierszy, jednocześnie wykorzystując równoległy charakter GPU do równoległego obliczania grup.

System rozproszony

Jeśli ten system ma być używany w produkcji, prawdopodobnie musi być w stanie wykorzystać wiele maszyn. Mogłem sobie wyobrazić heterogeniczną sieć współpracujących ze sobą urządzeń Apple (i innych niż Apple). Wyobraź sobie iPhone'a jako kontrolera hosta wysyłającego polecenia do innych maszyn oraz grupę iPadów, z których każdy przetwarza dane, które mają lokalnie, i wysyła przetworzone wiersze z powrotem do centralnego kontrolera. Alternatywnie, być może masz wdrożenie w chmurze, które uruchamia ten sam kod na procesorze w instancji lambda AWS lub na wielu GPU z lokalnym serwerem Mac Pro. Wszystkie te systemy mogą ze sobą współpracować, aby zapewnić bardzo szybki i responsywny dostęp do bardzo dużych zbiorów danych za pomocą urządzeń, które (jak sądzę) mają wciąż dużo niewykorzystanej mocy obliczeniowej.

Zmniejsz zużycie pamięci

Jako kolejną optymalizację, zwłaszcza że chcę, aby działało to na każdym urządzeniu z systemem Metal, byłoby miło zachować jak najmniejszy ślad pamięci, abyśmy mogli zmaksymalizować zasoby na urządzeniu dla uruchomionej aplikacji użytkownika końcowego . Idealnie byłoby, gdybyśmy byli w stanie odczytać fragment pliku z dysku do pamięci, przekształcić go w bufor, aby wysłać go do GPU, a następnie zwolnić ten fragment pamięci. Próbowałem zaprojektować system w ten sposób, używając shared_ptr, aby mieć system alokacji pamięci zliczający referencje dla buforów. Jednak w praktyce odkryłem, że ponieważ biblioteka zadań, z której korzystałem, nie wiedziała, czy musi ponownie uruchomić wykres zadań z wieloma danymi wejściowymi, biblioteka nie zwolniła lambdy przechwytującej odniesienie do bufora w trakcie. Oznacza to, żeshared_ptrktóry został przechwycony przez lambdę, jest nadal przywoływany i dlatego nie zwalnia swojej pamięci, dopóki wykres zadania nie zostanie zniszczony, co ma miejsce tylko wtedy, gdy cały wykres zakończy wykonywanie.

Wniosek

Ogólnie dobrze się bawiłem pracując i myśląc o tym projekcie. To bardzo różniło się od wielu innych projektów, które zrobiłem. Mam nadzieję, że dobrze się bawiłeś czytając ten artykuł. Moja pełna implementacja znajduje się na górze tego artykułu. Jeśli masz jakieś uwagi lub pomysły na to, co Ci się podobało lub co zrobiłbyś inaczej, skontaktuj się ze mną. Dzięki!