ภาพรวม

ไม่กี่เดือนที่ผ่านมา ฉันเริ่มสร้างต้นแบบของฐานข้อมูลเชิงสัมพันธ์ใน Metal Apple เพิ่งเปิดตัว M1 Max และ M1 Ultra เมื่อไม่กี่เดือนก่อนหน้านี้พร้อมหน่วยความจำรวมสูงสุด 128GB (ใน Mac Studio)

ฉันเห็นว่านี่เป็นโอกาสที่จะทำบางสิ่งด้วยการประมวลผลที่หนักมากซึ่งต้องใช้หน่วยความจำ GPU จำนวนมาก: การประมวลผลตารางเชิงสัมพันธ์ขนาดใหญ่บน GPU

ฉันไม่ใช่คนแรกที่คิดเกี่ยวกับการเขียนฐานข้อมูลเชิงสัมพันธ์บน GPU ฐานข้อมูล เช่นBlazingSQLซึ่งเป็นฐานข้อมูลเชิงสัมพันธ์ของ GPU ที่สร้างขึ้นบนRapids.AI Rapids.AI เป็นไลบรารี Python จาก NVIDIA ที่สะท้อนการทำงานของไลบรารี Python ยอดนิยมมากมาย เช่น Pandas แต่เรียกใช้ฟังก์ชันที่เทียบเท่ากันบน GPU NVIDIA ลงทุนอย่างมากในศูนย์ข้อมูลและช่วยพัฒนาเครื่องมือเพิ่มเติมที่ทำงานบนการ์ดของพวกเขา โดยเฉพาะอย่างยิ่งสำหรับการเรียนรู้ของเครื่องและการประมวลผลข้อมูลขนาดใหญ่

จากการดูการประชุมของ Apple เมื่อเร็ว ๆ นี้ ฉันรู้สึกว่ามีประสิทธิภาพที่เป็นไปได้มากมายที่ไม่ได้ใช้จริง จากสิ่งที่ฉันได้เห็น นักพัฒนากำลังใช้ประโยชน์จากความสามารถด้านกราฟิกใหม่ของชิปใหม่ ในด้านการคำนวณ การสาธิตและซอฟต์แวร์โอเพ่นซอร์สที่สร้างด้วย Metal ยังขาดอยู่ Apple สร้างโครงการตัวอย่างของการจำลองอนุภาค ซึ่งฉันคิดว่าจะแสดงตัวอย่าง CUDA ที่เทียบเท่า พวกเขาแสดงวิธีที่คุณสามารถใช้การคำนวณใน CUDA และแสดงผลใน OpenGL บน GPU โดยไม่ต้องกลับไปที่ CPU ระหว่างนั้น สถานที่อื่นที่ Apple ใช้ GPU อย่างหนักสำหรับงาน AI เมื่อใดก็ตามที่ Neural Engine ไม่รองรับการทำงานในโมเดล CoreML จะใช้ GPU แทนโดยอัตโนมัติเพื่อประสิทธิภาพที่มากขึ้น แม้ว่าสิ่งนี้จะมีประโยชน์และน่าสนใจมาก

ฉันเลือกฐานข้อมูลเชิงสัมพันธ์เนื่องจากฉันบังเอิญรักฐานข้อมูลมากและได้คิดเกี่ยวกับการออกแบบจำนวนหนึ่งสำหรับฐานข้อมูลเหล่านั้น ซึ่งบางรายการฉันได้สร้างต้นแบบไว้เป็นเวลาหลายปี ฐานข้อมูลเชิงสัมพันธ์ก็น่าสนใจเช่นกัน เนื่องจากใช้สตริงและค่า Null ทั้งตัวอย่าง AI และเครื่องจำลองอนุภาค แม้จะน่าประทับใจมาก แต่ก็ใช้เฉพาะจำนวนจริงและจำนวนเต็มเท่านั้น

การใช้งานที่ฉันสร้างขึ้นสามารถพบได้ที่นี่: MetalDB Github

แนวคิดการออกแบบ

ฉันจำไม่ได้ว่ามันถูกต้องในตอนเริ่มต้นหรือระหว่างกระบวนการ แต่ฉันได้รับแรงบันดาลใจจากเอกสารประกอบจากBigQuery Query Plansซึ่งพูดถึงกราฟของขั้นตอนการค้นหาที่ประกอบกันเป็นแผนดำเนินการค้นหา

หนึ่งในข้อจำกัดการออกแบบที่สำคัญของ Metal คือหน่วยความจำทั้งหมดจะต้องมีขนาดคงที่ในเวลาคอมไพล์ สิ่งนี้นำเสนอความท้าทายเพราะฉันไม่สามารถคัดลอกสตริงได้เนื่องจากไม่รู้ว่ามีสตริงกี่สตริงในแถวฐานข้อมูล หรือแต่ละสตริงจะใช้เวลานานเท่าใดในการคอมไพล์

ฉันคิดว่าการใช้อัลกอริทึมผลรวมของคำนำหน้าเพื่อคัดลอกข้อมูลทั้งหมดกลับจาก GPU ไปยัง CPU อย่างมีประสิทธิภาพ ซึ่งจะง่ายที่สุดหากแต่ละเธรดประมวลผลหนึ่งแถว ฉันยังต้องใช้บล็อกซิงโครไนซ์ที่ใหญ่ที่สุดที่มีอยู่ ซึ่งใน Metal คือ ThreadGroup

บางส่วนเป็นการเพิ่มประสิทธิภาพ และบางส่วนเป็นความท้าทายส่วนตัว ฉันต้องการเพิ่มปริมาณงานที่ทำบน GPU ให้ได้มากที่สุด ด้วยเหตุผลดังกล่าว ฉันเลือกที่จะเริ่มต้นด้วยการอ่านไฟล์ CSV บน CPU และทำการแยกวิเคราะห์ CSV บน GPU

ขณะใช้งาน ฉันยังต้องการทดสอบฐานข้อมูลบน CPU เพื่อให้สามารถผ่านการทดสอบหน่วยในดีบักเกอร์ได้ ด้วยเหตุผลนี้ ฉันตั้งค่าไปป์ไลน์สำหรับสร้างเพื่อให้เมล็ดโลหะทั้งหมดของฉันเขียนเป็นส่วนหัว เป็นผลให้ฉันสามารถรวมไว้ในไฟล์เคอร์เนลโลหะ แต่ยังรวมไว้ในการทดสอบใน C ++ การออกแบบนี้ยังช่วยให้ฉันสามารถกำหนดค่าคงที่และประเภทในส่วนหัวของโลหะและรับประกันได้ว่าค่าเหล่านั้นจะเหมือนกันเสมอในโค้ด C++ ที่จะเรียกใช้

