สกายเฟรม

รูปแบบการประเมินแบบขนานและการทำงานแบบเพิ่มของ Bazel

โมเดลข้อมูล

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

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

การประเมิน

การสร้างจะเกิดขึ้นจากการประเมินโหนดที่แสดงคำขอสร้าง

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

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

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

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

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

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

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

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

ส่วนเพิ่ม

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

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

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

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

Bazel จะทำการล้างข้อมูลจากล่างขึ้นบนเท่านั้น

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

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

การลิงก์ / การรวบรวมที่เพิ่มขึ้น

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

• การลิงก์แบบเพิ่มทีละรายการ
• เมื่อไฟล์คลาสเดียวมีการเปลี่ยนแปลงในไฟล์ JAR คุณจะแก้ไขไฟล์ JAR ในตำแหน่งเดิมได้แทนที่จะสร้างใหม่ตั้งแต่ต้น

เหตุผลที่ Bazel ไม่รองรับสิ่งเหล่านี้อย่างเป็นหลักการ มี 2 ประการ

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

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

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

ต่อไปนี้เป็นข้อมูลสรุประดับสูงของการใช้งานคีย์ SkyFunction และ SkyValue ที่ Bazel ใช้เพื่อทำการบิลด์

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

แผนภาพนี้แสดงความสัมพันธ์ระหว่างการติดตั้งใช้งาน SkyFunction หลังจากบิลด์ Bazel เองเพื่อเป็นเครื่องมือช่วยในการมองเห็น