Tổng quan

Một vài tháng trước, tôi bắt đầu làm việc trên nguyên mẫu của cơ sở dữ liệu quan hệ trong Metal. Apple vừa phát hành M1 Max và M1 Ultra vài tháng trước với bộ nhớ hợp nhất lên tới 128GB (trong Mac Studio).

Tôi coi đây là cơ hội để làm một việc gì đó với quá trình xử lý rất nặng đòi hỏi nhiều bộ nhớ GPU: xử lý các bảng quan hệ lớn trên GPU.

Tôi không phải là người đầu tiên nghĩ đến việc viết cơ sở dữ liệu quan hệ trên GPU. Cơ sở dữ liệu như BlazingSQL , cơ sở dữ liệu quan hệ GPU được xây dựng trên Rapids.AI . Rapids.AI là một thư viện Python của NVIDIA phản ánh chức năng của nhiều thư viện Python phổ biến, chẳng hạn như Pandas, nhưng chạy các chức năng tương đương trên GPU. NVIDIA đã đầu tư rất nhiều vào trung tâm dữ liệu và giúp phát triển thêm nhiều công cụ chạy trên thẻ của họ, đặc biệt là cho máy học và xử lý dữ liệu lớn.

Khi xem các hội nghị của Apple gần đây, tôi cảm thấy có rất nhiều hiệu suất tiềm năng không thực sự được sử dụng. Theo những gì tôi thấy, các nhà phát triển đang tận dụng khả năng đồ họa mới của các chip mới. Về mặt máy tính, các bản trình diễn và phần mềm mã nguồn mở được xây dựng bằng Metal còn thiếu. Apple đã thực hiện một dự án mẫu về mô phỏng hạt, tôi cho rằng sẽ hiển thị tương đương với mẫu CUDA. Chúng chỉ ra cách bạn có thể sử dụng tính toán trong CUDA và hiển thị trong OpenGL trên GPU mà không cần phải quay lại CPU ở giữa. Một nơi khác mà Apple đã sử dụng GPU rất nhiều là cho các tác vụ AI. Bất cứ khi nào Công cụ thần kinh không hỗ trợ hoạt động trong một mô hình, CoreML sẽ tự động dự phòng trên GPU để có hiệu suất cao hơn. Mặc dù điều này rất hữu ích và hấp dẫn,

Tôi đã chọn một cơ sở dữ liệu quan hệ vì tôi thực sự yêu thích cơ sở dữ liệu và đã nghĩ về một số thiết kế cho chúng, một số trong đó tôi đã tạo nguyên mẫu trong nhiều năm. Cơ sở dữ liệu quan hệ cũng thú vị vì chúng sử dụng các chuỗi và giá trị null. Cả ví dụ AI và trình mô phỏng hạt, mặc dù rất ấn tượng, nhưng chỉ sử dụng số thực và số nguyên.

Việc triển khai mà tôi đã xây dựng có thể được tìm thấy ở đây: MetalDB Github

ý tưởng thiết kế

Tôi không nhớ đó là ngay từ đầu hay ở đâu đó ở giữa quy trình, tuy nhiên, tôi đã được truyền cảm hứng từ tài liệu từ Kế hoạch truy vấn BigQuery nói về biểu đồ các giai đoạn truy vấn tạo nên một kế hoạch thực hiện truy vấn.

Một trong những hạn chế thiết kế chính với Metal là tất cả bộ nhớ phải có kích thước tĩnh tại thời điểm biên dịch. Điều này đưa ra những thách thức vì tôi không thể sao chép một chuỗi vì tôi không biết có bao nhiêu chuỗi trong một hàng cơ sở dữ liệu hoặc mỗi chuỗi sẽ dài bao lâu tại thời điểm biên dịch.

Tôi đã hình dung việc sử dụng thuật toán tổng tiền tố để sao chép tất cả dữ liệu trở lại từ GPU sang CPU một cách hiệu quả sẽ là cách đơn giản nhất nếu mỗi luồng xử lý một hàng. Tôi cũng cần sử dụng khối có thể đồng bộ hóa lớn nhất hiện có, khối này trong Metal là ThreadGroup.

Một phần là để tối ưu hóa và một phần là thử thách cá nhân, tôi muốn tối đa hóa khối lượng công việc được thực hiện trên GPU. Vì những lý do đó, tôi đã chọn bắt đầu bằng việc đọc các tệp CSV trên CPU và thực hiện phân tích cú pháp CSV trên GPU.

Trong khi triển khai, tôi cũng muốn có thể kiểm tra cơ sở dữ liệu trên CPU để có thể thực hiện từng bước kiểm tra đơn vị trong trình gỡ lỗi. Vì lý do này, tôi thiết lập quy trình xây dựng để tất cả các hạt nhân Kim loại của tôi được ghi dưới dạng tiêu đề. Kết quả là tôi có thể đưa chúng vào các tệp nhân Metal, nhưng cũng đưa chúng vào các thử nghiệm trong C++. Thiết kế này cũng sẽ cho phép tôi xác định các hằng số và loại trong các tiêu đề Metal và đảm bảo chúng luôn giống nhau trong mã C++ sẽ gọi nó.

