Yelp Abuses Binary Search for Merging Code
Finally, a real use case for learning data structures and algorithms.
⚡️TLDR;
Yelp merged pull requests serially. Just imagine the merge conflicts…
So they shipped merge requests in groups. If there was a bad one, they literally used binary search to fish for the faulty commit.
🧠 Random fact: Yelp is a Monorepo
This means all their code is in a single repository.
But why tho?
Because it was painful to make updates to individual microservices when some were behind in updates. It’s easier to do it all in one go for the entire code base all at once.
🔧 So what did the pipeline look like?
Every code change would be on a branch and then merged. The next one wouldn’t merge until the previous one finished.
Not really good at parallel processing but gets the job done.
💡 Serial is seriously slow.
And you’re right. Go faster and batch merge requests together into groups.
As an example, that means the first 5 merge requests would be submitted and before the next 5 would be submitted.
💔 But what if something breaks?
Because something always breaks.
If something breaks use binary search with extra steps
If a group fails to merge together, split the group into two groups and keep trying to merge successful groups.
Repeat again and again until you get the culprit commit to roll back.
It’s binary search with extra steps and runs in O(logn).
(This even works if there’s multiple faulty commits!)
📖 Give me more system design resources!
If you found this article helpful, you’ll enjoy amazingly detailed system designs from ByteByteGo’s System design Interview.
They’re more detailed and catered to interviews. Some are byte-sized, some are not. But it’s all amazing.
💰 HELP WANTED
This newsletter has grown to 5000+ → +8500 AMAZING READERS. It’s grown to a scale that a single person can’t maintain all of it on their own.
If you’re interested in being a byte-sized design writer, apply here!
📝 Official Article
(Links to official article and sources are available to paid subscribers. They help maintain and support this newsletter!)
Keep reading with a 7-day free trial
Subscribe to Byte-Sized Design to keep reading this post and get 7 days of free access to the full post archives.