ความท้าทายของกฎการเขียน

หน้านี้ให้ภาพรวมระดับสูงเกี่ยวกับปัญหาและความท้าทายเฉพาะในการเขียนกฎ Bazel ที่มีประสิทธิภาพ

ข้อกำหนดสรุป

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

สมมติฐาน

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

มุ่งเน้นความถูกต้อง อัตราการส่งข้อมูล ความง่ายในการใช้งาน และเวลาในการตอบสนอง

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

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

ความง่ายในการใช้งานเป็นเป้าหมายถัดไป จากแนวทางที่ถูกต้องหลายแนวทางซึ่งมีร่องรอยการใช้งานบริการการดำเนินการระยะไกลเหมือนกัน (หรือคล้ายกัน) เราจะเลือกแนวทางที่ใช้งานง่ายกว่า

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

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

ที่เก็บข้อมูลขนาดใหญ่

ระบบบิลด์ต้องทำงานในที่เก็บข้อมูลขนาดใหญ่ ซึ่งหมายความว่าที่เก็บข้อมูลมีขนาดใหญ่จนไม่สามารถจัดเก็บไว้ในฮาร์ดไดรฟ์เดียวได้ จึงเป็นไปไม่ได้ที่จะทำการเช็กเอาต์แบบเต็มในเครื่องของนักพัฒนาแอปเกือบทั้งหมด การบิลด์ขนาดกลางจะต้องอ่านและแยกวิเคราะห์ไฟล์ BUILD หลายหมื่นไฟล์ และประเมิน Globs หลายแสนรายการ แม้ว่าในทางทฤษฎีแล้วจะสามารถอ่านไฟล์ BUILD ทั้งหมดในเครื่องเดียวได้ แต่เรายังไม่สามารถทำได้ภายในเวลาและหน่วยความจำที่สมเหตุสมผล ดังนั้น ไฟล์ BUILD จึงต้องโหลดและแยกวิเคราะห์ได้อย่างอิสระ

ภาษาคำอธิบายคล้ายกับ BUILD

ในบริบทนี้ เราสมมติว่าภาษาการกำหนดค่าคล้ายกับไฟล์ BUILD ในการประกาศกฎไลบรารีและกฎไบนารี รวมถึงการพึ่งพากัน ไฟล์ BUILD สามารถอ่านและแยกวิเคราะห์ได้อย่างอิสระ และเราจะหลีกเลี่ยงการดูไฟล์ต้นฉบับทุกครั้งที่ทำได้ (ยกเว้นการตรวจสอบการมีอยู่)

ประวัติ

Bazel เวอร์ชันต่างๆ มีความแตกต่างกันซึ่งก่อให้เกิดความท้าทาย และเราได้อธิบายความแตกต่างบางส่วนไว้ในส่วนต่อไปนี้

การแยกการโหลด การวิเคราะห์ และการดำเนินการออกจากกันอย่างชัดเจนนั้นล้าสมัยแล้ว แต่ยังคงส่งผลต่อ API

ในทางเทคนิคแล้ว กฎเพียงแค่ต้องทราบไฟล์อินพุตและเอาต์พุตของการดำเนินการก่อนที่จะส่งการดำเนินการไปยังการดำเนินการระยะไกล อย่างไรก็ตาม ฐานโค้ด Bazel ดั้งเดิมมีการแยกการโหลดแพ็กเกจ การวิเคราะห์กฎโดยใช้การกำหนดค่า (โดยพื้นฐานแล้วคือแฟล็กบรรทัดคำสั่ง) และการเรียกใช้การดำเนินการใดๆ อย่างชัดเจน ความแตกต่างนี้ยังคงเป็นส่วนหนึ่งของ Rules API ในปัจจุบัน แม้ว่าแกนหลักของ Bazel จะไม่จำเป็นต้องใช้ความแตกต่างนี้อีกต่อไป (ดูรายละเอียดเพิ่มเติมด้านล่าง)