Nền tảng về các khái niệm Threadgroups và Metal

Để làm nền tảng cho các ý tưởng và giải thích thêm, Quá trình thực hiện kim loại được tổ chức thành lưới. Lưới là một nhóm 1D, 2D hoặc 3D của ThreadGroups. ThreadGroup là một nhóm có thể đồng bộ hóa trong lưới đó. Các luồng trong ThreadGroup bị chia nhỏ và thực hiện thành các nhóm khác, được gọi là warp.

Một luồng là khối cơ bản nhất trong lập trình GPU và tạm dịch là mô hình của một luồng trên lõi CPU. Nó là một lệnh thực hiện đơn, tuyến tính, theo thứ tự. Chuỗi có các thanh ghi mà nó có thể truy cập trực tiếp cũng như đọc và ghi vào bộ nhớ dùng chung. Nó là một kiểu bộ nhớ khác với trên CPU, nhưng điều đó nằm ngoài phạm vi của bài viết này.

Một sợi dọc (được gọi là SIMD trong tài liệu Kim loại) thường là một nhóm gồm 16 hoặc 32 luồng. Cùng một lệnh phải được thực thi cùng lúc trên tất cả các luồng trong một sợi dọc, mặc dù có khả năng trên các dữ liệu khác nhau (SIMD, Một lệnh, Nhiều dữ liệu). Nếu một số luồng đi theo một đường dẫn khác trong mã, thì tất cả các luồng trong sợi dọc đó phải đợi tất cả các nhánh thực thi nối tiếp. Điều này dẫn đến việc thiết kế mã GPU với càng ít nhánh càng tốt, sao cho bạn giữ cho tất cả các luồng trong một sợi dọc bận rộn nhất có thể.

Các hệ thống khác như CUDA và OpenCL có các khái niệm tương tự, chỉ khác tên gọi.

Thực hiện

Liên kết thực hiện:https://github.com/mattpaletta/metaldb

Theo tôi, tôi nghĩ sẽ hợp lý nhất khi nói về việc triển khai theo thứ tự luồng dữ liệu qua hệ thống. Tuy nhiên, đây gần như là sự đối lập hoàn hảo với cách tôi thực hiện nó.

nhị phân

Kết quả cuối cùng được tạo ra rất đơn giản. Nó là một nhị phân được gọi metaldbvà nó chỉ có một chức năng chính trong đó. Tôi đã làm cho ứng dụng rất nhẹ để tôi cũng như những người khác có thể sử dụng lại các thư viện bên trong một cách dễ dàng như một phần của các thư viện và ứng dụng khác trong tương lai.

Động cơ

Engine là nơi điều phối phần lớn logic của hệ thống. Engine tương tác với QueryPlanner, được triển khai trong thư viện QueryPlanner, cũng như Scheduler, chịu trách nhiệm chạy và điều phối việc thực hiện kế hoạch truy vấn đã tạo.

Trình phân tích truy vấn

Trình phân tích truy vấn là thành phần chịu trách nhiệm chuyển một truy vấn giống như SQL thành một AST mà phần còn lại của hệ thống có thể phân tích cú pháp dễ dàng hơn .

Phiên bản đầu tiên này của cơ sở dữ liệu không triển khai Trình phân tích truy vấn. Thay vào đó, tôi đã mã hóa cứng AST cho các truy vấn khác nhau mà tôi muốn kiểm tra. Viết trình phân tích cú pháp và tạo AST, mặc dù nghe có vẻ rất thú vị, nhưng tôi đã thực hiện trong một dự án khác và không phải là trọng tâm của dự án này.

Tôi cũng không có ý định biến dự án này thành một cơ sở dữ liệu sẵn sàng sản xuất. Do đó, nó không cần trình phân tích cú pháp truy vấn vào thời điểm này, nhưng tất cả các sơ khai đều có sẵn để tôi triển khai nó sau này nếu tôi muốn.

Ngoài việc hệ thống chấp nhận các chuỗi truy vấn, cuối cùng tôi dự định triển khai API Dataframe, tương tự như Pandas, nhưng trong C++. Theo quan điểm của tôi, loại API này sẽ đơn giản hơn đối với các thư viện khác để làm việc cùng. Điều này cũng giúp tiết kiệm bước thư viện khác chỉ phải tạo một chuỗi truy vấn để nó được trình phân tích cú pháp phân tích cú pháp ngay lập tức. API Dataframe này cũng được coi là công việc trong tương lai.

Là một bộ dữ liệu thử nghiệm, lần đầu tiên tôi sử dụng bộ dữ liệu Iris có sẵn công khai . Tôi chọn tập dữ liệu này vì nó tương đối nhỏ, ở định dạng CSV và chủ yếu là số, không có giá trị null.

