Rust Programming Language RustFest Rome 2018, 9 Dec 2018

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: RustFest Rome 2018 - Matteo Bertini : Simple CRDT in Rust

Description

A conflict-free replicated data type (CRDT) is a data structure that can be replicated, each replica can be updated independently and it is always mathematically possible to merge the replicas back without conflicts. The simplest CRDT is an _append only_ Set, where the _merge_ is the Set union, building upon this idea we can compose more complex data types. In this talk we will explore how to implement a `cli` for a CRDT shopping list, see how Traits are emerging during the code evolution, use cargo to include some useful crates with no pain, and document the code with runnable examples.

https://rome.rustfest.eu/sessions/simple-crdt-in-rust
https://media.ccc.de/v/rustfest-rome-10-simple-crdt-in-rust

A

Okay, my name is Matteo.

B

A

I work for SS doctor and our work in Florence and here to talk you about simple charity in in Rus, so the economy is already being funded, completely related data types enough data type that can its thing to be replicated in and as a property that you are free to update the replica without coordination and eventually, when you need some uniform you or your state, you can merge all these replicas together and convert to some unique state, and why are this interesting?

A

They are interesting for these properties and they're interesting, also because some piece of software is using them. So, if, like you, can find them implemented in.

A

The sig text engine is the reason why I started to look about this stuff because in the implementation of the shortest acting, these kind of thoughts are used. A lot, so disciplining is in fact double. We have to kind of these data types. We have the state-based one where C stands for convergent and in this kind of implementation and reasoning, we are moving the states, all the state and merging the state, and the operation based was distance or commutative in that kind of limitation.

A

We are moving on the operation, but they are formal equivalence and the first one is a bit easier to think about. So we will try to start something about them to some example.

A

So, let's dive in, let's think about a little problem, we have a start-up. We are starting to our new application. We are building our chartered shopping list, we'd like to have all the cool properties.

A

Some kind of application must have now so we'd, like your work, is connected to merge in some interesting way when we, the network here, is there, but we will soon end up with some kind of conflicts, because our Li, we decided to literally take the list as the structure, and the order is something that is creating got some problem, so we can make a step back and say: okay, in fact, the set can be enough, our shopping, and this is the first intuition about reality. Not every data type is valid reality.

A

You cannot implement all the interesting features you'd like to implement, if you for other types, but some of the data types are policy oddity and for them you have all that good properties.

A

So we have this set and we start thinking. Okay, I cannot pass that my said, my wife cannot paste. My set I can find that set. Union is some kind of valid way to merge them, and what I have created is something called its I grow only set the set that can only grow because our operation needs update is our update.

A

Operation is adding stuff and adding may only grow, or if the item is already there, let certain change it and the merge operation is Union and I am not losing anything when I'm doing Union and so I'm quite happy with the solution in rust. I can implement this as a simple themed wrapper around and ash. That I will add my value that it is an Alice four string.

A

This time to my set, the update is local and requires no coordination and whenever I need to merge with some other state, I will have a reference of the same type and return.

A

We are not mutating here, we're returning a new copy, but that is, we are returning and you type any resistance of the same type here is another intuition about CID keys. Both the add the update operation and the merge operation are growing. Inflating are not shrinking our data set, and this is something that we must ensure when we are developing some. This kind of data types and the merge operation has other cool properties, because we can merge our would be or be with our and the result is the same.

A

If we have more than two items, we can merge them in whatever order we like and result the same, and we can merge our with our again and result is our and is as properties that must hold for C oddities and here kickin another cool aspect of these tough types. Whenever you build something that works, that is verified, you can compose these small pieces together to build something more interesting. We had a set that can only grow.

A

We can take two of these sets that are allowed to grow and compose them in what is called a two-phase set. We will have the set of the other staff and the set of the remove s star. Both of them are growing.

A

Our merge function that is now appeared appearing as a tree is simply for boarding the merge two hours subfields, but now we have to do something more before the grow. Only set. The action to the query we are doing on the set was simply having all the items back this time we have to do some kind of operation. We have the stuff we added to the list. We added pasta. We added pistol if I bite, pasta, I put it in the remove it set and then I take the set difference.

A

I have only pistol left by, but it's not yet enough for our shopping list, because, if I buy pasta, if I add pasta, I bypassed I cannot have pasta anymore, and this is that problem. So, let's introduce another trick about CIT the tag trick. We have the simple string value. Our item was simply string this time. Our item is at a poll of two items. The first one is some kind of unique tag, this time, simply a string, but usually we are going to make to add to the item to the tag some more metadata.

A

Usually you will have some kind of counter some kind of timestamp. We know we cannot use it to order think because they are originated from different devices, but we are only using these times m to make something unique than some device ID or user ID or stuff like that, just to show something interesting to the user. The important thing is that is unique and then the value, what user care about?

A

