Bingkai

Evaluasi paralel dan model inkrementalitas Bazel.

Model data

Model data terdiri dari item berikut:

  • SkyValue. Juga disebut node. SkyValues adalah objek yang tidak dapat diubah yang berisi semua data yang dibangun selama proses 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. Mem-build node berdasarkan kuncinya dan node dependen.
  • Grafik node. Struktur data yang berisi hubungan dependensi antar-node.
  • Skyframe. Nama kode untuk framework evaluasi inkremental yang digunakan Bazel.

Evaluasi

Build terdiri dari mengevaluasi node yang mewakili permintaan build (ini adalah status yang kita perjuangkan, tetapi ada banyak kode lama yang sedang berlangsung). Pertama, SkyFunction ditemukan dan dipanggil dengan kunci SkyKey level teratas. Fungsi tersebut kemudian meminta evaluasi node yang diperlukan untuk mengevaluasi node level atas, yang kemudian menghasilkan pemanggilan fungsi lainnya, dan seterusnya, hingga node daun tercapai (yang biasanya merupakan node yang mewakili file input dalam sistem file). Terakhir, kita akan mendapatkan nilai SkyValue level atas, 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 di awal semua node yang diperlukan untuk melakukan tugasnya. Contoh sederhananya adalah mengevaluasi simpul file input yang ternyata adalah symlink: fungsi tersebut mencoba membaca file, menyadari bahwa file tersebut adalah symlink, dan dengan demikian mengambil simpul sistem file yang mewakili target symlink. Namun, fungsi itu sendiri bisa berupa symlink, sehingga fungsi asal juga perlu mengambil targetnya.

Fungsi direpresentasikan dalam kode oleh antarmuka SkyFunction dan layanan yang diberikan kepadanya oleh antarmuka yang disebut SkyFunction.Environment. Berikut adalah beberapa 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 terakhir, node dependen dievaluasi, lalu builder node asli dipanggil lagi, tetapi kali ini panggilan env.getValue yang sama akan menampilkan nilai non-null.
  • Minta evaluasi beberapa node lain dengan memanggil env.getValues(). Hal ini pada dasarnya sama, kecuali bahwa 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 saling menginjak jari kaki satu sama lain. Secara umum, penulisan efek samping (saat data mengalir keluar dari Bazel) tidak masalah, membaca efek samping (saat data mengalir ke dalam ke Bazel tanpa dependensi terdaftar) tidak demikian, karena merupakan dependensi yang tidak terdaftar dan dengan demikian, dapat menyebabkan build inkremental yang salah.

Implementasi SkyFunction tidak boleh mengakses data dengan cara selain meminta dependensi (seperti dengan langsung membaca sistem file), karena hal tersebut menyebabkan Bazel tidak mendaftarkan dependensi data pada file yang dibaca, sehingga menghasilkan 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:

  • Hermetisitas. Jika fungsi hanya meminta data input dengan bergantung pada node lain, Bazel dapat menjamin bahwa jika status input sama, data yang sama akan dikembalikan. Jika semua fungsi langit bersifat deterministik, berarti seluruh build juga akan bersifat deterministik.
  • Inkrementalitas yang benar dan sempurna. Jika semua data input dari semua fungsi direkam, Bazel hanya dapat membatalkan validasi set node yang tepat yang perlu dibatalkan validasinya saat data input berubah.
  • Paralelisme. Karena fungsi hanya dapat berinteraksi satu sama lain dengan meminta dependensi, fungsi yang tidak bergantung satu sama lain dapat dijalankan secara paralel dan Bazel dapat menjamin bahwa hasilnya sama seolah-olah dijalankan secara berurutan.

Inkrementalitas

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