Sau khi tôi làm cho tập dữ liệu đó hoạt động, tôi muốn thử một tập dữ liệu lớn hơn nhiều với nhiều tệp. Đối với điều này, tôi đã sử dụng Bộ dữ liệu taxi New York . Tập dữ liệu lớn hơn này đã chứng minh một số thách thức thú vị mà tôi không mong đợi, sẽ nói thêm về vấn đề này sau.

Công cụ lập kế hoạch truy vấn

Sau khi Trình phân tích cú pháp truy vấn đã tạo AST, thành phần tiếp theo là Công cụ lập kế hoạch truy vấn. Điều này chịu trách nhiệm biến AST thành một kế hoạch thực hiện được tối ưu hóa.

Bước đầu tiên để lập một kế hoạch thực hiện được tối ưu hóa là lập một kế hoạch. Lấy cảm hứng từ tài liệu tham khảo BigQuery , tôi thích ý tưởng chia nhỏ kế hoạch thực hiện thành biểu đồ “Giai đoạn”. Trong BigQuery, mỗi giai đoạn bao gồm một hoặc nhiều bước. Mỗi bước có thể là đọc hoặc ghi, tổng hợp hoặc tham gia, v.v. Tôi không muốn đi sâu vào mức độ chi tiết của các bước, nhưng tôi có một khái niệm tương tự, tôi gọi là “một phần”.

Để chuyển từ AST sang biểu đồ các giai đoạn, trước tiên tôi liệt kê các tệp trên đĩa cho (các) bảng. Tiếp theo, tôi đi đến các lá của AST và đối với mỗi lá, tôi tạo một giai đoạn mới sẽ đọc tệp đó.

Khi tôi đi ngược lên cây, tôi quyết định xem tôi sẽ tạo một phần mới như một phần của giai đoạn hiện có hay tạo một giai đoạn mới. Điểm mấu chốt là khi tôi phải chuyển từ GPU sang CPU hoặc ngược lại trong một bước, tôi sẽ tạo một giai đoạn mới. Điều này có nghĩa là có thể xử lý nhiều dữ liệu trên GPU đồng thời giảm thiểu thời gian truyền giữa CPU và GPU. Điều này đặc biệt phù hợp với các thiết bị không có bộ nhớ hợp nhất.

Mỗi giai đoạn có một danh sách riêng lẻ để chạy. Những điều này sau đó sẽ được dịch thành hướng dẫn cho GPU trong giai đoạn đó, khi chúng ta khám phá thêm trong phần về bộ lập lịch.

Mỗi khi tôi tạo một giai đoạn mới, tôi sẽ chèn một “Hướng dẫn xáo trộn”, yêu cầu GPU sao chép thông tin trở lại CPU.

Trong tương lai, tôi cũng sẽ viết một trình tối ưu hóa có thể viết lại các truy vấn để giảm thiểu lượng dữ liệu được đọc từ mỗi tệp và sao chép lại vào CPU sau khi được đọc.

Người lập kế hoạch

Bộ lập lịch chịu trách nhiệm thực hiện song song truy vấn. Tôi muốn viết thư viện đa luồng của riêng mình để làm việc này. Cuối cùng, tôi đã viết phần triển khai của mình trên TaskFlow , một thư viện đồ thị tác vụ C++ mã nguồn mở.

Ở cấp độ cao, việc tạo biểu đồ nhiệm vụ tuân theo biểu đồ của các giai đoạn. Mỗi giai đoạn là một nhiệm vụ trong biểu đồ và phụ thuộc vào các phần tử con của nó.

Trong một giai đoạn, mỗi phần, danh sách các bước được thực hiện trên CPU hoặc GPU, được mở rộng theo thứ tự. Vì mỗi phần đang được đăng ký, nó có một số nhiệm vụ trong biểu đồ nhiệm vụ mà nó có thể nối vào.

Nhiệm vụ chính có thể được nối vào, là nhiệm vụ mã hóa của nhiệm vụ trước đó. Một phần sẽ tạo một tác vụ mới phụ thuộc vào tác vụ mã hóa một phần gốc. Nó sử dụng Bộ mã hóa được truyền vào để mã hóa chính nó thành một biểu diễn được đánh số tự động có thể được gửi tới GPU. Đối với hầu hết các tác vụ, đây là tất cả những gì cần thiết và việc triển khai một phần là trên GPU trong Metal.

Nhiệm vụ khác có sẵn là nhiệm vụ công việc. Điều này tồn tại trong trường hợp một bộ phận muốn ghi đè điều gì đó về cách công việc được thực thi cho bộ phận đó thay vì hành vi mặc định.

Hầu hết các tác vụ đọc bộ đệm từ một hoặc nhiều giai đoạn con và ghi vào bộ đệm đầu ra của chúng. Lệnh đọc là duy nhất vì nó phải đọc từ đĩa chứ không phải từ bộ đệm con.

