Continuous integration systems play a crucial role in keeping software working while it is being developed. The basic steps most continuous integration systems follow are:
1. Get the latest copy of the code.
2. Run all tests.
3. Report results.
4. Repeat 1-3.
This works great while the codebase is small, code flux is reasonable and tests are fast. As a codebase grows over time, the effectiveness of such a system decreases. As more code is added, each clean run takes much longer and more changes gets crammed into a single run. If something breaks, finding and backing out the bad change is a tedious and error prone task for development teams.
Software development at Google is big and fast. The code base receives 20+ code changes per minute and 50% of the files change every month! Each product is developed and released from ‘head’ relying on automated tests verifying the product behavior. Release frequency varies from multiple times per day to once every few weeks, depending on the product team.
With such a huge, fast-moving codebase, it is possible for teams to get stuck spending a lot of time just keeping their build ‘green’. A continuous integration system should help by providing the exact change at which a test started failing, instead of a range of suspect changes or doing a lengthy binary-search for the offending change. To find the exact change that broke a test, we could run every test at every change, but that would be very expensive.
To solve this problem, we built a continuous integration system that uses dependency analysis to determine all the tests a change transitively affects and then runs only those tests for every change. The system is built on top of Google’s cloud computing infrastructure enabling many builds to be executed concurrently, allowing the system to run affected tests as soon as a change is submitted.
Here is an example where our system can provide faster and more precise feedback than a traditional continuous build. In this scenario, there are two tests and three changes that affect these tests. The gmail_server_tests are broken by the second change, however a typical continuous integration system will only be able to tell that either change #2 or change #3 caused this test to fail. By using concurrent builds, we can launch tests without waiting for the current build/test cycle to finish. Dependency analysis limits the number of tests executed for each change, so that in this example, the total number of test executions is the same as before.
Let’s look deeper into how we perform the dependency analysis.
We maintain an in-memory graph of coarse-grained dependencies between various tests and build rules across the entire codebase. This graph, several GBs in-memory, is kept up-to-date with each change that gets checked in. This allows us to transitively determine all tests that depend on the code modified in a given change and hence need to be re-run to know the current state of the build. Let’s walk through an example.
Consider two sample projects, each containing a different set of tests:
where the build dependency graph looks like this:
We will see how two isolated code changes, at different depths of the dependency tree, are analyzed to determine affected tests, that is the minimal set of tests that needs to be run to ensure that both Gmail and Buzz projects are “green”.
Case1: Change in common library
For first scenario, consider a change that modifies files in common_collections_util.
As soon as this change is submitted, we start a breadth-first search to find all tests that depend on it.
Once all the direct dependencies are found, continue BFS to collect all transitive dependencies till we reach all the leaf nodes.
When done, we have all the tests that need to be run, and can calculate the projects that will need to update their overall status based on results from these tests.
Case2: Change in a dependent project:
When a change modifying files in youtube_client is submitted.
We perform the same analysis to conclude that only buzz_client_tests is affected and status of Buzz project needs to be updated:
Use of smart tools and cloud computing infrastructure in the continuous integration system makes it fast and reliable. While we are constantly working on making improvements to this system, thousands of Google projects are already using it to launch-and-iterate quickly and hence making faster user-visible progress.
- Pooja Gupta, Mark Ivey and John Penix
Extremely interesting article. But there isn't a mention of a specific programming language, or is that not a limitation of the "system's dependency analysis"? If this 'dependency analysis' works on a C++ code-base, I for one would love to get more details. Or do I need to join Google for that :-)
ReplyDeleteAs we perform dependency analysis at build rule level, it is language agnostic as long as code base follows the convention of defining build rules. Send us your resume anyway? :-) Find more details at: http://www.google.com/intl/en/jobs/index.html
ReplyDeleteThat seems to mean that a hidden depdency - buzz depends on youtube_server for example but it is not listed in the manual dependencies would cause you to misdiagnose the offending changelist.
ReplyDeleteAlso, this system does not count sporadic failures - what happens if a test is flaky and fails sometimes?"
Thanks @poojagupta. Are you allowed to give us more information on what the build-rule looks like?
ReplyDeleteIs the dependency-analysis specific to the build tool Google uses (is that even publicly known?) or is it something that can be practically applied to any build-tool (e.g. CMake).
From the outside it seems like this tool, that you describe, can be a product in its own right. Any chance Google would sell it?
Thanks in advance.
@JohnM The change that made buzz depend on youtube_server, but didn't add the proper dependency to the build rule would cause a build failure for buzz. You are correct that any change to youtube_server while the buzz dependencies were broken would be missed - but this isn't a state that lasts long. I've never heard of this happening.
ReplyDelete@Ganeshram, The build-rule is specific to the build tool used at Google, which is not publicly known. Currently this system is tightly coupled with the rest of developer infrastructure at Google and not available as a product.
ReplyDeleteI'm not familiar with CMake, but looking at example in http://www.cmake.org/cmake/help/examples.html, I can imagine a dependency tree built on top of CMake's target_link_libraries, which seems to define the dependencies.
So did this get built in from the beginning or was it created later after the code base started getting large and awkward? I'd like to get a sense of the challenges and time involved in creating this against an existing code base if that's something you have experience with.
ReplyDeleteAlso does this help reduce intermittent test failures as tests are much less likely to have hidden dependencies?
It's an interesting idea, applying the dependency management to the test runs and not only the builds.
ReplyDeleteBut I have a question: in the first example you can track down that both change #2 and change #3 are breaking gmail_server_tests independently.
But how do you go back in the version control system and fix those changes individually? Do you go back to pre-change #2 and then serialize the (fixed) changes?
Another question is that now you can know earlier if it was change #2 or #3 that broke the tests, but you will not know (till later) if the combination of change #2 and #3 (also) breaks the tests.
Is this a tradeoff you agree upon since maybe individual changes breaking the build are more common than combination of changes?
Thanks for the interesting post!
I'm not sure I follow your first question. When we know both change #2 and #3 are breaking the test independently, a developer can make either a single change to fix both problems, or two separate changes. If for example the issue caused by change #2 is severe they can rollback change #2 and submit a change fixing the problem caused by change #3.
ReplyDeleteFor second question, change #2 and change #3 are likely to be submitted by different developers breaking the same test in different ways, hence they would probably fix their breakage separately. Also as you mentioned individual changes breaking the build are more common than combination of changes.
Just to answer Lukas Blakk's question:
ReplyDeleteThe system was built after the code base was already quite large (and still growing fast) and the cost of traditional continuous builds was getting to be a burden. For the server tracking dependency information, there were already files in pace containing dependency information so we just had to make something to read them all in and build up the graph. The work for creating the graph with sufficient information at the nodes isn't super hard if you have all of the edge information handy but dealing with the updates, checkpointing for error recovery, ... can definitely take more time.
As for flaky tests, those are a problem in and of themselves. Running them only when they could be affected reduces the noise but that's about it. It does make it easier to preemptively see what tests you should run to verify a change going in so in can be used to reduce surprising breakages.
I've been thinking about similar thing recently - these dependencies (even better to track also dependencies between tests) could be used to build something like "test case priorities"...
ReplyDeleteExample: there is a test case A, which depends on test case B (A tests feature AA which depends on feature BB, tested by B)...
Then if BB is broken, both B and A tests fail, but A doesn't test BB directly.
The idea is to display the results with sort of priority: B has higher priority than A, as fixing BB will fix both tests...
The main idea is to help find the real problem faster. Of course this is not related to pure unit tests which should not rely on other components.
Thanks for this post - great read!
ReplyDeleteIn Case 1:
Aren't we missing common_collections_util_tests? Wouldn't it be quicker to execute this first before executing any test from upstream dependencies?
@Mathias
ReplyDeleteGood catch. Yes there should also be common_collections_util_tests which will also get run for case 1.
With the current architecture, we do not prioritize some tests over the other for a single change. There is definitely scope for improvement here. e.g. by proximity as you suggested, or say run all small+stable+fast tests before running large+flaky tests.
Good suggestion.
How do you know which test tests which feature?
ReplyDeleteThis system does not know anything about features in a product. That is up to the respective teams.
ReplyDeleteHi, I went through your this post and found really interesting. I landed this page through internet search and found
ReplyDeletethis page very good.I am a web designer and works in a web design company
as a designer I liked the color of your blog also.
Thanks,
Saroda Swami
Interesting!! I am trying to do something similar to save on time it takes to test the whole system. I want to know how do you maintain the dependency matrix. To elaborate if some new component is added into my code base do i manually go and change the matrix and then reload the matrix on the memory or are you using some tool which does that for you ?
ReplyDeleteThanks
Harneet - struggling - Build and release Engg.
@Rebellious_jatt As changes are checked in the graph is automatically updated so that the correct tests are executed.
ReplyDeleteADMISSION OPEN-----
ReplyDeleteThe curriculum is transacted by highly qualified faculty using world-class facilities on an 18-acre sprawling, serene and lush green Wi-Fi campus in the meadows of Gurgaon (Haryana)..
Engineering college in Gurgaon
I can see that you are are genuinely passionate about this! great information.
ReplyDeletethank you...!
http://www.hadooponlinetraining.net/
ReplyDeleteWonderful blog & good post.Its really helpful for me, awaiting for more new post. Keep Blogging!
Software Training Chennai
Interesting. Honestly, I'm just a website hobbyist and reading this kind of information makes me want to know more. I read a few basic HTML and CSS from an Arizona web design blog website before, but this article proves to be too advanced to what I currently know. Anyway, it still helps to be knowledgeable about this stuff. At least in my future research, I already have an Idea about this.
ReplyDeleteIT Pathshala Private Limited is an initiative of Myzeal IT Solutions and driven by a sustainable vision under which, the company is committed to provide robust and industry ready software testing training. It’s a career enabling programs to industry requirements and also professionals who are working in fast growing Software Testing industry. Our modules cover an advanced spectrum of topics. The curriculums are built by professional software developers that are available in both text and video formats.
ReplyDeleteKey benefits of Our Software Testing Takeaways:
• Training Provided by CMMi L3 ready IT Company
• 100% Job assistance and In-House Job Opportunity
• Opportunity to work upon Real On-going projects
• Interaction with Industry Experts
• Experience Letter on Training completion
• Small Batches to focus on Each students
• Certification on Training Completion
You have shared what a nice article, keep it up...........
ReplyDeleteNice blog and thank you for the information. Awicon Technologies automation is a strong proponent of eco-friendly home automation systems which includes door locks, theater and security systems in Hyderabad.
ReplyDeleteHome Automation in Hyderabad
Thanks for sharing your valuable post
ReplyDeleteLoadrunner Training
It's a great article. Good Work.
ReplyDeleteKeep it up! :)
Software Testing Companies
This very useful this blogs nice information Cloud Computing Training VA|CEH Training Fairfax VA
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThe very interesting part is how do you maintain the dependency matrix!
ReplyDeleteRadios Costa Rica
Well it was very good to see your article... Thanks a lot for providing Information
ReplyDeleteRegarding Testing Tools.. Flaxit will provide the best Software Courses Online Training in USA.
Great article but something happened to the images. Can you please restore them? Thanks!
ReplyDeleteWhere are the images? I would love to read the article with the images.
ReplyDeleteThanks for sharing!! It's really good Blog..
ReplyDeleteDevOps Training
DevOps Online Training
This blog is really awesome and very helpful. thanks, I hope so. that you will continue to provide such information.
ReplyDeletevisit site
This is an informative blog. Keep it up. I am looking forward to this kind of blog. I took a lot away from this blog. also, your thoughts were very well organized as far as how you went into details and made it very. Thanks
ReplyDeleteGmail Nederland
This post is so interactive and informative.keep update more information...
ReplyDeleteselenium Automated Testing Main Features
selenium IDE basics
Spectrum Speed Test
ReplyDeleteHi, I want to express my gratitude to you for sharing this fascinating information. It's amazing that we now have the ability
ReplyDeleteto share our thoughts. Share such information with us through blogs and internet services.
Visit site
Thank you for sharing this amazing post. Looking forward to reading more.
ReplyDeleteVisit us: dot net training
Visit us: Dot Net Online Training Hyderabad
Hi, I want to express my gratitude to you for sharing this fascinating information. It's wonderful that we now have the ability to share our thoughts. through blogs and internet services, I felt the same way, keep sharing more posts on this side with us in the future.
ReplyDeleteyoutube bellen
The blog has been written in a manner that there isn't anything that has been left revealed, and furthermore, I have perused different web journals that are posted here and they are altogether worth a read.
ReplyDeletevisit site
Good Article. Thanks for sharing this wonderful information with us.
ReplyDeleteCloud Testing Training
Cloud Testing Online Training
I Like to add one more important thing here, The Automated Test Equipment Market is expected to be around US$ 26 Billion by 2025 at a CAGR of 5% in the given forecast period.
ReplyDeleteAmazing! Its a genuinely remarkable piece of writing, I
ReplyDeletehave got much clear idea on the topic from this post.
Outlook Bellen
All images are missing. Could you please re-enable them?
ReplyDelete