สกายเฟรม

รายงานปัญหาopen_in_new ดูแหล่งที่มาopen_in_new Nightly · 8.4 · 8.3 · 8.2 · 8.1 · 8.0 · 7.6

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

โมเดลข้อมูล

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

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

การประเมิน

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

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

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

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

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

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

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

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

ส่วนเพิ่ม

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

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

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

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

ปัจจุบันเราดำเนินการล้างข้อมูลจากล่างขึ้นบนเท่านั้น

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

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

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

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

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

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

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

การแมปกับแนวคิดของ 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 ของไฟล์อินพุต ปัจจุบันการดำเนินการที่ดำเนินการจะอยู่ในคีย์ท้องฟ้า ซึ่งขัดแย้งกับแนวคิดที่ว่าคีย์ท้องฟ้าควรมีขนาดเล็ก เรากำลังดำเนินการแก้ไขความคลาดเคลื่อนนี้ (โปรดทราบว่า ActionExecutionValue และ ArtifactValue จะไม่ได้ใช้หากเราไม่ได้เรียกใช้ระยะการดำเนินการใน Skyframe)