Lệnh đọc thiết lập một chuỗi tác vụ đọc tệp CSV (loại tệp duy nhất hiện được triển khai) nó đã được chỉ định và đọc nó vào bộ đệm. Vì nó đang đọc vào bộ đệm, nó theo dõi độ lệch của hàng hiện tại và lưu trữ chúng như một phần của RawTableđối tượng, được mô tả bên dưới.

Khi tệp đã được đọc, GPU có thể tự do bắt đầu xử lý các hàng. Thiết kế của cơ sở dữ liệu yêu cầu một luồng trên mỗi hàng. Metal tình cờ có giới hạn về số lượng luồng có thể được chỉ định cho mỗi ThreadGroup. Do đó, trước tiên chúng tôi chia các hàng thành nhiều bộ đệm, mỗi bộ đệm sẽ được gửi đến GPU một cách độc lập.

TaskFlow cho phép các nhiệm vụ phụ động trong một nhiệm vụ. Khi tôi nhận được RawTable, tôi truy vấn số luồng mà Metal cho phép tôi lên lịch và chia các hàng ban đầu thành các phần có kích thước đó.

Mỗi đoạn sau đó được gửi song song đến GPU.

Sau khi tất cả các khối đã được xử lý, tôi chạy một tác vụ hợp nhất để sao chép tất cả các OutputRowđối tượng từ GPU và hợp nhất chúng thành một khối khổng lồ duy nhất OutputRowđể giai đoạn tiếp theo có thể đọc chúng cùng nhau.

Trong tương lai, tôi muốn tối ưu hóa việc chia nhiều đợt. Ngay sau khi lô đã được phân chia, nó có thể được gửi đến GPU. Ngay sau khi khối đó quay trở lại, nó có thể được sao chép vào bộ đệm cuối cùng trong khi các tác vụ khác đang xử lý không đồng bộ.

Ngoài ra, tôi muốn giải phóng bản gốc RawTablesau khi tất cả các hàng đã được chia thành nhiều phần, mỗi phần lưu trữ một bản sao. Ngoài ra, tôi có thể giải phóng bộ đệm đầu ra khỏi đoạn ngay sau khi nó được sao chép vào bộ đệm cuối cùng, giảm tổng dung lượng bộ nhớ cần thiết.

Lệnh ParseRow

Bắt ParseRowInstructionđầu với một tiền đề đơn giản. Đưa ra một danh sách các chỉ mục cho phần đầu của mỗi hàng và thông tin về số lượng hàng và loại cột, phân tích các giá trị cho một hàng cụ thể, chuyển thành loại chính xác của chúng.

Loại cột đơn giản nhất là một chuỗi. Đối với hàng N , chúng ta có thể chuyển đến đầu hàng đó bằng cách tra cứu chỉ mục của nó mà CPU đã lưu trữ khi chúng ta đọc tệp từ đĩa. Sau đó chúng ta có thể lấy một con trỏ tới chỉ mục đó. Đây là phần đầu của hàng. Kết thúc của bất kỳ cột nào là vị trí trước dấu phẩy tiếp theo (đánh dấu cột tiếp theo) khi chúng ta di chuyển về phía trước một ký tự tại một thời điểm hoặc một ký tự trước khi bắt đầu hàng tiếp theo (nếu đó là cột cuối cùng của hàng) hoặc một trước khi kết thúc bộ đệm (nếu đó là cột cuối cùng của hàng cuối cùng).

Hướng dẫn đọc mọi cột dưới dạng chuỗi trước tiên. Nó phân tích một cột chính xác như được mô tả và đọc nó dưới dạng một chuỗi, từng ký tự một. Bây giờ để đọc cột tiếp theo, chúng ta bắt đầu từ đầu hàng. Khi chúng tôi đến dấu phẩy đầu tiên, chúng tôi đánh dấu đó là phần đầu và tiếp tục cho đến dấu phẩy sau đó. Quá trình lặp lại cho các cột tiếp theo.

Nếu chúng ta có một số nguyên, chúng ta chuyển các con trỏ đến đầu và cuối chuỗi cho một stoihàm tùy chỉnh. Điều này tương tự như một trong thư viện chuẩn C, chuyển đổi chuỗi thành biểu diễn số nguyên. Tôi cũng đã viết phiên bản của riêng mình stof.

Như bạn có thể tưởng tượng, việc đọc từng cột từ đầu hàng mỗi lần rất chậm và có nhiều công việc trùng lặp. Chúng ta có thể làm tốt hơn, tốt hơn nhiều.

Nhận thức đầu tiên trong việc tối ưu hóa việc tìm phần đầu của cột là thường có số lượng cột thấp. Tôi đã chọn 16 làm số lượng cột tùy ý để lưu vào bộ đệm.

Với mức bộ đệm đầu tiên này, nếu tôi đang đọc một cột trong 16 cột đầu tiên, tôi sẽ thử và đọc con trỏ đã lưu trong bộ đệm trước đó cho cột đó. Nếu nó không phải là null, tôi đã có giá trị. Hàng là bất biến, vì vậy con trỏ phải hợp lệ và quá trình kết thúc!

