{"algorithm":"tracker","about":["A Tracker runs a dependency graph the way a build system does. Ready returns the tasks that can start, and Done marks tasks as finished, which makes ready every task that was waiting only on them. An edge from A to B means B depends on A, so Ready returns B once A is done.","Levels split the same graph into rounds, and each round waits for its slowest task. The tracker starts a task the moment its own dependencies finish, so a long task in one round doesn't hold up the tasks of the next round that never waited for it.","The tracker leaves running the tasks to the caller, and with them how many run at once. This page uses two workers that take the ready tasks first in, first out, and each task takes its weight in time. NewTracker copies the graph in O(V+E), and all the Ready and Done calls of a run add up to O(V+E) too. It returns ErrDAGHasCycle for a graph with a cycle, and Done returns ErrNotReady for a task Ready hasn't returned."],"template":{"id":"build-pipeline","name":"Build pipeline","description":"The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Checkout","x":100,"y":440},{"id":"Install","x":300,"y":440},{"id":"Lint","x":500,"y":280},{"id":"Compile","x":500,"y":560},{"id":"Unit tests","x":700,"y":440},{"id":"Docker image","x":700,"y":760},{"id":"Deploy","x":900,"y":440}],"edges":[{"from":"Checkout","to":"Install"},{"from":"Checkout","to":"Docker image"},{"from":"Install","to":"Lint"},{"from":"Install","to":"Compile"},{"from":"Lint","to":"Deploy"},{"from":"Compile","to":"Unit tests"},{"from":"Compile","to":"Docker image"},{"from":"Unit tests","to":"Deploy"},{"from":"Docker image","to":"Deploy"}],"durations":{"Checkout":1,"Compile":3,"Deploy":2,"Docker image":5,"Install":3,"Lint":6,"Unit tests":6},"durationUnit":"minutes","details":{"vertices":7,"edges":9,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":2},"selfLoops":0,"components":1}},"problem":"With two runners, each job starting as soon as the jobs it waits for are done, how many minutes does the pipeline take, and how does that compare with running it level by level?","params":{"workers":2},"result":{"kind":"order","vertices":["Checkout","Install","Lint","Compile","Unit tests","Docker image","Deploy"]},"answer":"With 2 workers, the last of the 7 tasks finishes at time 17. Running the levels one after another on the same workers takes 18, since each level waits for its slowest task. One task at a time would take 26.","legend":{"vertex":[{"id":"idle","label":"Waiting on a task it depends on","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Ready, waiting for a worker","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Running","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Done","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Its start is done","color":"#009E73","shape":"thick"}],"panels":[{"id":"ends","title":"Ends at","kind":"table"},{"id":"running","title":"Running","kind":"list"},{"id":"ready","title":"Ready, first in first out","kind":"list"},{"id":"order","title":"Start order","kind":"list"}]},"steps":[{"say":"The tracker hands out a task once every task it depends on is done, and 2 workers take the ready tasks in the order it returns them. Each task takes its weight in time, and the time it ends shows next to its name once it starts. The first call to Ready returns Checkout, the only task that depends on nothing.","ops":[{"v":"Checkout","state":"waiting"},{"panel":"ready","list":[{"key":"Checkout"}]}]},{"say":"At time 0, Checkout starts and takes 1, so it ends at 1. One worker has nothing to do until another task is ready.","ops":[{"v":"Checkout","state":"current"},{"panel":"ends","set":{"Checkout":"1"}},{"panel":"running","list":[{"key":"Checkout","note":"until 1"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"}]}]},{"say":"At time 1, Checkout finishes. Done makes Install ready. Install starts and takes 3, so it ends at 4. One worker has nothing to do until another task is ready.","ops":[{"v":"Checkout","state":"done"},{"e":["Checkout","Install"],"state":"tree"},{"e":["Checkout","Docker image"],"state":"tree"},{"v":"Install","state":"waiting"},{"v":"Install","state":"current"},{"panel":"ends","set":{"Install":"4"}},{"panel":"running","list":[{"key":"Install","note":"until 4"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"}]}]},{"say":"At time 4, Install finishes. Done makes Lint and Compile ready. Lint and Compile start, to end at 10 and 7.","ops":[{"v":"Install","state":"done"},{"e":["Install","Lint"],"state":"tree"},{"e":["Install","Compile"],"state":"tree"},{"v":"Lint","state":"waiting"},{"v":"Compile","state":"waiting"},{"v":"Lint","state":"current"},{"panel":"ends","set":{"Lint":"10"}},{"v":"Compile","state":"current"},{"panel":"ends","set":{"Compile":"7"}},{"panel":"running","list":[{"key":"Lint","note":"until 10"},{"key":"Compile","note":"until 7"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"},{"key":"Lint","note":"at 4"},{"key":"Compile","note":"at 4"}]}]},{"say":"At time 7, Compile finishes. Done makes Unit tests and Docker image ready. Unit tests starts and takes 6, so it ends at 13. Every worker is busy, so 1 ready task waits for one to come free.","ops":[{"v":"Compile","state":"done"},{"e":["Compile","Unit tests"],"state":"tree"},{"e":["Compile","Docker image"],"state":"tree"},{"v":"Unit tests","state":"waiting"},{"v":"Docker image","state":"waiting"},{"v":"Unit tests","state":"current"},{"panel":"ends","set":{"Unit tests":"13"}},{"panel":"running","list":[{"key":"Lint","note":"until 10"},{"key":"Unit tests","note":"until 13"}]},{"panel":"ready","list":[{"key":"Docker image"}]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"},{"key":"Lint","note":"at 4"},{"key":"Compile","note":"at 4"},{"key":"Unit tests","note":"at 7"}]}]},{"say":"At time 10, Lint finishes. Done makes no new task ready. Docker image starts and takes 5, so it ends at 15.","ops":[{"v":"Lint","state":"done"},{"e":["Lint","Deploy"],"state":"tree"},{"v":"Docker image","state":"current"},{"panel":"ends","set":{"Docker image":"15"}},{"panel":"running","list":[{"key":"Unit tests","note":"until 13"},{"key":"Docker image","note":"until 15"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"},{"key":"Lint","note":"at 4"},{"key":"Compile","note":"at 4"},{"key":"Unit tests","note":"at 7"},{"key":"Docker image","note":"at 10"}]}]},{"say":"At time 13, Unit tests finishes. Done makes no new task ready. One worker has nothing to do until another task is ready.","ops":[{"v":"Unit tests","state":"done"},{"e":["Unit tests","Deploy"],"state":"tree"},{"panel":"running","list":[{"key":"Docker image","note":"until 15"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"},{"key":"Lint","note":"at 4"},{"key":"Compile","note":"at 4"},{"key":"Unit tests","note":"at 7"},{"key":"Docker image","note":"at 10"}]}]},{"say":"At time 15, Docker image finishes. Done makes Deploy ready. Deploy starts and takes 2, so it ends at 17. One worker has nothing to do until another task is ready.","ops":[{"v":"Docker image","state":"done"},{"e":["Docker image","Deploy"],"state":"tree"},{"v":"Deploy","state":"waiting"},{"v":"Deploy","state":"current"},{"panel":"ends","set":{"Deploy":"17"}},{"panel":"running","list":[{"key":"Deploy","note":"until 17"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout","note":"at 0"},{"key":"Install","note":"at 1"},{"key":"Lint","note":"at 4"},{"key":"Compile","note":"at 4"},{"key":"Unit tests","note":"at 7"},{"key":"Docker image","note":"at 10"},{"key":"Deploy","note":"at 15"}]}]},{"say":"Done. At time 17, Deploy finishes, the last of the 7 tasks. Running the levels one after another on 2 workers would take 18, and one task at a time 26.","ops":[{"v":"Deploy","state":"done"},{"panel":"running","list":[]}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"t, err := dag.NewTracker(g)\nif err != nil {\n\treturn err\n}\nworkers := make(chan struct{}, 2)\nfinished := make(chan string, g.Order())\nfor t.Remaining() > 0 {\n\tfor _, task := range t.Ready() {\n\t\tgo func() {\n\t\t\tworkers <- struct{}{}\n\t\t\trun(task) // task.Weight() is how long it takes\n\t\t\t<-workers\n\t\t\tfinished <- task.Label()\n\t\t}()\n\t}\n\tif err := t.Done(<-finished); err != nil {\n\t\treturn err\n\t}\n}"}