목차
도착 순서의 제약을 풀어낸 SubmitQueue의 BLRD (2023-08)
원문 정보
- 원문: Bypassing Large Diffs in SubmitQueue
- 매체 · 게시일: Uber Engineering Blog · 2023-08-31
- 저자: Zhongpeng Lin(Staff Software Engineer, Developer Platform), Matthew Williams(Staff Software Engineer, Developer Platform, SubmitQueue 테크 리드)
- 원문 내용을 바탕으로 재구성한 요약입니다.
검증을 끝내고도 기다려야 했던 변경
자기 빌드와 테스트를 마치고도 main에 반영되기까지 최대 두 시간을 기다리는 변경이 있었습니다. 앞에 큰 diff가 들어온 경우입니다. 많은 패키지에 영향을 주는 변경 하나를 검증하는 동안, 뒤따르는 작은 변경들은 검증을 끝내고도 기다려야 했습니다.
우버의 모노레포에서 main은 언제나 빌드되고 모든 테스트를 통과하는 녹색 상태여야 합니다. 하루 수천 건의 변경이 들어오는 환경에서 main이 깨지면 원인을 찾는 일부터 어려워집니다. main이 정상이어야 개발자는 로컬이나 CI에서 만난 오류가 자기 변경에서 비롯됐다고 확신하고, main에서 계속 배포할 수 있습니다.
그래서 SubmitQueue는 변경을 반영하기 전에 영향받는 모든 패키지를 빌드하고 테스트합니다. 하나씩 처리해서는 변경이 쌓이는 속도를 따라가지 못합니다. GitHub의 merge queue나 GitLab의 merge train처럼, 앞선 변경의 결과를 추측해 CI를 병렬로 실행하는 시스템이 필요한 이유입니다.
검증을 병렬로 돌려도 반영 순서에는 제약이 있었습니다. SubmitQueue의 충돌 분석기는 두 변경이 영향을 주는 패키지 집합을 비교합니다. 겹치는 패키지가 없으면 독립인 변경으로 보고 어느 순서로든 반영하지만, 하나라도 겹치면 충돌하는 변경으로 취급합니다. 이때는 반영하거나 거절하는 결정을 도착 순서대로 내렸습니다. 많은 패키지를 건드리는 큰 diff는 뒤따르는 거의 모든 변경과 충돌하고 검증도 오래 걸리므로, 뒤의 변경들이 기다리는 시간까지 길어집니다.
여기서 충돌은 Git 머지 충돌과 다릅니다. Git 머지 충돌이 있는 변경은 SubmitQueue가 검증 전에 거절하므로, 이후의 설명은 그런 충돌이 없는 변경을 전제로 합니다.
우버는 이전 글에서 이 기다림을 줄인 과정을 소개했습니다. 처음에는 큰 diff를 미국 업무 시간 밖에 반영하도록 제한했지만, 좋은 해법은 아니었습니다. 이후 CI 빌드 시간을 줄이자 큰 diff가 큐에 머무는 시간도 짧아졌고, 별도 정책은 필요 없어졌습니다.
한동안은 통했습니다. 그러나 2년 사이 한 달 중 가장 큰 변경이 영향을 주는 루트 타깃 수는 2.5배가 되었고, 변경 속도도 2배 넘게 늘었습니다. 큰 diff도 그에 비례해 많아진 상황입니다. 2021년 하반기에 줄였던 빌드와 테스트 시간이 다시 늘면서 대기 시간은 2021년 5월 수준으로 돌아갔습니다. 빌드 머신을 더 투입하는 방법에도 한계가 있었습니다. 병렬화 오버헤드 때문에 비용은 갈수록 커지고 추가로 얻는 효과는 줄어듭니다.
A를 기다리지 않고 반영하는 B
기다림을 줄일 실마리는 SubmitQueue가 이미 수행하던 검증에 있었습니다. 아직 끝나지 않은 변경의 성공과 실패를 각각 가정하고, 뒤따르는 변경을 미리 시험하는 추측 실행입니다. 이 가능한 경로들을 나타낸 것이 추측 트리입니다.
서로 충돌하는 C1, C2, C3이 차례로 도착했다고 가정하겠습니다. C3이 들어왔을 때도 C1과 C2의 빌드가 끝나지 않았다면, SubmitQueue는 앞선 변경의 결과에 맞춰 C3의 빌드를 나눕니다.
| C1의 결과 | C2의 결과 | C3을 포함한 빌드 |
|---|---|---|
| 거절 | 거절 | B3 |
| 거절 | 반영 | B2,3 |
| 반영 | 거절 | B1,3 |
| 반영 | 반영 | B1,2,3 |
B1이 끝나면 그 결과에 따라 B2와 B1,2 중 하나를 기다리고 다른 쪽은 취소합니다. C2의 결과까지 나오면 C3의 반영 여부를 판정할 빌드도 하나로 정해집니다. 여러 가능성을 미리 검증해 시간을 벌지만, 어느 결과를 채택할지는 앞선 변경이 끝나야 알 수 있는 방식입니다.
그런데 가능한 경로가 모두 같은 결과를 냈다면 이야기가 달라집니다. 큰 diff A 뒤에 충돌하는 변경 B가 온 경우를 보겠습니다. main 위에서 A를 검증하는 일을 A|main으로 쓰면, B에는 A의 결과에 따른 검증이 필요합니다. A가 성공할 경우를 위한 B|main+A와 실패할 경우를 위한 B|main입니다.
A|main은 아직 실행 중인데 B의 검증은 양쪽 모두 성공할 수 있습니다. A가 성공하든 실패하든 B를 반영한다는 판정은 같습니다. 기존 SubmitQueue에서는 이런 B도 A를 기다렸습니다. BLRD(Bypassing Large Diffs)는 B를 먼저 반영하도록 이 순서를 바꿉니다.
남은 문제는 나중에 반영될 A입니다. A가 실패하면 main+B만 남으므로 이미 성공한 B|main 검증으로 충분합니다. A도 성공하면 최종 상태는 main+B+A가 됩니다. 기존에 시험하던 main+A+B와는 반영 순서가 다릅니다. 이 새 경로에 필요한 모든 타깃과 정확한 버전까지 기존 검증으로 확인할 수 있어야, A를 다시 빌드하고 테스트하지 않고도 안전하게 반영할 수 있습니다.
BLRD 도입 뒤 짧아진 대기 시간
우버는 이 조건을 증명한 뒤 2023년 5월 말 Go 모노레포의 SubmitQueue에서 BLRD를 켰습니다. 6월의 P95 대기 시간은 4월보다 74% 줄었습니다. 빌드와 테스트 시간에는 큰 변화가 없었습니다.
2022년 1월과 비슷한 대기 시간입니다. 당시에는 큰 diff의 빌드와 테스트가 20% 빨랐고 월간 변경도 60% 적었는데, BLRD는 빌드와 테스트 시간을 크게 줄이지 않고 그때와 비슷한 대기 시간을 얻었습니다.
반영 순서가 달라도 같은 타깃 해시
안전성을 따질 때는 타깃 이름만 맞아서는 부족합니다. 검증할 버전도 같아야 합니다. 타깃의 버전은 입력 파일과 의존 타깃들의 해시로 정해지며, 증명은 이 해시가 타깃 상태에 영향을 주는 정보를 모두 담는다는 전제에서 출발합니다. 빌드는 같은 입력과 설정에서 같은 출력을 내는 hermetic 빌드이고, 테스트 결과도 실행할 때마다 같아야 합니다.
이 조건에서는 타깃이 현재 상태에 도달한 순서가 결과를 바꾸지 않습니다. A 뒤에 B를 적용한 타깃 버전을 T_AB, B 뒤에 A를 적용한 버전을 T_BA라고 쓰면 둘의 해시는 같습니다. 따라서 main+A+B에서 검증한 버전을 main+B+A에서도 사용할 수 있습니다. 확인할 것은 필요한 버전이 기존 검증에 빠짐없이 들어 있는지입니다.
CT(X|Y)는 Y 위에 X를 적용할 때 해시가 바뀌는 타깃 집합입니다. CT(A)와 CT(B)는 각각 main 위에 A와 B를 적용한 경우를 뜻합니다. B가 먼저 도착했다면 SubmitQueue는 CT(B)와 CT(A|B)를 검증했을 것입니다. 실제로는 A가 먼저 왔으므로 CT(A), CT(B), CT(B|A)를 검증합니다.
CT(B)는 어느 순서에서든 포함됩니다. 따라서 B 뒤에 A를 반영할 때 필요한 CT(A|B)가 기존 검증으로 다뤄지는지 보이면 됩니다. 정리 1은 그 포함 관계를 CT(A|B) ⊆ CT(A) ∪ CT(B) ∪ CT(B|A)로 나타냅니다.
B 뒤에 A를 적용하면서 바뀌는 타깃 T를 골라 보겠습니다. A만 적용했을 때는 T가 바뀌지 않았다면, B가 T를 추가했거나 T 또는 그 이행 의존성에 의존성을 추가한 경우입니다. 이 T는 CT(B)에 들어갑니다. 그런데 CT(B|A)에는 없으려면 A가 T를 삭제했거나 의존성을 제거했어야 합니다. T를 삭제했다는 가정은 B 뒤에 A를 적용한 결과에 T가 있다는 조건과 모순이고, 의존성을 제거했다는 가정은 A만으로 T가 바뀌지 않았다는 조건과 모순입니다. 결국 CT(B|A)에 필요한 최종 버전이 있으며, 그 버전이 통과하면 순서를 바꾼 T_BA도 통과합니다.
B만 적용했을 때 T가 바뀌지 않는 경우에는 B 뒤에 A를 적용한 버전이 A만 적용한 버전과 같습니다. CT(A)의 검증으로 충분한 경우입니다. A를 적용한 뒤 B를 적용해도 T가 바뀌지 않는 경우 역시 A만 적용한 버전과 최종 버전이 같으므로 CT(A)에 필요한 검증이 들어 있습니다.
이 포함 관계 덕분에 CT(B)와 CT(B|A)가 모두 통과하면 A의 검증이 끝나기 전에 B를 반영해도 됩니다. A의 결과는 나중에 받아도 됩니다. A를 B 앞에 반영할지 판단하던 검증이 B 뒤에 반영할 때도 유효하므로, A를 위한 추가 작업은 없습니다.
전제가 깨지는 경우도 있습니다. hermetic하지 않은 빌드나 불규칙하게 실패하는 flaky 테스트에서는 해시가 같아도 한 머신에서 통과한 타깃이 다른 머신에서는 실패할 수 있습니다. BLRD가 이 문제를 개선하거나 악화시키지는 않습니다. 도착 순서를 지켜 반영하더라도 검증 자체가 불안정한 경우이며, 우버는 별도 작업으로 대응하고 있습니다.
A와 C 사이에 생긴 거품
변경이 많아져도 판정 기준은 같습니다. 해당 변경의 추측 트리에서 모든 경로를 검증했고 결과가 전부 같으면, 앞선 충돌 변경을 기다리지 않고 반영하거나 거절할 수 있습니다. 앞선 변경이 하나씩 끝날 때까지 기다리는 대신, 어느 결과가 나와도 판정이 달라지지 않는지 확인하는 방식입니다.
A와 B 뒤에 도착한 C가 먼저 검증을 마쳤다면 CT(C|AB), CT(C|A), CT(C|B), CT(C)가 모두 통과해야 합니다. A와 B가 모두 성공하는 경우에는 둘을 순서대로 반영하는 일을 하나의 변경 AB를 반영하는 일로 묶어 생각합니다. 정리 1을 적용하면 정리 2, CT(AB|C) ⊆ CT(A) ∪ CT(B|A) ∪ CT(C) ∪ CT(C|AB)를 얻습니다. C가 먼저 반영되어도 A와 B에는 기존 검증만 있으면 됩니다. A나 B 중 하나만 성공하면 앞서 증명한 한 변경을 건너뛰는 경우로 줄어들고, 둘 다 실패하면 C만 반영됩니다. 같은 추론을 이어 가면 셋 이상의 변경도 건너뛸 수 있습니다.
한 변경을 여러 변경이 차례로 건너뛰는 경우도 가능합니다. B가 A를 건너뛰어 반영된 뒤에는 B가 포함된 상태를 새 main으로 보면 됩니다. 뒤따르는 C는 CT(C|AB)와 CT(C|B)가 통과하면 A보다 먼저 반영됩니다. 도착 순서는 A, B, C인데 반영 순서는 C, B, A가 되는 경우에도 원리는 같습니다. C가 먼저 A와 B를 건너뛴 뒤, B는 CT(B)와 CT(B|A)가 통과했다면 A를 건너뛸 수 있습니다.
큐 중간에 빈자리가 생겨도 이어지는 논리입니다. A, B, C, D가 기다리다가 B만 A를 건너뛰어 반영되면, 아직 남아 있는 A와 C 사이에 원문이 부르는 ‘거품’이 생깁니다. 이제 D가 A와 C를 건너뛰려면, 이미 반영된 B는 성공한 것으로 고정하고 나머지 경로를 확인합니다. 필요한 검증은 CT(D|B), CT(D|AB), CT(D|BC), CT(D|ABC)입니다. B가 포함된 상태를 새 main으로 두고 정리 1을 거듭 적용하면, 나중에 A와 C를 반영할 때 필요한 CT(AC|BD)도 기존 검증들의 합집합에 포함됩니다. A나 C가 실패하는 경우는 앞서 다룬 더 작은 경우로 돌아갑니다. 거품이 더 많아져도 같은 추론이 이어집니다.
실패 판정도 앞선 변경을 기다릴 이유가 없습니다. 모든 추측 경로가 실패했다면 그 변경을 먼저 거절해도 앞선 변경에는 영향이 없습니다. 이미 그 변경을 건너뛰어 반영된 변경들은 거절 경로까지 검증한 상태입니다. 아직 뒤에 남은 변경들은 거절된 변경이 반영된다고 가정한 경로를 지우면 됩니다.
검증 시간을 예측할 다음 모델
모든 경로를 검증하는 방식은 트리가 깊어질수록 비싸집니다. 충돌하는 변경이 하나 추가될 때마다 빌드에 해당하는 트리 노드 수가 두 배로 늘어납니다. 건너뛸 변경이 많아질수록 필요한 검증량도 지수적으로 커지는 문제입니다.
원래 SubmitQueue 논문은 확률 모델로 모든 경로를 추측하는 비용을 피하자고 제안했습니다. 하지만 이 모델이 예측하는 것은 변경이 수락될 확률뿐입니다. 큰 diff가 실패할 가능성이 높다고 보고 실패 경로만 시험하면, 뒤따르는 변경은 그 큰 diff를 건너뛸 수 없습니다. BLRD에는 큰 diff가 성공하는 경로의 검증 결과도 있어야 합니다.
그래서 다음 과제로 남은 것은 빌드와 테스트에 걸릴 시간까지 예측하는 모델입니다. 오래 걸릴 변경에는 모든 경로를 추측해 뒤따르는 변경이 건너뛸 기회를 주고, 나머지는 가능성이 높은 경로만 시험해 비용을 줄이려는 구상입니다. 어느 변경이 성공할지 예측하는 데서 더 나아가, 어느 변경을 기다리는 데 오래 걸릴지도 알아야 합니다.
원문 수치와 증명의 포함 관계
| 항목 | 값 |
|---|---|
| 큰 diff 직후 변경의 최대 대기 | 약 2시간 |
| 2년간 최대 변경의 영향 루트 타깃 | 2.5배 증가 |
| 같은 기간 변경 속도 | 2배 이상 증가 |
| BLRD 활성화 시점 | 2023년 5월 말(Go 모노레포) |
| P95 대기 시간 | 6월이 4월보다 74% 감소 |
| 비교 기준 | 2022년 1월, 큰 diff 빌드·테스트 20% 빠름, 월간 변경 60% 적음 |
| 추측 트리 크기 | 충돌 변경이 하나 늘 때마다 빌드 수 2배 |
| 정리 1 | CT(A|B) ⊆ CT(A) ∪ CT(B) ∪ CT(B|A) |
| 정리 2 | CT(AB|C) ⊆ CT(A) ∪ CT(B|A) ∪ CT(C) ∪ CT(C|AB) |