GitHub Git Merge 2022, 18 Oct 2022

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Git at GitHub Scale - Git Merge 2022

Description

Presented by Taylor Blau

This talk will cover how and why GitHub uses Git to host and serve millions of repositories. We'll cover GitHub's fork of Git, our development model and merging strategy. We'll also cover what new features GitHub has used from the upstream community (like commit-graphs, partial clones, etc.) as well as features that GitHub has developed (like MIDX bitmaps, and cruft packs). We'll discuss each of these features in detail, covering their impact on GitHub, as well as the open-source project. We'll also discuss future directions, including more bitmap enhancements, the use of merge-ort at GitHub, and more.

About Git Merge:
Git Merge is dedicated to amplifying new voices in the Git community and showcasing the most thought-provoking projects from developers, maintainers, and teams around the world. Git Merge 2022 took place at Morgan Manufacturing in Chicago, IL on September 14th and 15th.

A

Welcome to the final stretch of talks for today this is git at github scale. My name is taylor.

A

Blau,, I'm staff engineer at github, where I get the privilege and honor of working on git every day.

A

My work at github is kind of broadly speaking, divvied up into two categories.

A

I get to spend about half my time working on the open source. Git project spend time.

A

There triaging the mailing list responding to bugs submitting patches things like that.

A

And I spend about the other half of my timer so working on this thing that I call git at github.

A

So, broadly speaking, my goal there is to help teams within github, find and address problems.

A

Scaling to bigger and bigger repositories and rate code in order to achieve that direction,.

A

So today I want to talk about sort of three aspects of my work. First, I want to talk about.

A

What it's like to use and deploy git at github, so we'll talk about our fork model where and why.

A

We use git and why we made those decisions. I'll also talk about a handful of features from the.

A

Upstream git project that we've used at github and the impact that we've been able to have.

A

And finally, I'll talk about a handful of features that I and some others have written at github. That.

A

We've then shared with the open source community and the impact that it's had in both places.

A

Let's start with git at github: first, a couple of numbers: github has 200 million uh public.

A

And private repositories on github.com and among those we serve about two and a half.

A

Billion annual contributions per year, so that's every time somebody writes a.

A

Commit or pushes the repo or opens a new issue that all contributes to this number.

A

So powering all of this is a lightly modified fork of the open source git project. We know and love.

A

And we've called that fork at github, github git it powers, many of the internal apis and processes.

A

That drive the website anytime, you push or fetch or clone from github you're, interacting with git.

A

It also powers our periodic maintenance jobs that we'll talk about a lot in this talk, as well as all.

A

The rpcs that drive the contents of the website there's a handful of rpcs that aren't implemented.

A

Using git, we use libya2 for those, and I think by and large I'll mostly skip over them. In this talk.

A

So, what's in github git, the most boring answer is that it has a handful of uninteresting.

A

Patches that are sort of specific to github's infrastructure things like blogging or metrics.

A

Talking to other internal services and things like that, but more excitingly for me, it's the home of.

A

All the new feature- development we do in git at github, so here we implemented multi-pack bitmaps.

A

It was a staging ground for a lot of the commit graph changes we sent upstream a few years ago.

A

And it also is the permanent home for our tree level. Git blame implementation, which we'll talk.

A

About in this talk, we deploy it continuously to github.com, often a few times a week, and we.

A

Back merge with upstream git, usually one or two major versions behind the latest release.

A

Our work basically looks something like this: you can see. New work is happening.

A

At the bottom, those little black dots in between merges with upstream git, we.

A

Try to stay between one or two major versions behind the latest from the open source project.

A

So natural questions: why would we power the sort of ludicrously scaled product based on.

A

The open source project we could have picked any technology, including rolling our own, to drive a.

A

Lot of these operations, but we chose git for a few things. First, we think git is fast and it's getting.

A

Faster every day, thanks to the contributions from many of the folks that are in this room.

A

We also know that it's battle tested it's running billions and billions and billions.

A

Of times a day across the sort of collective of all developers, laptops in the world and.

A

So we can count on the reliability of this product to work for github too. We also know.

A

That it's secure github uh is the beneficiary of a huge open source community of people that.

A

Are finding and fixing security vulnerabilities in git all the time, but, most importantly, I think.

A

Using git is a mutually beneficial choice, both for github and the open source community, because.

A

Each gets to drive improvements in the other and that symbiotic cycle is pretty cool to me.

A