ซึ่งหมายความว่า Rules API ต้องมีคำอธิบายประกาศของอินเทอร์เฟซกฎ (แอตทริบิวต์ที่มี ประเภทของแอตทริบิวต์) มีข้อยกเว้นบางกรณีที่ API อนุญาตให้โค้ดที่กำหนดเองทำงานในระยะการโหลดเพื่อคำนวณชื่อโดยนัยของไฟล์เอาต์พุตและค่าโดยนัยของแอตทริบิวต์ ตัวอย่างเช่น กฎ java_library ที่ชื่อ "foo" จะสร้างเอาต์พุตชื่อ "libfoo.jar" โดยนัย ซึ่งสามารถอ้างอิงจากกฎอื่นๆ ในกราฟการบิลด์ได้

นอกจากนี้ การวิเคราะห์กฎยังอ่านไฟล์ต้นฉบับหรือตรวจสอบเอาต์พุตของการดำเนินการไม่ได้ แต่ต้องสร้างกราฟสองส่วนแบบมีทิศทางบางส่วนของขั้นตอนการบิลด์และชื่อไฟล์เอาต์พุตที่กำหนดจากกฎเองและการพึ่งพาอาศัยกันเท่านั้น

ลักษณะเฉพาะ

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

การดำเนินการระยะไกลและการแคชทำได้ยาก

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

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

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

เราได้กล่าวไว้ข้างต้นว่า Bazel ต้องทราบไฟล์อินพุตทั้งหมดที่เข้าสู่ขั้นตอนการบิลด์เพื่อตรวจหาว่าขั้นตอนการบิลด์นั้นยังคงเป็นเวอร์ชันล่าสุดหรือไม่ การโหลดแพ็กเกจและการวิเคราะห์กฎก็เช่นกัน และเรา ได้ออกแบบ Skyframe เพื่อจัดการเรื่องนี้ โดยทั่วไป Skyframe เป็นไลบรารีกราฟและเฟรมเวิร์กการประเมินที่ใช้โหนดเป้าหมาย (เช่น "บิลด์ //foo ด้วยตัวเลือกเหล่านี้") และแบ่งโหนดเป้าหมายออกเป็นส่วนประกอบต่างๆ ซึ่งจะได้รับการประเมินและรวมกันเพื่อให้ได้ผลลัพธ์นี้ Skyframe จะอ่านแพ็กเกจ วิเคราะห์กฎ และดำเนินการต่างๆ ซึ่งเป็นส่วนหนึ่งของกระบวนการนี้

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

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

Bazel ใช้พูลเธรดขนาดคงที่แทน อย่างไรก็ตาม นั่นหมายความว่าหากโหนดประกาศการพึ่งพาอาศัยกันที่ยังไม่พร้อมใช้งาน เราอาจต้องยกเลิกการประเมินนั้นและรีสตาร์ท (อาจอยู่ในเธรดอื่น) เมื่อการพึ่งพาอาศัยกันพร้อมใช้งาน ซึ่งหมายความว่าโหนดไม่ควรทำเช่นนี้มากเกินไป โหนดที่ประกาศการพึ่งพาอาศัยกัน N รายการแบบอนุกรมอาจรีสตาร์ทได้ N ครั้ง ซึ่งใช้เวลา O(N^2) เราจึงมุ่งเน้นการประกาศการพึ่งพาอาศัยกันแบบกลุ่มล่วงหน้า ซึ่งบางครั้งต้องมีการจัดระเบียบโค้ดใหม่ หรือแม้แต่แยกโหนดออกเป็นหลายโหนดเพื่อจำกัดจำนวนการรีสตาร์ท

