สกายเฟรม

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

โมเดลข้อมูล

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

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

การประเมิน

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

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

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

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

การติดตั้งใช้งาน SkyFunction ไม่ควรเข้าถึงข้อมูลด้วยวิธีอื่นนอกเหนือจากการขอทรัพยากร Dependency (เช่น การอ่านระบบไฟล์โดยตรง) เนื่องจากจะทำให้ 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 ที่เกี่ยวข้องและลิงก์สัญลักษณ์ที่ต้องแก้ไข (เช่น 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)