개요

몇 달 전 저는 Metal에서 관계형 데이터베이스의 프로토타입 작업을 시작했습니다. Apple은 몇 달 전에 128GB의 통합 메모리(Mac Studio에서)를 탑재한 M1 Max와 M1 Ultra를 막 출시했습니다.

나는 이것을 많은 GPU 메모리를 필요로 하는 매우 무거운 처리로 무언가를 할 수 있는 기회로 보았다: GPU에서 큰 관계형 테이블을 처리하는 것.

GPU에 관계형 데이터베이스를 작성하는 것에 대해 생각한 것은 제가 처음이 아닙니다. Rapids.AI 에 구축된 GPU 관계형 데이터베이스인 BlazingSQL 과 같은 데이터베이스 . Rapids.AI는 Pandas와 같은 많은 인기 있는 Python 라이브러리의 기능을 미러링하지만 GPU에서 동등한 기능을 실행하는 NVIDIA의 Python 라이브러리입니다. NVIDIA는 데이터 센터에 막대한 투자를 했으며 특히 머신 러닝 및 대규모 데이터 처리를 위해 카드에서 실행되는 더 많은 도구를 개발하는 데 도움을 주었습니다.

최근 Apple 컨퍼런스를 보면서 저는 실제로 사용되지 않는 많은 잠재적인 성능이 있다는 것을 느꼈습니다. 내가 본 바로는 개발자들이 새 칩의 새로운 그래픽 기능을 활용하고 있습니다. 컴퓨팅 측면에서 Metal로 구축된 데모 및 오픈 소스 소프트웨어가 부족했습니다. Apple은 입자 시뮬레이션의 샘플 프로젝트를 만들었습니다. 저는 CUDA 샘플과 동등한 것을 보여줄 것으로 추정합니다. 중간에 CPU로 돌아갈 필요 없이 CUDA에서 컴퓨팅을 사용하고 GPU에서 OpenGL로 렌더링하는 방법을 보여줍니다. Apple이 GPU를 많이 사용하고 있는 다른 곳은 AI 작업입니다. Neural Engine이 모델의 작업을 지원하지 않을 때마다 CoreML은 성능 향상을 위해 자동으로 GPU를 대체합니다. 이것은 매우 유용하고 매력적이지만,

저는 데이터베이스를 정말 좋아하기 때문에 관계형 데이터베이스를 선택했고 데이터베이스를 위한 여러 가지 디자인에 대해 생각해 보았고 그 중 일부는 몇 년 동안 프로토타입을 만들었습니다. 관계형 데이터베이스는 문자열과 null 값을 사용하기 때문에 흥미롭습니다. AI 예제와 입자 시뮬레이터 모두 매우 인상적이지만 부동 소수점과 정수만 사용합니다.

내가 구축한 구현은 여기에서 찾을 수 있습니다: MetalDB Github

디자인 아이디어

프로세스의 시작 부분에 있었는지 중간에 있었는지 기억이 나지 않지만 쿼리 실행 계획을 구성하는 쿼리 단계의 그래프에 대해 설명하는 BigQuery Query Plans 의 문서에서 영감을 받았습니다.

Metal의 주요 설계 제한 사항 중 하나는 모든 메모리가 컴파일 시간에 정적으로 크기 조정되어야 한다는 것입니다. 데이터베이스 행에 얼마나 많은 문자열이 있는지 또는 각 문자열이 컴파일 시간에 얼마나 오래 있는지 모르기 때문에 문자열을 복사할 수 없었기 때문에 문제가 발생했습니다.

접두사 합계 알고리즘을 사용하여 모든 데이터를 GPU에서 CPU로 효율적인 방식으로 다시 복사하는 것이 각 스레드가 하나의 행을 처리하는 경우 가장 간단할 것이라고 생각했습니다. 또한 사용 가능한 가장 큰 동기화 가능한 블록(Metal에서 ThreadGroup)을 사용해야 했습니다.

일부는 최적화로, 일부는 개인적인 도전으로 저는 GPU에서 수행되는 작업량을 최대화하고 싶었습니다. 이러한 이유로 CPU에서 CSV 파일을 읽고 GPU에서 CSV 파싱을 수행하는 것으로 시작했습니다.

