Google Engineering Tools

Bug Prediction at Google

2011-12-14T12:03:00.000-08:00

What's the problem?

Here at Google, we have thousands of engineers working on our code base every day. In fact, as previously noted, 50% of the Google code base changes every month. That’s a lot of code and a lot of people. In order to ensure that our code base stays healthy, Google primarily employs unit testing and code review for all new check-ins. When a piece of code is ready for submission, not only should all the current tests pass, but new tests should also be written for any new functionality. Once the tests are green, the code reviewer swoops in to make sure that the code is doing what it is supposed to, and stamps the legendary “LGTM” (Looks Good To Me) on the submission, and the code can be checked in.

However, Googlers work every day on increasingly more complex problems, providing the features and availability that our users depend on. Some of these problems are necessarily difficult to grapple with, leading to code that is unavoidably difficult. Sometimes, that code works very well, and is deployed without incident. Other times, the code creates issues again and again, as developers try to wrestle with the problem. For the sake of this article, we'll call this second class of code “hot spots”. Perhaps a hot spot is resistant to unit testing, or maybe a very specific set of conditions can lead the code to fail. Usually, our diligent, experienced, and fearless code reviewers are able to spot any issues and resolve them. That said, we're all human, and sneaky bugs are still able to creep in. We found that it can be difficult to realize when someone is changing a hot spot versus generally harmless code. Additionally, as Google's code base and teams increase in size, it becomes more unlikely that the submitter and reviewer will even be aware that they're changing a hot spot.

In order to help identify these hot spots and warn developers, we looked at bug prediction. Bug prediction uses machine-learning and statistical analysis to try to guess whether a piece of code is potentially buggy or not, usually within some confidence range. Source-based metrics that could be used for prediction are how many lines of code, how many dependencies are required and whether those dependencies are cyclic. These can work well, but these metrics are going to flag our necessarily difficult, but otherwise innocuous code, as well as our hot spots. We're only worried about our hot spots, so how do we only find them? Well, we actually have a great, authoritative record of where code has been requiring fixes: our bug tracker and our source control commit log! The research (for example, FixCache) indicates that predicting bugs from the source history works very well, so we decided to deploy it at Google.

How it works
In the literature, Rahman et al. found that a very cheap algorithm actually performs almost as well as some very expensive bug-prediction algorithms. They found that simply ranking files by the number of times they've been changed with a bug-fixing commit (i.e. a commit which fixes a bug) will find the hot spots in a code base. Simple! This matches our intuition: if a file keeps requiring bug-fixes, it must be a hot spot because developers are clearly struggling with it.

Aside from the speed of execution, this algorithm is also very attractive as it's easy to communicate to others: files are flagged if they have attracted a large number of bug-fixing commits, no more and no less. Some bug prediction algorithms use a large number of metrics and perform many calculations before they output a result, but how do we know it's not a false positive? We don't! Once developers start feeling a tool is lying to them, they'll quickly stop using it. With the Rahman algorithm, whether a developer agrees with the prediction or not is up for debate, but no one can argue with the actual number it outputs.

We implemented the Rahman algorithm by creating a program that hooked into our source control system, and pulls out all the changes which had a bug attached to them. It looks at each bug number, and verifies with the bug-tracking database that it was really a bug, and filters out everything else, such as feature requests. It then looks at all the files that appeared in these changes, and filters out those that have been deleted and are no longer at HEAD. For each file, the number of bug-fixing changes it's been in is calculated, and we output the files which were ranked in the top 10%.

We showed output to the development teams (you know, just to make sure). The response?

"Hey guys, this list looks great, but there's a couple of files that used to be a problem, but we fixed them, so they shouldn't be on here now."

It turns out that while the Rahman algorithm shows us where hot spots are, it doesn't adapt to changes readily. If a development team manages to nail down a hot spot and get it fixed, it'll still appear in the list because of all the bug-fixing commits it created in the past.

What we needed was a way of prioritizing newer bug-fixing commits, and downgrading the value of old ones, so fixed files begin to fall down the list.

After some trial-and-error, we decided to score each file by weighting each bug-fixing commit by how old it is. As the commit gets older, so its influence tends towards 0.

Where n is the number of bug-fixing commits, and ti is the timestamp of the bug-fixing commit represented by i. The timestamp used in the equation is normalized from 0 to 1, where 0 is the earliest point in the code base, and 1 is now (where now is when the algorithm was run). Note that the score changes over time with this algorithm due to the moving normalization; it's not meant to provide some objective score, only provide a means of comparison between one file and another at any one point in time.