ความเป็นมาเกี่ยวกับ Threadgroups และแนวคิดเกี่ยวกับโลหะ

ในฐานะที่เป็นพื้นหลังสำหรับแนวคิดและคำอธิบายเพิ่มเติม การดำเนินการด้วยโลหะจะจัดอยู่ในกริด ตารางคือกลุ่ม 1D, 2D หรือ 3D ของ ThreadGroups ThreadGroup เป็นกลุ่มที่ซิงโครไนซ์ได้ภายในกริดนั้น เธรดภายใน ThreadGroup จะถูกแยกย่อยและดำเนินการเป็นกลุ่มอื่นๆ ที่เรียกว่า warps

เธรดเป็นบล็อกพื้นฐานที่สุดในการเขียนโปรแกรม GPU และแปลคร่าวๆ เป็นโมเดลของเธรดบนคอร์ CPU เป็นการดำเนินการคำสั่งเดียว เชิงเส้น เรียงตามลำดับ เธรดมีรีจิสเตอร์ที่สามารถเข้าถึงได้โดยตรง ตลอดจนอ่านและเขียนไปยังหน่วยความจำที่ใช้ร่วมกัน เป็นหน่วยความจำรุ่นอื่นที่ไม่ใช่ CPU แต่อยู่นอกเหนือขอบเขตของบทความนี้

วิปริต (เรียกว่า SIMD ในเอกสารโลหะ) มักจะเป็นกลุ่มของ 16 หรือ 32 เธรด คำสั่งเดียวกันจะต้องดำเนินการพร้อมกันในทุกเธรดในวาร์ป แม้ว่าอาจเป็นไปได้ในข้อมูลที่แตกต่างกัน (SIMD, คำสั่งเดียว, หลายข้อมูล) ถ้าบางเธรดใช้พาธอื่นในโค้ด เธรดทั้งหมดภายในวาร์ปนั้นต้องรอให้แบรนช์ทั้งหมดดำเนินการตามลำดับ สิ่งนี้นำไปสู่การออกแบบโค้ด GPU ที่มีสาขาน้อยที่สุดเท่าที่จะเป็นไปได้ เช่น คุณเก็บเธรดทั้งหมดไว้ในวาร์ปที่ยุ่งมากที่สุดเท่าที่จะเป็นไปได้

ระบบอื่นๆ เช่น CUDA และ OpenCL มีแนวคิดที่คล้ายกัน เพียงแต่มีชื่อต่างกัน

การดำเนินการ

ลิงก์ไปยังการใช้งาน:https://github.com/mattpaletta/metaldb

ในความคิดของฉัน ฉันคิดว่ามันเหมาะสมที่สุดที่จะพูดคุยเกี่ยวกับการใช้งานตามลำดับการไหลของข้อมูลผ่านระบบ อย่างไรก็ตาม นี่เกือบจะเป็นสิ่งที่ตรงกันข้ามกับวิธีที่ฉันนำไปใช้

ไบนารี่

ผลลัพธ์สุดท้ายที่ผลิตนั้นง่ายมาก มันเป็นเลขฐานสองที่เรียกว่าmetaldbและมีหน้าที่หลักในนั้น ฉันสร้างแอปพลิเคชันที่เบามากเพื่อให้ฉันและคนอื่นๆ สามารถใช้ไลบรารีภายในซ้ำได้อย่างง่ายดายโดยเป็นส่วนหนึ่งของไลบรารีและแอปพลิเคชันอื่นๆ ในอนาคต

เครื่องยนต์

Engine เป็นที่ที่ตรรกะส่วนใหญ่ของระบบประสานกัน Engine โต้ตอบกับQueryPlannerซึ่งใช้งานในไลบรารี QueryPlanner เช่นเดียวกับSchedulerซึ่งมีหน้าที่รับผิดชอบในการเรียกใช้และประสานงานการดำเนินการของแผนการสืบค้นที่สร้างขึ้น

แบบสอบถาม Parser

Query Parser เป็นคอมโพเนนต์ที่รับผิดชอบในการเปลี่ยน Query ที่เหมือน SQL ให้เป็น AST ที่ ส่วนอื่นๆ ของระบบ สามารถแยกวิเคราะห์ได้ง่ายขึ้น

ฐานข้อมูลเวอร์ชันแรกนี้ไม่ได้ใช้ Query Parser แต่ฉันได้ฮาร์ดโค้ด AST สำหรับข้อความค้นหาต่างๆ ที่ฉันต้องการทดสอบแทน การเขียนโปรแกรมแยกวิเคราะห์และสร้าง AST แม้ว่าฟังดูน่าสนใจมาก แต่ก็เป็นสิ่งที่ฉันได้ทำในโปรเจ็กต์อื่น และไม่ใช่จุดสนใจของโปรเจ็กต์นี้

ฉันไม่ได้ตั้งใจให้โครงการนี้เป็นฐานข้อมูลที่พร้อมสำหรับการผลิต ดังนั้นจึงไม่ต้องการตัวแยกวิเคราะห์แบบสอบถามในขณะนี้ แต่มีต้นขั้วทั้งหมดให้ฉันนำไปใช้ในภายหลังหากฉันเลือก

นอกจากระบบจะยอมรับสตริงข้อความค้นหาแล้ว ฉันยังวางแผนที่จะใช้ Dataframe API ซึ่งคล้ายกับ Pandas ใน C++ จากมุมมองของฉัน API ประเภทนี้น่าจะง่ายกว่าสำหรับไลบรารี่อื่นที่จะทำงานด้วย สิ่งนี้ยังช่วยบันทึกขั้นตอนของไลบรารีอื่นที่ต้องสร้างสตริงการสืบค้นเท่านั้นเพื่อให้ตัวแยกวิเคราะห์แยกวิเคราะห์ใหม่ทันที Dataframe API นี้ถูกทิ้งไว้เป็นงานในอนาคต

