Rust Programming Language Rust Belt Rust 2016, 9 Jan 2017

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Pijul: Sane Version Control — Pierre Étienne Meunier

Description

This talk is about a new distributed version control system written in Rust, based on category theory to define conflicts properly, but nevertheless as fast as even the fastest competitors. Its main distinctive feature is to implement the naive intuition of how distributed version control system should work: a branch in a repository is just an (unordered) set of patches. This makes it really easy to use, which we believe has the potential to help beginners collaborate with others, and get non-programmers use version control for their work. Our tool can also simplifying the workflows of big projects, especially since it handles big codebases faster than others. Moreover, the solid theory means it is easy to understand and predict what it does, which makes it easy to script and reuse in other projects.

While previous systems based on this idea failed to compete in speed with the more widely-used tools out there, we invented a new data structure to efficiently handle asynchronous parallel contributions to a repository. We believe our construction of this datastructure can be reused in other contexts, especially since Rust is really well-suited to parallel computing. This talk will explain the architecture of the software, and what made Rust the best tool for writing it. We'll also talk about a few open problems, both about the theory and the implementation.

http://www.rust-belt-rust.com/

A

All right thanks, Dean thanks everyone. This is my first software, a conference ever simple little impressed or I'm going to talk about the project I've been working on for about a year. Now it's called people from the name of the Spanish bird. It's we're trying to do same version control and by saying, like I'm, going to like this talk, mostly about what sane means and what vertical should be like, so it all started because I was trying to surf long Baker.

A

My coop in this project, myself we're trying to convince our co-authors and an academic paper to use version control instead of just emails and like like reserving files for a week and analytic file right. So so, but well flow happens to be one of the core darks developers, which is a like rather old, ish version control system, and so we couldn't really convince him to use anything else.

A

So we try to convince our co-authors to start installing darks and windows and then like setting up SSH keys and pushing to pushing patches and pulling stuff, and that didn't really work out so well also turns out. It's darks has performance problems and get as simplicity problems so well. I wasn't really easy to do anything about this and that's pretty much the situation with vertical roll today, like most people, most non hackers, don't even use it. So it's write widely, regardless of hackers thing.

A

Most people like use extremely basic version: cultural, even like top like world experts in in computer science, still use like fight locking in emails, and that makes us lose a significant amount of data and or time and even the situation with programmers and sorry say, isn't much better because like as soon as distributed version controls for invented their like, if they were so complicated and hard to use that like business, is even started to resent, relies them and use the use.

A

The use them in a centralized way in order to master the Beast and Pramod this functional programming as finally convincing people that they can really tackle. Everything like all feel the computer science that were that were previously regarded as like elite field, just like Ashley showed us for operating systems. We're trying to replace C++ with rust recently also JavaScript.

A

It's like it's trying trying to get replaced by Elm package managers and Linux distributions are getting replaced by like nicks, it's not widely accepted so far, but and so these talks about letting adenine other functional tool to that collection, and it's called we start out to replace, gets. Probably this goal is as ambitious as for us to replace it, C++ or maybe more, but but anyway, so before.

A

Starting this talk, I just want you all to like get give some basic concepts about what I well I think functional programming is so most people have their own definition feel free to agree or not with this so I, think functional. So by what I like in functional languages like rust, is that there are static types. So we don't like. We can reason about code easily, there's fine control of immutability. It's like we're, not mutating some, some states all the time we're just thinking about transforms and stuff in functions.

A

Most operations are atomic, which is what most people use when they use like any software at all, and it's something that's not really happening in most most software Mo's tools, and we also like memory safe seaweed. We don't want, like you just corrupt our back hand or correct our storage, our files or something we don't want to lose data just because we're using it like using types in the wrong way.

A

So how does that apply? To? Has there any beneficial to version control? Well, because the way we use version call today has mostly about States we're talking about comets.

A

If we use gifts, we're talking about comments and coming so state fool they're, just basically a hash like a patch to like make it easier to expect, but it's just in optimizations just to make it easier to store and and their hash of the whole state. The repository. That's where the comment is, and will you commit something you just advance the head of the repository bye-bye, one small notch and you has to all state of the repository. That's the name of your new new comment and that's quite different from patches.

A

So patches are all about transforms. They are all about like bringing like any stays like applying. When you apply a patch, you can basically apply a patch to a file and it's like that's what most people think um it's our with the first first discover guess, but but then they realize it's not that's not the case, and so this can have major benefits like, for instance, in like any system that uses three-way merge such as like git, mercurial, lesbian, CVS and like most others.