Some of you might wonder why we don't factor in the number of commits in the algorithm: a file that changes often as it's being developed will get more bug-fixing commits. Wouldn't it be fairer to look at the ratio of non-fixing commits to bug-fixing commits? Having trialled this, we found the results unsatisfying. Code churn has previously been pointed at as an indicator of the presence of defects (particularly by Nagappan and Ball), so employing a ratio removes that useful signal.

If we plot our equation, it looks like this:
Running using this scoring algorithm means that as commits get older, they are worth less and less. The drop-off happens quickly in order to really push up those newer bug-fixing changes and devalue the older ones. Files that don't get many bug-fixing commits for a while will end up falling out of the top 10%.

How we're using it
When a file is predicted to be a hot spot, we place a warning in our code review system on that file. Whenever a reviewer logs in to review that code, the warning will appear, which hopefully will encourage them to spend some more time reviewing the code, or hand off the review to someone more experienced if need be.

Conclusion
Bug prediction is not an objective measure by any means: the attentive amongst you will see it's another tool that we can provide Googlers with in order to help them gain insight into their code. We hope that by highlighting code hot spots, we'll help to stop tricky bugs making their way into the code base. We'll be monitoring how developers are engaging with these reviews in the months to come.

- Chris Lewis and Rong Ou

Build in the Cloud: Distributing Build Outputs

2011-10-27T13:05:00.000-07:00

This is the fourth in a four part series describing how we use the cloud to scale building and testing of software at Google. This series elaborates on a presentation given during the Pre-GTAC 2010 event in Hyderabad. To get a sense of the scale and details on the types of problems we are solving in Engineering Tools at Google take a look at this post.

In the previous post, we saw how distributing build load across many machines and reusing the results of previous build actions can produce extremely fast build times. This distribution and reuse itself exposed other performance bottlenecks. Specifically, a full build of a large project may produce several gigabytes of output files, all of which need to be shipped from the cloud back to the developer’s local machine. This taxes both our networks and the developer’s local disk, the limited latencies and bandwidth of which slow down the build.

Furthermore, a developer typically does not need access to all of the outputs of a build. She may be interested only in the final binary that results from a build, not all of the intermediate object files. Another example is when the developer uses the distributed build system to build and execute a test in the cloud; in this case, she does not need local access to any build outputs at all, but simply an indication that the test passed or failed. It is thus unnecessary and wasteful to always ship all build outputs from the cloud back to the developer’s local machine. Instead, it is sufficient to ship back only those build outputs that are actually accessed by the developer on demand.

To address these bottlenecks, our distributed build system writes all build outputs that it generates to a persistent, distributed storage system in the cloud. This storage system can handle sustained read and write rates many times those of a local disk, and the network connectivity between the distributed build system and this storage system has significantly lower latency and higher bandwidth than to the developer’s local machine. The build outputs are stored by content fingerprint, providing a straightforward mechanism for indexing and retrieval of the files. (This cloud storage system also serves as a secondary caching layer for the distributed build system, providing an additional performance benefit in instances when build outputs fall out of the primary caching layer.) Using this distributed storage system in the cloud, we are able to make build speeds more than twice as fast as a distributed build that stores all build outputs on the developer’s local disk.

With cloud-based storage of build outputs providing substantial increases in build times, the remaining challenge is to still make build outputs available to the developer’s local machine, on demand, once the build completes. We achieve this by writing a custom file system to provide a view of the build outputs. Like we described in our first blog post, the File System in Userspace (FUSE) kernel module is a convenient way of implementing a user space daemon that implements such a file system. As individual build steps complete, the distributed build system informs the daemon about the creation of new build outputs, providing both a relative file path and a content fingerprint. Then, when the developer accesses one of the files on these paths, the daemon downloads the file from the cloud, using the content fingerprint as the key, and serves it via FUSE to the developer (caching downloaded files on the developer’s machine to speed up subsequent accesses). The content fingerprint itself is also made available to the build system as an extended attribute via the FUSE layer, which, as we indicated in our second blog post, is necessary for the build system to perform incremental builds.

In addition to serving build outputs from the cloud and build output metadata from the local machine, the local daemon performs many additional tasks important for the functionality of the system. For example, build outputs are kept in the cloud only as long as they are referenced by at least one developer’s local machine. The daemon periodically extends leases for all build outputs present in any build on a developer’s workstation. As another example, the performance of the virtual file system would be dismal if large build outputs were fetched sequentially once they were requested by the developer; instead, the daemon downloads chunks of the file in parallel from multiple storage servers in the cloud. The daemon is also responsible for local data integrity checks, local disk management and data eviction, and many other maintenance tasks.

The picture below summarizes how Google’s build system works as a whole, taking into account the four blog posts in this series:

The developer invokes the build system client on her workstation, specifying one or more targets to build. The client then coordinates and dispatches individual build actions to execute in the cloud, reading the necessary source code metadata from the FUSE daemon to provide as input to the cloud execution system. The build outputs of these actions (such as binaries) are then stored in our cloud storage system, and downloaded on demand by the user through FUSE daemon. The end result of this is a build system that can deliver build results to developers on the order of seconds or minutes, as opposed to hours.

This concludes our four-part series of blog posts describing how we use the cloud to scale building at Google. In this series, we covered cloud-based source control, how our build system works, and how we distribute both build actions and build outputs to the cloud. We encourage readers to comment on these posts, and to comment on any additional topics they would like to see covered in this blog.

- Milos Besta, Yevgeniy Miretskiy and Jeff Cox

Trying on the new Dynamic Views from Blogger

2011-09-27T15:09:00.000-07:00

As you may have noticed, the Engineering Tools blog looks a lot different today. That’s because we—along with a few other Google blogs—are trying out a new set of Blogger templates called Dynamic Views.

Launched today, Dynamic Views is a unique browsing experience that makes it easier and faster for readers to explore blogs in interactive ways. We’re using the Classic view, but you can also preview this blog in any of the other six new views by using the view selection bar at the top left of the screen.

We’re eager to hear what you think about the new Dynamic Views. You can submit feedback using the “Send feedback” link on the bottom right of this page, or just send us an email.

If you like what you see here, and we hope you do, we encourage you to try out the new look(s) on your own blog—read the Blogger Buzz post for more info.

Posted by John Thomas, Tech lEad

Build in the Cloud: Distributing Build Steps

2011-09-22T15:32:00.000-07:00

This is the third in a four part series describing how we use the cloud to scale building and testing of software at Google. This series elaborates on a presentation given during the Pre-GTAC 2010 event in Hyderabad. Please see our first post in the series for a description how we access our code repository in a scalable way. To get a sense of the scale and details on the types of problems we are solving in Engineering Tools at Google take a look at this post.

The two previous posts described a custom file system for providing access to source code hosted in the cloud, and how the build system works. This post builds on these to describe a system for efficiently distributing build steps across a large number of machines. As you will see, details of the source file system and the build system are important to how we achieve fast and efficient distributed builds. So before we get into the mechanics of how build steps are distributed, it is helpful to call attention to a few points.

First, the build system is content-based where the internal bookkeeping for inputs and outputs is based on content digest, not file and timestamp (as in Make). This means that content equality is determined by comparing content digests, and these digests are tracked internally by the build system as it builds and operates on the action graph. Computing content digests for builds with a large amount of source code could be expensive because of the time spent reading files. We avoid this problem by computing and storing digests as content is checked in, and then providing digests directly to the build system as extended attributes.

Second, the build system reads BUILD files to construct a graph of dependencies, and then uses the dependency graph to construct a graph of build actions or build steps. The graph is constructed by using the outputs of actions as inputs to other actions. Dependencies are expected to be completely specified and there is no dynamic dependency detection. The combination of content digests along with completely specified dependencies means that actions can be expressed as functions. In this functional model, the function inputs are the content digests and the environment (environment variables, command line options), the function is the tool or script which transforms inputs, and the outputs are the function results. These functional build actions are atomic units of work, and the transformation of inputs to outputs is opaque to the system. This means that build actions are language and tool agnostic and, among other things, may compile a C++ translation unit, compile Java files, link a binary, or even run a unit test.

An example of the action graph. Outputs of actions, such as search.o from from the CC action, become inputs to other actions (LD in this case).

Third, we require that every build action is a function of only its declared inputs. This means that if we would execute the same action with the same input again we would get bit-identical output. This guarantees that not re-executing an action because the input files have the same content as in a previous build will not change the build results. This sounds like a reasonable requirement, but in practice an action may depend on things other than the declared input files, such as the contents of system header files or even the time of day (consider the __DATE__ macro expanded by the C preprocessor, or the timestamps embedded in every jar file). We address these problems by configuring our tools to make actions hermetic and post-processing some file types to overwrite timestamps.

Now let’s continue with details of how we use these functional actions to distribute the build.

As self-contained, atomic units of work, build actions are portable in that they can be sent to other machines, along with the inputs, for remote execution. This is useful at Google because we happen to have a lot of machines in data centers, which means we can distribute execution of build actions across thousands of workers. In this model all actions can be distributed, and the parallelism of the build is limited only by the width of the action graph.

