วิธีที่ Roblox ลดต้นทุนการค้นหา Spark Join ด้วย Bloom Filters ที่ปรับให้เหมาะสมด้วย Machine Learning

บทคัดย่อ

ทุกวันบน Roblox มีผู้ใช้ 70 ล้านคนที่มีส่วนร่วมกับประสบการณ์นับล้านครั้ง รวมเป็นเวลา 16,000 ล้านชั่วโมงต่อไตรมาส การปฏิสัมพันธ์นี้สร้างแหล่งข้อมูลขนาดใหญ่ระดับเพตะไบต์ ซึ่งถูกเสริมสร้างเพื่อวัตถุประสงค์ในการวิเคราะห์และแมชชีนเลิร์นนิง (ML) การรวมตารางข้อเท็จจริงและตารางมิติในแหล่งข้อมูลของเราต้องใช้ทรัพยากรมาก ดังนั้นเพื่อเพิ่มประสิทธิภาพและลดการสับเปลี่ยนข้อมูล เราจึงใช้ Learned Bloom Filters [1] ซึ่งเป็นโครงสร้างข้อมูลอัจฉริยะที่ใช้ ML โดยการคาดการณ์การมีอยู่ ฟิลเตอร์เหล่านี้ช่วยลดข้อมูลการเชื่อมต่อได้อย่างมาก ซึ่งช่วยเพิ่มประสิทธิภาพและลดต้นทุน ในระหว่างนี้ เรายังได้ปรับปรุงสถาปัตยกรรมของโมเดลของเราและแสดงให้เห็นถึงประโยชน์ที่สำคัญที่มันมอบให้ในการลดหน่วยความจำและชั่วโมง CPU สำหรับการประมวลผล รวมถึงเพิ่มความเสถียรในการดำเนินงาน

บทนำ

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

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

เพิ่มประสิทธิภาพการเข้าร่วมด้วยตัวกรองบลูมที่เรียนรู้

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

วิวัฒนาการจากฟิลเตอร์บลูมแบบดั้งเดิมสู่ฟิลเตอร์บลูมแบบเรียนรู้

แม้ว่า Bloom Filter แบบดั้งเดิมจะมีประสิทธิภาพ แต่จะเพิ่มหน่วยความจำเพิ่มเติม 15-25% ต่อโหนดเวิร์กเกอร์ที่ต้องโหลดเพื่อให้ได้อัตราความผิดพลาดบวก (false positive) ตามที่ต้องการ แต่ด้วยการนำ Learned Bloom Filters มาใช้ เราสามารถลดขนาดดัชนีได้อย่างมากในขณะที่ยังคงรักษาอัตราความผิดพลาดบวกเท่าเดิมได้ นี่เป็นเพราะการเปลี่ยนแปลง Bloom Filter ให้เป็นปัญหาการจำแนกประเภทแบบไบนารี ป้ายกำกับบวกบ่งบอกถึงการมีอยู่ของค่าในดัชนี ในขณะที่ป้ายกำกับลบหมายถึงไม่มีค่าดังกล่าว

การนำโมเดล ML มาใช้ช่วยให้การตรวจสอบค่าเบื้องต้นเป็นไปอย่างง่ายดาย จากนั้นจึงใช้ Bloom Filter สำรองเพื่อกำจัดค่าที่ตรวจไม่พบโดยผิดพลาด (false negatives) ขนาดที่ลดลงเกิดจากการแสดงผลที่บีบอัดของโมเดลและจำนวนคีย์ที่น้อยลงซึ่ง Bloom Filter สำรองต้องการ สิ่งนี้ทำให้แตกต่างจากวิธีการ Bloom Filter แบบดั้งเดิม 

เป็นส่วนหนึ่งของงานนี้ เราได้กำหนดตัวชี้วัดสองตัวเพื่อประเมินแนวทาง Learned Bloom Filter ของเรา: ขนาดวัตถุที่ถูกซีเรียลไลซ์สุดท้ายของดัชนี และการใช้ CPU ระหว่างการดำเนินการของคำสั่ง join 

การรับมือกับความท้าทายในการดำเนินการ

ความท้าทายแรกของเราคือการจัดการกับชุดข้อมูลฝึกอบรมที่มีอคติสูงและมีคีย์ตารางมิติในตารางข้อเท็จจริงน้อย ในการดำเนินการดังกล่าว เราสังเกตเห็นการทับซ้อนของคีย์ประมาณหนึ่งในสามระหว่างตาราง เพื่อแก้ไขปัญหานี้ เราได้ใช้แนวทาง Sandwich Learned Bloom Filter [2] ซึ่งผสาน Bloom Filter แบบดั้งเดิมเพื่อปรับสมดุลการกระจายของชุดข้อมูลโดยการลบคีย์ส่วนใหญ่ที่หายไปจากตารางข้อเท็จจริงออก ซึ่งช่วยกำจัดตัวอย่างเชิงลบออกจากชุดข้อมูลได้อย่างมีประสิทธิภาพ จากนั้น เฉพาะคีย์ที่รวมอยู่ใน Bloom Filter เริ่มต้น พร้อมกับค่าบวกที่ผิดพลาดเท่านั้นที่ถูกส่งต่อไปยังโมเดล ML ซึ่งมักเรียกว่า "ออราเคิลที่เรียนรู้" วิธีการนี้ส่งผลให้ชุดข้อมูลการฝึกอบรมสำหรับออราเคิลที่เรียนรู้มีความสมดุลที่ดี แก้ไขปัญหาความลำเอียงได้อย่างมีประสิทธิภาพ