구현하는 동안 디버거에서 단위 테스트를 단계별로 수행할 수 있도록 CPU에서 데이터베이스를 테스트할 수 있기를 원했습니다. 이러한 이유로 모든 Metal 커널을 헤더로 작성하도록 빌드 파이프라인을 설정했습니다. 결과적으로 Metal 커널 파일에 포함할 수 있을 뿐만 아니라 C++의 테스트에도 포함할 수 있습니다. 이 디자인을 사용하면 Metal 헤더에서 상수와 유형을 정의하고 이를 호출하는 C++ 코드에서 항상 동일하도록 보장할 수 있습니다.

Threadgroup 및 Metal 개념에 대한 배경

추가 아이디어 및 설명을 위한 배경으로 Metal 실행은 그리드로 구성됩니다. 그리드는 ThreadGroup의 1D, 2D 또는 3D 그룹입니다. ThreadGroup은 해당 그리드 내에서 동기화 가능한 그룹입니다. ThreadGroup 내의 스레드는 분할되어 워프라고 하는 추가 그룹으로 실행됩니다.

스레드는 GPU 프로그래밍에서 가장 기본적인 블록이며 대략 CPU 코어의 스레드 모델로 변환됩니다. 명령의 단일 선형 순서 실행입니다. 스레드에는 공유 메모리에 대한 읽기 및 쓰기는 물론 직접 액세스할 수 있는 레지스터가 있습니다. CPU와 다른 메모리 모델이지만 이 기사의 범위를 벗어납니다.

워프(Metal 문서에서는 SIMD라고 함)는 종종 16개 또는 32개의 스레드 그룹입니다. 잠재적으로 다른 데이터(SIMD, 단일 명령, 다중 데이터)에서 동일한 명령이 워프의 모든 스레드에서 동시에 실행되어야 합니다. 일부 스레드가 코드에서 다른 경로를 사용하는 경우 해당 워프 내의 모든 스레드는 모든 분기가 순차적으로 실행될 때까지 기다려야 합니다. 이는 가능한 한 적은 수의 분기로 GPU 코드를 설계하여 워프 내의 모든 스레드를 가능한 한 많이 사용하도록 합니다.

CUDA 및 OpenCL과 같은 다른 시스템은 이름만 다를 뿐 비슷한 개념을 가지고 있습니다.

구현

구현 링크:https://github.com/mattpaletta/metaldb

제 생각에는 시스템을 통한 데이터 흐름의 순서대로 구현에 대해 이야기하는 것이 가장 합리적이라고 생각합니다. 그러나 이것은 내가 그것을 구현하는 방법과 거의 완벽하게 반대입니다.

바이너리

생성되는 최종 결과는 매우 간단합니다. 그것은 호출되는 바이너리 metaldb이며 그 안에 주요 기능이 있습니다. 저뿐만 아니라 다른 사람들도 나중에 내부 라이브러리를 다른 라이브러리 및 애플리케이션의 일부로 쉽게 재사용할 수 있도록 애플리케이션을 매우 가볍게 만들었습니다.

엔진

엔진은 시스템의 로직 대부분이 조정되는 곳입니다. 엔진 QueryPlanner은 QueryPlanner 라이브러리에 구현된 와 상호 작용하며 Scheduler, 생성된 쿼리 계획의 실행 및 조정을 담당하는 와 상호 작용합니다.

쿼리 파서

Query Parser는 SQL과 유사한 쿼리를 나머지 시스템에서 더 쉽게 구문 분석할 수 있는 AST로 전환하는 역할을 하는 구성 요소입니다.

데이터베이스의 이 첫 번째 버전은 쿼리 구문 분석기를 구현하지 않습니다. 대신 테스트하려는 다양한 쿼리에 대해 AST를 하드코딩했습니다. 파서를 작성하고 AST를 생성하는 것은 매우 흥미롭게 들리지만 다른 프로젝트에서 수행한 작업이며 이 프로젝트의 초점이 아닙니다.

또한 이 프로젝트를 프로덕션 준비가 된 데이터베이스로 만들 생각은 없었습니다. 따라서 지금은 쿼리 파서가 필요하지 않지만 나중에 선택하는 경우 이를 구현할 수 있도록 모든 스텁이 있습니다.