A

They don't have that really cool property, that we call the sensitivity in algebra and that property is the following. So if you have two of two people at least in Bob and you're, not really good communication right, you're a couple well at least bride's, like the red patch here and Bob in thrall that writes that, like first a blue patch and then a great green patch, well, depending on the order in which you merge things. Depending on what like your merge strategy, you might get different results in three-way.

A

Merge like if the patch are exactly the same. I like first I try to merge the blue patch. First and then the green patch I might guess in get sometimes I might get different results. Then, if I do the other, you have a theme like on the image on the top. If I merge, the two branches I may get one result and if I merge the two like the exact same patches and they are not conflicting, they are not like. They are not weird.

A

The situation like you're dealing, they're, really different parts of the file, sometimes Bob's patches might get merged in parts of the files is never seen, and when you consider applying tools like that to like highly sensitive code such that it's like cryptography, libraries, it's kind of scary, but it's like what everyone does, and so so, what's even worse is that you can.

A

Actually, you can actually tell when this hits you like, if you're a gates user- and this happened to you- there's no way it doesn't wait to tell get says: yeah I've merged, it's fine, it works and you don't you don't notice it. Maybe it maybe it even complies like. There are real-world examples of this. This thing: it's not just an implementation bug that can be worked around. It's like a fundamental problem in the three-way, merge algorithm all right, so we're we're not the first ones to believe this is wrong. There was another version called system.

A

I talked about in my intro slide, which was called darks. It's still still called darks by the way, so they so they are their main. Their main principle is that you say two patches are okayed of like fighting with each other down conflicts if they commute so with that, that means it's simply that you can apply them in the order. Well then, you're, like oh, they almost commute, it's not exactly like.

A

If, for you would like do W RL into algebra, it's not really commuting, because you sometimes you may have to change the like line numbers like, for instance, if Bob at the line called which containing just F and main and slang one and at least adds a line that, like line 10, saying println hello world, when you merge them well, you might have to merge at least Elise's line after Bob's line at line 11 instead of 10, but that's what that's kind of commuting anyway.

A

So that's our that's the situation with darks when it commutes it's fine. What if it doesn't commute which happens sometimes well, it's an under commanded part, the algorithm. So no one really knows what it does flow home. My co-author on people is one of the core darks developers and he told me like I, was pretty confident in darks before they told me at some point yeah. We have no absolutely no clue what it does. It seems to work most of the time.

A

It's like it's highlights conflicts, but we don't really know other than that, so that praises obviously issues about correctness. So the situation with darks not much much better than we were kids well at least highlights complex and warns the user about complex, but then what it does no one knows. Another problem is slightly bigger.

A

That's the main reason why darks was in, but I've been done, even though it came before before get is that it sometimes exponentially slow, so exponentially, slow in the size of history number of patches in their position and so that some people to device the like merge over that we can work through where you like, try to synchronize all the patches you made during the week and instead of synchronizing like while you're working on it you're, just like waiting for Friday night to arrive start to merge like booster patches and well, hopefully, by Monday morning, when you come back to office.

A

Well, the patches are merged, but sometimes not so. This is this is no. This makes it kind of like not really acceptable, and this is also one of the reasons why we could not convince our colleagues to out to use it because they tried to use it naively thought yeah well patches. Well, we cannot understand what they are. So, let's try to push about bunch of patches repository and well. They were surprised to have to wait for like half an hour merge. So it's not usually like that like when we write we're.

A

Developing people were using darks to develop it and it's like we've never had we've never ever runs you that's brought that problem, but that's also because we're like we know how it works. We know what the drawbacks are. We know when the exponentially is slow merges happen. So, but that's not acceptable like that. It's it's not like I, wouldn't recommend it to anyone and that's where people comes in, so we try to after our day trying to convince our colleagues to use this.

A

We just like grab, grab a beer and started discussing about like the here. If patchy is what which could be like what what good way would be like, you have a cool patch algebra we could use, and that would be simple and easy to use and that's where we're starting to learning about category theory. So we don't exactly started learning learning it back then, because it's a kind of it's now. It's not the easiest theory on earth on earth, but well, so whether it is what it is.

A

Basically, it's a general theory of transformations of things so clearly theorists like to see it as like the general theory of everything the there are numerous attempts to rewrite all mathematics in a categorical language and I think it's pretty successful, except that no one can understand this.