Secara khusus, ada dua kemungkinan strategi inkrementalitas: yang dari bawah ke atas dan yang dari atas ke bawah. Mana yang optimal tergantung pada bagaimana grafik dependensi terlihat.

  • Selama pembatalan validasi dari bawah ke atas, setelah grafik dibuat dan rangkaian input yang diubah diketahui, semua node menjadi tidak valid dan secara transitif bergantung pada file yang diubah. Hal ini optimal jika kita mengetahui bahwa node tingkat atas yang sama akan dibangun kembali. Perhatikan bahwa pembatalan dari bawah ke atas memerlukan menjalankan stat() pada semua file input build sebelumnya untuk menentukan apakah file tersebut diubah. Hal ini dapat ditingkatkan menggunakan inotify atau mekanisme serupa untuk mempelajari file yang diubah.

  • Selama pembatalan validasi dari atas ke bawah, penutupan transitif node tingkat atas akan diperiksa dan hanya node yang penutupan transitifnya bersih, hanya node tersebut yang dipertahankan. Ini lebih baik jika kita mengetahui bahwa grafik node saat ini besar, tetapi kita hanya memerlukan subset kecil darinya di build berikutnya: pembatalan dari bawah ke atas akan membatalkan grafik yang lebih besar dari build pertama, tidak seperti pembatalan top-down, yang hanya berjalan pada grafik kecil build kedua.

Saat ini kami hanya melakukan pembatalan dari bawah ke atas.

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

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

Penautan / Kompilasi Inkremental

Keterbatasan utama model ini adalah pembatalan validasi node adalah masalah semuanya atau tidak ada sama sekali: saat dependensi berubah, node dependen akan selalu dibangun ulang dari awal, sekalipun ada algoritma yang lebih baik yang akan mengubah nilai lama node berdasarkan perubahan tersebut. Beberapa contoh yang akan berguna:

  • Penautan inkremental
  • Saat satu file .class berubah dalam .jar, secara teori kita dapat mengubah file .jar, bukan mem-build-nya dari awal lagi.

Alasan Bazel saat ini tidak mendukung hal-hal ini secara berprinsip (kami memiliki beberapa dukungan untuk penautan inkremental, tetapi tidak diterapkan di Skyframe) adalah dua kali lipat: kami hanya memiliki peningkatan performa yang terbatas dan sulit untuk menjamin bahwa hasil mutasi tersebut sama dengan build ulang bersih, dan build nilai Google yang sedikit demi bit dapat diulang.

Hingga saat ini, kita selalu bisa mencapai performa yang cukup baik hanya dengan mengurai langkah build yang mahal dan mencapai evaluasi ulang parsial dengan cara tersebut: ini membagi semua class dalam aplikasi menjadi beberapa grup dan melakukan dexing secara terpisah. Dengan demikian, 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 melakukan build:

  • FileStateValue. Hasil lstat(). Untuk file yang ada, kami juga menghitung informasi tambahan untuk mendeteksi perubahan pada file tersebut. Node ini merupakan node level terendah dalam grafik Skyframe dan tidak memiliki dependensi.
  • FileValue. Digunakan oleh apa pun yang peduli dengan isi aktual dan/atau jalur file yang diselesaikan. Bergantung pada FileStateValue yang sesuai dan symlink yang perlu di-resolve (seperti FileValue untuk a/b memerlukan jalur a yang di-resolve dan jalur a/b yang di-resolve). Perbedaan antara FileStateValue bersifat penting karena dalam beberapa kasus (misalnya, mengevaluasi glob sistem file (seperti srcs=glob(["*/*.java"])) konten file tidak benar-benar diperlukan.
  • DirectoryListingValue. Pada dasarnya, ini adalah hasil dari readdir(). Bergantung pada FileValue terkait yang terkait dengan direktori.
  • PackageValue. Menunjukkan versi file BUILD yang telah 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 terkait berada, ConfiguredTargetValues dependensi langsung, dan node khusus yang mewakili konfigurasi build.
  • ArtifactValue. Menyatakan file dalam build, baik itu artefak sumber atau output (artefak hampir setara dengan file, dan digunakan untuk merujuk ke file selama eksekusi langkah-langkah build yang sebenarnya). Untuk file sumber, class ini bergantung pada FileValue node terkait, untuk artefak output, bergantung pada ActionExecutionValue tindakan apa pun yang menghasilkan artefak.
  • ActionExecutionValue. Mewakili eksekusi tindakan. Bergantung pada ArtifactValues file inputnya. Tindakan yang dijalankan saat ini terdapat dalam sky key-nya, yang bertentangan dengan konsep bahwa skykey harus berukuran kecil. Kami sedang berupaya mengatasi perbedaan ini (perhatikan bahwa ActionExecutionValue dan ArtifactValue tidak akan digunakan jika kita tidak menjalankan fase eksekusi di Skyframe).