Distributing actions across lots of workers makes the build fast, but we also found that workers duplicated a lot of work since many engineers build the same code. The functional nature of build actions, where the same inputs alway produce bit-identical outputs, means that we can easily and correctly cache and reuse results. We construct a cache key by computing a digest from the entire request (the command line and inputs), so it is not possible to “leave out” something and get incorrect cache hits. Remember that input files are described by content digest, so computing the cache key is relatively cheap, even for a large amount of content. When an action is ready for remote execution, we first compute the cache key. In case of a cache miss, the action is executed on a worker and the result is cached as it is returned to the user. In case of a cache hit, we simply return the cached result. To maintain the illusion that a cached action is actually executed, we also cache and replay the stdout+stderr of the action.

As changes are submitted to the code base, the first build to encounter each change waits a bit longer on actions affected by the code change because these need to be re-executed, but because build actions are distributed the difference is not very noticeable. In many cases, such as whitespace or comment changes in C++, different inputs still produce bit-identical output. Because the build system is content-based, this situation will then produce cache hits for subsequent actions, which provides another form of build avoidance. The end result is a greater than 90% cache hit rate overall. This means that even “clean” rebuilds are mostly reusing work done for previous builds, resulting in extremely fast build times. Another way to think of this is that each change to the code base results in an on-demand binary release of every library and executable affected by the change.

Distributing build load across many machines and reusing build actions have been so successful in speeding up builds that we inadvertently created another issue. A clean build of a large project may produce several gigabytes of output, and since these builds typically take less than a few minutes and we do tens of thousands of builds per day, the volume of data produced by the distributed build resulted in considerable load on our networks and local disk I/O. Our next and final post in this series will describe how we solved this problem.

Stay tuned! In this post we explained how builds are distributed and cached to make the build fast and efficient. Part four in this series describes how we solved the problem of dealing with the large amount of data produced by doing many builds very quickly.

- Nathan York

Build in the Cloud: How the Build System works

2011-08-18T02:44:00.000-07:00

This is the second in a four part series describing how we use the cloud to scale building and testing of software at Google. This series elaborates on a presentation given during the Pre-GTAC 2010 event in Hyderabad. Please see our first post in the series for a description how we access our code repository in a scalable way. To get a sense of the scale and details on the types of problems we are solving in Engineering Tools at Google take a look at this post.

As you have learned in the previous post, at Google every product is constantly building from head. In this article we will go into a little more detail in how we tell the build system about the source code and its dependencies. In a later article we will explain how we take advantage of having this exact knowledge to distribute the builds at Google across a large cluster of machines and share build results between developers.

From some of the feedback we got for our first posts it is clear that you want to see how we actually go about describing the dependencies we use to drive our build and test support.

At Google we partition our source code into smaller entities that we call packages. You can think of a package as a directory containing a number of source files and a description of how these source files should get translated into build outputs. The files describing that are all called BUILD and the existence of a BUILD file in a directory makes that directory into a package.

All packages reside in a single file tree and the relative path from the root of that tree to the directory containing the BUILD file is used as a globally unique identifier for the package. This means that there is a 1:1 relationship between package names and directory names.

Within a BUILD file we have a number of named rules describing the build outputs of the package. The combination of package name and rule name uniquely identifies the rule. We call this combination a label and we use labels to describe dependencies across rules.

Let’s look at an example to make this a little more concrete:

/search/BUILD:
cc_binary(name = ‘google_search_page’,
deps = [ ‘:search’,
‘:show_results’])

