<div dir="ltr">Ah, the last part there is a nice algorithm. It determines the intended merge order when patches are submitted to the queue, then runs tests for multiple patches in parallel. So, assuming most patches pass their tests, the rate at which patches can land is limited only by how fast it can run parallelized tests, and as long as the queue isn't congested, each patch lands roughly as soon as its tests succeed.<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jan 2, 2016 at 10:06 PM, Nick Coghlan <span dir="ltr"><<a href="mailto:ncoghlan@gmail.com" target="_blank">ncoghlan@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 3 January 2016 at 15:08, Guido van Rossum <<a href="mailto:guido@python.org">guido@python.org</a>> wrote:<br>
> In general I like the idea of a commit queue; we built one at Dropbox which<br>
> has been very useful in keeping our master green. Based on this experience,<br>
> I note that testing each commit before it's merged limits the rate at which<br>
> commits can be merged, unless you play some tricks that occasionally<br>
> backfire. Taking homu's brief description literally, it would seem that if<br>
> it takes e.g. 10 minutes to run the tests you can't accept more than 6<br>
> commits per hour. I don't recall how long Python's tests take, but I I<br>
> wouldn't be surprised if it was a lot longer than 10 minutes.<br>
<br>
</span>It's less than 10 minutes on a modern laptop (although I admit I<br>
haven't done a -uall run in a while), but longer than that on the<br>
Buildbot fleet (since some of the buildbots aren't particularly fast).<br>
<span class=""><br>
> Now, you can reduce the running time by parallelizing test runs, and Python<br>
> doesn't see that many commits typically, so perhaps this isn't a problem.<br>
> But for larger projects it may be -- it definitely was a big concern at<br>
> Dropbox, and I recall hearing about some astronomical stats from the<br>
> Chromium project.<br>
><br>
> At Dropbox we solved this by not literally testing each commit after the<br>
> last one has been merged. Instead, for each commit to be tested, we create a<br>
> throwaway branch where we merge the commit with the current HEAD on the<br>
> master branch, test the result, and then (if the tests pass) re-merge the<br>
> commit onto master. This way we can test many commits in parallel (and yes,<br>
> we pay a lot of money to Amazon for the needed capacity :-).<br>
<br>
</span>As far I'm aware, OpenStack's Zuul mergebot is currently best in class<br>
at solving this problem:<br>
<br>
* while a patch is in review, they run a "check" test against master<br>
to see if the change works at all<br>
* to be approved for merge, patches need both a clean check run and<br>
approval from human reviewers<br>
* once patches are approved for merge, they go into a merge queue,<br>
where each patch is applied atop the previous one<br>
* Zuul runs up to N test runs in parallel, merging them in queue order<br>
as they finish successfully<br>
* if any test run fails, any subsequent test runs (finished or not)<br>
are discarded, the offending patch is removed from the merge queue,<br>
and Zuul rebuilds the queue with the failing patch removed<br>
<br>
It's a lot like a CPU pipeline in that regard - when everything goes<br>
well, patches are merged as fast as they're approved, just with a<br>
fixed time delay corresponding to the length of time it takes to run<br>
the test suite. If one of the merges fails, then it's like branch<br>
prediction in a CPU failing - you have to flush the pipeline and start<br>
over again from the point of the failure.<br>
<br>
Cheers,<br>
Nick.<br>
<div class="HOEnZb"><div class="h5"><br>
--<br>
Nick Coghlan   |   <a href="mailto:ncoghlan@gmail.com">ncoghlan@gmail.com</a>   |   Brisbane, Australia<br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature">--Guido van Rossum (<a href="http://python.org/~guido" target="_blank">python.org/~guido</a>)</div>
</div>