쿼리 문자열을 허용하는 시스템 외에도 궁극적으로 Pandas와 유사하지만 C++로 Dataframe API를 구현할 계획입니다. 내 관점에서 볼 때 이런 종류의 API는 다른 라이브러리에서 작업하기 더 간단할 것입니다. 이것은 또한 파서에 의해 즉시 재분석될 수 있도록 쿼리 문자열을 생성해야 하는 다른 라이브러리의 단계를 저장합니다. 이 Dataframe API도 향후 작업으로 남겨둔다.

테스트 데이터 세트로 먼저 공개적으로 사용 가능한 Iris 데이터 세트 를 사용 했습니다. 이 데이터 세트는 상대적으로 작고 CSV 형식이며 null 값이 없는 대부분 숫자이기 때문에 선택했습니다.

해당 데이터 세트를 작동시킨 후 여러 파일이 포함된 훨씬 더 큰 데이터 세트를 시도하고 싶었습니다. 이를 위해 New York Taxi Dataset 을 사용 했습니다. 이 더 큰 데이터 세트는 내가 예상하지 못한 몇 가지 흥미로운 문제를 입증했으며 이에 대해서는 나중에 자세히 설명합니다.

쿼리 플래너

Query Parser가 AST를 생성한 후 다음 구성 요소는 Query Planner입니다. 이는 AST를 최적화된 실행 계획으로 바꾸는 역할을 합니다.

최적화된 실행 계획을 세우는 첫 번째 단계는 전혀 계획을 세우는 것입니다. BigQuery 참조 에서 영감을 받아 실행 계획을 "단계" 그래프로 나누는 아이디어가 마음에 들었습니다. BigQuery에서 각 단계는 하나 이상의 단계로 구성됩니다. 각 단계는 읽기 또는 쓰기, 집계 또는 조인 등이 될 수 있습니다. 단계의 세분성으로 내려가고 싶지는 않지만 비슷한 개념이 있습니다. "부분"이라고 합니다.

AST에서 단계 그래프로 이동하기 위해 먼저 테이블에 대한 디스크의 파일을 나열합니다. 다음으로 AST의 리프로 이동하여 각각에 대해 해당 파일을 읽을 새 단계를 생성합니다.

트리를 다시 올라가면서 기존 스테이지의 일부로 새 부분을 생성할지 아니면 새 스테이지를 생성할지 결정합니다. 요점은 한 단계에서 GPU에서 CPU로 또는 그 반대로 이동해야 할 때 새 단계를 생성한다는 것입니다. 이는 CPU와 GPU 간의 전송 시간을 최소화하면서 GPU에서 많은 데이터를 처리할 수 있음을 의미합니다. 이는 통합 메모리가 없는 장치와 특히 관련이 있습니다.

모든 단계에는 실행할 부분의 단일 목록이 있습니다. 스케줄러에 대한 섹션에서 더 자세히 살펴볼 것이므로 나중에 해당 단계 내에서 GPU에 대한 지침으로 변환됩니다.

새 단계를 만들 때마다 GPU가 정보를 다시 CPU로 복사하도록 지시하는 "셔플 명령"을 삽입합니다.

앞으로는 각 파일에서 읽고 읽은 후 다시 CPU로 복사되는 데이터의 양을 최소화하기 위해 쿼리를 다시 작성할 수 있는 옵티마이저를 작성할 것입니다.

스케줄러

스케줄러는 쿼리의 병렬 실행을 담당합니다. 나는 이것을 하기 위해 나만의 다중 스레드 라이브러리를 작성하고 싶은 유혹을 느꼈습니다. 오픈 소스 C++ 작업 그래프 라이브러리 인 TaskFlow 위에 구현을 작성하게 되었습니다 .

높은 수준에서 작업 그래프 생성은 단계 그래프를 따릅니다. 각 단계는 그래프의 작업이며 자식에 따라 다릅니다.

단계 내에서 CPU 또는 GPU에서 수행할 단계 목록인 각 부분이 순서대로 확장됩니다. 각 부분이 등록될 때 연결할 수 있는 작업 그래프 내에 여러 작업이 있습니다.

후킹할 수 있는 주요 작업은 이전 작업의 인코딩 작업입니다. 부분은 상위 부분 인코딩 작업에 종속되는 새 작업을 생성해야 합니다. 전달된 Encoder를 사용하여 GPU로 보낼 수 있는 직렬화된 표현으로 자체를 인코딩합니다. 대부분의 작업에서 이것이 필요한 전부이며 부분 구현은 Metal의 GPU에 있습니다.

