Kotlin 云端差分緩存技術
本文由字節跳動 Buildinfra 團隊出品。
在我們的工程上線 Monorepo 全源碼后，Kotlin 編譯成了整個編譯中最耗時的步驟，全源碼過程中大量的 BuildCache Miss 導致我們的編譯數據落后原來多倉二進制時代很多，且業界沒有相關的解決方案。本篇文章我們來具體闡述下 BuildInfra 團隊自研的解決方案 - Kotlin 云端差分方案的原理和技術實現。
一、Monorepo 中的噩夢
在 2022-2023 年，我們的頭部業務開始慢慢地從原來的多倉二進制模式，遷移到全新 Monorepo 方案。
在多倉二進制時代，由于 Maven 的加持，大部分時候我們的都不需要直接編譯代碼，而是復用 Maven 的『緩存』。
在工程進入 Monorepo 時代之后，我們花了大量的精力建設 BuildCache，來試圖抹平 Monorepo 與二進制的構建速度差異，但遺憾的是，盡管我們已經做了很多的努力，但由于 Gradle 脆弱的 BuildCache 設計，導致很多時候改動一行代碼就會全局 miss，不得不重新編譯一遍所有的源碼。這很不環保（
- 本地編譯：首次編譯/更新代碼/切分支等場景，非常容易觸發整個工程的重新編譯，動輒 20min+。
- CI 編譯：從原來多倉二進制時代的 25min 劣化到了 40min+
并且，90 分位的構建劣化更是飆升到不可控的地步，它直接決定了本地開發、CI 合碼的體驗。
在可預見的將來，隨著代碼的快速增長、更多子倉的合入，僅靠 BuildCache 已經完全無法支撐大型 Monorepo 工程的開發。
二、分析
如果想優化 Kotlin 的全量編譯，如果從計算機通用優化角度來看，不外乎以下幾種方案：
- 更高效的實現
- 并發
- 緩存
更高效的實現：語言編譯是一個龐大且復雜的系統，涉及前后端編譯，目前針對前后端編譯流程進行優化實施起來難度較大，是一個長期且艱巨的任務。但它并不和其他優化方案有沖突。
并發：如果是相互之間沒有復雜依賴關系的多 Module，那么 Gradle 已經保證了模塊之間的并行度；只要你的項目依賴足夠 flat，那么就可以充分利用計算機并發資源，在 CI 場景會獲得非常大的提升，所以從工程角度可以進行依賴的優化來提升并行度。但這也不是一個通用的方案，非常依賴于業務方的改造。
緩存：Kotlin 目前使用的是 Gradle 的緩存，眾所周知，Gradle 為了保證正確性，有著一套極其嚴格的 Cache key 生成策略，很多「可能」不影響 kotlin 編譯正確性的變化（比如編譯插件的 classpath）卻會讓整個 BuildCache 崩盤，全部 Task 全部 Cache Miss。
在 kotlin 中，不僅是 classpath 這些變動會導致 cache miss，kotlin 的 sourceset（即源碼）也會作為 cache key 的計算輸入。這意味著，只要代碼里有一個字符不一樣，就會導致 cache miss，整個模塊就需要重新編譯，那么這塊是否有優化空間呢？
綜合來看，從緩存角度入手，可以以比較低成本來實現較大的收益。
為此，我們提出了一套創新性的方案：
通過云端模糊匹配緩存來將全量編譯轉化為增量編譯，來減少全量編譯的耗時。
三、核心原理
我們通過改造 Kotlin Gradle Plugin 入手，當 Kotlin Task 由于各種原因不能命中 Build Cache 時，就會 fallback 到我們的『Kotlin 差分編譯系統』。通過云端模糊匹配緩存來將全量編譯轉化為增量編譯，來將本來動輒 10min+ 的全量編譯轉化成 10s 內的增量編譯。
云端緩存模糊匹配
常規編譯構建緩存方案如 Gradle Build Cache 采用的是 kv 一對一匹配。
對于 Kotlin 來說，即通過對源碼文件、依賴 Jar 包，編譯參數等信息算出一個緩存 key 之后，唯一匹配出一個緩存。當匹配到緩存后，緩存包的內容就是 Kotlin 的最終產物，然后就可以跳過 Kotlin Task，直接進入下一步。
由于精確匹配需要達成的條件較多，比如只要修改了一個 .kt文件，就無法匹配到緩存。
因此可以考慮實現一套模糊匹配的機制：
- 先根據一些必要參數匹配一組可能符合要求的緩存
- 然后從這一組緩存中尋找與當前場景最接近的緩存包來進行使用
全量轉增量
最接近的緩存包，也只是最接近的，是不能直接拿來用的。
那我們是不是可以將這個緩存包對應的源碼與當前源碼做 diff，然后將全量轉增量呢？
比如，某個模塊有 A.kt，B.kt，我們基于某個 Commit 打出來了一個云端緩存包。
有一天，我們新增了一個 C.kt，改動了 B.kt，這時候，我們找到之前打出來的緩存包，對他們對應的源碼做一次 diff，那么我們可以得到這組變動：
[
changed: ["B.kt"],
added: ["C.kt"]
]我們只需要將這個 Diff 輸入給 kotlin 編譯器，kotlin 就會自動幫我們完成耗時較低的增量編譯。
基于 #1 和 #2 的兩個核心原理，我們設計了一套『Kotlin 差分編譯系統』，整體架構圖如下，有四個重要的角色：
- 客戶端：Hook Kotlin Compiler，負責將全量編譯轉為增量編譯。
- 服務端：基于客戶端的請求匹配最佳緩存。
- 種子節點：基于 develop 分支，定時打包，上傳緩存。
- 分布式緩存：我們內部使用的緩存系統，主要通過 K-V 的形式來存儲我們的緩存包。
圖片
四、方案詳解
客戶端方案
客戶端的核心邏輯：對 kotlin 編譯流程進行 hook，構造/加載緩存包，將全量編譯轉換為增量編譯，轉換的關鍵在于增量編譯與全量編譯的差異部分：
- 增量編譯環境中有上次編譯好的編譯產物、增量追蹤文件（符號引用關系，abi 信息等）。
- 增量編譯相比于上次編譯有哪些輸入文件產生了修改的文件 diff 信息。
圖片
緩存包內容
為了能夠在全量編譯時順利還原出一個正確的增量編譯現場，要求加載的緩存包中應該包含的內容有:
- 編譯產物 （減少不必要的源文件重新編譯耗時）
- metadata 包括 kt 、java、layout 文件等 源文件信息，包括這些文件在項目中的相對路徑以及 hash 值，在還原編譯現場時，根據這些內容還原為源文件的 diff 信息 (
add,remove,modify) - 編譯器信息：編譯器參數,編譯器 JAR 包的 hash 信息等。
- 增量中間產物：涉及到一系列追蹤文件，這些文件包含了kotlin 編譯器在增量編譯時 用來計算
dirty file(需要重新編譯的源文件）的關鍵信息，包括符號引用關系、abi 信息、源文件與編譯產物的對應關系等。
圖片
緩存匹配
如前文中的『核心原理』章節所描述，我們采取以下方案來進行緩存的匹配。
- 先根據一些精準參數匹配一組可能符合要求的緩存
- 然后從這一組緩存中尋找與當前場景最接近的緩存包來進行使用
其中以下參數會參與精確參數（unique_hash）的計算
- Kotlin 版本
- Kotlin Compiler Plugin (KCP)
- Kotlin 編譯器參數
我們通過將這些參數組合到一起組成一個 hash 值：unique_hash。
在之后的流程中，會使用 unique_hash 來篩選出一組緩存。我們再通過服務端的策略來篩選出最佳的緩存。
圖片
編譯流程 hook
拿到了緩存包后，我們就可以進行緩存包的復用了。但是我們在上一個流程中匹配到的僅僅是最優緩存，但是這個緩存和我們當前的包還存在 diff，比如代碼、模塊依賴信息 等的差異。
我們需要計算出拉到的緩存包和當前編譯的 diff，然后將 diff 傳給 kotlin 編譯器，并將全量編譯轉成增量編譯。
為了能夠實現增量編譯的轉換，需要在編譯流程的三個階段進行 hook
- 編譯前執行前解析模塊依賴信息。
- 在提交編譯參數到編譯器執行前，匹配、下載、校驗、加載緩存包，將全量編譯參數轉換為增量編譯參數。
- 編譯完成后構造并上傳緩存包。
圖片
其中，最核心的 Hook 點在于：將全量編譯轉化成增量編譯。
internal fun CallCompilerAsyncOpt.callCompilerAsyncOpt(
....
) {
val icEnv = IncrementalCompilationEnvironment(
changedFiles,
classpathChanges,
workingDir ,
...
)
val hookedIcEnv = hook(icEnv)
val environment = GradleCompilerEnvironment(
incrementalCompilationEnvironment = hookedIcEnv,
outputFiles,...
)
optRunJvmCompilerAsync(..., source, args, environment , ... )
}我們會 Hook KotlinCompile 中的 callCompilerAsync 方法，將原來的全量 Env 轉換成增量 Env。增量的 InputChanges 來源于我們的緩存包和編譯的 diff (源碼、依賴的變更等)。
而這個關鍵的全量轉增量 Hook 步驟為：
- 匹配下載緩存：為了能夠匹配到最接近的緩存包，實現最佳增量編譯效率，需要對這些參數進行比較：
- 根據 metadata 中 java/kotlin/layout 文件的 hash 比較源碼文件的 diff (其中包括 layout xml 是因為 KAE 會根據 layout 進行 kotlin 代碼插樁）
- 利用 kotlin 1.7+ 的
classpath-snapshot.bin計算依賴模塊依賴信息的 abi diff
- 校驗加載緩存: 基于緩存包中的 metadata ，結合編譯產物、編譯中間產物等，將對應信息加載到對應位置。
- 構造增量編譯參數: 將加載的緩存包中的相對路徑轉換為絕對路徑，用絕對路徑的 diff 信息等構造出可用的增量 Env , 并提交給 Kotlin Compiler
預期之外的問題
理論上來講，如果 kotlin 編譯器是能保證增量編譯是完全不出錯的，那么我們的方案肯定不會引入穩定性的問題。
但是這樣的期待或許過高。我們的方案是基于 Kotlin 1.7.21 進行開發的，kotlin 在 1.7+ 引入了新的 kotlin 增量編譯方案，還在一個相對不穩定的階段。實際上，我們也在上線前后遇到了各種奇怪的問題。經過長時間的 debug 和翻閱源碼后得到了解決，目前在抖音項目上已經趨于穩定。
跨端緩存復用問題
問題表現為：OSX 復用 ci 種子節點打包的緩存時，對于部分刪除的源代碼文件，并沒有將其對應的編譯產物刪除
通過一系列的排查發現，該問題是 Kotlin Compiler 自身的 bug ，且在高版本進行了修復，bug 來源于 kotlin 的增量編譯中間產物中，用于追蹤源碼文件與編譯產物關系的信息異常，在涉及到大小寫敏感不一致的系統時，無法正常刪除編譯產物。
解決方案: 對高版本的修復 commit 進行了 cherry-pick
kotlin 修復 https://github.com/JetBrains/kotlin/commit/be71d8841ebc22c79bb6b4bc6f3ad93c147ba9c0
大小寫敏感問題
由于 OSX 不是一個大小寫敏感的操作系統，這意味著，在一個文件夾中，不能同時存在去掉大小寫后字符一樣的兩個文件。比如：
圖片
但是這個行為在 Linux 系統上是允許的。
我們的遇到的問題是，項目中不同文件夾中有兩個包名叫 com.xxx.legoImp ，一個叫com.xxx.legoimp 。這兩個包名會在 Linux 種子節點上進行 Jar 包壓縮，在 mac 上進行解壓 ，由于 Linux 不是 Case Sensitive 的系統，所以 jar 包中，他倆會同時存在，但是在 mac 上解壓時，mac 會自動合并了這兩個包，并且轉換成小寫。這樣就會在運行時崩潰，找不到這個包名。
解決方案：我們提供了一個類似的包名大小寫檢測，幫助業務提前暴露問題，并進行代碼的整改。
方案性能極致優化
加速緩存解壓
在最初的緩存包壓縮中，采用的是 Java ZipFile 中默認的壓縮算法，上線后發現有較多模塊的緩存解壓時間較長，后續參考了Gradle build-cache 方案，將壓縮算法修改為 lz4，大大降低了解壓縮的時間。
降低緩存淘汰率
在本方案中，緩存遠端存儲在我們的分布式緩存服務中，由于分布式緩存空間有限(2TB)，超過緩存空間時會根據 LRU 淘汰最近未使用的緩存，這樣就會導致緩存命中率下降，而由于在抖音項目中，生產緩存的種子節點會在每個 MR 合入后進行緩存打包，每次全量打包緩存時，緩存包約1GB+ , 為了減少不必要的緩存上傳，采取了兩個方案:
- 與 build-cache 進行關聯，如果種子節點打包時命中 build-cache ，將 kotlin 緩存與
build-cache進行關聯，而不是重復上 kotlin 緩存 - 計算緩存包內容 hash ，如果存在相同的緩存包，將他們關聯到一起，而不是重復上傳緩存。
服務端策略
區別于傳統的 Build Cache 服務端的簡單 K-V 存儲，我們的服務端需要幫助客戶端去存儲產物、匹配產物、選擇最佳產物。客戶端和服務端的通信時序圖如下：
圖片
其中，服務端最核心的邏輯在于匹配最佳產物。
每一個 unique hash 都會對應一組產物，我們要從這一組產物里找到一個最優解。
最優解的定義是：這個產物離我們當前的編譯較為接近。我們為這個『接近』，定義了一個記分制度。
data class Diff(val added: List<String>,
val removed: List<String>,
val modified: List<String>)
fun diffScore(): Int {
return this.diff.removed.size * 3 +
this.diff.modified.size * 2 +
this.diff.added.size
}每個產物和當前編譯都會產生一個 diff，diff 里有 added、removed、modified。
我們定義一個函數 diffScore，remove 記三分，modified 記兩分，added 記一分。
之所以按照這樣的系數，是因為 removed 大概率會引起很多底層依賴的重新編譯，所以我們需要盡可能地減少 removed 的代碼，added 的代碼一般不會引起其它代碼重新編譯，所以我們可以記為一分。modified 介于兩者之間，記兩分。
那么，我們的核心的邏輯就變成了：從一組緩存里，找到 diffScore 最少的產物。
但是因為我們的 unique hash 對應的 hash 生成并不復雜，一般來說，除非是升級 kotlin 版本，其它情況這個 unique hash 基本不會變，所以這個緩存的量可能會很大，我們不可能實現找到所有的緩存，并且進行 diffScore 的比較。我們需要篩選出一定范圍內的緩存。
首先，我們的所有的產物生成都是在主干分支上。
那么意味著，對于 feature 分支，與其代碼最接近的 commit 應該是圖中的 base commit。
圖片
因為成本的原因，種子任務可能并不會在主干分支的每個節點都打緩存包，可能是定時打包。那么意味著不是所有的 merge commit 都有緩存包。
所以，我們找到這個 commit 的前后一天時間內的 commit。并和表中的所有產物進行取交集。
圖片
最后得到所有黃色的點。（黃色的點是打了緩存包的 merge 節點）
我們將所有黃色的點對應的 MetaData 與當前 commit 的 MetaData 進行 diff。
取一個 diffScore 最少的節點，作為最終的產物。
val bestArtifact = artifacts.minOf {
it.diffScore()
}這樣我們就可以認為它是和當前 commit 最接近的 commit。對應的產物對于客戶端來說，轉增量編譯的風險最小、速度最快。
五、上線收益
目前項目上線了大部分的字節 Monorepo 項目，穩定運行了半年有余。期間也修復了 kotlin 1.7 上的若干官方增量編譯相關的 bug，最后取得了較為理想的收益。
抖音從二進制演進到 Mopnorepo 后，Kotlin 部分的編譯時間劣化超過 10m+，我們通過本文的方案，將劣化的部分基本抹平，90 分位下降 60%，大幅提升了開發的體驗和 CI 合碼效率。
六、總結
本文主要闡述了 Kotlin 云端差分方案的技術原理。
實現超大型工程 Monorepo 全源碼的研發模式，僅靠 BuildCache 是無法實現的，Kotlin 云端差分方案對于全源碼起著不可或缺的作用。
通過模糊匹配緩存的方式將全量編譯模擬成增量編譯的思想，可能在其他端上比較容易實現或者就是標準方案，但目前 Android CI 構建領域均采用 clean 編譯，無法復用構建中間產物。該方案的出現也有望實現思想的復用，運用到所有『類似』的任務中，比如 Java Compile、Transform、Dex 等，只要它本身是支持增量、編譯冪等特性的，都可以復用這套方案，從而進一步提升 Android 的構建效率。
在研究云端差分方案期間，我們積累了大量的 Kotlin 編譯器相關的知識，為我們平時排查 kotlin 疑難問題提供了非常多的技術儲備，也發現了很多 kotlin 官方的 bug 和設計上的缺陷，我們也會在將來修復后回饋 kotlin 社區。
歡迎對編譯構建、Kotlin相關技術感興趣的小伙伴找我們進行技術交流與討論！