A

So it's already well written. We have all mathematics in there, but no one knows what it does all right. So, but it's pretty good for us, though, because it's a so we're trying to talk about changes and files, and this is a theory of changes of on things, so one particularly cool concept. So this you can, you see all like I I should like these things in darks. These are commutative diagrams and category theories. Try like drawing them basically all day long.

A

If several colleagues working mates they have their whiteboard through that these diagrams, sometimes in 3d. Sometimes it like, we are interleaved arrows and no one knows, but what they are doing, because they're yeah they're talking about transformations on things all right, so in particular, when very cool concepts of category theory is the concept of push out.

A

So push have is a depreciated of two patches is like for in our particular case, the push out of two patches would be a file such that, no matter what you do after these two patches that yield the common States like a common file. So if at least in Bob write some stuff and then later, they can find some patches to agree in a common file. Well, the via star here is a. We call it the push out. If you can reach the car, you can reach any common state state in the future.

A

From that star that clear, alright, so anything you can do to reach common stage. You can also reach it from the Prashad. So that means the push out is kind of a minimal common state. That can be like that. You that you really need to reach leg, and it's really watch what we want. In a version control system, we really want push out. We want minimum common states that any further developments any further work in the repository can also be reached from that common States.

A

That's what a merge really is, and it's it's it's it's so the run problem is that it's not the case at all. Categories have push outs. Have all shouts like we see that, like the translation of that in English, is it's not clear than any editing any of any couple of editing operations on a file will always be merge about, like sometimes we have conflicts. We all know.

A

Like most programmers know, bits are in conflicts, so it's not the case that tries have piles and patches have old shouts, but what's cool, but category theory is that there's a solution? You just need to dig into them like pretty big books of like abstract, diagrams that I don't fit in, but then you can ultimately find something called the free conservative code, completion of a category and that's a way to artificially add all push outs into the category.

A

So that means when you, when you have a category of files and passes between files, the free conservative code, completion is a construction that will automatically give you a category like a generalized generalization of files. So that's like that.

A

Generalization will have all push outs so in people, if we translate it into like files and patches, for instance, if Bob adds the line country like saying just print a line Bob and at least at the lines in just print a line, at least when they merge that in people, what they get is just a graph of lines where the two lines are added: they're, not comparable.

A

If not yet said what like how they should compare and how they they should relate to each other in the file you may be, at least is write, anybody's right, maybe you're both right, maybe they're, both right, but in a different order. You don't mean. Oh, that's a conflict, and so what that theory or the category theory gives you here as a generalization of files, its which is well in most cases a little more complex.

A

That gets more the the benefits for a three lines, file or maybe not obvious, but when files get really large, it's it's really great to have that sound theory that backs you up and right. So that's that's what people is about. That's that's how it works.

A

So I want to say before moving on that this is quite different from see our LEDs sociology's are conflict-free replicated data types and people is more like conflict, tolerant, replicated data types, so we're not resolving all the conflicts. All the time we're just rather than that, we're just like accepting conflicts as part of the system like the data structure can handle like it can it can represent. Conflicts doesn't have to resolve them all the time, and so that's what makes it fast. That's what makes people really fast because you can apply many patches.

A

They are conflicting, but that's alright and then, once you are done applying a bunch of patches you're, you can just like detect conflicts and I'll put the files and that's it. So what what would the situation be with theologies if we were trying to apply your leans to this problem of like merging patches? Well, in theory, oddities, you need to always order. So the way it gets real complex is by ordering all operation determine deterministically, so it finds whatever solution like whatever deterministic merge algorithm.

A

They can find to like just order order things all their operations in an arbitrary but deterministic order like, for instance, we can have a rule same lease, Elisa's patches always can always come first and when there are two conflicting patches from at least I'll just take like take them in alphabetical order, for instance, and so you know in our case that would like lead to the following file like two lines. One saying print a line at least one same printer and Bob and the user would barely see anything they would be like yeah.

A

That's that's it. The merge has succeeded, but that doesn't that isn't really right, because that, like it, the user should that be we at least be warned that there's a conflict and they should do something about it all right. So the end result of that it's well, the fury is a slightly more complicated in what I've explained, but not much more. The result of that is that we developed a sound theory of fashions sound the giraffe patches.

A