사용 가능한 다른 작업은 작업 작업입니다. 부분이 기본 동작 대신 해당 부분에 대해 작업이 실행되는 방식에 대해 무언가를 재정의하려는 경우에 존재합니다.

대부분의 작업은 하나 이상의 하위 단계에서 버퍼를 읽고 출력 버퍼에 씁니다. 읽기 명령은 하위 버퍼가 아닌 디스크에서 읽어야 하기 때문에 고유합니다.

읽기 명령어는 할당된 CSV 파일(현재 구현된 유일한 파일 유형)을 읽고 버퍼로 읽는 일련의 작업을 설정합니다. 버퍼로 읽을 때 현재 행의 오프셋을 추적하고 RawTable아래에서 설명하는 개체의 일부로 저장합니다.

파일을 읽고 나면 GPU는 자유롭게 행 처리를 시작할 수 있습니다. 데이터베이스 디자인은 행당 하나의 스레드를 요구합니다. Metal에는 ThreadGroup당 할당할 수 있는 스레드 수에 대한 제한이 있습니다. 따라서 우리는 먼저 행을 각각 독립적으로 GPU로 보낼 여러 버퍼로 분할합니다.

TaskFlow는 작업 내에서 동적 하위 작업을 허용합니다. RawTable. _

그런 다음 각 청크는 병렬로 GPU로 전송됩니다.

모든 청크가 각각 처리된 후 GPU에서 모든 개체를 복사 하고 다음 단계에서 함께 읽을 수 있도록 OutputRow단일 거인으로 병합하는 병합 작업을 실행합니다.OutputRow

앞으로는 여러 배치의 분할을 최적화하고 싶습니다. 배치가 분할되는 즉시 GPU로 보낼 수 있습니다. 해당 청크가 돌아오면 다른 작업이 비동기적으로 처리되는 동안 최종 버퍼에 복사할 수 있습니다.

RawTable또한 모든 행이 각각 사본을 저장하는 청크로 분할되면 원본을 해제하고 싶습니다 . 또한 출력 버퍼가 최종 버퍼에 복사되는 즉시 청크에서 출력 버퍼를 해제하여 필요한 총 메모리 양을 줄일 수 있어야 합니다.

ParseRow 명령어

ParseRowInstruction간단한 전제로 시작합니다 . 각 행의 시작에 대한 인덱스 목록과 행 수 및 열 유형에 대한 정보가 제공되면 특정 행의 값을 구문 분석하고 올바른 유형으로 캐스트합니다.

가장 간단한 열 유형은 문자열입니다. N 행 의 경우 디스크에서 파일을 읽을 때 CPU가 저장한 인덱스를 조회하여 해당 행의 시작 부분으로 이동할 수 있습니다. 그런 다음 해당 인덱스에 대한 포인터를 얻을 수 있습니다. 이것은 행의 시작입니다. 열의 끝은 한 번에 한 문자씩 앞으로 이동할 때 다음 쉼표(다음 열 표시) 앞의 위치이거나 다음 행의 시작 전(행의 마지막 열인 경우) 또는 버퍼가 끝나기 전에(마지막 행의 마지막 열인 경우).

명령어는 먼저 모든 열을 문자열로 읽습니다. 설명된 대로 정확하게 열을 구문 분석하고 문자별로 문자열로 읽습니다. 이제 다음 열을 읽으려면 행의 처음부터 시작합니다. 첫 번째 쉼표에 도달하면 시작으로 표시하고 그 다음 쉼표까지 이동합니다. 후속 열에 대해 프로세스가 반복됩니다.

정수가 있는 경우 문자열의 시작과 끝을 가리키는 포인터를 사용자 지정 stoi함수에 전달합니다. 이것은 문자열을 정수 표현으로 변환하는 C 표준 라이브러리의 것과 유사합니다. 나는 내 자신의 버전도 썼습니다 stof.

상상할 수 있듯이 매번 행의 처음부터 모든 열을 읽는 것은 매우 느리고 중복 작업이 많습니다. 우리는 훨씬 더 잘할 수 있습니다.

열의 시작 부분 찾기를 최적화할 때 첫 번째 깨달음은 종종 열 수가 적다는 것입니다. 캐시할 열의 임의 개수로 16개를 선택했습니다.