Nếu con trỏ là null, tôi có thể lặp ngược bộ nhớ cache của mình từ chỉ mục cột thứ 16 cho đến khi tôi tìm thấy một cột đã lưu trong bộ nhớ cache trước đó hoặc tôi đến được mục đầu tiên.

Từ bất cứ nơi nào tôi dừng lại, tôi có thể lặp qua hàng theo cách ngây thơ, từng ký tự một. Mỗi khi tôi tìm thấy một dấu phẩy, tôi lưu con trỏ tới đầu cột đó trong bộ đệm của mình để các truy vấn tiếp theo có thể nhảy thẳng tới đó.

Điều này có nghĩa là quyền truy cập ngẫu nhiên vào 16 cột đầu tiên về cơ bản là miễn phí vì nó trở thành tra cứu con trỏ thẳng. Điều này không bao gồm quyền truy cập đầu tiên, đó là O(n) .

Còn những hàng có hơn 16 cột thì sao? Tôi đã biết cột thứ 15 ở đâu (bắt đầu từ 0) nên tôi có thể nhảy thẳng đến cột thứ 15 và sau đó tương tác một cách ngây thơ. Nếu tôi không biết cột thứ 15 ở đâu, tôi có thể nhanh chóng tính toán và lưu trữ nó.

Điều này khá tốt, ngoại trừ có một tối ưu hóa nữa có thể được thực hiện. Nhận thức khác là trong ParseRowInstruction khi nó đang xây dựng hàng đầu ra, nó sẽ truy cập các cột theo thứ tự. Ngoài bộ đệm ngẫu nhiên có kích thước cố định cho 16 cột đầu tiên, chúng ta có thể giữ một con trỏ bổ sung lưu trữ phần đầu của cột cuối cùng được truy cập và chỉ mục của cột đó. Điều này cho phép tra cứu con trỏ thẳng để truy cập tuần tự cho bất kỳ số lượng cột nào mà không cần phải lưu trữ vô số con trỏ, như ở cấp bộ nhớ đệm đầu tiên. Tất nhiên, hai lớp bộ nhớ đệm này hoạt động cùng nhau. Khi chúng tôi cập nhật 16 giá trị đầu tiên, chúng tôi cũng cập nhật last_accessedcon trỏ.

Khi chạy trên GPU, mỗi luồng chịu trách nhiệm cho một hàng. Vì vậy, mỗi luồng có bộ đệm nhiều lớp riêng như được mô tả. Bộ đệm cũng theo dõi hàng nào chúng tôi đang lưu vào bộ đệm. Nếu nó khác với yêu cầu, chúng tôi sẽ đặt lại bộ đệm để chúng tôi biết bộ đệm luôn phù hợp. Có thể mở rộng điều này để bao gồm các trường hợp sử dụng đọc nhiều hàng hoặc chia sẻ bộ nhớ đệm giữa các luồng, nhưng điều này nằm ngoài phạm vi triển khai ban đầu.

hướng dẫn chiếu

Việc ProjectionInstructionso sánh rất đơn giản. Nó được cung cấp một danh sách các chỉ mục cột để tìm nạp. Nó tạo một đối tượng TempRow mới và sao chép các cột đó từ TempRow cuối cùng, cập nhật siêu dữ liệu trong đối tượng TempRow mới.

Hướng dẫn lọc

Việc triển khai cơ bản của the FilterInstructionđược thiết kế xung quanh việc đánh giá một số hàng dựa trên một số biểu thức trả về hoặc truehoặc false.

Điều này đã được thực hiện như một máy ảo dựa trên ngăn xếp. Việc phân bổ ngăn xếp được cố định tại thời điểm biên dịch và do đó luôn phân bổ kích thước tối đa của nó.

Ngăn xếp hơi thú vị để thực hiện. Tôi đã chọn thiết kế mã byte cho VM để bao gồm các loại cũng như hướng dẫn chuyển loại này sang loại khác. Việc triển khai ngăn xếp cho phép dữ liệu không đồng nhất, nhưng người gọi chịu trách nhiệm cung cấp các loại.

Trong một ngăn xếp bình thường, bạn có thể tạo các hộp cho một đối tượng và hộp sẽ lưu trữ loại đối tượng cũng như một con trỏ tới đối tượng. Trong trường hợp này, trình biên dịch (chưa được triển khai) chịu trách nhiệm viết mã byte để bao gồm tất cả quá trình truyền cần thiết. Điều này cho phép bộ thực thi đẩy một số nguyên vào ngăn xếp, là xbyte, và sau đó khi nó đọc một số nguyên, nó có thể bật các xbyte ra khỏi ngăn xếp và nhận được cùng một số nguyên. Không cần hộp hoặc đúc động. Điều này đặt trách nhiệm lên trình biên dịch để có được tất cả các loại chính xác, nhưng điều đó còn lại để thực hiện trong tương lai.

Hướng dẫn đầu ra