It has the following very cool properties, so bear with me for a moment what I'm right like saying these like bad words, so they're the the fury is like the or algebra is commutative. It means you can like if pet cheese don't depend on each other, you can apply them in any order. So that's that's what you would expect from that cheese right, it's associative, so we resolved the initial the initial problem and started this talk with so you can.

A

You can basically like no matter how you merge patches if the merge is right, like there's only one solution to merge and you're, not you're, like you're, not getting into trouble like by you're. Never like do you're never doing what get does, which is like merging things from Bob in parts of the fight is never seen. That's what associativity is about, and also one very cool property, is that all past is about semantic inverse, which means when you're, when you've read in a patch you can.

A

You can derive in other patch permits that has the like the opposite effects and then like push it to other predators. You cancel previous patches. The thing is you can, since you can it's, it's all commits all commutative, so you can basically compute an inverse for pets. You boost like 1,000 patches ago, and it all just works, and it it does even better than just working. It's also pretty fast, so merging and applying patches, it's basically the same operation in our system. Well, it's possibly the last complicated slide.

A

I've written like there I'll move on to like easier stuff. After that, so our complexity for people. We know complexity here. Our complexity is like linear inside of the patch and the guy, with make in the size of history. So it's like it doesn't like. You can have an arbitrarily big history. It's not it doesn't really matter like you can. You can apply the new patch, your new patch P, after an arbitrary alerts arbitrarily large number of patches.

A

It doesn't matter, it always works the same like almost, and this is this is actually that was surprising to us, but it's actually better than three-way merge, which also adds in a like square factor of the size of the file.

A

That's actually really also observed that in real world cases, where we're trying to benchmark like in early stages of our development, we were trying to burnish mark it against like really fast competitors such as yet and as file size increase. We not. We actually noticed the difference in performance to the point that people who was actually faster and get when merging, really large patches on really large price, which I'm not really sure, is a real-world case, but anyway, and so that brings me to the last part of this talk, so why?

A

What made Russ a cool tool to work with? What did we like and rust and how it helped us build this, this cool new system, so one thing is we're working on our algorithms mathematical objects, and that means we need types. We need to be able to reason about our code and that's very important to us like we couldn't really like. We want to develop a sound theory of patches and we couldn't like the implement it and then rely on like our intuition to build correct, CC, Curcio C++ code. That would be like yeah.

A

Maybe the theory is correct, then what about the implementation so because we have types and rust that makes it easy to do so, but we also want to be fast like as I said, like the complexity theory stuff tells us that we have the. We have the potential to become faster than gates, and we really want to exploit that potential and we really want to to have like to be as fast as we can and rust.

A

That I was also asked to do that because we can add, like we can use a like fast back hands. We can add, like roll pointers, to like the parameter memory like I'm Maps and what now that's really cool, and that wasn't the case in the early prototypes that were really not in other languages, but also more. Maybe more importantly.

A

So we started doing that because we couldn't convince Windows users to install dark cinder machines and, and that's and and our goal was to be as inclusive as possible was to like green version control to everyone. But we cannot really do that. If can only tell you a small portion of computer users which are like expert Linux users, and so what we really loved in rust is that we can write clients and servers for real word protocols. So I had to write some of that myself, but it was actually quite pleasant right, but also yeah.

A

There was a there's a Lord unit, an HTTP stack working out pretty well and I wrote the message, library, alright, and so we finally got Windows support and so I'd like to thank the rust developers. For that. That's that's really awesome thanks.

A

Ok, so as part of like what needed to be Bradon because rust, pretty young language, there aren't that many libraries, so there are I, just wanted to conclude with two really hard things like two really two things that I really did didn't put didn't. Think I would have to write when I when I started its projects, so when, as a as a project that I call sonically I'll just finish word for dictionary, there was infinite time. Well, security has a transactional on this b3, with like many others, like LM DB.

A

If you know an MV like many other database backends, but it's particularly is that it has a fork operation. That trends in logarithmic time, like a fast for corporation, so for cooperation, means you can clone the database in like log log in time and then have two copies of the database, behave as two different databases, so I needed that to implement branches and still work in progress, because it's really hard to do I'm coming back to it in a minute and then there's a another bacterial agent. Just like crossed fingers like I crossed.

A

It's called fresh, it's nested current and server library. They wrote it's. It's been made like it's really entirely in rust, and it's been it's gotten rid of all unsafe blocks two weeks ago, thanks to our brian smith, who's, not okay. So the trickiest parts, the trickiest thing that I had to do in where this is sanic area. So why was it tricky? Well because rust always wants to free everything before the program closes and when you're writing a database back-end, it doesn't really sound right.