이 첫 번째 수준의 캐시를 사용하여 처음 16개 열 내의 열을 읽는 경우 해당 열에 대해 이전에 캐시된 포인터를 읽으려고 합니다. null이 아니면 이미 값이 있는 것입니다. 행은 변경할 수 없으므로 포인터가 유효해야 하며 프로세스가 완료됩니다!

포인터가 null이면 이전에 캐시된 열을 찾거나 첫 번째 항목에 도달할 때까지 16번째 열 인덱스부터 내 캐시를 역방향으로 반복할 수 있습니다.

내가 멈추는 곳에서 한 번에 한 문자씩 순진한 방식으로 행을 반복할 수 있습니다. 쉼표를 찾을 때마다 후속 쿼리가 바로 이동할 수 있도록 해당 열의 시작 부분에 대한 포인터를 캐시에 저장합니다.

이는 처음 16개 열에 대한 임의 액세스가 직선 포인터 조회가 되므로 기본적으로 무료여야 함을 의미합니다. 이것은 O(n) 인 첫 번째 액세스를 제외합니다 .

열이 16개 이상인 행은 어떻습니까? 15번째 열이 어디에 있는지 이미 알고 있으므로(0부터 시작) 15번째 열로 바로 이동한 다음 순진한 방식으로 인터레이트할 수 있습니다. 15번째 열이 어디에 있는지 모를 경우 빠르게 계산하여 캐시할 수 있습니다.

수행할 수 있는 최적화가 하나 더 있다는 점을 제외하면 꽤 좋습니다. 다른 실현은 출력 행을 구성할 때 ParseRowInstruction 내 에서 순서대로 열에 액세스한다는 것입니다. 처음 16개 열에 대한 고정 크기 임의 캐시 외에도 액세스한 마지막 열의 시작 부분과 해당 열의 인덱스를 저장하는 추가 포인터를 유지할 수 있습니다. 이를 통해 캐싱의 첫 번째 수준에서와 같이 무한한 수의 포인터를 저장할 필요 없이 여러 열에 대한 순차 액세스에 대한 직선 포인터 조회가 가능합니다. 물론 이 두 캐싱 계층은 함께 작동합니다. 처음 16개 값을 업데이트하면 last_accessed포인터도 업데이트됩니다.

GPU에서 실행될 때 모든 스레드는 단일 행을 담당합니다. 따라서 모든 스레드에는 설명된 대로 자체 다중 계층 캐시가 있습니다. 캐시는 또한 우리가 캐싱하는 행을 추적합니다. 요청한 것과 다른 경우 캐시를 재설정하므로 캐시가 항상 관련이 있음을 알 수 있습니다. 여러 행을 읽거나 스레드 간에 캐시를 공유하는 사용 사례를 다루기 위해 이를 확장할 수 있지만 이는 초기 구현 범위를 벗어났습니다.

프로젝션 지침

ProjectionInstruction비교해 보면 매우 간단합니다 . 가져올 열 인덱스 목록이 제공됩니다. 새 TempRow 개체를 만들고 마지막 TempRow에서 해당 열을 복사하여 새 TempRow 개체의 메타데이터를 업데이트합니다.

필터 명령

의 기본 구현은 또는 FilterInstruction중 하나를 반환하는 일부 식에 대해 일부 행을 평가하도록 설계되었습니다 .truefalse

이것은 스택 기반 가상 머신으로 구현되었습니다. 스택 할당은 컴파일 시간에 고정되므로 항상 최대 크기를 할당합니다.

스택은 구현하기에 다소 흥미로웠습니다. 유형과 한 유형을 다른 유형으로 캐스팅하기 위한 지침을 포함하도록 VM용 바이트코드를 설계하기로 했습니다. 스택 구현은 이기종 데이터를 허용하지만 호출자는 유형 제공을 담당합니다.

일반 스택에서는 개체에 대한 상자를 만들 수 있으며 상자는 해당 항목에 대한 포인터뿐만 아니라 해당 항목의 유형을 저장합니다. 이 경우 컴파일러(아직 구현되지 않음)는 필요한 모든 캐스팅을 포함하도록 바이트 코드를 작성해야 합니다. 이를 통해 런타임은 x바이트인 스택에 정수를 푸시할 수 있으며 나중에 정수를 읽을 때 x스택에서 바이트를 팝할 수 있고 동일한 정수를 얻을 수 있습니다. 상자나 다이내믹 캐스팅이 필요하지 않습니다. 이렇게 하면 컴파일러가 모든 유형을 올바르게 가져오는 책임을 지게 되지만 향후 구현을 위해 남겨둡니다.

