اسکای فریم

ارزیابی موازی و مدل افزایشی بازل.

مدل داده

مدل داده شامل موارد زیر است:

• 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() ارزیابی چندین گره دیگر را درخواست کنید. این اساساً همین کار را انجام می دهد، با این تفاوت که گره های وابسته به صورت موازی ارزیابی می شوند.
• در حین فراخوانی آنها محاسبات را انجام دهید
• عوارض جانبی داشته باشد، به عنوان مثال، نوشتن فایل در سیستم فایل. باید مراقب بود که دو عملکرد متفاوت روی انگشتان یکدیگر قرار نگیرند. به طور کلی، عوارض جانبی نوشتن (جایی که داده‌ها از Bazel به بیرون جریان می‌یابند) مشکلی ندارند، عوارض جانبی خواندنی (جایی که داده‌ها بدون وابستگی ثبت‌شده به داخل Bazel جریان می‌یابند) وجود ندارد، زیرا آنها یک وابستگی ثبت نشده هستند و به همین دلیل می‌توانند باعث ساخت‌های افزایشی نادرست شوند. .

پیاده‌سازی SkyFunction نباید به روش دیگری جز درخواست وابستگی‌ها (مانند خواندن مستقیم سیستم فایل) به داده‌ها دسترسی داشته باشد، زیرا این امر باعث می‌شود Bazel وابستگی داده‌ها را بر روی فایلی که خوانده شده ثبت نکند، در نتیجه ساخت‌های افزایشی نادرست ایجاد می‌شود.

هنگامی که یک تابع داده کافی برای انجام کار خود را داشته باشد، باید یک مقدار غیر null که نشان دهنده اتمام است را برگرداند.

این استراتژی ارزیابی چندین مزیت دارد:

• هرمتیک. اگر توابع فقط از طریق وابستگی به گره‌های دیگر، داده‌های ورودی را درخواست می‌کنند، Bazel می‌تواند تضمین کند که اگر وضعیت ورودی یکسان باشد، همان داده‌ها برگردانده می‌شوند. اگر همه توابع آسمان قطعی باشند، به این معنی است که کل ساخت نیز قطعی خواهد بود.
• افزایشی صحیح و کامل. اگر تمام داده‌های ورودی همه توابع ثبت شود، Bazel می‌تواند تنها مجموعه دقیق گره‌هایی را که باید با تغییر داده‌های ورودی باطل شوند، باطل کند.
• موازی سازی. از آنجایی که توابع فقط می توانند از طریق درخواست وابستگی با یکدیگر تعامل داشته باشند، توابعی که به یکدیگر وابسته نیستند می توانند به صورت موازی اجرا شوند و Bazel می تواند تضمین کند که نتیجه همان است که اگر به صورت متوالی اجرا شوند.

افزایشی

از آنجایی که توابع فقط می توانند به داده های ورودی بسته به گره های دیگر دسترسی داشته باشند، Bazel می تواند یک نمودار جریان داده کامل از فایل های ورودی به فایل های خروجی ایجاد کند و از این اطلاعات فقط برای بازسازی گره هایی استفاده کند که واقعاً نیاز به بازسازی دارند: گذر معکوس. بسته شدن مجموعه فایل های ورودی تغییر یافته

به طور خاص، دو استراتژی افزایشی ممکن وجود دارد: یکی از پایین به بالا و دیگری از بالا به پایین. اینکه کدام یک بهینه است بستگی به شکل نمودار وابستگی دارد.

• در خلال عدم اعتبار از پایین به بالا، پس از ساخته شدن یک نمودار و مشخص شدن مجموعه ورودی های تغییر یافته، تمام گره هایی که به طور گذرا به فایل های تغییر یافته وابسته هستند، باطل می شوند. این بهینه است اگر بدانیم که همان گره سطح بالا دوباره ساخته خواهد شد. توجه داشته باشید که عدم اعتبار از پایین به بالا نیازمند اجرای stat() بر روی تمامی فایل های ورودی بیلد قبلی است تا مشخص شود آیا تغییر کرده اند یا خیر. این را می توان با استفاده از inotify یا مکانیزم مشابه برای یادگیری در مورد فایل های تغییر یافته بهبود بخشید.