Let's talk about a few of the features that github uses from the open source project to drive.

A

Contents on the website we're going to touch on three we'll talk about the commit graph and change.

A

Path, bloom filters, partial clones and what you just heard from elijah a little bit on merge ort.

A

Start with commit graphs commit graphs are an upstream feature that was developed by derek.

A

Stolley, my colleague then at microsoft, now at github and what they are, if you're unfamiliar.

A

Is an on-disc serialization of the data inside your repositories commits so it stores a table.

A

Of the retreat id the commit date, any parents and octopus edges corresponding to all of your commits.

A

It looks something like this on disk and what's really important about having something like this.

A

In place is that it allows us to sort of skip the classic parsing and deflating an object in order.

A

To read different parts of a commit, because we know we can just drive all of this stuff by table.

A

Lookup, so it makes history traversals really fast by eliminating a lot of the costly steps.

A

So we maintain these on the server every new push that you send to github generates a new layer in.

A

The commit graph and occasionally we'll take many of these layers and squash them down into.

A

One slightly larger layer in order to keep the commit graph chain, pretty small. We also use pretty.

A

Importantly, these change path, bloom filters which were developed by garima singh, while at microsoft.

A

And these store what is called a probabilistic set of the changed paths in each commit relative.

A

To their first parent and so for any commit, we can ask: did this commit change, path x and we'll either.

A

Get back the answer, it definitely didn't or we'll get back an answer that says probably, and we can.

A

Determine with high probability that that pad was likely changed by that commit, and so we've been.

A

Able to use all of this to accelerate a number of history. uh Traversal operations on github.com.

A

That are scoped to specific paths. By being able to ignore parts of history that we know don't change.

A

The path of interest, so I'm going to show you a few graphs of what it looked like to deploy. That.

A

Starting with git log, this powers, all the history views on the website, you can see there where we.

A

Deployed change, path, bloom filters and commit graphs, we were able to drive the p999 or the.

A

99.9 percentile down from about one and three quarters of a second to just around one. Second,.

A

Here we're looking at the git blame operation. That's that line level history operation there.

A

We were able to drive about a 40 reduction in the 99.9th percentile by using bloom filters.

A

And you can't quite see it, but there in the top right, we were able to drive down significantly.

A

That sort of flat horizontal line which represent timed out operations into a state where they would.

A

No longer time out, quite as frequently at the top end for us, we also uh had a similar improvement.

A

In the tree level, blame implementation that we use at github here we were able to drive down.

A

The 99.8 percentile performance from about three and a half seconds to just two seconds so we're.

A

Really excited about this and being able to drop off some of the timeouts there at the top right.

A

Let's talk a little bit more about blame tree though so blame tree is a custom command like.

A

I've said that provides the tree level blame information on github.com. So if you've ever.

A

Noticed that second column in your repository tree views, it just shows the commit message of each.

A

Commit to most recently touch every directory uh entry, and so last year, derek stoli and myself at.

A

Github thought that we could make this algorithm a little bit faster, so to tell you how we did that.

A

We basically looked at the existing algorithm, which is sort of the naive approach, and it.

A

Basically, recursively blames uh recursively does a tree diff at each level in history, assigning.

A

The current commit to each entry in the tree based on whether or not it was changed at that path and.

A

Hasn't yet been blamed, and we just repeat that until either we reach the beginning of history.

A

Or we've blamed everything in the directory. The new algorithm works a little bit differently. The.

A

General idea is to only compute tree level, blames where we need to so we keep track of sort of the.

A

The remaining interesting paths or the unblamed paths, and we can skip over parts of history where.

A

We know that we've already assigned some commit to an entry, and then we pass any unblame paths to.

A

The parents and continue until we either blame everything or reach the beginning of history.

A

So we're able to deploy this again and blame street performance improved even further moving.

A

The 99.8 percentile down to just two seconds and we saw a significant drop off in timeouts.

A

In that sort of 99.9th and top level 99.99 percentile there at the top right, so you're.

A

Really excited to see this operation succeed more quickly and more often for users on github.com.

A

Next thing I want to talk about is partial clones. Partial clones are an upstream feature.

A

That was developed by jeff hostel or at github and jonathan tana at google, and they allow you.

A

To clone just specific parts of your repository, you can dictate this by specifying a filter option.

A

At clone time, which allows you to say, I just want blobs or I just want trees of depth, zero and so on.

A