ในฐานะชุดข้อมูลทดสอบ ฉันใช้ชุดข้อมูล Iris ที่เผยแพร่ต่อสาธารณะเป็นครั้ง แรก ฉันเลือกชุดข้อมูลนี้เพราะมีขนาดค่อนข้างเล็ก อยู่ในรูปแบบ CSV และส่วนใหญ่เป็นตัวเลข โดยไม่มีค่า Null

หลังจากที่ฉันทำให้ชุดข้อมูลนั้นใช้งานได้แล้ว ฉันต้องการลองใช้ชุดข้อมูลที่ใหญ่กว่านี้มากโดยมีหลายไฟล์ สำหรับสิ่ง นี้ฉันใช้New York Taxi Dataset ชุดข้อมูลที่ใหญ่ขึ้นนี้พิสูจน์ให้เห็นถึงความท้าทายที่น่าสนใจบางอย่างที่ฉันคาดไม่ถึง ไว้จะมาเพิ่มเติมในภายหลัง

เครื่องมือวางแผนแบบสอบถาม

หลังจากที่ Query Parser สร้าง AST แล้ว ส่วนประกอบถัดไปคือ Query Planner สิ่งนี้มีหน้าที่รับผิดชอบในการเปลี่ยน AST ให้เป็นแผนการดำเนินการที่เหมาะสมที่สุด

ขั้นตอนแรกของการจัดทำแผนการดำเนินการที่เหมาะสมคือการจัดทำแผนทั้งหมด ได้รับแรงบันดาลใจจากการอ้างอิงของ BigQueryฉันชอบแนวคิดในการแบ่งแผนการดำเนินการออกเป็นกราฟของ "ระยะ" ใน BigQuery แต่ละขั้นตอนประกอบด้วยอย่างน้อยหนึ่งขั้นตอน แต่ละขั้นตอนอาจเป็นการอ่านหรือเขียน การรวมหรือการรวม ฯลฯ ฉันไม่ต้องการลงลึกถึงรายละเอียดของขั้นตอน แต่ฉันมีแนวคิดที่คล้ายกัน ฉันเรียกว่า "บางส่วน"

หากต้องการเปลี่ยนจาก AST เป็นกราฟของขั้นตอน ขั้นแรกฉันจะแสดงรายการไฟล์ในดิสก์สำหรับตาราง ต่อไป ฉันไปที่ส่วนย่อยของ AST และสำหรับแต่ละส่วน ฉันจะสร้างสเตจใหม่ที่จะอ่านไฟล์นั้น

ขณะที่ฉันเดินกลับขึ้นไปบนต้นไม้ ฉันตัดสินใจว่าฉันจะสร้างบางส่วนใหม่โดยเป็นส่วนหนึ่งของสเตจที่มีอยู่หรือสร้างสเตจใหม่ ประเด็นสำคัญคือเมื่อฉันต้องเปลี่ยนจาก GPU เป็น CPU หรือในทางกลับกัน ฉันจะสร้างสเตจใหม่ ซึ่งหมายความว่าข้อมูลจำนวนมากสามารถประมวลผลบน GPU ในขณะที่ลดเวลาการถ่ายโอนระหว่าง CPU และ GPU สิ่งนี้เกี่ยวข้องอย่างยิ่งกับอุปกรณ์ที่ไม่มีหน่วยความจำรวม

ทุกๆ ด่านมีรายการพาร์ทิชันเดียวที่จะรัน สิ่งเหล่านี้จะถูกแปลเป็นคำแนะนำไปยัง GPU ในขั้นตอนนั้นในภายหลัง เนื่องจากเราจะสำรวจเพิ่มเติมในส่วนเกี่ยวกับตัวกำหนดตารางเวลา

ทุกครั้งที่ฉันสร้างสเตจใหม่ ฉันจะใส่ "คำสั่งสุ่ม" ซึ่งจะบอกให้ GPU คัดลอกข้อมูลกลับไปยัง CPU

ในอนาคต ฉันจะเขียนเครื่องมือเพิ่มประสิทธิภาพที่สามารถเขียนข้อความค้นหาใหม่เพื่อลดจำนวนข้อมูลที่อ่านจากแต่ละไฟล์และคัดลอกกลับไปยัง CPU หลังจากอ่าน

กำหนดการ

ตัวกำหนดตารางเวลามีหน้าที่รับผิดชอบในการดำเนินการคิวรีแบบขนาน ฉันถูกล่อลวงให้เขียนไลบรารีแบบมัลติเธรดของตัวเองเพื่อทำสิ่งนี้ ฉันลงเอยด้วยการเขียนการใช้งานบนTaskFlowซึ่งเป็นไลบรารีกราฟงาน C++ แบบโอเพ่นซอร์ส

ในระดับสูง การสร้างกราฟงานจะเป็นไปตามกราฟของระยะ แต่ละด่านเป็นงานในกราฟ และขึ้นอยู่กับลูกของมัน

ภายในสเตจ แต่ละบางส่วน รายการของขั้นตอนที่ต้องทำบน CPU หรือ GPU จะถูกขยายตามลำดับ เนื่องจากแต่ละส่วนกำลังถูกลงทะเบียน จึงมีงานหลายอย่างภายในกราฟงานที่สามารถเชื่อมต่อได้

งานหลักที่สามารถเชื่อมต่อได้คืองานเข้ารหัสของงานก่อนหน้า บางส่วนควรสร้างงานใหม่ที่ขึ้นอยู่กับงานเข้ารหัสบางส่วนพาเรนต์ มันใช้ตัวเข้ารหัสที่ส่งผ่านเพื่อเข้ารหัสตัวเองเป็นการแสดงแบบอนุกรมที่สามารถส่งไปยัง GPU สำหรับงานส่วนใหญ่ นี่คือทั้งหมดที่จำเป็นและการใช้งานบางส่วนนั้นอยู่ใน GPU ในโลหะ

งานอื่นที่มีอยู่คืองาน สิ่งนี้มีอยู่ในกรณีที่บางส่วนต้องการแทนที่บางอย่างเกี่ยวกับวิธีการทำงานสำหรับบางส่วนนั้นแทนที่จะเป็นพฤติกรรมเริ่มต้น

งานส่วนใหญ่อ่านบัฟเฟอร์จากสเตจย่อยอย่างน้อยหนึ่งสเตจ และเขียนไปยังบัฟเฟอร์เอาต์พุต คำสั่งอ่านไม่ซ้ำกันเนื่องจากต้องอ่านจากดิสก์ ไม่ใช่จากบัฟเฟอร์ลูก

