สกายเฟรม

โมเดลการประเมินแบบขนานและส่วนเพิ่มของ Bazel

โมเดลข้อมูล

โมเดลข้อมูลประกอบด้วยรายการต่อไปนี้

• SkyValue หรือที่เรียกว่าโหนด SkyValues เป็นออบเจ็กต์ที่ไม่เปลี่ยนแปลงซึ่งมีข้อมูลทั้งหมดที่สร้างขึ้นระหว่างการบิลด์และอินพุตของการบิลด์ ตัวอย่างเช่น ไฟล์อินพุต ไฟล์เอาต์พุต เป้าหมาย และเป้าหมายที่กำหนดค่า
• SkyKey ชื่อสั้นๆ ที่ไม่เปลี่ยนแปลงเพื่ออ้างอิง SkyValue เช่น FILECONTENTS:/tmp/foo หรือ PACKAGE://foo
• SkyFunction สร้างโหนดตามคีย์และโหนดที่ขึ้นต่อกัน
• กราฟโหนด โครงสร้างข้อมูลที่มีความสัมพันธ์แบบขึ้นต่อกันระหว่างโหนด
• Skyframeชื่อโค้ดสำหรับเฟรมเวิร์กการประเมินแบบเพิ่มที่ Bazel ใช้

การประเมิน

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

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

ฟังก์ชันจะแสดงในโค้ดโดยอินเทอร์เฟซ SkyFunction และบริการที่อินเทอร์เฟซชื่อ SkyFunction.Environment มอบให้ ฟังก์ชันสามารถทำสิ่งต่อไปนี้ได้

• ขอให้ประเมินโหนดอื่นโดยเรียกใช้ env.getValue หากโหนดพร้อมใช้งาน ระบบจะแสดงผลค่าของโหนดนั้น ไม่เช่นนั้น ระบบจะแสดงผล null และฟังก์ชันเองก็คาดว่าจะแสดงผล null ในกรณีหลัง ระบบจะประเมินโหนดที่ขึ้นต่อกัน จากนั้นระบบจะเรียกใช้ตัวสร้างโหนดเดิมอีกครั้ง แต่คราวนี้การเรียกใช้ env.getValue เดียวกันจะแสดงผลค่าที่ไม่ใช่ null
• ขอให้ประเมินโหนดอื่นๆ หลายโหนดโดยเรียกใช้ env.getValues() การดำเนินการนี้จะทำสิ่งเดียวกันโดยพื้นฐาน ยกเว้นว่าระบบจะประเมินโหนดที่ขึ้นต่อกันแบบขนาน
• ทำการคำนวณระหว่างการเรียกใช้
• มีผลข้างเคียง เช่น การเขียนไฟล์ลงในระบบไฟล์ ต้องระมัดระวังไม่ให้ 2 ฟังก์ชันที่แตกต่างกันรบกวนการทำงานของกันและกัน โดยทั่วไป ผลข้างเคียงจากการเขียน (ที่ข้อมูลไหลออกจาก Bazel) จะใช้ได้ แต่ผลข้างเคียงจากการอ่าน (ที่ข้อมูลไหลเข้าสู่ Bazel โดยไม่มีการขึ้นต่อกันที่ลงทะเบียนไว้) จะใช้ไม่ได้ เนื่องจากเป็นการขึ้นต่อกันที่ไม่ได้ลงทะเบียนไว้และอาจทำให้เกิดการบิลด์แบบเพิ่มที่ไม่ถูกต้อง

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

เมื่อฟังก์ชันมีข้อมูลเพียงพอที่จะทำงานให้เสร็จแล้ว ฟังก์ชันควรแสดงผลค่าที่ไม่ใช่ null เพื่อระบุว่าการทำงานเสร็จสมบูรณ์

กลยุทธ์การประเมินนี้มีประโยชน์หลายประการ ได้แก่

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

ส่วนเพิ่ม

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

โดยเฉพาะอย่างยิ่ง กลยุทธ์ส่วนเพิ่มที่เป็นไปได้ 2 กลยุทธ์ ได้แก่ กลยุทธ์จากล่างขึ้นบนและกลยุทธ์จากบนลงล่าง กลยุทธ์ที่เหมาะสมที่สุดจะขึ้นอยู่กับลักษณะของกราฟการขึ้นต่อกัน

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

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

ปัจจุบันเราใช้การยกเลิกการใช้งานจากล่างขึ้นบนเท่านั้น

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

กลยุทธ์นี้มีประโยชน์ เช่น หากคุณเปลี่ยนความคิดเห็นในไฟล์ C++ ไฟล์ .o ที่สร้างจากไฟล์นั้นจะเหมือนเดิม ดังนั้นเราจึงไม่จำเป็นต้องเรียกใช้ตัวลิงก์อีกครั้ง