Here's a few attempts of me cloning, the linux kernel from github.com, is sort of a classically.

A

Large repository to talk about, and you can see my best attempt over a pretty fast network- was.

A

Just shy of five minutes: that's all the time it takes to get all the objects from github.

A

Necessary to build and compile the kernel, the partial clone which just downloads the.

A

Blobs, reachable from the very root of history uh takes just shy of two minutes and so we're.

A

Really excited about being able to deploy this change on github.com to allow our customers to.

A

Work more quickly in even bigger repositories, just on their laptop. Finally, I want to talk.

A

Briefly about github's deployment of merger rt, a lot of these details uh were covered in the talk.

A

Just before mine and elijah's, but I want to talk about how this work sort of progressed on github.

A

So we compute merges all the time the background on github.com. They power the existence of.

A

That merge pull request button that hopefully you're familiar with from the pull request view.

A

The way these work basically is, every time a pull request advances its state. We proactively.

A

Try to compute the merge of its head and base in the background to see whether or not we're.

A

Actually be able to merge that uh pull request when all of your builds have passed. For example,.

A

And then, when you actually click that button, all we do is a reference update in the.

A

Background in order to point at the merge commits that we've generated ahead of time.

A

We used to power this at github, actually using the recursive merge engine, which was the predecessor.

A

To ort, but the problem was this required a working copy in order to represent the conflicted state of.

A

A repository since github stores bare repos, we actually had to temporarily spawn a hydrated or.

A

Full working copy of any repository we wanted to computer, merge on and then perform the merge there.

A

Copy the objects over and spin down the copy- and you can imagine this is pretty slow, especially for.

A

Large repositories, and so a number of years ago, my colleagues implemented the same strategy in libya.

A

2, which eliminated the need to have a working copy of the repository present most recently elijah.

A

And johannes, both johannes and get up and elijah palantir collaborated on bringing all the power.

A

And speed from ort into git merge tree, which is a command that we've now used on the server side to.

A

Power all merges on github.com. This work was done by my colleague, johannes at github, and greg curl.

A

This was the result of deploying merger rt to github.com. There were too many graphs to.

A

Pick from- and this was just the most beautiful thing that I could have imagined- we were able.

A

To drive down the p99 times dramatically from sort of six or seven seconds to well under a.

A

Half a millisecond so we're able to much more efficiently generate merges on the back end.

A

Finally, I want to talk about a few of the features that I and my colleagues have developed at github.

A

That we've sent to the open source project to achieve bigger and bigger scales at github.

A

So we're going to cover four I'm going to talk first about multi-pack reachability.

A

Bitmaps then we're going to take a two or through two sort of sub projects that were.

A

Developed along the way, we'll talk about on disk, reverse indexes and geometric repacking.

A

And lastly, we'll talk about a recent development that we've used to eliminate unreachable objects.

A

On github.com that we call cruft packs, let's start with multi-pack bitmaps, so.

A

A brief refresher every time a repository gets pushed to on github.com, we add a new.

A

Pack to that repository representing the objects that were sent to us by the client.

A

As more and more packs get added to the repository, the performance can degrade over time and in order.

A

To keep repositories running smoothly, we do a periodic maintenance routine that effectively.

A

Compacts, the set of packs in a repository to make sure the performance runs smoothly.

A

This is basically amounting to something like running the following, which takes everything and.

A

Moves it into a single pack, and so you may be asking yourself: why would you actually want to.

A

Take some of these ludicrously size repositories and generate just a single pack of all of their.

A

Objects, it seems kind of slow and wasteful there's an naive answer, which is that any operation needs.

A

To do object, lookups has to consult all of the packs in your repository in the worst case in.

A

Order to find the location of each object, so if you have just one pack, that operation becomes.

A

Really really quick, but the key point for us much more important than the sort of speed of.

A

Object lookups was having reachability bitmaps. So what are reachability bitmaps? A bitmap allows us.

A

To very quickly answer the question: what objects are reachable from some commit? Every commit gets.

A

Associated with a long bit string each bit in that bit string represents an object and when.

A

A bit is one: it means that that commit can reach that object and when it's zero, it means it can't.

A

This eliminates the need for object reversals if you want to know the set of reachable objects from.

A

The tip of your main branch- you can just read them off of the bitmap instead of having to actually.

A

Crawl throughout history, and so this is a crucial optimization for us at github, because those.

A

History, traversals can often be unbounded. We're able to combine these bitmaps in sort of some.