Again, we can use composition, we are doing what is called and observer to remove, set building upon our to face set before that was it set with two Rolly set and modify a bit our API, or at least our API, is almost the same when we are going to add, we are taking the value. This time is again string. We are generating some kind of new unique tag and we are adding the couple the support to the to the set.

A

Whenever we are going to query we are going to under create it, we are going to ask our sub field the items with for us the difference and we are going to show the user only. The second part here is another intuition about CIT. Most of time, your state is more complex than what you want to show to your user. The state is some kind of implementation detail of your data type. You use a clean only on about a part of it and what change it?

A

What we are introducing is the strategy we are using to avoid conflicts, and this time we use this kind of strategy whenever we are going to remove something we're going to remove only something that we can locally observe. So, for example, if I added pasta, it will be implicitly target as pasta Matteo.

A

Whenever I am removing pasta, I will look up in my other set. I will look only for the user facing part of the value. I will add to the remove it set all the matching tuples, with all the matching tax I find locally in my added set. If before we merge before I, am removing something someone else added again pasta to our shared set.

A

Whenever we merge, I will see popping up again, pasta and, if I add some intelligent metadata, I can show that Giovanni added the pasta whenever, when index time, I was buying it or one hour later or whatever and I can decide to call him or to do something reasonable. This is up to the problem we are facing. We have used. This is what is called ad win strategy. We can apply some remove win strategy or some other strategy, but it's up to the problem.

A

What you want is to avoid conflicts and to apply the same algorithm. All your instances of the coat brands around your dust types.

A

So some try around tweet. Imagine from this journey. We have an implicit one or second simplicity. We had only the function, add and remove that were taking directly value. We can had some kind of update trait working on some kind of a Newman and enforce what we said before, so that, after an update, our state must grow. Our state, in fact, can be forced to implement partial older, just to check that some order is a what the theory asked us is verified.

A

Then we have the merge trait that operated on the same type is closed. So I am working on our server to remove, set merging only with the same type and returning same type, and we can see with you can find the formal verification, but we can intuitively accept that Union is valid, merge operation for sets and the maximum is valid, merge operation for numbers and then a query trait.

A

Whenever we are going to ask something to our data structure, we must implement it straight so that we can explicitly declare what is the sub part of the state we'd like to show, or we can also generate something on the flight Buzzard on what's inside state and.

B

A

Trait was hidden before because we had some kind of an animal, a unique tag generator. Usually your tab will like to we likely introspect your local state and generally, it's some kind of next tag for some kind of order we like to have- and so here the reference to the self and.

B

A

This is local and you can do you can evolve your state without coordination.

A

So in the abstract, I talked about clean I have not time to show you here, but it's on the wrapper and just to thank some creates. I used cloud plans. Truck top are fantastic and not in this project, but quickly is very neat use. I used some other common line tools and here's some references, the first one. If you have time it's very interesting, it's one hour and stuff long, video from marcia pedo. It was one of the name behind these data types. It will eat, reduce the theory behind them eventually consistent.

A

All the theory about eventually event well, consistency- and here is the paper that will introduce you a lot of data types that are verified to be capt.

A

You can use, you can find, sets counters registers and then you can build upon them graphs, and if you are brave enough, you can reach the collaborative in text edit or state at the end, and if you like to dip on the on death aspect inside the exceed that documentation is, there is a series of blog post now groupid in the documentation that will explore all the trade off and all the problems you may find if you'd like to take from the toy level to something derivative deliverable, because here we are moving all the state when the state starts growing, you have to find some compromise you'd like to move less and you like, perhaps to forget something from the very very old past, and you have to find some compromises about this.

A

Here is my code you can find is very educational. Is you can find it from the steps from simple append-only set to the observer to remove set till a generic implementation?

A

This is quite long if you want to require all of the parts Tahlequah as stuff you are required to, and if you do something like that or if you do what the author or a capt did, we can fire again or your check and requirements, something like quick check and have some kind of be sure that your code is respecting the rules and there are a lot of implementation in other languages. You can look at so what I am suggesting? It's, it's, not black magic.

A

It's quite the paper are not so easy to read, but if you are accepting something by intuition and not going deep in same a lot eyes connected join stuff that you may perhaps know if you are mathematician, you can be something interesting with acidity. Thank you.

B

A

B

You Matteo: maybe we have time for a couple of questions.

B

B

So maybe that's not the point of the talk, but I saw a lot of high level structures used like hash map and I immediately thought about performance concerns. So what are the solutions.

A

So if you'd like to deepen those performance problems, perhaps the rope series is what it's like, because is.

A

The trade-off is between something you can easily use and something that is usable in reality with big text files and the Rope is using for the text. Editor are a bit complex stuff, and so he found a lot of good implementation solution for while maintaining these kind of properties. But it's something that you can find on your exact problem. Maybe.

B

B

Okay, look sweet done! Thank you, mother.