โปรดทราบว่าเทคโนโลยีนี้ยังไม่พร้อมใช้งานใน Rules API ในปัจจุบัน แต่ Rules API ยังคงกำหนดโดยใช้แนวคิดเดิมของระยะการโหลด การวิเคราะห์ และการดำเนินการ อย่างไรก็ตาม ข้อจำกัดพื้นฐานคือการเข้าถึงโหนดอื่นๆ ทั้งหมดต้องผ่านเฟรมเวิร์กเพื่อให้เฟรมเวิร์กติดตามการพึ่งพาอาศัยกันที่เกี่ยวข้องได้ ไม่ว่าระบบบิลด์จะใช้ภาษาใดในการติดตั้งใช้งานหรือกฎจะเขียนขึ้นด้วยภาษาใด (ไม่จำเป็นต้องเป็นภาษาเดียวกัน) ผู้เขียนกฎต้องไม่ใช้ไลบรารีหรือรูปแบบมาตรฐานที่ข้าม Skyframe สำหรับ Java หมายความว่าต้องหลีกเลี่ยง java.io.File รวมถึงการสะท้อนทุกรูปแบบ และไลบรารีใดก็ตามที่ทำอย่างใดอย่างหนึ่ง ไลบรารีที่รองรับการแทรกการพึ่งพาอาศัยกันของอินเทอร์เฟซระดับต่ำเหล่านี้ยังคงต้องตั้งค่าอย่างถูกต้องสำหรับ Skyframe

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

การหลีกเลี่ยงการใช้เวลาและหน่วยความจำแบบกำลังสองทำได้ยาก

สิ่งที่แย่กว่านั้นคือ นอกเหนือจากข้อกำหนดที่กำหนดโดย Skyframe ข้อจำกัดทางประวัติศาสตร์ของการใช้ Java และความล้าสมัยของ Rules API แล้ว การใช้เวลาหรือหน่วยความจำแบบกำลังสองโดยไม่ได้ตั้งใจยังเป็นปัญหาพื้นฐานในระบบบิลด์ใดก็ตามที่อิงตามกฎไลบรารีและกฎไบนารี มีรูปแบบที่พบบ่อย 2 รูปแบบที่ทำให้เกิดการใช้หน่วยความจำแบบกำลังสอง (และดังนั้นจึงทำให้เกิดการใช้เวลาแบบกำลังสอง)

1. กฎไลบรารีแบบลูกโซ่ - พิจารณากรณีของกฎไลบรารีแบบลูกโซ่ที่ A ขึ้นอยู่กับ B, B ขึ้นอยู่กับ C และอื่นๆ จากนั้น เราต้องการคำนวณพร็อพเพอร์ตี้บางอย่างผ่านการปิดแบบส่งผ่านของกฎเหล่านี้ เช่น Classpath รันไทม์ Java หรือคำสั่ง Linker C++ สำหรับแต่ละไลบรารี เราอาจใช้การติดตั้งใช้งานรายการมาตรฐานอย่างง่ายๆ แต่การดำเนินการนี้จะทำให้เกิดการใช้หน่วยความจำแบบกำลังสองแล้ว โดยไลบรารีแรกมี 1 รายการใน Classpath, ไลบรารีที่ 2 มี 2 รายการ, ไลบรารีที่ 3 มี 3 รายการ และอื่นๆ รวมเป็น 1+2+3+...+N = O(N^2) รายการ

2. กฎไบนารีที่ขึ้นอยู่กับกฎไลบรารีเดียวกัน - พิจารณากรณีที่ไบนารีชุดหนึ่งขึ้นอยู่กับกฎไลบรารีเดียวกัน เช่น หากคุณมีกฎการทดสอบจำนวนหนึ่งที่ทดสอบโค้ดไลบรารีเดียวกัน สมมติว่าจากกฎ N ข้อ กฎครึ่งหนึ่งเป็นกฎไบนารี และอีกครึ่งหนึ่งเป็นกฎไลบรารี ตอนนี้พิจารณาว่าไบนารีแต่ละรายการสร้างสำเนาของพร็อพเพอร์ตี้บางอย่างที่คำนวณผ่านการปิดแบบส่งผ่านของกฎไลบรารี เช่น Classpath รันไทม์ Java หรือบรรทัดคำสั่ง Linker C++ ตัวอย่างเช่น อาจขยายการแสดงสตริงบรรทัดคำสั่งของการดำเนินการ Link C++ สำเนา N/2 รายการขององค์ประกอบ N/2 รายการคือหน่วยความจำ O(N^2)

คลาสคอลเล็กชันที่กำหนดเองเพื่อหลีกเลี่ยงความซับซ้อนแบบกำลังสอง

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

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