Bingkai

Laporkan masalah Lihat sumber {/18/}{/1/}

Evaluasi paralel dan model inkrementalitas Bazel.

Model data

Model data terdiri dari item berikut:

  • SkyValue. Juga disebut dengan node. SkyValues adalah objek tidak dapat diubah yang berisi semua data yang dibangun selama build dan input build. Contohnya adalah: file input, file output, target, dan target yang dikonfigurasi.
  • SkyKey. Nama pendek yang tidak dapat diubah untuk mereferensikan SkyValue, misalnya, FILECONTENTS:/tmp/foo atau PACKAGE://foo.
  • SkyFunction. Membangun node berdasarkan kunci dan node dependennya.
  • Grafik node. Struktur data yang berisi hubungan dependensi antar-node.
  • Skyframe. Nama kode untuk framework evaluasi inkremental yang menjadi dasar Bazel.

Evaluasi

Build terdiri dari mengevaluasi node yang merepresentasikan permintaan build (ini adalah status yang kita perjuangkan, tetapi ada banyak kode lama yang menghalangi). Pertama, SkyFunction-nya ditemukan dan dipanggil dengan kunci SkyKey tingkat teratas. Fungsi ini kemudian meminta evaluasi node yang diperlukan untuk mengevaluasi node tingkat atas, yang pada akhirnya menghasilkan pemanggilan fungsi lainnya, dan seterusnya, hingga node daun tercapai (yang biasanya merupakan node yang mewakili file input dalam sistem file). Terakhir, kita berakhir dengan nilai SkyValue level teratas, beberapa efek samping (seperti file output dalam sistem file) dan grafik asiklik terarah dependensi antara node yang terlibat dalam build.

SkyFunction dapat meminta SkyKeys dalam beberapa penerusan jika tidak dapat mengetahui terlebih dahulu semua node yang diperlukan untuk melakukan tugasnya. Contoh sederhana adalah mengevaluasi node file input yang ternyata adalah symlink: fungsi tersebut mencoba membaca file, menyadari bahwa file tersebut adalah symlink, dan dengan demikian mengambil node sistem file yang mewakili target symlink. Namun, itu sendiri bisa berupa symlink, dalam hal ini fungsi asli juga harus mengambil targetnya.

Fungsi ditunjukkan dalam kode oleh antarmuka SkyFunction dan layanan yang disediakan oleh antarmuka yang disebut SkyFunction.Environment. Berikut adalah hal-hal yang dapat dilakukan fungsi:

  • Minta evaluasi node lain dengan memanggil env.getValue. Jika node tersedia, nilainya akan ditampilkan. Jika tidak, null akan ditampilkan dan fungsi itu sendiri diharapkan menampilkan null. Pada kasus yang terakhir, node dependen akan dievaluasi, lalu builder node asli dipanggil lagi, tetapi kali ini panggilan env.getValue yang sama akan menampilkan nilai non-null.
  • Minta evaluasi beberapa node lainnya dengan memanggil env.getValues(). Hal ini pada dasarnya sama, hanya saja node dependen dievaluasi secara paralel.
  • Melakukan komputasi selama pemanggilan
  • Memiliki efek samping, misalnya, menulis file ke sistem file. Harus diperhatikan bahwa dua fungsi yang berbeda tidak menginjak jari kaki satu sama lain. Secara umum, efek samping tulis (di mana data mengalir keluar dari Bazel) diperbolehkan, efek samping baca (ketika data mengalir ke dalam Bazel tanpa dependensi terdaftar) tidak diperbolehkan, karena mereka merupakan dependensi yang tidak terdaftar dan dengan demikian, dapat menyebabkan build inkremental yang salah.

Implementasi SkyFunction tidak boleh mengakses data dengan cara apa pun selain meminta dependensi (seperti dengan langsung membaca sistem file), karena hal tersebut menyebabkan Bazel tidak mendaftarkan dependensi data pada file yang dibaca, sehingga mengakibatkan build inkremental yang salah.

Setelah memiliki cukup data untuk melakukan tugasnya, fungsi akan menampilkan nilai non-null yang menunjukkan penyelesaian.

Strategi evaluasi ini memiliki sejumlah manfaat:

  • Hermetikitas. Jika fungsi hanya meminta data input dengan bergantung pada node lain, Bazel dapat menjamin bahwa jika status input sama, data yang sama akan ditampilkan. Jika semua fungsi langit bersifat determenistik, ini berarti seluruh bangunan juga akan bersifat determenistik.
  • Inkrementalitas yang benar dan sempurna. Jika semua data input untuk semua fungsi direkam, Bazel hanya dapat membatalkan kumpulan node yang tepat, yang perlu dibatalkan validasinya saat data input berubah.
  • Paralelisme. Karena fungsi hanya dapat berinteraksi satu sama lain dengan cara meminta dependensi, fungsi yang tidak bergantung satu sama lain dapat dijalankan secara paralel dan Bazel dapat menjamin bahwa hasilnya sama seperti jika dijalankan secara berurutan.

Inkrementalitas

Karena fungsi hanya dapat mengakses data input bergantung pada node lain, Bazel dapat membuat grafik aliran data lengkap dari file input ke file output, dan menggunakan informasi ini untuk hanya membangun ulang node yang benar-benar perlu dibangun ulang: penutupan transitif terbalik dari kumpulan file input yang diubah.