Được sử dụng để kết OutputInstructionhợp tất cả dữ liệu từ các luồng riêng lẻ trong ThreadGroup và loại bỏ tất cả dữ liệu trùng lặp mà mỗi luồng riêng lẻ cần, nhưng dữ liệu đó chỉ thực sự cần được sao chép một lần vào CPU và đưa nó vào một bộ đệm lớn một cách hiệu quả. .

Bước đầu tiên là mỗi hàng (mỗi luồng) tính toán kích thước của chính nó. Sau đó, chúng tôi chạy tổng tiền tố của các kích thước. Điều này cung cấp cho chúng tôi một chỉ mục nơi chúng tôi biết rằng chúng tôi có thể bắt đầu ghi dữ liệu của mình.

Tổng tiền tố là một thuật toán thường được sử dụng trong tính toán GPU trong đó một mảng số nguyên được cung cấp, trả về một mảng mới trong đó đối với mọi chỉ mục i, chứa tổng của tất cả các mục nhỏ hơn i . Nếu tổng bao gồm mục i cho vị trí i , thì nó được gọi là tổng bao gồm, nếu không thì nó được gọi là tổng loại trừ. Tôi đã sử dụng một khoản tiền độc quyền cho việc thực hiện của mình.

Trước khi chúng ta có thể bắt đầu ghi dữ liệu, các luồng phải phối hợp ghi tiêu đề của tệp OutputRow. Để làm điều này, hàng đầu tiên, chịu trách nhiệm viết tiêu đề, cũng thêm kích thước tiêu đề vào kích thước của chính nó. Sau khi chúng tôi thực hiện tính tổng tiền tố, chúng tôi cũng thực hiện giảm kích thước hàng để chuỗi đầu tiên có thể ghi tổng số byte vào tiêu đề.

Sau khi hoàn thành, mỗi hàng có thể chuyển sang phần bù của nó từ đầu ra tổng tiền tố và sao chép song song các byte của nó vào bộ đệm bắt đầu từ điểm đó và chúng tôi được đảm bảo sẽ không có bất kỳ xung đột nào.

hàng tạm thời

Đây TempRowlà cấu trúc dữ liệu được truyền xung quanh trong khi dữ liệu đang được xử lý trong Metal. Lý tưởng nhất là chúng ta sẽ phân bổ một vùng có thể thay đổi kích thước TempRowtrên heap để giảm thiểu dung lượng bộ nhớ, nhưng vì Metal không hỗ trợ phân bổ bộ nhớ động. Mỗi TempRowlà một bộ đệm có kích thước cố định. Tôi đã chọn nó là 1024 byte hoặc 1 kilobyte. Phần đầu tiên của TempRowlà một tiêu đề, theo sau là dữ liệu.

Giá trị đầu tiên trong tiêu đề là độ dài của nó. Điều này quan trọng vì dữ liệu bắt đầu ngay sau tiêu đề và tiêu đề có kích thước thay đổi tùy thuộc vào số lượng cột và loại của chúng.

Byte tiếp theo là số cột. Vì đây chỉ là 1 byte, nên số lượng cột tối đa là 256. Tôi cảm thấy điều này là đủ cho hầu hết các trường hợp sử dụng.

N byte tiếp theo là các loại cột. Các cột có thể là một trong số: Integer, Float, Stringhoặc tương đương nullable của chúng. Giá trị boolean được biểu thị đơn giản dưới dạng số nguyên.

Một số nguyên và một số float luôn có kích thước không đổi, vì vậy chúng ta không phải lưu trữ kích thước của chúng trong tiêu đề, trừ khi đó là một cột có thể null. Ngược lại, một chuỗi có thể có bất kỳ số lượng ký tự nào. Do đó, chúng tôi lưu trữ kích thước của tất cả các cột có độ dài thay đổi (chuỗi và cột tùy chọn) trong các byte tiếp theo. Một lần nữa, vì kích thước của một cột chỉ là 1 byte, độ dài tối đa của một chuỗi là 256 ký tự.

Sau tiêu đề, tất cả dữ liệu cho các cột được thêm vào lần lượt.

Để làm cho việc xây dựng TempRowđơn giản hơn, có một lớp trình trợ giúp TempRowBuildernơi người gọi có thể viết tất cả các loại và kích thước cột, v.v. vào các mảng riêng biệt. Sau TempRowđó, có thể được xây dựng tầm thường từ trình tạo bằng cách sao chép các giá trị.

Dữ liệu từ các cột sau đó có thể được thêm vào theo thứ tự. Có các phương thức trợ giúp để hỗ trợ sao chép theo chuỗi, số nguyên và số float, đồng thời viết chúng theo từng byte.

Khi phương thức tiếp theo chuyển sang đọc TempRow, sẽ có các phương thức trợ giúp đọc từ tiêu đề để xác định chỉ mục bắt đầu và kết thúc trong bộ đệm cho cột đó và chuyển các byte trở lại thành loại thích hợp. Người gọi chịu trách nhiệm truy vấn ColumnTypecột mà họ quan tâm, trước khi đọc nó dưới dạng loại đó.