การลิงก์ / การคอมไพล์แบบเพิ่ม

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

• การลิงก์แบบเพิ่ม
• เมื่อไฟล์ .class ไฟล์เดียวมีการเปลี่ยนแปลงในไฟล์ .jar ในทางทฤษฎี เราสามารถแก้ไขไฟล์ .jar แทนที่จะสร้างไฟล์ใหม่ตั้งแต่ต้น

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

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

การแมปกับแนวคิดของ Bazel

นี่คือภาพรวมคร่าวๆ ของการใช้งาน SkyFunction บางส่วนที่ Bazel ใช้เพื่อทำการบิลด์

• FileStateValue ผลลัพธ์ของ lstat() สำหรับไฟล์ที่มีอยู่ เรายังคำนวณข้อมูลเพิ่มเติมเพื่อตรวจหาการเปลี่ยนแปลงในไฟล์ นี่คือโหนดระดับต่ำสุดในกราฟ Skyframe และไม่มีการขึ้นต่อกัน
• FileValue ใช้โดยทุกสิ่งทุกอย่างที่สนใจเนื้อหาจริงและ/หรือเส้นทางที่แก้ไขแล้วของไฟล์ ขึ้นต่อกันกับ FileStateValue ที่เกี่ยวข้องและ symlink ที่ต้องแก้ไข (เช่น FileValue สำหรับ a/b ต้องใช้เส้นทางที่แก้ไขแล้วของ a และเส้นทางที่แก้ไขแล้วของ a/b) ความแตกต่างระหว่าง FileStateValue มีความสำคัญเนื่องจากในบางกรณี (เช่น การประเมิน glob ของระบบไฟล์ (เช่น srcs=glob(["*/*.java"])) เราไม่จำเป็นต้องใช้เนื้อหาของไฟล์จริง
• DirectoryListingValue โดยพื้นฐานแล้วคือผลลัพธ์ของ readdir() ขึ้นต่อกันกับ FileValue ที่เชื่อมโยงกับไดเรกทอรี
• PackageValue แสดงเวอร์ชันที่แยกวิเคราะห์แล้วของไฟล์ BUILD ขึ้นต่อกันกับ FileValue ของไฟล์ BUILD ที่เกี่ยวข้อง และแบบส่งผ่านกับ DirectoryListingValue ใดๆ ที่ใช้เพื่อแก้ไข glob ในแพ็กเกจ (โครงสร้างข้อมูลที่แสดงเนื้อหาของไฟล์ BUILD ภายใน)
• ConfiguredTargetValue แสดงเป้าหมายที่กำหนดค่า ซึ่งเป็นทูเพิลของชุดการดำเนินการที่สร้างขึ้นระหว่างการวิเคราะห์เป้าหมายและข้อมูลที่มอบให้กับเป้าหมายที่กำหนดค่าซึ่งขึ้นต่อกันกับเป้าหมายนี้ ขึ้นต่อกันกับ PackageValue ที่เป้าหมายที่เกี่ยวข้องอยู่ ConfiguredTargetValues ของการขึ้นต่อกันโดยตรง และโหนดพิเศษที่แสดงการกำหนดค่าการบิลด์
• ArtifactValue แสดงไฟล์ในการบิลด์ ไม่ว่าจะเป็นอาร์ติแฟกต์แหล่งที่มาหรืออาร์ติแฟกต์เอาต์พุต (อาร์ติแฟกต์เกือบจะเทียบเท่ากับไฟล์ และใช้เพื่ออ้างอิงไฟล์ระหว่างการดำเนินการจริงของขั้นตอนการบิลด์) สำหรับไฟล์แหล่งที่มา ไฟล์นี้จะขึ้นต่อกันกับ FileValue ของโหนดที่เกี่ยวข้อง สำหรับอาร์ติแฟกต์เอาต์พุต ไฟล์นี้จะขึ้นต่อกันกับ ActionExecutionValue ของการดำเนินการใดก็ตามที่สร้างอาร์ติแฟกต์
• ActionExecutionValue แสดงการดำเนินการ ขึ้นต่อกันกับ ArtifactValues ของไฟล์อินพุต การดำเนินการที่ไฟล์นี้ดำเนินการอยู่ในคีย์ Sky ของไฟล์ในปัจจุบัน ซึ่งขัดแย้งกับแนวคิดที่ว่าคีย์ Sky ควรมีขนาดเล็ก เรากำลังพยายามแก้ไขความคลาดเคลื่อนนี้ (โปรดทราบว่าระบบจะไม่ใช้ ActionExecutionValue และ ArtifactValue หากเราไม่เรียกใช้ระยะการดำเนินการใน Skyframe)