A

Cute and intuitive ways like, if you want to know the union of reachable objects across multiple.

A

Bases you can just take the bitwise or of all of their bitmaps. Similarly, if you want to compute the.

A

Set difference say the objects that are reachable from some set of tips, but not reachable from some.

A

Other set of tips like when serving a fetch, you can just combine these with an and not operation.

A

So these bitmaps are great, but the problem is they can only encode information about objects.

A

That are contained in a single pack, and so that's the reason that we needed to pack.

A

All of the repositories objects down into just one humongous pack file, but for us we noticed.

A

Starting a few years ago that this operation became prohibitively expensive as repositories.

A

Continued to grow larger and larger that we often couldn't re-deltify and compress all.

A

Of the contents of a repository into a single pack within our maintenance, timeout windows,.

A

So to address this limitation, we turn to an upstream feature developed by derek stoli called.

A

The multi-pack index, the midex acts like a single index over multiple pack files and I've drawn it a.

A

Little bit here so here's a cartoon that shows a few packs on the bottom of the screen identified.

A

With some colorful little objects in between them and the mid x, which spans all of the packs takes.

A

The unique set of objects described and contained in the packs of your repository, and it refers to.

A

The location both what pack contains each object and where in the pack, you can look for the object.

A

So we have this idea that we could start with the mid x and define what we call a pseudo pack order.

A

Over it that we would then use to generate a bitmap based on the contents of a mid x.

A

We thought if we could do this, that we'd be able to repack a repository in sort of any.

A

Arbitrary structure of packs that we wanted write a medics containing just the packs we.

A

Want to keep in the repository and then write a bitmap covering those packs. So we thought that.

A

Would look something like this there's my same diagram from earlier extended with a bitmap on.

A

Top just with some randomly chosen ones and zeros to indicate which objects are reachable.

A

And we're really excited about this until I realized it wouldn't work, because there's no.

A

Way for us to map the fifth bit which points to the blue object back to the blue object.

A

Let me show you why this is the case. You would think that the way you would do it is by counting.

A

The number of objects in the packs prior to the one containing the blue object and then knowing.

A

The pack relative position of the blue object in order to narrow down which bit pertains to it.

A

But this doesn't quite work because you actually need to know not just the number of objects in.

A

Each pack, but the number of unique objects across all the packs preceding the uh the containing one.

A

You can see there there's actually two copies of the red object down below, but the mid x only knows.

A

About one of them, and so you're going to be off by one in either direction when you try to go look.

A

For the blue object, so we knew we needed something better to address that we began sort of the first.

A

Of two major side quests on this expedition to implement something called on disk, reverse indexes.

A

So a brief primer packs, like we mentioned before, contain a sequence of objects in a semi-arbitrary.

A

Order indexes map the objects in those packs to their lexicograph. Sorry map the objects in.

A

Lexicographic order to the corresponding offsets in those packs and reverse indexes do the opposite.

A

Task they take a pack of objects uh in their pack order and map them to the lexical order. So reverse.

A

Indexes are something that's been in git for as long as I can remember, these are uh exist already.

A

And are used to power things like computing, the on disk size of some object. If you want to know.

A

The on disk size of a given object, we'll look in the reverse index to find we'll look in the.

A

Index to find the position of that object and then use the reverse index to find the position.

A

Of the immediately adjacent object and compute their difference in order to determine the size.

A

The way we do this is by generating it in memory on the fly by a rate of sorting an.

A

Array of an object id and offset pair this works. It uses the most sort of efficient.

A

Sort that you can imagine in this regime, but it still takes time proportional to the number of.

A

Packed objects and, more importantly, it's super memory intensive, because we have to store about.

A

32 bytes worth of information for each one of these records. So not only do you pay the.

A

Cost in sorting time and sort of persistent memory allocations, but it can often take your.

A

Library, uh measurable amounts of time to just allocate that much memory and hand it to you.

A

So get up a number of years ago sort of improve the situation by implementing.

A

A sort of precursor to the on disk reverse index as an optional extension within the bitmap format,.

A

This is a custom format that uh we developed at the end of the bitmap file and it's a table of.

A

Four byte unsigned integer values that each correspond to a packed object in the pack.

A

Corresponding to the bitmap and these this table was stored in pack order, and each value is the.

A

Lexicographic index for each object, and so when we were trying to address our problem of mapping.

A

