หน้านี้จะแสดงภาพรวมระดับสูงของปัญหาและข้อจํากัดเฉพาะในการเขียนกฎ 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 ด้วย) การนําเสนอกราฟนี้อย่างชัดเจนในหน่วยความจําจะช่วยให้ระบบบิลด์ระบุได้อย่างแม่นยําว่าโหนดใดได้รับผลกระทบจากการเปลี่ยนแปลงไฟล์อินพุตหนึ่งๆ (รวมถึงการสร้างหรือลบไฟล์อินพุต) ซึ่งทํางานเพียงเล็กน้อยเพื่อกู้คืนต้นไม้เอาต์พุตกลับไปยังสถานะที่ตั้งใจไว้
โหนดแต่ละโหนดจะดำเนินการตามกระบวนการค้นหาทรัพยากรที่เกี่ยวข้อง โหนดแต่ละโหนดสามารถประกาศการพึ่งพา จากนั้นใช้เนื้อหาของการพึ่งพาเหล่านั้นเพื่อประกาศการพึ่งพาเพิ่มเติมได้ โดยหลักการแล้ว รูปแบบนี้จะเหมาะกับรูปแบบเธรดต่อโหนด อย่างไรก็ตาม บิลด์ขนาดกลางมีโหนด 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 ด้วย)
กฎของไลบรารีแบบเชน - ให้พิจารณากรณีที่กฎของไลบรารี 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 ไปยังเมธอดใดเมธอดหนึ่งโดยไม่ตั้งใจจะทําให้ระบบทําการคัดลอกและเพิ่มการบริโภคหน่วยความจําแบบสี่เหลี่ยมจัตุรัส