Secara khusus, ada dua kemungkinan strategi inkrementalitas: strategi bottom-up dan top-down. Mana yang optimal tergantung pada bagaimana grafik dependensi terlihat.

  • Selama pembatalan validasi bottom-up, setelah grafik dibuat dan kumpulan input yang diubah diketahui, semua node menjadi tidak valid dan bergantung secara transitif pada file yang diubah. Hal ini akan optimal jika kami mengetahui bahwa node level teratas yang sama akan dibuat lagi. Perhatikan bahwa pembatalan validasi bottom-up perlu menjalankan stat() pada semua file input build sebelumnya untuk menentukan apakah file tersebut diubah atau tidak. Hal ini dapat ditingkatkan menggunakan inotify atau mekanisme serupa untuk mempelajari file yang diubah.

  • Selama pembatalan validasi top-down, penutupan transitif node level teratas akan diperiksa dan hanya node yang penutupan transitifnya dipertahankan. Ini akan lebih baik jika kita mengetahui bahwa grafik node saat ini berukuran besar, tetapi kita hanya memerlukan subset kecilnya dalam build berikutnya: pembatalan validasi bottom-up akan membatalkan grafik yang lebih besar dari build pertama, tidak seperti pembatalan validasi top-down, yang hanya menelusuri grafik kecil build kedua.

Saat ini kami hanya melakukan pembatalan validasi bottom-up.

Untuk mendapatkan inkrementalitas lebih lanjut, kami menggunakan pemangkasan perubahan: jika node menjadi tidak valid, tetapi setelah dibuat ulang, ditemukan bahwa nilai barunya sama dengan nilai lamanya, node yang menjadi tidak valid karena perubahan dalam node ini akan “diaktifkan kembali”.

Ini berguna, misalnya, jika seseorang mengubah komentar dalam file C++: maka file .o yang dihasilkan darinya akan sama, sehingga kita tidak perlu memanggil penaut lagi.

Penautan / Kompilasi Inkremental

Keterbatasan utama model ini adalah pembatalan validasi node adalah masalah total atau tidak sama sekali: saat dependensi berubah, node dependen akan selalu dibuat ulang dari awal, meskipun ada algoritma yang lebih baik yang akan memutasikan nilai lama node berdasarkan perubahan tersebut. Beberapa contoh yang dapat membantu hal ini:

  • Penautan inkremental
  • Saat satu file .class berubah dalam .jar, secara teoretis kita dapat mengubah file .jar, bukan membangunnya dari awal lagi.

Alasan mengapa Bazel saat ini tidak mendukung hal-hal ini dengan cara yang berprinsip (kami memiliki dukungan untuk penautan inkremental, tetapi tidak diimplementasikan dalam Skyframe) ada dua: kami hanya memiliki peningkatan kinerja yang terbatas dan sulit untuk menjamin bahwa hasil mutasinya sama dengan hasil dari rebuild yang bersih, dan nilai-nilai Google untuk build yang bit-for-bit dapat diulang.

Sampai sekarang, kita selalu dapat mencapai performa yang cukup baik hanya dengan menguraikan langkah build yang mahal dan mencapai evaluasi ulang parsial dengan cara tersebut: langkah ini membagi semua class dalam aplikasi menjadi beberapa grup dan melakukan dexing padanya secara terpisah. Dengan cara ini, jika class dalam grup tidak berubah, dexing tidak perlu diulangi.

Pemetaan ke konsep Bazel

Ini adalah ringkasan kasar dari beberapa implementasi SkyFunction yang digunakan Bazel untuk menjalankan build:

  • FileStateValue. Hasil lstat(). Untuk file yang ada, kami juga menghitung informasi tambahan untuk mendeteksi perubahan pada file tersebut. Ini adalah node level terendah dalam grafik Skyframe dan tidak memiliki dependensi.
  • FileValue. Digunakan oleh apa pun yang peduli dengan konten sebenarnya dan/atau jalur file yang di-resolve. Bergantung pada FileStateValue yang sesuai dan symlink apa pun yang perlu diselesaikan (seperti FileValue untuk a/b memerlukan jalur a yang di-resolve dan jalur a/b yang di-resolve). Perbedaan antara FileStateValue penting karena dalam beberapa kasus (misalnya, mengevaluasi glob sistem file (seperti srcs=glob(["*/*.java"])) konten file sebenarnya tidak diperlukan.
  • DirectoryListingValue. Pada dasarnya, hasil dari readdir(). Bergantung pada FileValue terkait yang terkait dengan direktori.
  • PackageValue. Mewakili versi file BUILD yang diurai. Bergantung pada FileValue file BUILD terkait, dan juga secara transitif pada DirectoryListingValue apa pun yang digunakan untuk me-resolve glob dalam paket (struktur data yang mewakili konten file BUILD secara internal)
  • ConfiguredTargetValue. Mewakili target yang dikonfigurasi, yang merupakan tuple dari serangkaian tindakan yang dihasilkan selama analisis target dan informasi yang diberikan ke target yang dikonfigurasi, yang bergantung pada target ini. Bergantung pada PackageValue tempat target yang sesuai berada, ConfiguredTargetValues dependensi langsung, dan node khusus yang mewakili konfigurasi build.
  • ArtifactValue. Mewakili file dalam build, baik berupa artefak sumber maupun output (artefak hampir setara dengan file, dan digunakan untuk merujuk file selama eksekusi aktual langkah-langkah build). Untuk file sumber, metode ini bergantung pada FileValue node terkait, untuk artefak output, dependensi ini bergantung pada ActionExecutionValue dari tindakan apa pun yang menghasilkan artefak tersebut.
  • ActionExecutionValue. Menyatakan eksekusi suatu tindakan. Bergantung pada ArtifactValues file inputnya. Tindakan yang dijalankan saat ini dimuat dalam {i>sky key<i}-nya, yang bertentangan dengan konsep bahwa {i>sky key<i} harus berukuran kecil. Kami sedang berupaya menyelesaikan perbedaan ini (perhatikan bahwa ActionExecutionValue dan ArtifactValue tidak akan digunakan jika kami tidak menjalankan fase eksekusi di Skyframe).