คำแนะนำในการอ่านจะตั้งค่าห่วงโซ่ของงานที่อ่านไฟล์ CSV (ประเภทไฟล์เดียวที่ใช้งานอยู่ในปัจจุบัน) ซึ่งได้รับมอบหมายและอ่านลงในบัฟเฟอร์ ขณะที่กำลังอ่านข้อมูลในบัฟเฟอร์ จะติดตามออฟเซ็ตของแถวปัจจุบันและจัดเก็บไว้เป็นส่วนหนึ่งของRawTableอ็อบเจ็กต์ ดังที่อธิบายไว้ด้านล่าง

เมื่ออ่านไฟล์แล้ว GPU จะเริ่มประมวลผลแถวได้อย่างอิสระ การออกแบบฐานข้อมูลเรียกหนึ่งเธรดต่อแถว Metal มีการจำกัดจำนวนเธรดที่สามารถกำหนดได้ต่อ ThreadGroup ดังนั้นเราจึงแบ่งแถวออกเป็นหลาย ๆ บัฟเฟอร์ซึ่งแต่ละแถวจะถูกส่งไปยัง GPU แยกกัน

TaskFlow ช่วยให้งานย่อยแบบไดนามิกภายในงาน เมื่อฉันได้รับRawTableฉันจะค้นหาจำนวนของเธรดที่ Metal อนุญาตให้ฉันตั้งเวลาและแบ่งแถวเดิมออกเป็นชิ้นขนาดดังกล่าว

แต่ละอันจะถูกส่งไปยัง GPU พร้อมกัน

หลังจากแต่ละชิ้นได้รับการประมวลผลแล้ว ฉันเรียกใช้งานการผสานที่คัดลอกออบเจกOutputRowต์ทั้งหมดจาก GPU และรวมเข้าด้วยกันเป็นขนาดยักษ์เดียวOutputRowเพื่อให้ขั้นตอนต่อไปสามารถอ่านพร้อมกันได้

ในอนาคต ฉันต้องการเพิ่มประสิทธิภาพการแยกชุดงานหลายชุด ทันทีที่แบทช์ถูกแบ่ง ก็สามารถส่งไปยัง GPU ได้ ทันทีที่อันนั้นกลับมา ก็สามารถคัดลอกไปยังบัฟเฟอร์สุดท้ายในขณะที่งานอื่นๆ กำลังประมวลผลแบบอะซิงโครนัส

นอกจากนี้ ฉันต้องการปล่อยต้นฉบับRawTableเมื่อแบ่งแถวทั้งหมดออกเป็นส่วนๆ ซึ่งแต่ละแถวเก็บสำเนาไว้ นอกจากนี้ ฉันควรทำให้บัฟเฟอร์เอาต์พุตออกจากก้อนข้อมูลได้ทันทีที่คัดลอกไปยังบัฟเฟอร์สุดท้าย ซึ่งช่วยลดจำนวนหน่วยความจำทั้งหมดที่ต้องใช้

คำสั่ง ParseRow

เริ่ม ต้นParseRowInstructionด้วยหลักฐานง่ายๆ กำหนดรายการของดัชนีสำหรับการเริ่มต้นของแต่ละแถวและข้อมูลเกี่ยวกับจำนวนของแถวและประเภทของคอลัมน์ แยกวิเคราะห์ค่าสำหรับแถวหนึ่งๆ แปลงเป็นประเภทที่ถูกต้อง

ประเภทคอลัมน์ที่ง่ายที่สุดคือสตริง สำหรับแถวNเราสามารถข้ามไปที่จุดเริ่มต้นของแถวนั้นได้โดยค้นหาดัชนีซึ่ง CPU เก็บไว้เมื่อเราอ่านไฟล์จากดิสก์ จากนั้นเราจะได้ตัวชี้ไปที่ดัชนีนั้น นี่คือจุดเริ่มต้นของแถว จุดสิ้นสุดของคอลัมน์ใดๆ คือตำแหน่งก่อนเครื่องหมายจุลภาคถัดไป (ทำเครื่องหมายคอลัมน์ถัดไป) เมื่อเราเลื่อนไปข้างหน้าทีละอักขระ หรือหนึ่งอักขระก่อนจุดเริ่มต้นของแถวถัดไป (หากเป็นคอลัมน์สุดท้ายของแถว) หรือหนึ่ง ก่อนสิ้นสุดบัฟเฟอร์ (หากเป็นคอลัมน์สุดท้ายของแถวสุดท้าย)

คำสั่งจะอ่านทุกคอลัมน์เป็นสตริงก่อน มันแยกวิเคราะห์คอลัมน์ตรงตามที่อธิบายไว้และอ่านเป็นสตริง อักขระต่ออักขระ ตอนนี้เพื่ออ่านคอลัมน์ถัดไป เราจะเริ่มที่จุดเริ่มต้นของแถว เมื่อเราไปถึงเครื่องหมายจุลภาคแรก เราจะทำเครื่องหมายว่าเป็นจุดเริ่มต้น และดำเนินการต่อไปจนถึงเครื่องหมายจุลภาคหลังจากนั้น กระบวนการนี้ซ้ำสำหรับคอลัมน์ถัดไป

ถ้าเรามีจำนวนเต็ม เราจะส่งพอยน์เตอร์ไปยังจุดเริ่มต้นและจุดสิ้นสุดของสตริงไปยังstoiฟังก์ชัน แบบกำหนดเอง สิ่งนี้คล้ายกับไลบรารีมาตรฐาน C ซึ่งจะแปลงสตริงเป็นการแสดงจำนวนเต็ม ฉันเขียนเวอร์ชันของตัวเองstofเช่นกัน

อย่างที่คุณคิด การอ่านทุกคอลัมน์ตั้งแต่ต้นแถวในแต่ละครั้งนั้นช้ามากและมีงานที่ซ้ำกันจำนวนมาก เราทำได้ดีกว่า ดีกว่ามาก

สิ่งสำคัญประการแรกในการเพิ่มประสิทธิภาพการค้นหาจุดเริ่มต้นของคอลัมน์คือ มักจะมีจำนวนคอลัมน์น้อย ฉันเลือก 16 เป็นจำนวนคอลัมน์ที่จะแคชโดยพลการ