Bởi vì nó TempRowđọc tất cả dữ liệu trực tiếp từ một bộ đệm có kích thước cố định, nên nó có thể được điều chỉnh một cách tầm thường thành một constexprlớp cho các ứng dụng khác.

Hàng đầu ra

The OutputRowđược tạo bởi OutputRowInstruction(được mô tả ở trên) và phục vụ mục đích di chuyển nhiều hàng xung quanh chia sẻ cùng một lược đồ. Sẽ rất lãng phí nếu sao chép TempRowtrực tiếp tất cả các đối tượng riêng lẻ vì mỗi hàng có cùng một lược đồ, do đó có rất nhiều siêu dữ liệu trùng lặp. Thay vào đó, chúng tôi sao chép tất cả dữ liệu vào một cấu trúc đơn lẻ sao cho chúng tôi có thể sao chép dữ liệu đó thành các TempRowđối tượng riêng biệt nếu cần sau này hoặc chia dữ liệu thành hai hoặc nhiều OutputRowđối tượng nếu cần.

Tương tự như TempRow, the OutputRowcó định nghĩa tiêu đề, mặc dù nó hơi khác so với TempRow. Giá trị đầu tiên như đã giải thích trước đó là kích thước của tiêu đề, nhưng giá trị này lớn hơn, với 2 byte được phân bổ thay vì 1. Giá trị tiếp theo là số byte trong OutputRow, và đây là số nguyên không dấu 32 bit. Sau đây là số lượng cột và đây chỉ là một byte đơn. Tiếp theo là các loại cột, tương tự như TempRow.

Sau tiêu đề, tất cả dữ liệu được thêm vào. Vì the OutputRowluôn được xây dựng từ một hoặc nhiều TempRowhoặc từ một hàng khác OutputRow, nên chúng ta có thể tính song song kích thước dữ liệu của mỗi hàng bằng cách sử dụng thuật toán tổng tiền tố và ghi song song vào bộ đệm dữ liệu.

Khi chạy trong Metal, OutputRowtệp được phân bổ tĩnh có kích thước cố định là 1.000.000 byte. Trên CPU, chúng ta có thể hiệu quả hơn và sử dụng a std::vectorđể chỉ phân bổ dung lượng chúng ta cần.

Để tạo điều kiện thuận lợi hơn cho mọi luồng đọc và ghi OutputRowsong song, thay vì kích thước của các cột có kích thước thay đổi được ghi trong tiêu đề như trong TempRow, thay vào đó, chúng được thêm vào trước dữ liệu cho cột đó trên mỗi hàng. Vì vậy, ví dụ, một hàng có 2 số nguyên theo sau là một chuỗi 3 ký tự “abc”, sẽ có định dạng: <integer><integer>3abc. Trình đọc của OutputRow(hiện chỉ được triển khai trên CPU) biết rằng cột là một chuỗi và do đó có thể chuyển đến đầu chuỗi để đọc nội dung của nó. Kích thước của mỗi hàng không được ghi vàoOutputRow. Thay vào đó, trình đọc lặp qua bộ đệm và ghi lại điểm bắt đầu của mỗi hàng và kích thước của mỗi cột có kích thước thay đổi cho mỗi hàng. Điều này được thực hiện để tiết kiệm dung lượng, nhưng có thể được tối ưu hóa để ghi vào tiêu đề hoặc mỗi hàng, sao cho việc đọc OutputRowhiệu quả hơn và do đó nhanh hơn. Chi tiết về đọc, tách và hợp nhất OutputRowcác đối tượng trên CPU đã được thảo luận ngắn gọn trước đó trong phần về Scheduler.

Công việc tương lai

Tôi đã làm việc với dự án này như một thử nghiệm để xem liệu nó có khả thi hay không. Có rất nhiều thứ mà tôi muốn thực hiện, nếu tôi định làm cho nó sẵn sàng sản xuất, hoặc thậm chí chỉ dành nhiều thời gian hơn cho nguyên mẫu so với thời gian tôi có.

Đó là một lỗi

Vấn đề đầu tiên tôi muốn giải quyết là (điều mà tôi tin là lỗi trong Xcode 13), trong đó nhiều luồng đang được chỉ định luồng 0 trong một Nhóm chủ đề. Hãy cho tôi biệt nếu bạn có ý tưởng gì đó. Điều này khiến nhiều luồng thử và viết tiêu đề. Điều này dẫn đến việc tiêu đề bị nén một phần dữ liệu, tùy thuộc vào thứ tự của chuỗi. Tôi đã cố gắng google về nó, nhưng không thể tìm thấy bất kỳ nguồn nào đặc biệt hữu ích. Tôi nghĩ nó liên quan đến dung lượng bộ nhớ mà tôi đang cố phân bổ cho từng luồng. Thật không may, tài liệu chính thức của Apple không nói bất cứ điều gì về điều đó mà tôi có thể tìm thấy.

Công cụ truy vấn + Trình phân tích cú pháp

