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