ด้วยแคชระดับแรกนี้ ถ้าฉันกำลังอ่านคอลัมน์ภายใน 16 คอลัมน์แรก ฉันจะลองและอ่านตัวชี้ที่แคชก่อนหน้านี้สำหรับคอลัมน์นั้น หากไม่เป็นโมฆะ แสดงว่าฉันมีค่าอยู่แล้ว แถวไม่เปลี่ยนรูป ดังนั้นตัวชี้ต้องถูกต้อง และกระบวนการเสร็จสิ้น!

หากตัวชี้เป็น null ฉันสามารถวนซ้ำแคชย้อนหลังจากดัชนีคอลัมน์ที่ 16 จนกว่าจะพบคอลัมน์ที่แคชไว้ก่อนหน้านี้หรือไปที่รายการแรก

จากที่ใดก็ตามที่ฉันหยุด ฉันสามารถวนซ้ำไปซ้ำมาในแถวด้วยวิธีไร้เดียงสา ทีละอักขระ ทุกครั้งที่ฉันพบเครื่องหมายจุลภาค ฉันจะเก็บตัวชี้ไปที่จุดเริ่มต้นของคอลัมน์นั้นไว้ในแคชของฉัน เพื่อให้ข้อความค้นหาที่ตามมาสามารถข้ามไปตรงนั้นได้

ซึ่งหมายความว่าการเข้าถึงแบบสุ่มไปยัง 16 คอลัมน์แรกนั้นโดยทั่วไปแล้วจะไม่เสียค่าใช้จ่ายเนื่องจากจะกลายเป็นการค้นหาตัวชี้แบบตรง ซึ่งไม่รวมการเข้าถึงครั้งแรก ซึ่งก็คือO(n )

แล้วแถวที่มีมากกว่า 16 คอลัมน์ล่ะ? ฉันรู้อยู่แล้วว่าคอลัมน์ที่ 15 อยู่ที่ไหน (เริ่มจาก 0) ดังนั้นฉันจึงสามารถข้ามไปที่คอลัมน์ที่ 15 ได้เลย แล้วสลับไปมาด้วยวิธีไร้เดียงสาหลังจากนั้น ถ้าฉันไม่รู้ว่าคอลัมน์ที่ 15 อยู่ที่ไหน ฉันสามารถคำนวณและแคชได้อย่างรวดเร็ว

ค่อนข้างดี ยกเว้นมีการเพิ่มประสิทธิภาพอื่นที่สามารถทำได้ การรับรู้อีกอย่างคือภายในParseRowInstructionขณะที่สร้างแถวเอาต์พุต จะเข้าถึงคอลัมน์ตามลำดับ นอกจากแคชสุ่มขนาดคงที่สำหรับ 16 คอลัมน์แรกแล้ว เราสามารถเก็บตัวชี้เพิ่มเติมซึ่งเก็บจุดเริ่มต้นของคอลัมน์สุดท้ายที่เข้าถึง และดัชนีของคอลัมน์นั้น ซึ่งช่วยให้การค้นหาตัวชี้แบบตรงสำหรับการเข้าถึงตามลำดับสำหรับคอลัมน์จำนวนเท่าใดก็ได้ โดยไม่ต้องเก็บตัวชี้เป็นจำนวนไม่จำกัดเหมือนในระดับแรกของการแคช แน่นอนว่าเลเยอร์แคชทั้งสองนี้ทำงานร่วมกัน เมื่อเราอัปเดตค่า 16 ค่าแรก เราจะอัปเดตlast_accessedตัวชี้ด้วย

เมื่อทำงานบน GPU ทุกเธรดจะรับผิดชอบในแถวเดียว ดังนั้นทุกเธรดจึงมีแคชหลายชั้นของตัวเองตามที่อธิบายไว้ แคชยังคอยติดตามว่าเรากำลังแคชแถวไหน หากแตกต่างจากที่ร้องขอ เราจะรีเซ็ตแคช ดังนั้นเราจึงรู้ว่าแคชมีความเกี่ยวข้องเสมอ เป็นไปได้ที่จะขยายให้ครอบคลุมกรณีการใช้งานของการอ่านหลายแถวหรือแชร์แคชระหว่างเธรด แต่สิ่งนี้อยู่นอกเหนือขอบเขตของการใช้งานครั้งแรก

คำแนะนำในการฉายภาพ

ProjectionInstructionมันง่ายมากโดยการเปรียบเทียบ จะได้รับรายการของดัชนีคอลัมน์ที่จะดึงข้อมูล สร้างวัตถุ TempRow ใหม่และคัดลอกคอลัมน์เหล่านั้นจาก TempRow ล่าสุด อัปเดตข้อมูลเมตาในวัตถุ TempRow ใหม่

คำแนะนำในการกรอง

การใช้งานพื้นฐานของ the FilterInstructionได้รับการออกแบบโดยประเมินบางแถวเทียบกับบางนิพจน์ที่ส่งกลับค่าอย่างใดอย่างหนึ่งtrueหรือfalse

สิ่งนี้ถูกนำมาใช้เป็นเครื่องเสมือนแบบสแต็ค การจัดสรรสแต็กได้รับการแก้ไข ณ เวลาคอมไพล์ ดังนั้นจึงจัดสรรขนาดสูงสุดเสมอ

สแต็คค่อนข้างน่าสนใจที่จะนำไปใช้ ฉันเลือกที่จะออกแบบ bytecode สำหรับ VM เพื่อรวมประเภทและคำแนะนำในการส่งประเภทหนึ่งไปยังอีกประเภทหนึ่ง การใช้สแต็กช่วยให้ข้อมูลต่างกัน แต่ผู้โทรมีหน้าที่รับผิดชอบในการจัดหาประเภท

ในสแต็กปกติ คุณอาจสร้างกล่องสำหรับวัตถุหนึ่งๆ และกล่องจะเก็บชนิดของสิ่งนั้นไว้ รวมทั้งตัวชี้ไปยังสิ่งนั้นด้วย ในกรณีนี้ คอมไพเลอร์ (ยังไม่ได้ใช้งาน) มีหน้าที่รับผิดชอบในการเขียนโค้ดไบต์เพื่อรวมการแคสต์ทั้งหมดที่จำเป็น ซึ่งช่วยให้รันไทม์ผลักจำนวนเต็มไปยังสแต็กซึ่งเป็นxไบต์ และต่อมาเมื่อมันไปอ่านจำนวนเต็ม มันสามารถxดึงไบต์ออกจากสแต็กและได้จำนวนเต็มเดียวกัน ไม่ต้องใช้กล่องหรือการหล่อแบบไดนามิก สิ่งนี้ทำให้คอมไพเลอร์ต้องรับผิดชอบเพื่อให้ทุกประเภทถูกต้อง แต่ที่เหลือสำหรับการใช้งานในอนาคต