ความท้าทายประการที่สองมุ่งเน้นไปที่สถาปัตยกรรมของโมเดลและคุณสมบัติการฝึกอบรม ซึ่งแตกต่างจากปัญหาคลาสสิกของ URL ฟิชชิ่ง [1] คีย์การรวมของเรา (ซึ่งในกรณีส่วนใหญ่เป็นตัวระบุเฉพาะสำหรับผู้ใช้/ประสบการณ์) ไม่ได้ให้ข้อมูลโดยธรรมชาติ สิ่งนี้ทำให้เราสำรวจคุณลักษณะของมิติต่างๆ ในฐานะคุณสมบัติของโมเดลที่อาจช่วยทำนายได้ว่ามีเอนทิตีมิติอยู่ในตารางข้อเท็จจริงหรือไม่ ตัวอย่างเช่น จินตนาการถึงตารางข้อเท็จจริงที่มีข้อมูลเซสชั่นของผู้ใช้สำหรับประสบการณ์ในภาษาที่เฉพาะเจาะจง คุณสมบัติของตำแหน่งทางภูมิศาสตร์หรือความชอบทางภาษาของมิติผู้ใช้จะเป็นตัวบ่งชี้ที่ดีว่าผู้ใช้แต่ละคนอยู่ในตารางข้อเท็จจริงหรือไม่

ความท้าทายที่สาม—ความล่าช้าในการอนุมาน—ต้องการโมเดลที่สามารถลดข้อผิดพลาดในการตรวจไม่พบ (false negatives) และให้การตอบสนองอย่างรวดเร็วได้พร้อมกัน โมเดลต้นไม้ที่ได้รับการเสริมด้วยค่าความชัน (gradient-boosted tree model) เป็นตัวเลือกที่เหมาะสมที่สุดสำหรับตัวชี้วัดหลักเหล่านี้ และเราได้ทำการตัดแต่งชุดคุณลักษณะของโมเดลเพื่อสร้างสมดุลระหว่างความแม่นยำและความเร็ว

การปรับปรุงคำค้นหาการเข้าร่วมของเราโดยใช้ Bloom Filters ที่เรียนรู้แล้วแสดงดังต่อไปนี้:

ผลลัพธ์

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

การเปรียบเทียบขนาดของ Bloom Filter ที่ผ่านการเรียนรู้

ดังแสดงด้านล่าง เมื่อพิจารณาอัตราผลบวกลวงที่กำหนดไว้ ตัวแปรทั้งสองของ Bloom Filter ที่เรียนรู้สามารถปรับปรุงขนาดวัตถุทั้งหมดได้ระหว่าง 17-42% เมื่อเทียบกับ Bloom Filter แบบดั้งเดิม

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

ผลลัพธ์การใช้งาน Bloom Filter ที่เรียนรู้ 

ในส่วนนี้ เราจะเปรียบเทียบประสิทธิภาพของการรวมข้อมูลโดยใช้ Bloom Filter กับการรวมข้อมูลแบบปกติในหลายตัวชี้วัด 

ตารางด้านล่างเปรียบเทียบประสิทธิภาพของงานที่มีและไม่มีการใช้ Learned Bloom Filters โดย Learned Bloom Filter ที่มีโอกาสผิดพลาดบวกทั้งหมด 1% แสดงการเปรียบเทียบด้านล่างนี้ในขณะที่ยังคงการกำหนดค่าคลัสเตอร์เดียวกันสำหรับทั้งสองประเภทของการรวมข้อมูล 

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

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

เรายังพบว่าการใช้ทรัพยากรลดลงในปริมาณงานการผลิตอื่นๆ ที่อยู่ระหว่างการทดลองเช่นกัน ตลอดระยะเวลาสองสัปดาห์ในทั้งห้าปริมาณงาน วิธีการ Learned Bloom Filter ช่วยประหยัดค่าใช้จ่ายเฉลี่ยต่อวันได้ 25% ซึ่งรวมถึงการฝึกอบรมโมเดลและการสร้างดัชนีด้วย

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

เอกสารอ้างอิง

[1] ที. ครัสกา, เอ. เบอเทิล, อี. เอช. ชิ, เจ. ดีน, และ เอ็น. โพลิโซติส. กรณีศึกษาสำหรับโครงสร้างดัชนีที่เรียนรู้ได้. https://arxiv.org/abs/1712.01208, 2017.

[2] เอ็ม. มิทเซนมาเคอร์. การเพิ่มประสิทธิภาพของฟิลเตอร์บลูมที่เรียนรู้โดยการแซนวิช. 

https://arxiv.org/abs/1803.01474, 2018.

¹ณ วันที่ 30 มิถุนายน 2566

²ณ วันที่ 30 มิถุนายน 2566