That, fifth bit to the blue object, we thought we could actually use this bit. Cache extension as.

A

A good starting point, so we decided that we could upstream it and then use it for multi-pack bitmaps.

A

But that it required a bitmap to be useful because it was implemented as an extension in the bitmaps.

A

And so we wanted to do something a little bit more general and for that we implemented the rev.

A

File, this is a new on disk format that sits aside your packs, just like pack indexes it can be used.

A

Outside of the bitmap file, and it corresponds to both the packs and middixes for packs, you can use.

A

It with or without bitmaps and for midxes, it's really only useful. If you have a bitmap today,.

A

This is a little bit of what it looks like here. You can see I've drawn a pack with three objects.

A

A red, yellow and green one which appear in that order in the pack, but in lexical order.

A

You can see the yellow object, precedes the red one which precedes the green one.

A

So if you're looking at the yellow object in the pack- and you want to know which what order does.

A

It appear in lexically, you can just follow the arrow to the reverse index and read off that value.

A

One and then, if you look at the array, subscript one in the index file, there's the yellow object.

A

So we were pretty excited to deploy this at github because we thought we could save some time by not.

A

Having to sort through this big uh in in memory reverse index- and we were really pleased with the.

A

Result so this is the p50 fetch time for fetches on the homebrew core repository. This is a sort of.

A

Classically or well-known highly trafficked repo at github, and so we're really happy to.

A

Drop uh the run times in p50 from about two and a half seconds to just under 500 milliseconds.

A

And we actually saw this continue over all repositories at github.com. Here's.

A

Just the sort of p50 through p99 runtimes in one single site, showing fetches across.

A

All repos in that site and you can see we achieved about a 40 speed up there.

A

Most importantly, though, we were able to use this to untangle our problem from a few slides back.

A

So you can see if you want to discover that the fifth bit pertains to the blue object. You just.

A

Follow the arrow down read the fifth array element in the reverse index file and you can see that it.

A

Corresponds to the 11th index in the multi-pack index file and I'll spare you, the counting, but.

A

If you go 11 spaces from the left, there you'll end up with the blue object. So now that we have.

A

This in place, we thought we could define a pseudo pack order of all the objects in the mid x, which.

A

Appear themselves in pack order, and then we arrange the packs by sort of grouping them.

A

According to how new they are- and we eliminate ties in favor of sort of this preferred pack.

A

We store this order in either an on disk reverse index file or, as an extension within the.

A

Multi-Pack index more recently, and we use that to be able to translate bit positions from the bitmap.

A

To the corresponding entries in the midx file, so now that we had sort of unlocked this arbitrary.

A

Pack, structure capability: we need to figure out how we were going to repack repositories at github.

A

So, to do that, we implemented something called geometric repacking when we were searching.

A

For sort of what strategy we wanted to use, we knew that we wanted to achieve two properties.

A

One that, on average, relatively few packs, would remain after doing repository maintenance. That's.

A

Key for that sort of object, lookup, speed thing that we were talking about a few minutes ago.

A

And we also wanted it to be the case that, on average, the work required to get to that new pack.

A

Structure would correspond roughly to the number of new objects that have entered the repository.

A

Since the last maintenance run the simplest approach that we could think of, that would capture.

A

Those sort of two properties was to make the packs appear in a geometric progression of sorts, so the.

A

Idea there is that each pack contains at least twice as many objects as the next largest pack.

A

So let me show you a little bit about how we compute those.

A

Here's a pack structure, there's about seven packs here and you can see the green ones. I've colored.

A

The first step is to identify how many large packs already obey this property. We're sort.

A

Of doing this, geometric repacking thing all the time, and so we expect the bigger packs which are.

A

Going to change on average, less frequently to mostly already be in this progression.

A

So we count off and we say: okay, the top five packs are already in progression, and so I know.

A

Everything to the left of that line is going to have to get repacked into one single new pack.

A

But as soon as I do that I'm going to throw off my progression because the first pack will contain.

A

Two objects, but the second pack will only contain one, and so we violated that doubling property.

A

So we then expand the line in order to figure out how many packs we need to sort of compact.

A

Together at the low end of the spectrum, in order to restore this property, so here you.

A

Can see in this example, we need to combine the four smallest packs together in order to.

A

Restore that geometric property that we talked about and that's what we end up with as a result.

A

So, between on disk, reverse indexes, geometric repacking, ultimately multi-pack bitmaps we're.

A