출력 명령어

는 OutputInstructionThreadGroup 내 개별 스레드의 모든 데이터를 결합하고 각 개별 스레드에 필요한 모든 중복 데이터를 제거하는 데 사용되지만 실제로는 CPU에 한 번만 복사하면 되고 효율적으로 하나의 큰 버퍼에 넣습니다. .

첫 번째 단계는 모든 행(모든 스레드)이 자체 크기를 계산하는 것입니다. 그런 다음 크기의 접두사 합계를 실행합니다. 이것은 우리가 데이터 쓰기를 시작할 수 있다는 것을 아는 색인을 제공합니다.

접두사 합계는 정수 배열이 주어지면 모든 인덱스 i에 대해 i 보다 작은 모든 항목의 합계를 포함 하는 새 배열을 반환하는 GPU 계산에 자주 사용되는 알고리즘 입니다. 합계 에 위치 i 에 대한 항목 i 가 포함되어 있으면 포함 합계라고 하고, 그렇지 않으면 제외 합계라고 합니다. 내 구현을 위해 독점 합계를 사용했습니다.

데이터 쓰기를 시작하기 전에 스레드는 의 헤더 쓰기를 조정해야 합니다 OutputRow. 이를 위해 헤더 쓰기를 담당하는 첫 번째 행도 헤더 크기를 자체 크기에 추가합니다. 접두사 합계를 수행한 후 첫 번째 스레드가 헤더에 총 바이트 수를 쓸 수 있도록 행 크기도 축소합니다.

완료되면 각 행은 접두사 합계 출력에서 ​​해당 오프셋으로 점프하고 해당 지점에서 시작하여 해당 바이트를 버퍼에 병렬로 복사할 수 있으며 충돌이 발생하지 않을 것임을 보장합니다.

TempRow

TempRowMetal에서 데이터가 처리되는 동안 전달되는 데이터 구조입니다 . 이상적으로는 크기 조정 가능한 TempRow메모리를 힙에 할당하여 메모리 공간을 최소화하지만 Metal은 동적 메모리 할당을 지원하지 않기 때문입니다. Every TempRow는 고정 크기의 버퍼입니다. 저는 1024바이트 또는 1킬로바이트로 선택했습니다. 의 첫 번째 섹션은 TempRow헤더이고 그 뒤에 데이터가 있습니다.

헤더의 첫 번째 값은 길이입니다. 헤더 바로 뒤에 데이터가 시작되고 헤더는 열의 수와 유형에 따라 크기가 가변적이기 때문에 중요합니다.

다음 바이트는 열 수입니다. 이것은 1바이트에 불과하므로 최대 열 수는 256개입니다. 대부분의 사용 사례에 이 정도면 충분하다고 생각합니다.

다음 N 바이트는 열 유형입니다. 열은 , 또는 nullable 등가물 중 하나일 Integer수 있습니다 Float. String부울 값은 단순히 정수로 표현됩니다.

정수와 실수는 항상 일정한 크기이므로 null 허용 열이 아닌 한 헤더에 크기를 저장할 필요가 없습니다. 대조적으로 문자열은 여러 문자를 가질 수 있습니다. 따라서 모든 가변 길이 열(문자열 및 선택적 열)의 크기를 후속 바이트에 저장합니다. 다시 말하지만 열의 크기는 1바이트에 불과하므로 문자열의 최대 길이는 256자입니다.

헤더 다음에 열의 모든 데이터가 차례로 추가됩니다.

구성을 더 간단하게 만들기 위해 호출자가 모든 열 유형 및 크기 등을 별도의 배열에 쓸 수 TempRow있는 도우미 클래스 가 있습니다. TempRowBuilder그런 TempRow다음 값을 복사하여 빌더에서 간단하게 구성할 수 있습니다.

그런 다음 열의 데이터를 순서대로 추가할 수 있습니다. 문자열, 정수 및 실수를 복사하고 바이트 단위로 쓰는 데 도움이 되는 도우미 메서드가 있습니다.