• در طول بی اعتباری از بالا به پایین، بسته شدن گذرای گره سطح بالا بررسی می شود و تنها گره هایی نگه داشته می شوند که بسته شدن گذرا آنها تمیز است. این بهتر است اگر بدانیم گراف گره فعلی بزرگ است، اما فقط به یک زیرمجموعه کوچک از آن در ساخت بعدی نیاز داریم: باطل کردن از پایین به بالا، گراف بزرگتر ساخت اول را باطل می کند، برخلاف عدم اعتبار از بالا به پایین، که فقط نمودار کوچک ساخت دوم را نشان می دهد.

ما در حال حاضر فقط ابطال از پایین به بالا انجام می دهیم.

برای افزایش بیشتر، از هرس تغییر استفاده می کنیم: اگر یک گره باطل شود، اما پس از بازسازی، مشخص شود که مقدار جدید آن همان مقدار قبلی است، گره هایی که به دلیل تغییر در این گره باطل شده اند، دوباره احیا می شوند. ".

این مفید است، به عنوان مثال، اگر شخصی یک نظر را در یک فایل C++ تغییر دهد: پس فایل .o ایجاد شده از آن یکسان خواهد بود، بنابراین، ما نیازی به فراخوانی مجدد پیوند دهنده نداریم.

پیوند افزایشی / کامپایل

محدودیت اصلی این مدل این است که باطل کردن یک گره یک امر همه یا هیچ است: وقتی یک وابستگی تغییر می کند، گره وابسته همیشه از ابتدا بازسازی می شود، حتی اگر الگوریتم بهتری وجود داشته باشد که مقدار قدیمی را تغییر دهد. گره بر اساس تغییرات چند مثال که در آن مفید خواهد بود:

• پیوند افزایشی
• وقتی یک فایل .class منفرد در یک .jar تغییر می کند، ما می توانیم از نظر تئوری فایل .jar را به جای اینکه دوباره آن را از ابتدا بسازیم، تغییر دهیم.

دلیل اینکه Bazel در حال حاضر از این موارد به صورت اصولی پشتیبانی نمی کند (ما تا حدودی از پیوندهای افزایشی پشتیبانی می کنیم، اما در Skyframe پیاده سازی نشده است) دو مورد است: ما فقط دستاوردهای عملکردی محدودی داشتیم و تضمین کردن نتیجه دشوار بود. جهش مانند بازسازی تمیز است و گوگل بیلدهایی را که بیت به بیت قابل تکرار هستند ارزش گذاری می کند.

تا به حال، ما همیشه می‌توانستیم به سادگی با تجزیه یک مرحله ساخت گران قیمت و دستیابی به ارزیابی مجدد جزئی، به عملکرد کافی خوب دست یابیم: همه کلاس‌های یک برنامه را به چند گروه تقسیم می‌کند و به طور جداگانه بر روی آن‌ها بررسی می‌کند. به این ترتیب، اگر کلاس ها در یک گروه تغییر نکنند، dexing لازم نیست دوباره انجام شود.

نگاشت به مفاهیم بازل

این یک نمای کلی از برخی از پیاده سازی های SkyFunction است که Bazel برای اجرای یک ساخت استفاده می کند:

• FileStateValue . نتیجه یک lstat() . برای فایل‌های موجود، اطلاعات اضافی را نیز محاسبه می‌کنیم تا تغییرات فایل را شناسایی کنیم. این پایین ترین گره در گراف Skyframe است و هیچ وابستگی ندارد.
• FileValue . برای هر چیزی که به محتوای واقعی و/یا مسیر حل شده یک فایل اهمیت می دهد استفاده می شود. بستگی به FileStateValue مربوطه و هر پیوند نمادینی دارد که باید حل شود (مانند FileValue برای a/b به مسیر حل‌شده a و مسیر حل‌شده 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 ​​فایل های ورودی آن بستگی دارد. عملی که اجرا می کند در حال حاضر در کلید آسمان آن قرار دارد، که برخلاف این مفهوم است که کلیدهای آسمان باید کوچک باشند. ما در حال حل این اختلاف هستیم (توجه داشته باشید که اگر مرحله اجرا را در Skyframe اجرا نکنیم، ActionExecutionValue و ArtifactValue استفاده نمی شوند).