Able to deploy all three of these together to achieve a pretty dramatic reduction in the time.

A

It takes to maintain repositories on github the blue line. There is the sum of all time we've spent.

A

In maintenance on sort of a individual basis and the gray line- that's just above it is- is that same.

A

Value from a week prior in case you're having a hard time reading the y-axis I'll tell you that.

A

We saved five and nearly two-thirds of a cpu day every single hour on github.com, with these changes.

A

We're really excited about that. Finally, I want to talk about a sort of more recent development.

A

That we've made to clean up unreachable objects at github. You may be wondering what is an unreachable.

A

Object well, they're, all the red ones in this picture, so an object is reachable when you can.

A

Start at some branch or tag walk throughout history and find yourself at that object.

A

Walking out here just mean to say you started a commit and you look at its parents or a tree.

A

And look at its sub trees and blobs, and so on any object that satisfies that property gets colored.

A

Blue- and it means it's reachable here- any object that doesn't is red and means it's unreachable. So.

A

We have kind of a lot of these at github. They come from all sorts of places. Test merges force, pushes.

A

Branch deletions any of these can create a set of unreachable objects and, historically we've. Let.

A

These grow without bounds, so we'll almost never clean up unreachable objects. Unless you ask us to.

A

But sometimes we do have to clean up unreachable objects, so users will request a manual cleanup.

A

Say to remove sensitive data, they accidentally entered into a repository or if they noticed.

A

Poor performance- and they just want to clean up- do some spring cleaning we'll help them out with that.

A

So support engineers respond to these requests by running the dot gc command on chat, which triggers.

A

A garbage collection- and it basically causes us to run something like the following, which has.

A

This unpack unreachable keyword at the end of it. What this does is it takes all the reachable.

A

Objects and moves it into one pack. It takes any unreachable objects which haven't been written to.

A

Within the last five minutes- and it just deletes them from the repository- then anything that is.

A

Unreachable but has been written within the last five minutes, gets stored as a loose object. You.

A

Can remember to the very first talk of the day where we discussed what loose objects are here.

A

So why have this cut off? Why not just delete all the unreachable objects at.

A

Once the problem is that there's a little bit of a race between object, deletion and.

A

Object advertising. Let me explain what I mean there so suppose: you're a git server and you.

A

Decide that you want to prune and just remove this object c, which we'll say here is a commit.

A

Before you actually do, that c becomes made reachable by some ref update or just background.

A

Operation and then another client starts a push they're going to hear about c via the.

A

Reference advertisement and then they may send you a pack that contains c in it or.

A

Worse, it depends on c in some way. In that case, objects are going to then enter the repository.

A

Which are dependent on c either by referring to them or being stored as a delta, amongst them.

A

And if all of that happens before c actually gets removed, then you have objects referring.

A

To c in the repository without actually c itself, so that leaves the repository in a corrupt state.

A

So what we do to accommodate this or what git did before our recent changes, is that.

A

It would store these sort of pretty recent unreachable objects individually as loose files.

A

The stat level m time of each loose object file would track the object's age and then rewriting.

A

The object, which just means anytime, we sort of wanted to write it as a new object entering the.

A

Object store. We just take that existing loose file and set its m time to the current timestamp.

A

And this works fine in practice makes the uh the race that we described a few slides.

A

Ago, less likely to happen, but it has some other problems, namely, if you have a lot of unreachable.

A

Objects in your repository, it can result in creating many loose object files, especially.

A

If those unreachable objects have been written to relatively recently, some other drawbacks too.

A

If you have pairs of unreachable objects, which have very similar contents, because they're stored.

A

In separate loose objects, they're not allowed to de-duplicate amongst themselves and share contents.

A

But the most important problem that we faced is that having too many of these files can lead.

A

To significant performance problems, including inode exhaustion, which basically, we were able.

A

To observe at github a single repository, garbage collection would annihilate the.

A

Machine hosting many thousands or tens of thousands of repositories in one fell swoop.

A

So to address this, we introduce this concept that we now call the cruft pack. This is an.

A

Old idea that was originated by jeff king on the mailing list and the idea is relatively simple. You.

A

Take a pack in its index and you associate all the objects in the pack with an m time. That's written.

A

As a table of integer numbers in an m times file, so you no longer have to store each unreachable.

A

Object loose, you can just read the value in the end times: file and anytime. We say that a pack.

A

Has both an index and an m times? We can group that into a concept that we call cruft packs so.