Nhiệm vụ lớn tiếp theo là triển khai trình phân tích cú pháp và công cụ truy vấn để cơ sở dữ liệu có thể chấp nhận các truy vấn giống như SQL và biến chúng thành các kế hoạch truy vấn và thực thi chúng. Nhiệm vụ này cũng liên quan đến việc triển khai API DataFrame hoặc ghi ở nhiều định dạng vào đĩa để các thư viện và chương trình khác sử dụng.

Tham gia + Nhóm theo

Mở rộng trên thông số kỹ thuật SQL, sẽ rất thú vị khi có thể tính toán một mệnh đề nối và mệnh đề Nhóm theo. Tôi nghĩ rằng cách ngây thơ để thực hiện phép nối là tính toán song song từng hàng thô trên GPU, sau đó thực hiện phép nối băm trên CPU, một lần cho mỗi đoạn. Tuy nhiên, thay vào đó, có thể hiệu quả hơn nếu tìm ra cách gửi một đoạn từ 2 bảng khác nhau mà bạn muốn tham gia cùng một lúc và yêu cầu GPU trả về các hàng đã tham gia.

Đối với Nhóm theo, bạn có thể thực hiện trên CPU hoặc có thể thực hiện tổng hợp một phần trên GPU. Hoặc bạn có thể thực hiện một số kết hợp theo đó bạn thực hiện xử lý thô ban đầu trên GPU, sau đó có một nhân khác mà bạn thực thi ở nơi đã cho một tập hợp các hàng, tính toán nhóm cho từng hàng trong tập hợp đó. Điều này sẽ cho phép bạn nhanh chóng nhóm các hàng trên CPU, nơi bạn có thể phân bổ nhiều dữ liệu hơn để giữ các hàng, đồng thời tận dụng tính chất song song của GPU để tính toán các nhóm song song.

Hệ thống phân phối

Nếu hệ thống này sẽ được sử dụng trong sản xuất, nó có thể cần phải có khả năng tận dụng nhiều máy móc. Tôi có thể tưởng tượng một mạng không đồng nhất gồm các thiết bị được kết nối của Apple (và không phải của Apple) hoạt động cùng nhau. Hãy tưởng tượng một chiếc iPhone là bộ điều khiển máy chủ gửi lệnh đến các máy khác và một nhóm iPad mà mỗi chiếc xử lý dữ liệu mà chúng có cục bộ và gửi các hàng đã xử lý trở lại bộ điều khiển trung tâm. Ngoài ra, có lẽ bạn có một triển khai đám mây chạy cùng một mã trên CPU trong phiên bản AWS lambda hoặc trên nhiều GPU có máy chủ Mac Pro tại chỗ. Tất cả các hệ thống này có thể hoạt động cùng nhau để cung cấp cho bạn quyền truy cập phản hồi rất nhanh vào các tập dữ liệu rất lớn với các thiết bị (tôi cảm thấy) vẫn còn nhiều sức mạnh xử lý chưa được khai thác.

Giảm dấu chân bộ nhớ

Là một tối ưu hóa khác, đặc biệt là vì tôi muốn điều này chạy trên bất kỳ thiết bị nào chạy Metal, sẽ rất tốt nếu giữ dung lượng bộ nhớ càng nhỏ càng tốt để chúng tôi có thể tối đa hóa tài nguyên trên thiết bị cho ứng dụng người dùng cuối đang chạy . Lý tưởng nhất là chúng ta có thể đọc một đoạn tệp từ đĩa vào bộ nhớ, biến nó thành bộ đệm để gửi đến GPU, sau đó giải phóng đoạn bộ nhớ đó. Tôi đã cố gắng thiết kế hệ thống theo cách đó bằng cách sử dụng shared_ptr, như vậy tôi sẽ có một hệ thống phân bổ bộ nhớ đếm tham chiếu cho bộ đệm. Tuy nhiên, trên thực tế, tôi nhận thấy rằng vì thư viện tác vụ mà tôi đang sử dụng không biết liệu nó có cần chạy lại biểu đồ tác vụ với nhiều đầu vào hay không, nên thư viện đã không giải phóng lambda bắt tham chiếu đến bộ đệm khi nó hoạt động. Điều này có nghĩa làshared_ptrđã được lambda ghi lại vẫn được tham chiếu và do đó không giải phóng bộ nhớ của nó cho đến sau khi đồ thị tác vụ bị hủy, điều này chỉ xảy ra khi toàn bộ đồ thị kết thúc thực thi.

Phần kết luận

Nhìn chung, tôi đã có rất nhiều niềm vui khi làm việc và suy nghĩ về dự án này. Nó rất khác so với nhiều dự án khác mà tôi đã thực hiện. Tôi hy vọng bạn thích đọc bài viết này. Việc triển khai đầy đủ của tôi được liên kết ở đầu bài viết này. Nếu bạn có bất kỳ nhận xét hoặc ý tưởng nào về những điều bạn thích hoặc sẽ làm khác đi, vui lòng liên hệ với tôi. Cảm ơn!