그런 다음 다음 메서드가 를 읽으려고 TempRow하면 헤더에서 읽어서 해당 열에 대한 버퍼의 시작 및 끝 인덱스를 결정하고 바이트를 다시 적절한 유형으로 캐스팅하는 도우미 메서드가 있습니다. ColumnType호출자는 해당 유형으로 읽기 전에 관심 있는 열 을 쿼리할 책임이 있습니다.

는 고정된 크기의 버퍼에서 직접 모든 데이터를 읽기 때문에 다른 응용 프로그램의 클래스에 TempRow쉽게 적응할 수 있습니다 .constexpr

출력 행

는 (위에 설명된) OutputRow에 의해 생성되며 OutputRowInstruction동일한 스키마를 공유하는 여러 행을 이동하는 목적을 제공합니다. TempRow모든 행이 동일한 스키마를 가지고 있어 많은 중복 메타데이터가 있기 때문에 모든 개별 개체를 직접 복사하는 것은 낭비 입니다. 대신 모든 데이터를 단일 구조로 복사하여 나중에 필요할 경우 별도의 개체에 복사하거나 필요한 경우 두 개 이상의 개체 TempRow로 분할할 수 있습니다.OutputRow

와 유사하게 에는 TempRow와 OutputRow약간 다르지만 헤더 정의가 있습니다 TempRow. 앞에서 설명한 첫 번째 값은 헤더의 크기이지만 이 값은 더 커서 1이 아닌 2바이트가 할당됩니다. 다음 값은 의 바이트 수 OutputRow이며 이것은 32비트 부호 없는 정수입니다. 다음은 열의 수이며 이것은 단일 바이트입니다. 와 유사한 열 유형이 뒤따릅니다 TempRow.

헤더 뒤에 모든 데이터가 추가됩니다. OutputRow는 항상 하나 이상 TempRow또는 다른 에서 구성 되므로 OutputRow접두사 합계 알고리즘을 사용하여 모든 행의 데이터 크기를 병렬로 계산하고 데이터 버퍼에 병렬로 쓸 수 있습니다.

Metal에서 실행할 때 OutputRow는 1,000,000바이트의 고정 크기로 정적으로 할당됩니다. CPU에서 더 효율적일 수 있고 a std::vector를 사용하여 필요한 공간만 할당할 수 있습니다.

모든 스레드가 병렬로 읽고 쓰는 것을 더 용이하게 하기 위해 OutputRow가변 크기 열의 크기가 에 있는 것처럼 헤더에 기록되는 TempRow대신 행당 해당 열의 데이터 앞에 추가됩니다. 예를 들어, 2개의 정수 뒤에 3개의 "abc" 문자열이 있는 행의 형식은 다음과 같습니다 <integer><integer>3abc. 의 판독기 OutputRow(현재 CPU에서만 구현됨)는 열이 문자열임을 알고 있으므로 문자열의 시작 부분으로 이동하여 해당 내용을 읽을 수 있습니다. 각 행의 크기는OutputRow. 대신 판독기는 버퍼를 반복하고 모든 행의 시작과 모든 행에 대한 모든 가변 크기 열의 크기를 기록합니다. 이것은 공간을 절약하기 위해 수행되었지만 헤더 또는 행별로 작성되도록 최적화할 수 있으므로 읽기 OutputRow가 더 효율적이고 따라서 더 빠릅니다. CPU에서 개체 읽기, 분할 및 병합에 대한 자세한 내용은 OutputRow앞서 Scheduler.

미래의 일

나는 그것이 가능한지 알아보기 위한 실험으로 이 프로젝트에 참여했습니다. 생산 준비가 되거나 프로토타입에 더 많은 시간을 할애할 수 있다면 구현하고 싶었던 많은 것들이 있습니다.

그 버그 하나

해결하고 싶은 첫 번째 문제는 여러 스레드가 ThreadGroup 내에서 스레드 0을 할당받는 문제(Xcode 13의 버그라고 생각되는 문제)입니다. 아이디어가 있으면 알려주세요. 이로 인해 여러 스레드가 헤더 쓰기를 시도합니다. 이로 인해 스레드 순서에 따라 헤더가 부분적으로 데이터로 압축됩니다. 나는 그것에 대해 구글링을 시도했지만 특별히 도움이 되는 소스를 찾을 수 없었다. 각 스레드에 할당하려는 메모리 양과 관련이 있다고 생각합니다. 불행하게도 Apple의 공식 문서는 내가 찾을 수 있는 것에 대해 아무 말도 하지 않습니다.