คำแนะนำเอาต์พุต

ใช้OutputInstructionเพื่อรวมข้อมูลทั้งหมดจากแต่ละเธรดภายใน ThreadGroup และลบข้อมูลที่ซ้ำกันทั้งหมดที่แต่ละเธรดต้องการ แต่จำเป็นต้องคัดลอกเพียงครั้งเดียวไปยัง CPU และใส่ลงในบัฟเฟอร์ขนาดใหญ่อย่างมีประสิทธิภาพ .

ขั้นตอนแรกคือทุกแถว (ทุกเธรด) คำนวณขนาดของตัวเอง จากนั้นเราจะเรียกใช้ผลรวมคำนำหน้าของขนาด สิ่งนี้ทำให้เรามีดัชนีที่เรารู้ว่าเราสามารถเริ่มเขียนข้อมูลของเราได้

ผลรวมของคำนำหน้าเป็นอัลกอริทึมที่มักใช้ในการคำนวณ GPU โดยกำหนดอาร์เรย์ของจำนวนเต็ม ส่งคืนอาร์เรย์ใหม่ที่สำหรับทุกๆ ดัชนีiมีผลรวมของรายการทั้งหมดที่น้อยกว่าi หากผลรวมรวมรายการiสำหรับตำแหน่งiจะเรียกว่าผลรวมรวม มิฉะนั้นจะเรียกว่าผลรวมพิเศษ ฉันใช้ผลรวมพิเศษสำหรับการใช้งานของฉัน

ก่อนที่เราจะเริ่มเขียนข้อมูล เธรดต้องประสานการเขียนส่วนหัวOutputRowของ ในการดำเนินการนี้ แถวแรกซึ่งรับผิดชอบในการเขียนส่วนหัวจะเพิ่มขนาดส่วนหัวตามขนาดของตัวเองด้วย หลังจากที่เราทำผลรวมของคำนำหน้าแล้ว เรายังดำเนินการลดขนาดแถวเพื่อให้เธรดแรกสามารถเขียนจำนวนไบต์ทั้งหมดไปยังส่วนหัวได้

เมื่อดำเนินการเสร็จสิ้นแล้ว แต่ละแถวสามารถข้ามไปยังออฟเซ็ตจากเอาต์พุตผลรวมของคำนำหน้า และคัดลอกไบต์ไปยังบัฟเฟอร์ที่เริ่มต้นที่จุดนั้นพร้อมกัน และเรารับประกันว่าจะไม่มีการชนกันใดๆ

TempRow

คือ โครงสร้างTempRowข้อมูลที่ส่งผ่านในขณะที่ข้อมูลกำลังประมวลผลในโลหะ ตามหลักการ แล้ว เราจะจัดสรรTempRowฮีปที่ปรับขนาดได้เพื่อลดรอยเท้าของหน่วยความจำ แต่เนื่องจาก Metal ไม่สนับสนุนการจัดสรรหน่วยความจำแบบไดนามิก ทุกTempRowเป็นบัฟเฟอร์ที่มีขนาดคงที่ ฉันเลือกให้เป็น 1024 ไบต์หรือ 1 กิโลไบต์ ส่วนแรกของTempRowเป็นส่วนหัว ตามด้วยข้อมูล

ค่าแรกในส่วนหัวคือความยาว นี่เป็นสิ่งสำคัญเนื่องจากข้อมูลเริ่มต้นทันทีหลังจากส่วนหัว และส่วนหัวมีขนาดตัวแปรขึ้นอยู่กับจำนวนของคอลัมน์และประเภทของคอลัมน์

ไบต์ถัดไปคือจำนวนคอลัมน์ เนื่องจากมีเพียง 1 ไบต์ จำนวนคอลัมน์สูงสุดคือ 256 ฉันรู้สึกว่านี่เพียงพอสำหรับกรณีการใช้งานส่วนใหญ่

N ไบต์ถัดไปคือประเภทคอลัมน์ คอลัมน์สามารถเป็นหนึ่งใน: Integer, Float, Stringหรือค่าเทียบเท่าที่เป็นโมฆะ ค่าบูลีนจะแสดงเป็นจำนวนเต็ม

จำนวนเต็มและทศนิยมมีขนาดคงที่เสมอ ดังนั้นเราจึงไม่ต้องเก็บขนาดไว้ในส่วนหัว เว้นแต่จะเป็นคอลัมน์ที่เป็นค่าว่าง ในทางตรงกันข้าม สตริงสามารถมีอักขระกี่ตัวก็ได้ ดังนั้นเราจึงเก็บขนาดของคอลัมน์ความยาวผันแปรทั้งหมด (สตริงและคอลัมน์เผื่อเลือก) ในไบต์ถัดไป เนื่องจากขนาดของคอลัมน์มีเพียง 1 ไบต์ ความยาวสูงสุดของสตริงคือ 256 อักขระ

หลังจากส่วนหัว ข้อมูลทั้งหมดสำหรับคอลัมน์จะถูกต่อท้ายทีละคอลัมน์

เพื่อให้การสร้างTempRowง่ายขึ้น มีคลาสตัวช่วยTempRowBuilderที่ผู้โทรสามารถเขียนประเภทและขนาดคอลัมน์ทั้งหมด ฯลฯ ลงในอาร์เรย์แยกกัน จากTempRowนั้นสามารถสร้างได้เล็กน้อยจากตัวสร้างโดยการคัดลอกค่า

ข้อมูลจากคอลัมน์สามารถต่อท้ายตามลำดับได้ มีเมธอดตัวช่วยที่ช่วยในการคัดลอกสตริง จำนวนเต็ม และทศนิยม และเขียนแบบไบต์ต่อไบต์

เมื่อเมธอดถัดไปอ่านTempRowจะมีเมธอดตัวช่วยที่อ่านจากเฮดเดอร์เพื่อกำหนดดัชนีเริ่มต้นและสิ้นสุดในบัฟเฟอร์สำหรับคอลัมน์นั้น และแปลงไบต์กลับเป็นประเภทที่เหมาะสม ผู้โทรมีหน้าที่สอบถามColumnTypeคอลัมน์ที่พวกเขาสนใจก่อนที่จะอ่านเป็นประเภทนั้น