A

You won't like something to remain on disk after the program closes, so that was really hard. So you have to do like manual memory management, you're, like--you're yourself, and that's not really when you're used to a functional programming, high scale or cameras like coming back to manual memory management, isn't free Pleasants.

A

So how does it work so I'm going to explain anyway? How rust helped us do that? So how does it work? It's just not going to be very technical here, but like most database and Giants are like sorry. Some cool database is enjoying that I liked are based on be trees, so B trees are basically like trees made of blocks in each block. Yours, there are like ordered elements.

A

There's no word list of elements, there's a constant number of elements and between these elements you have pointers to other other blocks to children blocks, and it's so insertion happens. It believes and then, while the blocks plate, when they're gonna get too big, but that's well, that's how B trees work, there's a good B tree library in the standard brush library. So now that's cool, but we can actually use it to like it doesn't allocate inside the files.

A

So yeah it's allocates the program's memory, so we have to write a like a different like a new library for B trees. That would work in files, and so the main thing I've wish I knew when I started. Writing that as about iterators, so wait I'm coming back to it.

A

So when, when sometimes in B trees, you have to merge blocks when they're when they get to like well when they get to like under fool, we have to merge them and something I wasn't doing in the beginning, because, like since, since I was doing manual, memory management, I figured I could like, like the root habits came back and I was like okay, let's do manual like manual stuff, roll pointers and manual things, and that's not really the right solution, Rus, because you can use like cool right things anyway, even if you have to roll pointers so main thing, I've learned, while doing this is iterators and how to use them.

A

So merging pages like merging blocks like this can be done in the following way. So if right, you're, basically right in each other, like two iterators one for each page, there will like give you yield like all elements, all successive elements in the two pages, and you can then chain them and add other elements in the middle. That's exactly what you want to do with your merchant pages and well deletions and B.

A

Trees are usually pretty tricky and that allows you to our get tested really easily, and so the main reason why I've, why I really like this is that when you're prototyping, usually your your head is kind of in a messy state, and you really don't know what you're going to so most of the lines. You're writing will be deleted in the end, and you really don't know how to proceed.

A

What to do, and so this kind of hurry, concise and and short sorts of statements allow you to uh to get that phase and get like production ready code much much faster, because the prototype start working much much faster. Another thing is that I've learned is that. Well then I was like oh yeah, so we can have saved I've tried like we can have cool attractions anyway. So then there has Carol, reflexes came back and I was like oh yeah.

A

Let's do recursion, let's put in record recursion everywhere, and one thing I've learned is that it's not always so in Russ you can't you can write very concise code, but the recursive way is not as surely the most concise you can do so in sanik area, for instance. Sometimes we need so it's on these cried so there's a every time. You load something from this from this kit.

A

Like cost you a lot, so you want to avoid like do you avoid doing that at all cost like and any time you can avoid loading, your page, it's a map right, so anytime, you can avoid loading your page to the program's memory. You won't really want to avoid it, and so, in order to do that, the solutions that will do things lazily so we're, instead of deleting something or adding like I, think new element to the sabitri. What we're doing is just like we're doing it lazily.

A

That means we're we're just saying well, next time you want to do something you have to copy too. You have to copy the page and update everything, but just at the time of doing it not right now, because we we don't really know what we're going through this page. Maybe we will merge it, maybe we'll drop it and it would be a huge waste of time to copy it and then edit it or or copy it and then merge it.

A

That would be like we would have to copy the page twice, instead of just once so, in order to do that, we need to have like write actually something that looks like a recursive function. Well, we just have to the that function, which we have access to. Several consecutive elements in the programs call stack and that's not really easy when you're writing a like writing, it's really recursively.

A

So the way it's done actually at the moment, it's there's a fake call stack it's just basically an array and the fact that B trees are well balanced, means that there are not actually they're not actually going to eat up the world memory of the computer.

A

So you know that the the the death is not going to be larger than 64, so you can allocate an array on the stack and and write like how does fall off a stack pointer, so you're basically simulating the program stack and so that these are the two main things I wish I knew when I started writing something yeah. So just why do? Thank you especially you're. A spell trust organizers. This conference is awesome, we're really enjoying us and if you have questions, I'm, really happy you're, answering Thanks.