쿼리 엔진 + 파서

다음 큰 작업은 파서와 쿼리 엔진을 구현하여 데이터베이스가 SQL과 유사한 쿼리를 수락하고 이를 쿼리 계획으로 전환하고 실행할 수 있도록 하는 것입니다. 이 작업에는 DataFrame API를 구현하거나 다른 라이브러리 및 프로그램에서 사용할 여러 형식으로 디스크에 쓰는 작업도 포함됩니다.

조인 + 그룹화 기준

SQL 사양을 확장하면 조인과 Group By 절을 계산할 수 있다면 재미있을 것입니다. 조인을 구현하는 순진한 방법은 GPU에서 각 원시 행을 병렬로 계산한 다음 청크당 한 번씩 CPU에서 해시 조인을 수행하는 것이라고 생각했습니다. 그러나 동시에 조인하려는 2개의 다른 테이블에서 하나의 청크를 대신 제출하고 GPU가 조인된 행을 반환하도록 하는 방법을 찾는 것이 더 효율적일 수 있습니다.

Group By의 경우 CPU에서 수행하거나 GPU에서 부분 집계를 수행할 수 있습니다. 또는 GPU에서 초기 원시 처리를 수행한 다음 행 집합이 지정된 경우 다른 커널을 실행하고 집합 내의 각 행에 대한 그룹을 계산하는 조합을 수행할 수 있습니다. 이렇게 하면 행을 보유하기 위해 더 많은 데이터를 할당할 수 있는 CPU에서 행을 빠르게 버킷팅하고 GPU의 병렬 특성을 활용하여 그룹을 병렬로 계산할 수 있습니다.

분산 시스템

이 시스템을 생산에 사용하려면 여러 시스템을 활용할 수 있어야 합니다. 함께 작동하는 Apple(및 Apple이 아닌) 연결 장치의 이기종 네트워크를 상상할 수 있습니다. iPhone을 호스트 컨트롤러로 다른 시스템에 명령을 보내고, 각각 로컬에 있는 데이터를 처리하고 처리된 행을 중앙 컨트롤러로 다시 보내는 iPad 그룹을 상상해 보십시오. 또는 AWS Lambda 인스턴스의 CPU에서 또는 온프레미스에 Mac Pro 서버가 있는 여러 GPU에서 동일한 코드를 실행하는 클라우드 배포가 있을 수 있습니다. 이 모든 시스템은 함께 작동하여 아직 사용 가능한 미개척 처리 능력이 많은 장치를 사용하여 매우 큰 데이터 세트에 매우 빠르게 응답할 수 있습니다.

메모리 풋프린트 줄이기

또 다른 최적화로서, 특히 Metal을 실행하는 모든 기기에서 실행되기를 원하기 때문에 실행 중인 최종 사용자 애플리케이션을 위해 기기의 리소스를 최대화할 수 있도록 메모리 공간을 가능한 한 작게 유지하는 것이 좋을 것입니다. . 이상적으로는 디스크에서 메모리로 파일 청크를 읽고 버퍼로 전환하여 GPU로 보낸 다음 해당 메모리 청크를 해제할 수 있어야 합니다. shared_ptr나는 버퍼를 위한 참조 카운트 메모리 할당 시스템을 가지도록 를 사용하여 그런 방식으로 시스템을 설계하려고 했습니다 . 그러나 나는 실제로 내가 사용하고 있는 작업 라이브러리가 여러 입력으로 작업 그래프를 다시 실행해야 하는지 알지 못하기 때문에 라이브러리가 버퍼에 대한 참조를 캡처하는 람다를 해제하지 않았다는 것을 발견했습니다. 이것은shared_ptr람다에 의해 캡처된 것은 여전히 ​​참조되므로 작업 그래프가 소멸될 때까지 메모리를 해제하지 않습니다. 이는 전체 그래프 실행이 완료될 때만 발생합니다.

결론

전반적으로 저는 이 프로젝트에 대해 작업하고 생각하는 것이 매우 즐거웠습니다. 내가 한 많은 다른 프로젝트와는 매우 달랐습니다. 이 기사를 읽으셨기를 바랍니다. 내 전체 구현은 이 문서의 맨 위에 링크되어 있습니다. 마음에 들었거나 다르게 해보고 싶은 의견이나 아이디어가 있으시면 언제든지 연락주세요. 감사!