A

The remaining part of my time I want to talk about how we generate those crossbacks, there's two cases.

A

There's sort of an easy case and a little bit of a harder case. The easy case is when we know that.

A

We're not going to expire any objects out of the repository. All we have to do. There is mark all the.

A

Reachable objects create a pack containing them, then take any remaining objects which didn't show.

A

Up in that pack pack, those separately along with their m times and delete all the existing packs.

A

When we're doing object expiration, it's basically the same process as above, but we don't want to.

A

Pack, all the unreachable objects. We just want to pack the ones that we know are old enough. Sorry.

A

That we know are new enough to need to remain in the repository. Any old objects will get deleted.

A

Except before we actually create that pack, we want to traverse any unreachable objects that.

A

Were new enough to stay around in the repository and rescue anything that we were able to reach.

A

Along the way, the idea here is that if a cluster of unreachable objects gets partially deleted and.

A

Then that cluster then becomes reachable via a later update. That repository would be in a.

A

Corrupt state because it'd be missing some of its reference, but if we keep around all.

A

Of the objects in unreachable clusters, as long as at least one of them is surviving, then we.

A

Can eliminate, or at least significantly reduce the likelihood of that happening in the future.

A

So let's uh go through a few animations here, so first, this is how we generate objects. I.

A

Generated crough packs without object expiration. We mark all of the reachable objects by starting.

A

At each branch tip and following the arrows throughout history, coloring them a slightly.

A

Darker shade of blue and then we take a look at all of the objects in existing packs and scan.

A

For their existence in the new reachable pack, we're going to color them green. If we.

A

See them in that case, we know where they're reachable in red, if they aren't, which case.

A

Will mark them as unreachable and generate a new pack containing just those objects.

A

When we want to generate a cuff pack with object expiration, like I said earlier, we want to keep.

A

Unreachable objects in clusters around in either a sort of all or nothing state. So if any part of.

A

A cluster that's unreachable is too recent to be actually deleted from the repository we keep all.

A

Of those clusters- and we perform that by doing a reachability traversal over the recent objects.

A

Here you can see, we take all the unreachable objects and start it just the ones that are.

A

New enough to stay in the repository marking them as we see them and those objects then get.

A

Entered into the craft pack, instead of being pruned, we use this at github by geometrically.

A

Repacking, the repository sort of every eight out of nine operations and the ninth maintenance job.

A

Collects repositories into a reachable and a craft pack in normal course of maintenance. We.

A

Don't bother to any ever prune these objects, so we do a repack croft with no expiration.

A

But github support can still respond to requests from our customers by running.

A

Gc repo, which, instead of unpacking unreachable objects, now has a cruft expiration, parameter.

A

I want to talk about one more thing, which is that we still have the problem of being unable to in a.

A

Race-Free manner prune objects from the repository, so my colleagues had an idea that instead of.

A

Eliminating this race entirely, we've actually used crough packs to make it far easier to recover from.

A

So this is joint work with my colleagues, michael haggerty and torsten walter from github and the.

A

Idea was to move every unreachable object that we were going to leave to delete from.

A

A repository into a separate craft pack that was stored outside of the repository.

A

We can then, after we do that, do an integrity check on the main repository to ensure all.

A

Of its objects are still present if they aren't we'll restore them from.

A

What we call the limbo repository and then remove the limbo repository once we're done.

A

So the limbo repository crucially is really just another cruft pack, but has two tweaks. One is.

A

That generating that cruft pack will exclude any objects that it found in both the reachable and.

A

Craft packs, in the main repository it also doesn't have any sort of pruning conditions, and so every.

A

Object that it sees that meets the above condition ends up in the limbo repository. So this means that.

A

Every object that would have been pruned during a normal gc ends up in the limbo repository in the.

A

Destination specified by this sort of experimental expire to option, and I have some rfc level patches.

A

That explore this concept on the mailing list, for anybody curious enough to try it out.

A

So, to recap: I'm going to leave you with four things: git is a reliable, fast and secure.

A

Implementation that can be relied upon even at github scale. Github gets to use features from the.

A

Open source git community, including partial clones, commit graphs the multi-pack index and merge ort.

A

And github also contributes tools that it develops back to the ecosystem, like multi-packed bitmaps,.

A

Craft packs and more finally, what I want to say is that the same tools that powerghettup.com can.

A

And do run on your laptops all the time, I think that's pretty cool. Thank you, foreign.