cc_library(name = ‘search’,
srcs = [ ‘search.h’,‘search.cc’],
deps = [‘//index:query’])

/index/BUILD:

cc_library(name = ‘query’,
srcs = [ ‘query.h’, ‘query.cc’, ‘query_util.cc’],
deps = [‘:ranking’,
‘:index’])

cc_library(name = ‘ranking’,
srcs = [‘ranking.h’, ‘ranking.cc’],
deps = [‘:index’,
‘//storage/database:query’])

cc_library(name = ‘index’,
srcs = [‘index.h’, ‘index.cc’],
deps = [‘//storage/database:query’])

This example shows two BUILD files. The first one describes a binary and a library in the package //search and the second one describes several libraries in the package //index. All rules are named using the name attribute, You can see the dependencies expressed in the deps attribute of each rule. The ‘:’ separates the package name from the name of the rule. Dependencies on rules in a different package start with a “//” and dependencies on rules in the same package can just omit the package name itself and start with a ‘:’. You can clearly see the dependencies between the rules. If you look carefully you will notice that several rules depend on the same rule //storage/database:query, which means that the dependencies form a directed graph. We require that the graph is acyclic, so that we can create an order in which to build the individual targets.

Here is a graphical representation of the dependencies described above:

You can also see that instead of referring to concrete build outputs as typically happens in make based build systems, we refer to abstract entities. In fact a rule like cc_library does not necessarily produce any output at all. It is simply a way to logically organize your source files. This has an important advantage that our build system uses to make the build faster. Even though there are dependencies between the different cc_library rules, we have the freedom to compile all of the source files in arbitrary order. All we need to compile ‘query.cc’ and ‘query_util.cc’ are the header files of the dependencies ‘ranking.h’ and ‘index.h’. In practice we will compile all these source files at the same time, which is always possible unless there is a dependency on an actual output file of another rule.

In order to actually perform the build steps necessary we decompose each rule into one or more discrete steps called actions. You can think of an action as a command line and a list of the input and output files. Output files of one action can be the input files to another action. That way all the actions in a build form a bipartite graph consisting of actions and files. All we have to do to build our target is to walk this graph from the leaves - the source files that do not have an action that produces them - to the root and executing all the actions in that order. This will guarantee that we will always have all the input files to an action in place prior to executing that action.

An example of the bipartite action graph for a small number of targets. Actions are shown in green and files in yellow color:

We also make sure that the command-line arguments of every action only contain file names using relative paths - using the relative path from the root of our directory hierarchy for source files. This and the fact that we know all input and output files for an action allows us to easily execute any action remotely: we just copy all of the input files to the remote machine, execute the command on that machine and copy the output files back to the user’s machine. We will talk about some of the ways we make remote builds more efficient in a later post.

All of this is not much different from what happens in make. The important difference lies in the fact that we don’t specify the dependencies between rules in terms of files, which gives the build system a much larger degree of freedom to choose the order in which to execute the actions. The more parallelism we have in a build (i.e. the wider the action graph) the faster we can deliver the end results to the user. At Google we usually build our solutions in a way that can scale simply by adding more machines. If we have a sufficiently large number of machines in our datacenter, the time it takes to perform a build should be dominated only by the height of the action graph.

What I describe above is how a clean build works at Google. In practice most builds during development will be incremental. This means that a developer will make changes to a small number of source files in between builds. Building the whole action graph would be wasteful in this case, so we will skip executing an action unless one or more of its input files change compared to the previous build. In order to do that we keep track of the content digest of each input file whenever we execute an action. As we mentioned in the previous blog post, we keep track of the content digest of source files and we use the same content digest to track changes to files. The FUSE filesystem described in the previous post exposes the digest of each file as an extended attribute. This makes determining the digest of a file very cheap for the build system and allows us to skip executing actions if none of the input files have changed.

Stay tuned! In this post we explained how the build system works and some of the important concepts that allow us to make the build faster. Part three in this series describes how we made remote execution really efficient and how it can be used to improve build times even more!

- Christian Kemper

Are SSDs a silver bullet to improve IntelliJ's indexing performance?

2011-07-27T04:24:00.000-07:00

[cross post from http://inside-intellij.blogspot.com/2010/09/is-there-silver-bullet-to-improve.html]

We are the IntelliJ IDE team at Google. We develop IntelliJ code (plugins and patches) to provide a seamless integration with Google’s unique build system, and make IntelliJ scale to Google’s huge and rapidly changing codebase performance-wise.

We recently investigated whether using Solid State Devices (SSDs) could improve indexing performance for large projects. We decided to share our analysis and results here for the benefit of our Engineering Tools blog readers.

First, what do we mean by indexing? IntelliJ, like any IDE, maintains a datastore of source code meta-information that helps autocomplete, hyperlinking in source code, refactoring and a plethora of other features that operate on code. The process of creating this datastore is called ‘indexing’.

But why do we want to speed up indexing? Indexing occurs whenever a new IntelliJ project is created or source files change outside of IntelliJ (like a source control sync). As you can imagine, these are frequent operations. Now considering the scale and size of projects in a monolithic codebase like Google’s, the changed delta can be large and so it can take a significant amount of time to index. This operation effectively blocks users from using many rich features the IDE has to offer. We want to minimize this block time.

Why SSDs? Being aware that indexing is I/O intensive, we thought that using faster storage devices could be a silver bullet to improve indexing performance. But when we did some experiments, we learned otherwise.

SSDs use solid state memory to store data and have no electromechanical parts like a Hard Disk Drive (HDD). They offer lower latencies for data transfer in general. For random accesses read operations SSDs perform 50x-200x times better than typical HDDs, and they perform better than HDDs for sequential reads as well. Though SSD writes are not as fast as reads, write operations on modern SSDs are still faster than typical HDDs.

Now doing these experiments is one thing, but how to measure results? It would be ideal to determine the total mix of read and write operations performed by IntelliJ process during indexing to compute effective performance benefits. But while there are tools like blktrace that offer process level drill down of IO operations, it’s not easy for them to track internal file system level optimizations made before disk writes. For example, many write operations will actually be buffered and executed together by pdflush, but IO monitoring tools would actually count those as pdflush process writes only.

Long story short, we think the most reliable way to measure indexing improvements for now is to actually trigger a build/indexing for sample projects with and without SSDs and measure each case.

Now on to the fun stuff. Here are some details of the machine we used for sampling:

CPU: Intel quad core 2.4GHz
SSD: Kingston 128GB
HDD: WDC 500GB 7200RPM SATA-II
RAM: 8 GB DDR2, 800MHz (1.2ns)
JVM - 64-bit OpenJDK
IntelliJ Version - 10.5
File system: ext3

For the experiments, we chose sample projects that represented the set of projects we’re trying to optimize indexing performance for. We ran these experiments using SSDs in one case and HDDs in the other, keeping everything else constant. These are the results averaged out for 10 runs for one such sample project:

Storage Device

Num Files

Scanning Files to index Time

(secs)

Indexing Time

(secs)

SSD

78144

24.51

128.71

HDD

78144

15.69

141.1

Table 1: Index times of IntelliJ community edition code using SSD, normal hard-disk

Conclusion
From our experiments we did not find any significant improvements in indexing time when SSDs were used. While SSDs did offer 25% faster performance in the first run, which is when the source files of interest are not already cached by the file system (like after a reboot), on subsequent indexing operations (the practical case) this advantage reduces sharply. So the cost-benefit of this silver bullet does not really come through for us.

However this doesn’t mean SSDs can not possibly make things better. We feel there could be greater indexing performance boosts using SSDs if:

The underlying filesystem is highly optimized for SSDs (like ZFS for Solaris)
Number of disk read operations performed is more than number of write operations.

But some of these requirements are not trivial for us to implement. Till then, we will explore other ideas to improve IntelliJ performance and post any learnings that we feel would benefit our readers and the community. Stay tuned.

- Chandra Sekhar Pydi, Siddharth Priya, Abhishek Sheopory

Build in the Cloud: Accessing Source Code

2011-06-21T07:21:00.000-07:00

This is the first in a four part series describing how we use the cloud to scale building and testing of software at Google. This series elaborates on a presentation given during the Pre-GTAC 2010 event in Hyderabad. Please see our first post for more details on the types of problems we are solving in Engineering Tools at Google.

Much of our day-to-day activities as software engineers involves source code. When we join a project one of the first things we do is look at the source. We want to build it, run it, experiment with changes, test it, and challenge our assumptions about how it works. For most of us this means we start by “checking out” the source from version control. For small to moderately sized projects almost any reasonable version control system is adequate. But as the number of engineers increases and the code base grows, this can put a strain on the version control system and decrease engineer productivity.

Here at Google, all products are built from head. This approach has advantages: the code is open for anyone to explore and tinker with, it avoids the headaches associated with merging long-lived branches, and building from source ensures there are no binary compatibility issues between libraries. The downside is, with over a hundred million lines of code, it takes a long time to check out. And Google is a global company, which means checkout times are amplified in distributed offices. By computing dependency graphs and using this information to limit the number of files checked out, we have been somewhat successful in reducing checkout time. However, computing dependencies also takes time, and even with this improvement things still took too long.

Engineer time lost to checking out code is the most obvious cost, but the true cost is much higher. Automated build and testing systems also need access to source code. Time spent checking out code in these systems increases the feedback cycle, which decreases their utility. It also increases the complexity of these systems since they are required to maintain state on a file system and interact closely with the version control system for what is essentially read-only access to source code.

In fact, we have found that engineers check out and edit a very small amount code relative to the amount read to perform builds. This is because we always build from source, and changes tend to be localized to a small part of our source tree. So, both engineers and automated systems primarily need quick, read-only access to the large quantity of unedited code required to perform their builds. The unedited code itself is immutable, since it doesn’t change once it’s checked in to the version control system. This means we can use Google infrastructure to mirror all version control information in the cloud as a way to provide fast and scalable read-only access to source code.

In our system, every revision of every file has an associated metadata record. The metadata includes information such as the path location in the repository, the file name, size, version, and such. It also includes a digest of the content associated with this file revision. This digest is the hash of the file content itself, created using a hashing function appropriate for Content Addressable Storage (CAS). There are many areas in our system where we utilize CAS; expect to hear more about it in subsequent posts.

A view of the metadata for version 5 of /some/path/foo.cc and CAS file content:

Our system watches for changes arriving in the version control system. As changes arrive, we hash the file contents to compute digests and insert the content into BigTable. We then construct metadata records for each affected file and insert these into BigTable. At this point we have a complete history of all file versions in the cloud.

Now that we have this data, what do we do with it? We could write a command line tool to checkout code from the cloud to the developer’s workstation. This would be an improvement because it reduces load on the version control system, and replicating the data near distributed offices improves performance by reducing network latency. However it would be extremely useful if, instead of checking out source before it is actually needed, we automatically downloaded code on-demand.

This can be accomplished by writing a custom file system to provide a read-only view of the version history. The File System in Userspace (FUSE) kernel module is a convenient way of implementing a user space daemon that implements such a file system. Users interact with this source file system like any other file system, with the exception that certain path elements are special in that they configure the version information.

For example, accessing foo.cc at global version 1000 from our previous example:

The file system resolves metadata calls such as stat() and readdir() by first interpreting the version number from the path and then querying the version control data in the cloud.

For example, using gcc (or any other tool) to compile foo.cc, where gcc first calls stat() to check file existence:

This allows users and tools to explore the version control using just the version metadata. File content is only downloaded at the point where it is opened. Since file versions are immutable, content can be cached and reused indefinitely. The use of CAS provides de-duplication of file content for free and the same content is never downloaded twice.

By putting our revision history in the cloud we provide engineers with complete access to all the source, and yet almost no time is spent checking out code. Replicating the cloud to multiple geographic regions ensures that performance is similar in all offices around the world. Finally, automated build and test systems can easily access code via a simple file system interface without dealing with the version control system directly. All of this adds up to a fast and efficient system which enables engineers and automated systems to focus on building and testing software instead of the mechanics of downloading source code.

Stay tuned! In this post we mentioned dependency analysis and Content Addressable Storage. Part two in this series describes our build system and how it relates to these topics.

- Nathan York

Testing at the speed and scale of Google

2011-06-07T17:25:00.000-07:00

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:

The example above illustrates how we optimize the number of tests run per change without sacrificing the accuracy of end results for a project. A lesser number of tests run per change allows us to run all affected tests for every change that gets checked in, making it easier for a developer to detect and deal with an offending change.

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

C++ at Google: Here Be Dragons

2011-05-23T13:00:00.000-07:00

(Cross-posted on the LLVM Project Blog)

Google has one of the largest monolithic C++ codebases in the world. We have thousands of engineers working on millions of lines of C++ code every day. To help keep the entire thing running and all these engineers fast and productive we have had to build some unique C++ tools, centering around the Clang C++ compiler. These help engineers understand their code and prevent bugs before they get to our production systems.

Of course, improving the speed of Google engineers—their productivity—doesn’t always correlate to speed in the traditional sense. It requires the holistic acceleration of Google’s engineering efforts. Making any one tool faster just doesn’t cut it; the entire process has to be improved from end to end.

As a performance junkie, I like to think of this in familiar terms. It’s analogous to an algorithmic performance improvement. You get “algorithmic” improvements in productivity when you reduce the total work required for an engineer to get the job done, or fundamentally shift the time scale that the work requires. However, improving the time a single task requires often runs afoul of all the adages about performance tuning, 80/20 rules, and the pitfalls of over-optimizing.

One of the best ways to get these algorithmic improvements to productivity is to completely remove a set of tasks. Let’s take the task of triaging and debugging serious production bugs. If you’ve worked on a large software project, you’ve probably seen bugs which are somehow missed during code review, testing, and QA. When these bugs make it to production they cause a massive drain on developer productivity as the engineers cope with outages, data loss, and user complaints.

What if we could build a tool that would find these exact kinds of bugs in software automatically? What if we could prevent them from ever bringing down a server, reaching a user’s data, or causing a pager to go off? Many of these bugs boil down to simple C++ programming errors. Consider this snippet of code:

Response ProcessRequest(Widget foo, Whatsit bar, bool *charge_acct) {
  // Do some fancy stuff...
  if (/* Detect a subscription user */) {
    charge_acct = false;
  }
  // Lots more fancy stuff...
}

Do you see the bug? Careful testing and code reviews catch these and other bugs constantly, but inevitably one will sneak through, because the code looks fine. It says that it shouldn’t charge the account right there, plain as day. Unfortunately, C++ insists that ‘false’ is the same as ‘0’ which can be a pointer just as easily as it can be a boolean flag. This code sets the pointer to NULL, and never touches the flag.

Humans aren’t good at spotting this type of devious typo, any more than humans are good at translating C++ code into machine instructions. We have tools to do that, and the tool of choice in this case is the compiler. Not just any compiler will do, because while the code above is one example of a bug, we need to teach our compiler to find lots of other examples. We also have to be careful to make certain that developers will act upon the information these tools provide. Within Google’s C++ codebase, that means we break the build for every compiler diagnostic, even warnings. We continually need to enhance our tools to find new bugs in new code based on new patterns, all while maintaining enough precision to immediately break the build and have high confidence that the code is wrong.

To address these issues we started a project at Google which is working with the LLVM Project to develop the Clang C++ compiler. We can rapidly add warnings to Clang and customize them to emit precise diagnostics about dangerous and potentially buggy constructs. Clang is designed as a collection of libraries with the express goal of supporting diverse tools and application uses. These libraries can be directly integrated into IDEs and commandline tools while still forming the core of the compiler itself.

We’ve been working on Clang for over a year now so that it can understand and reason about all of the C++ code at Google. But building the tools and technology to catch these bugs is only half the battle; we have to get engineers to use them as well. When other teams at Google respond to production bugs, our team will often begin working to enable any Clang diagnostics that might have caught the bug. Within one week of production issues, we can sweep the entire code base using these diagnostics to fix any latent bugs.

Recently we enabled the Clang C++ compiler for every C++ build at Google in order to provide accurate and helpful warnings and diagnostics to engineers. Some examples of how Clang can help developers with bad code are discussed on this post to the LLVM blog. Beyond that, once we have swept the codebase with a bug-finding diagnostic, we can enable it for all our engineers to catch future bugs before they’re committed. These diagnostics break the entire build of that piece of software to ensure that they aren’t ignored and are acted on immediately. For the code sample above, the user gets an error message:

example1.cc:4:17: error: initialization of pointer of type 'bool *' from literal 'false' [-Werror,-Wbool-conversions]
   charge_acct = false;
                 ^

Here are two other classes of bugs we’ve found::

long kMaxDiskSpace = 10 << 30;  // Ten gigs ought to be enough for anybody.

void SomeService() {
  // Setup task using external resource...
  while (/* Check if resource is available yet ... */) {
    sleep(0.5);  // Yield the CPU
  }
}

Which now trigger the following errors:

example2.cc:12:25: error: shift result (10737418240) requires 35 bits to represent, but 'int' only has 32 bits [-Werror,-Wshift-overflow]
long kMaxDiskSpace = 10 << 30;  // Thirty gigs ought to be enough for anybody.
                     ~~ ^  ~~
example2.cc:16:11: error: implicit conversion turns literal floating-point number into integer: 'double' to 'unsigned int' [-Werror,-Wliteral-conversion]
    sleep(0.5);
    ~~~~~ ^~~

All of these represent real bugs that we have found in our code, and that we are catching and fixing with the help of Clang today.

Clang and its diagnostics don’t in any way obviate the need for careful code review and thorough testing. Rather, they complement these practices, combining to help reduce the number of bugs in our code. This is the platform on which we are developing new and better diagnostics for engineers going forward. This is how we are providing an algorithmic improvement to their productivity, and accelerating Google.

Stay tuned for more posts about how we rolled Clang out to Google engineers, how we have enhanced Clang to make it even more relevant for our code and our developers’ needs, and some of the exciting tools we’re building on top of this platform.

Posted by Chandler Carruth

Welcome to the Google Engineering Tools blog!

2011-05-03T09:49:00.001-07:00

We pride ourselves on being a company that develops new products and features at a very fast pace. At the heart of all of this is the way software is developed here—which enables us to maintain the rapid pace of development while keeping the quality of our products high. Of course, this rapid pace wouldn’t be possible without our world-class engineers, but a key part of Google's success is our investment in developer infrastructure and tools.

Googlers are obsessed with speed and scale—and our infrastructure and tools are no exception. With developers across the world writing, building, testing and releasing code in multiple programming languages like C++, Java, Python, Javascript and others, the Engineering Tools team’s challenge is to keep this development ecosystem running smoothly.

To get a sense of the size and scale of our challenge, take a look at some of these stats from a talk Ashish (Director, Engineering Tools) gave last year:

5000+ developers across 40+ offices around the world
20+ changes per minute; 50% code base changes every month
More than 50 million test cases executed every day
Single-rooted code tree with mixed language code
Development on head; all releases from source

… And the numbers continue to grow!

Over time we have picked up knowledge about how to keep software development running at scale. Through this blog we plan to share news and updates related to our developer tools and infrastructure, the technical challenges of keeping such an infrastructure running at an ever-increasing scale, and lessons we learn along the way.

We’d like to engage with a community of folks who are equally passionate about developer productivity. Please send us your thoughts, ideas and comments about tools and productivity challenges and solutions in your areas. In addition, please point us to other leading research and industry work in the engineering tools area.

John Thomas (Engineering Manager) and Ashish Kumar (Engineering Director)