เนื่องจากการTempRowอ่านข้อมูลทั้งหมดโดยตรงจากบัฟเฟอร์ขนาดคงที่ จึงสามารถปรับให้เข้ากับconstexprคลาสสำหรับแอปพลิเคชันอื่นได้เล็กน้อย

เอาต์พุตแถว

The OutputRowถูกสร้างขึ้นโดยOutputRowInstruction(อธิบายไว้ข้างต้น) และทำหน้าที่ในการย้ายหลายแถวรอบๆ ที่ใช้สคีมาเดียวกัน การคัดลอกแต่ละอ็อบเจ็กต์ทั้งหมดโดยตรงจะเป็นการสิ้นเปลืองTempRowเนื่องจากทุกแถวมีสคีมาเหมือนกัน ดังนั้นจึงมีข้อมูลเมตาที่ซ้ำกันจำนวนมาก แต่เราคัดลอกข้อมูลทั้งหมดลงในโครงสร้างเดียว เพื่อให้เราสามารถคัดลอกเป็นTempRowวัตถุแยกกันได้หากจำเป็นในภายหลัง หรือแยกออกเป็นสองOutputRowวัตถุหรือมากกว่าหากจำเป็น

คล้ายกับTempRowthe OutputRowมีคำนิยามส่วนหัวแม้ว่าจะแตกต่างจากTempRow. ค่าแรกตามที่อธิบายไว้ก่อนหน้านี้คือขนาดของส่วนหัว แต่ค่านี้มีขนาดใหญ่กว่า โดยมีการจัดสรร 2 ไบต์แทน 1 ค่าถัดไปคือจำนวนไบต์ในOutputRowและนี่คือจำนวนเต็ม 32 บิตที่ไม่ได้ลงนาม หลังจากนี้คือจำนวนคอลัมน์ และนี่เป็นเพียงหนึ่งไบต์เท่านั้น ตามด้วยประเภทคอลัมน์ คล้ายกับTempRow.

หลังจากส่วนหัว ข้อมูลทั้งหมดจะถูกต่อท้าย เนื่องจาก the OutputRowถูกสร้างขึ้นจากหนึ่งหรือมากกว่าTempRowหรือจากอีกอันหนึ่งOutputRowเสมอ เราจึงสามารถคำนวณขนาดข้อมูลของทุกแถวแบบขนานโดยใช้อัลกอริทึมผลรวมของคำนำหน้า และเขียนลงในบัฟเฟอร์ข้อมูลแบบขนาน

เมื่อทำงานใน Metal OutputRowจะมีการจัดสรรแบบสแตติกให้เป็นขนาดคงที่ 1,000,000 ไบต์ บน CPU เราสามารถทำงานได้อย่างมีประสิทธิภาพมากขึ้นและใช้ a std::vectorเพื่อจัดสรรพื้นที่เท่าที่เราต้องการเท่านั้น

เพื่อให้อ่านและเขียนเธรดOutputRowแบบขนานได้ง่ายขึ้น แทนที่จะเขียนขนาดของคอลัมน์ขนาดตัวแปรในส่วนหัวตามที่อยู่ในส่วนหัว คอลัมน์TempRowเหล่านี้จะถูกต่อท้ายข้อมูลสำหรับคอลัมน์นั้นต่อแถวแทน ตัวอย่างเช่น แถวที่มีเลขจำนวนเต็ม 2 ตัวตามด้วยสตริงอักขระ "abc" 3 ตัว จะมีรูปแบบ<integer><integer>3abcดังนี้ ตัวอ่านของOutputRow(ปัจจุบันใช้งานบน CPU เท่านั้น) รู้ว่าคอลัมน์นั้นเป็นสตริง ดังนั้นจึงสามารถข้ามไปที่จุดเริ่มต้นของสตริงเพื่ออ่านเนื้อหาได้ ขนาดของแต่ละแถวไม่ได้ถูกเขียนไปที่OutputRow. แต่เครื่องอ่านจะวนซ้ำผ่านบัฟเฟอร์และบันทึกจุดเริ่มต้นของทุกแถวและขนาดของคอลัมน์ทุกขนาดตัวแปรสำหรับทุกแถว สิ่งนี้ทำขึ้นเพื่อประหยัดพื้นที่ แต่สามารถปรับให้เหมาะสมเพื่อเขียนลงในส่วนหัวหรือต่อแถว เพื่อให้การอ่านOutputRowมีประสิทธิภาพมากขึ้นและเร็วขึ้น รายละเอียดของการอ่าน การแยก และการรวมอOutputRowอบเจกต์บน CPU ได้กล่าวถึงสั้น ๆ ก่อนหน้านี้ในหัวข้อเกี่ยวกับScheduler.

งานในอนาคต

ฉันทำงานในโครงการนี้เป็นการทดลองเพื่อดูว่าเป็นไปได้หรือไม่ มีหลายสิ่งที่ฉันอยากจะนำไปใช้ ถ้าฉันจะทำให้พร้อมสำหรับการผลิต หรือแม้แต่ใช้เวลากับต้นแบบมากกว่าที่ฉันมี

ข้อผิดพลาดนั้น

ปัญหาแรกที่ฉันอยากแก้ไขคือ (สิ่งที่ฉันเชื่อว่าเป็นข้อบกพร่องใน Xcode 13) ซึ่งมีหลายเธรดถูกกำหนดให้เป็นเธรด 0 ภายใน ThreadGroup แจ้งให้เราทราบหากคุณมีความคิดใด ๆ สิ่งนี้ทำให้หลายเธรดพยายามเขียนส่วนหัว ซึ่งส่งผลให้ส่วนหัวถูกบีบด้วยข้อมูลบางส่วน ทั้งนี้ขึ้นอยู่กับลำดับของเธรด ฉันพยายาม google เกี่ยวกับเรื่องนี้ แต่ไม่พบแหล่งข้อมูลใด ๆ ที่เป็นประโยชน์อย่างยิ่ง ฉันคิดว่ามันเกี่ยวข้องกับจำนวนหน่วยความจำที่ฉันพยายามจัดสรรให้กับแต่ละเธรด น่าเสียดายที่เอกสารอย่างเป็นทางการของ Apple ไม่ได้พูดอะไรเกี่ยวกับสิ่งที่ฉันสามารถหาได้

Query Engine + Parser

