หน้านี้จะแสดงภาพรวมระดับสูงของปัญหาและข้อจํากัดเฉพาะในการเขียนกฎ Bazel ที่มีประสิทธิภาพ
ข้อกำหนดในการสรุป
- สมมติฐาน: มุ่งเน้นความถูกต้อง อัตราการส่งข้อมูล การใช้งานง่าย และ เวลาในการตอบสนอง
- สมมติฐาน: ที่เก็บข้อมูลขนาดใหญ่
- สมมติฐาน: ภาษาคำอธิบายเหมือนกับ BUILD
- ข้อมูลย้อนหลัง: การแยกการโหลด การวิเคราะห์ และการดำเนินการออกจากกันอย่างชัดเจนนั้นล้าสมัยแล้ว แต่ยังส่งผลต่อ API
- ปัจจัยภายใน: การดำเนินการจากระยะไกลและการแคชเป็นเรื่องยาก
- Intrinsic: การใช้ข้อมูลการเปลี่ยนแปลงเพื่อสร้างส่วนเพิ่มที่ถูกต้องและรวดเร็ว ต้องใช้รูปแบบการเขียนโค้ดที่ผิดปกติ
- ปัจจัยภายใน: การหลีกเลี่ยงเวลาและการใช้หน่วยความจําแบบสี่เหลี่ยมจัตุรัสนั้นทําได้ยาก
สมมติฐาน
ต่อไปนี้คือข้อสันนิษฐานบางอย่างเกี่ยวกับระบบบิลด์ เช่น ความต้องการความถูกต้อง ความง่ายในการใช้งาน ปริมาณงาน และที่เก็บข้อมูลขนาดใหญ่ ส่วนต่อไปนี้จะกล่าวถึงสมมติฐานเหล่านี้และหลักเกณฑ์เกี่ยวกับข้อเสนอ และเขียนกฎอย่างมีประสิทธิภาพ
มุ่งเน้นที่ความถูกต้อง อัตราการส่งข้อมูล ความสะดวกในการใช้งาน และเวลาในการตอบสนอง
เราคิดว่าระบบบิลด์จำเป็นต้องมีความถูกต้องเป็นอย่างแรกและสำคัญที่สุดกับ เกี่ยวกับบิลด์ที่เพิ่มขึ้น สําหรับต้นไม้ต้นทางหนึ่งๆ เอาต์พุตของบิลด์เดียวกันควรเหมือนกันเสมอ ไม่ว่าต้นไม้เอาต์พุตจะมีลักษณะเป็นอย่างไร การประมาณครั้งแรกหมายความว่า Bazel จำเป็นต้องทราบ ที่อยู่ในขั้นตอนบิลด์ที่กำหนด เพื่อให้เรียกใช้ขั้นตอนนั้นอีกครั้งได้หากมี อินพุตจะเปลี่ยนไป ความถูกต้องของ Bazel มีข้อจำกัดเนื่องจากมีการรั่วไหลข้อมูลบางอย่าง เช่น วันที่/เวลาของบิลด์ และละเว้นการเปลี่ยนแปลงบางประเภท เช่น การเปลี่ยนแปลงแอตทริบิวต์ไฟล์ แซนด์บ็อกซ์ ช่วยให้มั่นใจว่าถูกต้องโดยป้องกันการอ่านไฟล์อินพุตที่ไม่ได้ประกาศ นอกจากข้อจำกัดโดยเนื้อแท้ของระบบแล้ว ยังมีปัญหาความถูกต้องที่ทราบอยู่ 2-3 ข้อ ซึ่งส่วนใหญ่เกี่ยวข้องกับชุดไฟล์หรือกฎ C++ ซึ่งเป็นปัญหาที่แก้ได้ยาก เรามีความพยายามในระยะยาวที่จะแก้ไขปัญหานี้
เป้าหมายที่ 2 ของระบบบิลด์คือการมีอัตราผ่านข้อมูลสูง เราพยายามขยายขีดความสามารถของสิ่งที่ทำได้ภายในการจัดสรรเครื่องปัจจุบันสำหรับบริการการเรียกใช้จากระยะไกลอยู่เสมอ หากบริการการเรียกใช้จากระยะไกลมีการใช้งานมากเกินไป ทุกคนจะทำงานไม่ได้
ถัดมาคือความสะดวกในการใช้งาน ของวิธีการที่ถูกต้องหลายแนวทาง โดยใช้ (หรือ คล้ายกัน) ของบริการดำเนินการระยะไกล เราจะเลือกรายการที่เป็น ใช้งานง่ายขึ้น
เวลาในการตอบสนองหมายถึงเวลาที่ใช้ในการเริ่มสร้างจนถึงได้ผลลัพธ์ที่ต้องการ ไม่ว่าจะเป็นบันทึกการทดสอบจากการทดสอบที่ผ่านหรือไม่ผ่าน หรือข้อความแสดงข้อผิดพลาดที่ไฟล์ BUILD มีการพิมพ์ผิด
โปรดทราบว่าเป้าหมายเหล่านี้มักจะทับซ้อนกัน เวลาในการตอบสนองคือฟังก์ชันของอัตราการส่งข้อมูล ของบริการดำเนินการจากระยะไกลได้ตามความถูกต้องที่เกี่ยวข้องเพื่อให้ใช้งานได้ง่าย
ที่เก็บขนาดใหญ่
ระบบบิลด์ต้องทำงานตามระดับของที่เก็บขนาดใหญ่ซึ่ง
หมายความว่า ขนาดไม่พอดีกับฮาร์ดไดรฟ์หนึ่งๆ ดังนั้นจึงเป็นไปไม่ได้ที่จะ
ชำระเงินเต็มจำนวนบนเครื่องสำหรับนักพัฒนาซอฟต์แวร์เกือบทั้งหมด บิลด์ขนาดกลางจะต้องอ่านและแยกวิเคราะห์ไฟล์ BUILD หลายหมื่นไฟล์ และประเมินการจับคู่แบบทั่วไปหลายแสนรายการ แม้ว่าในทางทฤษฎีจะเป็นไปได้ที่จะอ่านทั้งหมด
BUILD ไฟล์ในเครื่องเดียว เรายังไม่สามารถทำเช่นนั้นได้ภายใน
ระยะเวลาและหน่วยความจำที่เหมาะสม ด้วยเหตุนี้ ไฟล์ BUILD จึงมีความสำคัญ
สามารถโหลดและแยกวิเคราะห์แยกจากกันได้
ภาษาคำอธิบายที่คล้ายกับ BUILD
ในบริบทนี้ เราจะใช้ภาษาการกำหนดค่า
คล้ายกับไฟล์ BUILD ในการประกาศกฎไลบรารีและกฎไบนารี
และการพึ่งพาอาศัยกัน ไฟล์ BUILD สามารถอ่านและแยกวิเคราะห์ได้อย่างอิสระ และเราจะไม่ดูไฟล์ต้นฉบับเลยหากเป็นไปได้ (ยกเว้นเพื่อตรวจสอบว่ามีไฟล์อยู่หรือไม่)
ประวัติศาสตร์
เวอร์ชัน Bazel แต่ละเวอร์ชันมีความแตกต่างกันซึ่งทำให้เกิดปัญหา ซึ่งปัญหาบางส่วนจะระบุไว้ในส่วนต่อไปนี้
การแยกการโหลด การวิเคราะห์ และการดำเนินการออกจากกันอย่างชัดเจนนั้นล้าสมัยแล้ว แต่ยังส่งผลต่อ API
ในทางเทคนิค กฎเพื่อให้ทราบไฟล์อินพุตและเอาต์พุตของ การดำเนินการก่อนที่จะส่งการดำเนินการไปยังการดำเนินการจากระยะไกล อย่างไรก็ตาม ฐานโค้ด Bazel เดิมมีการแบ่งแยกแพ็กเกจการโหลดอย่างเคร่งครัด วิเคราะห์กฎโดยใช้การกำหนดค่า (หลักๆ แล้วแฟล็กบรรทัดคำสั่ง) และ จากนั้นจึงเรียกใช้การดำเนินการต่างๆ เท่านั้น ความแตกต่างนี้ยังคงเป็นส่วนหนึ่งของ API กฎในปัจจุบัน แม้ว่าส่วนหลักของ Bazel จะไม่ต้องใช้อีกต่อไป (ดูรายละเอียดเพิ่มเติมด้านล่าง)
ซึ่งหมายความว่า API ของกฎต้องมีคำอธิบายกฎอย่างชัดเจน ของอินเทอร์เฟซ (แอตทริบิวต์ที่มี ประเภทของแอตทริบิวต์) แต่มีข้อยกเว้นบางประการที่ API อนุญาตให้โค้ดที่กำหนดเองทำงานในระยะการโหลดเพื่อคํานวณชื่อไฟล์เอาต์พุตและค่าแอตทริบิวต์โดยนัย ตัวอย่างเช่น กฎ java_library ที่มีชื่อว่า "foo" จะสร้างเอาต์พุตชื่อ "libfoo.jar" โดยปริยาย ซึ่งสามารถอ้างอิงจากกฎอื่นๆ ในกราฟการบิลด์ได้
นอกจากนี้ การวิเคราะห์กฎจะอ่านไฟล์ต้นทางหรือตรวจสอบเอาต์พุตของการดำเนินการไม่ได้ แต่จะต้องสร้างกราฟแบบ 2 กลุ่มที่มีทิศทางบางส่วนของขั้นตอนการสร้างและชื่อไฟล์เอาต์พุตที่กําหนดจากกฎเองและข้อกําหนดของกฎเท่านั้น
Intrinsic
มีคุณสมบัติเฉพาะบางอย่างที่ทำให้กฎการเขียนเป็นเรื่องที่ท้าทายและ โดยวิธีดำเนินการที่พบบ่อยที่สุดบางส่วนได้อธิบายไว้ในส่วนต่อไปนี้
การดำเนินการและการแคชระยะไกลนั้นทำได้ยาก
การดำเนินการและการแคชจากระยะไกลช่วยปรับปรุงเวลาบิลด์ในที่เก็บขนาดใหญ่ด้วย ขนาดประมาณ 2 ลำดับเมื่อเทียบกับการเรียกใช้บิลด์บน อุปกรณ์ อย่างไรก็ตาม ปริมาณงานที่จำเป็นต้องดำเนินการนั้นกลับลดลงอย่างมาก: บริการดำเนินการระยะไกลออกแบบมาเพื่อรองรับคำขอจำนวนมหาศาลต่อ อย่างที่สอง และโปรโตคอลจะหลีกเลี่ยงการไป-กลับที่ไม่จำเป็นอย่างรอบคอบ รวมถึง ในด้านบริการโดยไม่จำเป็น
ในขณะนี้ โปรโตคอลต้องการให้ระบบบิลด์รู้อินพุตทั้งหมด การดำเนินการล่วงหน้า ระบบบิลด์จะคำนวณการกระทำที่ไม่ซ้ำ ลายนิ้วมือ และขอให้เครื่องจัดตารางเวลาพบแคช หากพบรายการที่ตรงกันในแคช ตัวจัดเวลาจะตอบกลับด้วยข้อมูลสรุปของไฟล์เอาต์พุต โดยระบบจะจัดการไฟล์ด้วยข้อมูลสรุปในภายหลัง อย่างไรก็ตาม วิธีนี้กำหนดข้อจำกัดสำหรับ Bazel ที่ต้องประกาศไฟล์อินพุตทั้งหมดล่วงหน้า
การใช้ข้อมูลการเปลี่ยนแปลงสำหรับบิลด์ที่เพิ่มขึ้นอย่างถูกต้องและรวดเร็วต้องใช้รูปแบบการเขียนโค้ดที่ผิดปกติ
ด้านบน เราโต้แย้งว่าเพื่อความถูกต้อง Bazel จำเป็นต้องรู้ข้อมูลทั้งหมด ที่เข้าสู่ขั้นตอนบิลด์เพื่อตรวจสอบว่าขั้นตอนบิลด์นั้น ยังคงทันสมัย เช่นเดียวกันสำหรับการโหลดแพ็กเกจและการวิเคราะห์กฎ และเรา ได้ออกแบบ Skyframe เพื่อจัดการกับเรื่องนี้ โดยทั่วไป Skyframe คือไลบรารีกราฟและกรอบการประเมินที่ โหนดเป้าหมาย (เช่น "สร้าง //foo ด้วยตัวเลือกเหล่านี้") และแบ่งโหนดเป็น ส่วนประกอบต่างๆ ของ Google Analytics ซึ่งจะมีการประเมินและรวมเข้าด้วยกันเพื่อทำให้เกิด ผลลัพธ์ ในกระบวนการนี้ Skyframe จะอ่านแพ็กเกจ วิเคราะห์กฎ และดำเนินการ
ที่แต่ละโหนด Skyframe จะติดตามว่าโหนดใดใช้โหนดใดในการคํานวณเอาต์พุตของตนเอง ตั้งแต่โหนดเป้าหมายไปจนถึงไฟล์อินพุต (ซึ่งเป็นโหนด Skyframe ด้วย) การแสดงกราฟนี้ในหน่วยความจำอย่างชัดเจน ช่วยให้ระบบบิลด์สามารถระบุโหนดที่ได้รับผลกระทบจาก การเปลี่ยนแปลงไฟล์อินพุต (รวมถึงการสร้างหรือการลบไฟล์อินพุต) การดำเนินการ จำนวนงานน้อยที่สุดในการกู้คืนโครงสร้างเอาต์พุตให้กลับสู่สถานะที่ต้องการ
โหนดแต่ละโหนดจะดำเนินการตามกระบวนการค้นหาทรัพยากรที่เกี่ยวข้อง โหนดแต่ละโหนดสามารถประกาศทรัพยากร Dependency จากนั้นใช้เนื้อหาของทรัพยากร Dependency เหล่านั้นเพื่อประกาศทรัพยากร Dependency เพิ่มเติมได้ โดยหลักการแล้ว รูปแบบนี้จะเหมาะกับรูปแบบเธรดต่อโหนด อย่างไรก็ตาม งานสร้างขนาดกลางประกอบด้วย โหนด Skyframe หลายพันโหนด ซึ่งทำได้ยากเมื่อใช้ Java ในปัจจุบัน เทคโนโลยี (และด้วยเหตุผลทางประวัติศาสตร์ ปัจจุบันเรายึดมั่นอยู่กับการใช้ Java ดังนั้น ไม่มีชุดข้อความที่เรียบง่ายและไม่มีความต่อเนื่อง)
แต่ Bazel จะใช้ Thread Pool ที่มีขนาดคงที่แทน อย่างไรก็ตาม นั่นหมายความว่าหากโหนดประกาศทรัพยากร Dependency ที่ยังไม่พร้อมใช้งาน เราอาจต้องยกเลิกการประเมินนั้นและเริ่มใหม่ (อาจในอีกเธรดหนึ่ง) เมื่อทรัพยากร Dependency พร้อมใช้งาน นั่นหมายความว่าโหนดต่างๆ ไม่ควรทำสิ่งนี้มากเกินไป CANNOT TRANSLATE โหนดที่ประกาศทรัพยากร Dependency แบบอนุกรมสามารถรีสตาร์ทได้ N ครั้ง ซึ่งทำให้เสียเวลา O(N^2) แต่เราตั้งเป้าที่จะประกาศ ทรัพยากร Dependency ซึ่งบางครั้งก็ต้องมีการจัดระเบียบโค้ดใหม่ หรือแม้แต่การแยก หนึ่งโหนดลงในหลายโหนดเพื่อจำกัดจำนวนการรีสตาร์ท
โปรดทราบว่าเทคโนโลยีนี้ยังไม่พร้อมใช้งานในกฎ API ในขณะนี้ แทน กฎ API ยังคงได้รับการกำหนดโดยใช้แนวคิดเดิมเกี่ยวกับการโหลด การวิเคราะห์ และการดำเนินการ อย่างไรก็ตาม ข้อจํากัดพื้นฐานคือ การเข้าถึงโหนดอื่นๆ ทั้งหมดต้องผ่านเฟรมเวิร์กเพื่อให้ติดตามการพึ่งพาที่เกี่ยวข้องได้ ไม่ว่าระบบบิลด์จะใช้ภาษาใดก็ตาม ถูกนำไปใช้ หรือมีการระบุกฎ (กฎที่ว่าไม่จำเป็นต้องเป็น เดียวกัน) ผู้เขียนกฎต้องไม่ใช้ไลบรารีมาตรฐานหรือรูปแบบที่ข้าม Skyframe สําหรับ Java หมายความว่าให้หลีกเลี่ยง java.io.File รวมถึงการสะท้อนกลับทุกรูปแบบและไลบรารีใดก็ตามที่ทําเช่นนั้น ไลบรารีที่รองรับการแทรกพึ่งพาอินเทอร์เฟซระดับต่ำเหล่านี้ยังคงต้องตั้งค่าอย่างถูกต้องสำหรับ Skyframe
เราขอแนะนําอย่างยิ่งให้หลีกเลี่ยงการแสดงรันไทม์ภาษาแบบสมบูรณ์ต่อผู้เขียนกฎตั้งแต่แรก อันตรายของการใช้ API ดังกล่าวโดยไม่ตั้งใจนั้นมากเกินไป ข้อบกพร่องของ Bazel หลายรายการในอดีตเกิดจากกฎที่ใช้ API ที่ไม่ปลอดภัย แม้ว่ากฎจะเขียนโดยทีม Bazel หรือผู้เชี่ยวชาญด้านโดเมนอื่นๆ
การหลีกเลี่ยงเวลาและการใช้หน่วยความจําแบบ 2 เท่านั้นทําได้ยาก
ปัญหายิ่งแย่ลงเมื่อ Skyframe มีข้อกำหนดเพิ่มเติม การใช้ Java มีข้อจำกัดมาอย่างยาวนาน และ Rules API ล้าสมัย การนำเวลาหรือการใช้หน่วยความจำแบบกำลังสองมาใช้โดยไม่ตั้งใจเป็นปัญหาพื้นฐานในระบบการสร้างทุกระบบที่ใช้กฎของไลบรารีและไบนารี มี 2 แบบ รูปแบบที่พบได้ทั่วไปซึ่งทำให้เกิดการใช้หน่วยความจำกำลังสอง (ดังนั้น เวลาที่ใช้กำลังสอง)
กลุ่มกฎห้องสมุด - ลองพิจารณากรณีของเชนกฎไลบรารี A ขึ้นอยู่กับ B ขึ้นอยู่กับ C และ เป็นต้น จากนั้น เราต้องการคำนวณทรัพย์สินบางส่วนจากการปิดทางอ้อมของ กฎเหล่านี้ เช่น คลาสพาธรันไทม์ของ Java หรือคำสั่ง C++ Linker สำหรับ ห้องสมุดแต่ละแห่ง อย่างไรก็ดี เราอาจใช้รายการมาตรฐาน อย่างไรก็ตาม มีการใช้หน่วยความจำกำลังสองแล้ว: ไลบรารีแรก มีรายการ 1 รายการในคลาสพาธ รายการที่ 2 รายการที่ 3 และ 3 รายการตามลำดับ เปิด รวมแล้วเป็นจำนวน 1+2+3+...+N = O(N^2) รายการ
กฎไบนารีที่ขึ้นอยู่กับกฎไลบรารีเดียวกัน - ให้พิจารณากรณีที่ชุดไบนารีขึ้นอยู่กับกฎไลบรารีเดียวกัน เช่น หากคุณมีกฎทดสอบหลายรายการที่ทดสอบโค้ดไลบรารีเดียวกัน สมมติว่าจากกฎ N ข้อ กฎครึ่งหนึ่งเป็นกฎไบนารี และ กฎอีกครึ่งหนึ่งของไลบรารี ตอนนี้ให้พิจารณาว่าไบนารีแต่ละรายการจะสร้างสำเนาของพร็อพเพอร์ตี้บางอย่างที่คำนวณจากกฎของไลบรารีแบบทรานซิทีฟ โคลซ เช่น เส้นทางคลาสรันไทม์ของ Java หรือบรรทัดคำสั่งของโปรแกรมเชื่อมโยง C++ เช่น การดำเนินการนี้อาจขยายการแสดงสตริงบรรทัดคำสั่งของการดำเนินการลิงก์ C++ N/2 สำเนาขององค์ประกอบ N/2 ใช้หน่วยความจำ O(N^2)
คลาสคอลเล็กชันที่กำหนดเองเพื่อหลีกเลี่ยงความซับซ้อนของกำลังสอง
Bazel ได้รับผลกระทบอย่างมากจากทั้ง 2 สถานการณ์นี้ เราจึงเปิดตัวชุดคลาสคอลเล็กชันที่กำหนดเองซึ่งบีบอัดข้อมูลในหน่วยความจำได้อย่างมีประสิทธิภาพด้วยการหลีกเลี่ยงการคัดลอกในแต่ละขั้นตอน โครงสร้างข้อมูลเกือบทั้งหมดเหล่านี้ได้ตั้ง
เราเรียกมันว่า
depset
(หรือที่เรียกว่า NestedSet ในการใช้งานภายใน) ส่วนใหญ่ของ
การเปลี่ยนแปลงเพื่อลดการใช้หน่วยความจำของ Bazel ในช่วงหลายปีที่ผ่านมา
เปลี่ยนมาใช้ค่ากำหนดแทนสิ่งที่ใช้ก่อนหน้านี้
อย่างไรก็ตาม การใช้ Depset ไม่ได้ช่วยแก้ปัญหาทั้งหมดโดยอัตโนมัติ โดยเฉพาะอย่างยิ่ง แม้กระทั่งการทำซ้ำในช่วงหนึ่งของกฎแต่ละข้อ เวลาที่ใช้กำลังสอง NestedSet ยังมีเมธอดตัวช่วยบางอย่างภายในด้วยเพื่ออำนวยความสะดวกในการทํางานร่วมกันกับคลาสคอลเล็กชันปกติ แต่การส่ง NestedSet ไปยังเมธอดใดเมธอดหนึ่งโดยไม่ตั้งใจจะทําให้ระบบทําการคัดลอกและเพิ่มการบริโภคหน่วยความจําแบบสี่เหลี่ยมจัตุรัส