งานใหญ่ถัดไปคือการใช้โปรแกรมแยกวิเคราะห์และเอ็นจิ้นการสืบค้นเพื่อให้ฐานข้อมูลสามารถรับการสืบค้นที่คล้ายกับ SQL และเปลี่ยนเป็นแผนการสืบค้นและดำเนินการได้ งานนี้เกี่ยวข้องกับการใช้ DataFrame API หรือการเขียนในหลายรูปแบบไปยังดิสก์ เพื่อให้ใช้โดยไลบรารีและโปรแกรมอื่นๆ

เข้าร่วม + กลุ่มโดย

การขยายข้อมูลจำเพาะของ SQL เป็นเรื่องสนุกที่จะสามารถคำนวณการรวมและ Group By clause ฉันคิดว่าวิธีที่ไร้เดียงสาในการใช้การรวมคือการคำนวณแถวดิบแต่ละแถวบน GPU ในแบบคู่ขนาน จากนั้นทำแฮชเข้าร่วมบน CPU หนึ่งครั้งต่อ chunk อย่างไรก็ตาม การหาวิธีส่งหนึ่งอันจากตารางที่แตกต่างกัน 2 ตารางที่คุณต้องการเข้าร่วมพร้อมกันอาจมีประสิทธิภาพมากกว่า และให้ GPU ส่งคืนแถวที่รวมกัน

สำหรับ Group By คุณสามารถทำได้บน CPU หรืออาจทำการรวมบางส่วนบน GPU หรือคุณสามารถทำการผสมผสานโดยที่คุณทำการประมวลผลดิบเริ่มต้นบน GPU แล้วมีเคอร์เนลอื่นที่คุณดำเนินการโดยกำหนดชุดของแถว คำนวณกลุ่มสำหรับแต่ละแถวภายในชุด ซึ่งจะช่วยให้คุณสามารถฝากข้อมูลแถวบน CPU ได้อย่างรวดเร็ว ซึ่งคุณสามารถจัดสรรข้อมูลได้มากขึ้นเพื่อเก็บแถว ในขณะที่ใช้ประโยชน์จากธรรมชาติแบบคู่ขนานของ GPU เพื่อคำนวณกลุ่มแบบขนาน

ระบบกระจาย

หากจะนำระบบนี้ไปใช้ในการผลิต มีแนวโน้มว่าจะต้องสามารถใช้ประโยชน์จากเครื่องจักรหลายเครื่องได้ ฉันสามารถจินตนาการถึงเครือข่ายที่แตกต่างกันของอุปกรณ์ที่เชื่อมต่อของ Apple (และไม่ใช่ของ Apple) ที่ทำงานร่วมกัน ลองนึกภาพ iPhone เป็นตัวควบคุมโฮสต์ที่ส่งคำสั่งไปยังเครื่องอื่นๆ และกลุ่มของ iPad ที่แต่ละเครื่องทำการประมวลผลข้อมูลที่มีอยู่ในเครื่องและส่งแถวที่ประมวลผลกลับไปยังตัวควบคุมกลาง อีกทางหนึ่ง คุณอาจปรับใช้ระบบคลาวด์ที่รันโค้ดเดียวกันบน CPU ในอินสแตนซ์แลมบ์ดา AWS หรือข้าม GPU หลายตัวด้วยเซิร์ฟเวอร์ Mac Pro ในองค์กร ระบบทั้งหมดเหล่านี้สามารถทำงานร่วมกันเพื่อให้คุณเข้าถึงชุดข้อมูลขนาดใหญ่ได้อย่างรวดเร็วด้วยอุปกรณ์ที่ (ฉันรู้สึก) มีพลังในการประมวลผลที่ยังไม่ได้ใช้อยู่มาก

ลดรอยเท้าหน่วยความจำ

เป็นการเพิ่มประสิทธิภาพอื่น โดยเฉพาะอย่างยิ่งเมื่อฉันต้องการให้สิ่งนี้ทำงานบนอุปกรณ์ใด ๆ ที่ใช้ Metal มันจะเป็นการดีที่จะรักษารอยเท้าของหน่วยความจำให้เล็กที่สุดเท่าที่จะเป็นไปได้ เพื่อที่เราจะสามารถเพิ่มทรัพยากรบนอุปกรณ์ให้สูงสุดสำหรับแอปพลิเคชันของผู้ใช้ปลายทางที่กำลังทำงานอยู่ . ตามหลักการแล้ว เราควรจะสามารถอ่านไฟล์ก้อนหนึ่งจากดิสก์ไปยังหน่วยความจำ เปลี่ยนเป็นบัฟเฟอร์เพื่อส่งไปยัง GPU แล้วจึงปล่อยหน่วยความจำก้อนนั้น ฉันพยายามออกแบบระบบด้วยวิธีนั้นโดยใช้shared_ptrเพื่อให้ฉันมีระบบการจัดสรรหน่วยความจำแบบนับอ้างอิงสำหรับบัฟเฟอร์ อย่างไรก็ตาม ในทางปฏิบัติฉันพบว่าเนื่องจากไลบรารีงานที่ฉันใช้ไม่รู้ว่าจำเป็นต้องรันกราฟงานซ้ำด้วยอินพุตหลายตัวหรือไม่ ไลบรารีจึงไม่ทำให้แลมบ์ดาจับการอ้างอิงไปยังบัฟเฟอร์ว่าง ซึ่งหมายความว่าshared_ptrที่ถูกจับโดยแลมบ์ดายังคงถูกอ้างอิง ดังนั้นจึงไม่เพิ่มหน่วยความจำจนกว่ากราฟงานจะถูกทำลาย ซึ่งจะเกิดขึ้นก็ต่อเมื่อกราฟทั้งหมดเสร็จสิ้นการดำเนินการ

บทสรุป

โดยรวมแล้วฉันสนุกกับการทำงานและคิดเกี่ยวกับโครงการนี้มาก มันแตกต่างจากโครงการอื่น ๆ ที่ฉันเคยทำมามาก ฉันหวังว่าคุณจะสนุกกับการอ่านบทความนี้ การใช้งานทั้งหมดของฉันมีการเชื่อมโยงที่ด้านบนของบทความนี้ หากคุณมีความคิดเห็นหรือแนวคิดเกี่ยวกับสิ่งที่คุณชอบหรือจะทำแตกต่างออกไป โปรดอย่าลังเลที่จะติดต่อฉัน ขอบคุณ!