I first of all want to talk about how this confidence is possible.
It's not any sponsor, it's not any big company organizing this, it's not me, it is volunteers.
And Dylan is volunteering today to help me organize this day.
First of all, I'm an applause for organizing.
I will forget myself later.
I am introducing Dylan Nalswell's speaker today.
We actually have been working together on some amazing open source projects, which are also super complex.
And I was always complaining about 500 variables, throwing around everywhere in our codebase.
And somebody very smart said, let's fix this and let's build something called StateDB.
And it was so interesting that I invited Dylan here on stage to talk about this.
Run for pass for Dylan.
No, it's not that green.
Other side?
Yeah, that's all.
All right, thank you all. How is your fourth name?
Yeah, how are you doing?
Great.
So you need not more excited?
It keeps on for the rest of the day.
So I would like to talk about StateDB for I do, like a little wham I, my name is Iamank.
I work for Isabel and which is now part of Cisco.
I'm a silly contributor.
Thank my main, my main job, and I do, I'm a refuer for the CBPF project, which CBM silly muses.
And for those of you who don't know, those are both like very go heavy projects.
To explain why StateDB, I need to explain a little bit about Sillium.
So Sillium is a cloud network product that both a lot.
Won't go into it very deeply.
But I like to draw a very basic diagram of like all of the things that go in and out of Sillium.
API servers at CD and why a bunch of things on the kernel and even interprocess on the same notes.
And what tends to happen is a lot of information comes in.
A lot of events happen.
We need to reconcile all of that information.
And we need to do it, we need to do it quite often with a lot of different data.
So if you, if we look at how you store program state, one of the very naive approach,
like which, which is good like to start with always, is you take a map.
I put my data in a map or an array or some sort of container.
Now I need to make it multiprocess or slap a local in there.
And then we replicate this pattern.
So I made an apple manager and an orange manager and they managed to own little bits of data.
And these have consumers.
So what tends to happen is that these managers are created by different people with different goals.
They take maybe the same data, maybe different data indexed differently.
And you have to create some sort of API for this.
So with a normal map, you would just make a lookup function at that function at the lead function.
But with a look, as you add a look, so you can look and defer the release whenever you do it in a function.
But this doesn't always work.
If you need to operate on bits at the data.
So what we often have is we say, okay, we need to like loop over this map.
So to do that, we need to hope to look the entire time because we can't have changes in the middle of looking at it.
So, but you don't really, like, so what ends up happening is you need to expose that looks somehow to your consumer, which is back practice, shouldn't be done.
Or you create some sort of callback mechanism, we say, okay, let me loop over all of the state that I have and call some sort of callback function while that look is held.
But in the callback function, your consumer can do anything, including, for example, to help me through some other manager taking another look.
And this, this calls of problems. So we have stated the way we discussed some problems.
And the biggest one that I found that is actually super breaking is that looks.
So let's say consumer one takes the look from Apple manager and then orange manager and consumer two happens through it the other way around.
If they both happen to take their own looks for like the preferred looks first, then they need to both wait for each other and your application simply stops working.
No one can proceed and there's no way to recover from that.
So to summarize, we have that looks, we have data duplication, which was also the thing, like, you have a store, you have a map, but you need to have a key.
And not every consumer wants to index on the same data, someone to, for example, take a Kubernetes resource index on the name, but all the ones to do it on a namespace or label set or something else.
And we have a bunch of these API variations, which we're really frustrating for developers because you do it one way here, you have to do it another way here.
Every time you want to use some data to relearn how this specific bit of call did it.
So we started looking into ways to fix this.
And the big inspiration was Jacob Nomad.
So Jacob Nomad is also sort of cloud orchestration platform.
And the way they dealt with distributing state is to use something called GoMMDB.
So they have a raft protocol to basically pick masters and those masters are where you insert data and they distribute everywhere.
And this distribution of data is picked up by a single thread in their system.
And it takes, and it writes into this in memory database.
So we looked at this and this was, like, 90% of what we want, but there are a few issues.
Namely, we had a single database right look.
And we typically have not one place very insert data, but a lot of producers of data.
They, it's an older code base, so they, they used plain interface sold and we want to type safety.
And there were just a number of small little features that we wanted and they just didn't have yet.
We actually first started with this as our basis.
But then we wanted to, to do with to add some things.
So we basically took that and rewrote it to suit our needs.
So we added generic, so all of our tables have generic data types.
Independent right look, so you can look multiple tables independently or sets of tables.
And also like the few other little features that we're talking about.
So we can initialize tables.
We can watch tables.
So whenever things change, we can see what happens, metrics, it's a nice iterators.
Optimistic concurrency, stuff.
I won't be talking about all of this, but these are, these are, like, the things that we, the added.
So to summarize what is, what is this in memory database, state to be.
So it's in memory, it doesn't persist to this.
And your application starts up, you get it, empty database.
You need to populate to yourself.
Technically, you can, like, persist to yourself, but the library just doesn't do it for you.
And because it's all in memory, you can actually have very complicated data types in there,
such as maps, channels, pointers, like you name it.
If it's a go type, you can store it as a value in the store.
Something you wouldn't be able to do on a disk easily.
It has multi-version concurrency control.
So multiple processes can read and write.
And you can, and they don't interfere with each other.
So you can have a re-transaction, a write transaction going.
And the re-transaction will still see, like, all of the data consistently.
We can lock across tables, so we can, we can lock up set of tables together.
And then, like, update them together in a transaction or not.
But multiple indexes, so you also have primary index, which you can make as many secondary indexes as you want,
to index at same data and watch channels, which is a concept we took from Hasicorp.
And the idea is that you can, basically, you do a query.
You got a channel back to see when did my, like, did my query change, did the content change.
So how would you use something like that?
I'm back to the Apple, to the fruit example.
I created an Apple.
I created, I defined an Apple ID.
I will come back to that as part of it.
So that would be the ID part of my key.
And I assigned the grade, which is there's an enum, a letter A to F.
And then we create a table.
In this case, I'm creating a global object from the table, because that's easier from a standalone perspective.
In our case, we use it in a via dependency injection method.
So, but for, like, a standalone review, this is, this is best.
So we define it as a readable and writeable table.
You can technically also cost it to a read only table if you want to.
And we, we said it, it stores an Apple.
And we give it some, and we give it to indexes.
So the ID index is a primary index, and the Apple grade index is an index,
so it's no longer a key, but on this value, this is a great value that it has.
So the primary index looks something like this.
So we have, so, so I have this Apple ID.
It has a two key method.
I defined this myself.
It's just, it produces a bite slice where it takes three numbers that just makes one key out of it.
Put it in a key set.
And we, and I take the Apple ID itself, and I call the same method.
So what you'll notice is I give this index a name, this is just for observability.
From object is whenever you insert an object into the database, it will call this function.
To translate it to get a key from your object, whatever it's shape is.
And from key is when you do a query, so you give a key to a query.
And it will, and it will go into the database to actually find it.
The unique part is, because it's a primary index, it has to be unique,
which can also have a new unique indexes.
For example, the grade one is a non-unique index.
If I, I can have multiple, I can have multiple apples with the A grade, for example.
And what I did here is I took the grade.
Because it's an, I have to cost it into, into you into 32.
And the index that you, you in 32 is just like predefined.
We have a few predefined functions that take go data types and turn them into keys.
And again, a key is just a, a bite slice.
Anything that can be represented as a bite slice can be indexed in the database.
So we start our, we create our database, we register our table, and we start it.
So this starts, this start bit is starts a background worker, which is important for a few things.
I've got produce a few apples.
So, oh, so when I produce something, I write a transaction.
I say, I will defer the commit. I insert my apple.
And if something errors, I will abort my transaction.
And but you can imagine that you can do this with multiple, multiple things.
I didn't take the first and the second argument that it returns, but it actually returns the old object.
So if there was already an apple with the same key in there, it would return me the old apple that it has replaced.
And the Boolean tells me if it did replace something or not.
Basically an insert and an or update.
Getting it is very simple. So we, again, we, we do a get with a reach transaction.
We have the, we create a query from this ID.
And we get our, we would get our apple back.
To read the whole table, we use a different call.
So we tell the table, hey, we want to get all and watch.
So you, every apiical has the or most apiicals have this watch variant, which would, so this returns an iterator.
So they, they, these are the new, the new iterator types.
And they, it just returns me an iterator of apple.
And the watch is a channel, just an, an empty channel with a, or a channel with an empty struct.
And it gets closed by the database when, in this case, because we query the whole table of anything happens to the stable.
It, it, it closes the channel and notify us that, hey, your data, you, there's something new you, you can observe.
We can do a prefix watch. So if you notice, if you notice, here I have orchards, three and a number.
Here I only have the orchards and the three.
So this is only the first part of my key. And I can basically say, give me every apple from this orchard and this three.
And it will give me everything with that prefix prefix in the key.
And you can use this for IP addresses, strings, even stuff like, stuff like this.
So what is the practical example of this? So this is how, sort of, how we use it.
So we have a bunch of resources on the top.
This, they, they live in the Kubernetes API server.
We have a GRPC watch that goes into a component called Recall or Reflector.
There's no part of the library, but something we built in Selium.
They go into tables and these tables can then be observed.
And the cool thing about this infrastructure is that you have the tables as an abstraction layer between all of your components.
Meaning that if I wanted to test my LB Reflector, I can, in my test, leave out the Reflectors and the map.
And I can just create a bunch of information in my tables.
This is my input. And then I can assert that after it's records that after it's like looked at it,
that it produced exact output to my, to my lower tables that I expected.
So I can test my components in isolation.
It's also extensible.
So like we've got a few errors going off to other components that need to use the same information.
And if some component needs to index it, then we just add a new index to the existing table.
And we don't have to create a separate completely separate data store.
So how does this internally work? It's actually a really cool data structure behind it,
called an immutable depth of red X-3.
So to explain it, we'll first start at the red X-3.
For those who don't know, I added six objects in here.
And what are red X-3 does is effort.
So it's essentially the idea of a binary 3, where you sort things,
where you sort your keys, but instead of having two children,
you can have 255 children.
So it's basically a 3, where your nodes get very, very big.
So the yellow ones are my nodes.
So this is what something would look like and everything with a common prefix.
Everything with a common prefix shares nodes in this way.
The depth of this has to do with how the data gets represented.
So normal red X will be the picture above, where you would use 255 pointers for every time you get a byte.
You can basically look that up in an array and get your next node.
But 255 is very big if you have a sparse set.
So what the depth of red X-3 does is it picks smaller nodes if you have less data in there.
This is essentially an implementation detail.
There are four different nodes.
So the small node gets represented like this.
So you just have an array of your keys and your pointers.
And you simply loop over them to find the next one,
because it's just fast to some modern CPUs.
And then only when you need to do very big, when you actually have very wide trees,
you scale up internally to use bigger nodes.
And this is both faster and lookup and also memory use.
The immutable part is the thing that makes the database actually work.
So if we go back to our red X, what if you want to update this?
So let's say I'm going to add a testing node to this.
So the steps would be for an immutable red X-3.
So we kind of change existing the existing nodes.
We create a new root.
The T, we already, we know that T is a shared node.
So we basically take the existing T, we copy it.
So we copy also the existing link it has.
We know that EST is a node.
So this is both a leaf node and so it has a value in it.
And also goes further.
So we copy it.
And then we put our in under it.
So now we have two copies of this bit.
And if you actually look at.
So if you look at this from the new point,
I can still access all of the same nodes.
That I would be able to from the left accept.
It's also a testing.
So basically create a sort of diff between if I were to just modify it three.
I just add the difference.
From our immutable red X, the way we, this would work is we have a consumer.
That says I'll give me the root node.
So it gets the old one.
Now the update happens.
So these green ones get added.
We switch the pointer over.
So it's a sort of RCU change.
And then the new node comes along.
It says I'll give me the root of three.
It gets the new one.
And this is how our versioning works at a basic level.
So the new consumer can see the new version, the old consumer
can see the new version, the new changes.
And they can both independently operate on this.
Man, the moment the consumer one goes away.
There are no longer any points or studies to this root.
So it gets actually garbage collected by go.
It's by the go runtime itself.
It just automatically goes away.
And we can rearrange the three.
And from that on, it just seems as if the three always had.
Had it like this.
So we have a sort of generational radics tree that keeps growing and going.
And when you want to use this in a database, we extend this out.
So you start with a database with a database root.
The root has a bunch of tables.
And every table has a multiple indexes.
Every index is actually one of these immutable radics trees.
And so these are not, this is not a radics tree.
But it uses the same principle.
So every time we update a table or an index, we make a copy of the header of that index of that table.
And we do a sort of, and we do a generational copy.
And then we just switch the root database pointer.
So the way these queries work is because we have this tree.
We can exploit its properties to the queries.
So if we wanted to query a very specific object, we simply,
because we know that they are sorted from less to more.
We can just basically do sort of binary search through our tree work tree.
But we can also do the prefix.
Sorry, this is a lower bound search.
So you basically say, I want to have this key and everything that is more than this key.
So we can, we basically get a split.
And from that point on, you can traverse the tree from left to right,
all the way until you find all of the leaves.
You can also do a prefix search.
So you say, OK, this is my prefix.
And then you can traverse the whole stop tree.
So this way, we can do a bunch of these queries.
Secondly, indexes work like such.
So a primary index is just, I just made a primary index.
A primary index with one byte for now.
They point to objects.
And every, this is a unique one.
So every key points to exactly one object.
And they come to know.
Our objects in the below want to have this full property, which is a slice.
So we store a slice in there.
And we can actually index on that slice.
So we create a full index.
We take the primary.
So we take that value.
We index it.
So we get bar or bas.
And then every bar or bas points to one or more.
Like, or points to the, to the actual objects.
But they're still the same objects.
Whenever we, whenever we did this moving.
So whenever we duplicate it, we actually copied objects.
But just something to remember about this.
Because if you, if you have some objects that don't like shallow clones,
then it isn't ideal for storage in here.
Because then you get very weird issues.
And I told you about the watches.
So I showed you where this channel comes from.
And the way this works is every header.
So this is the header of every note.
No, never mind which of the four versions to this.
It has some flags.
It has this, the prefix.
So we can compress a prefix.
So we don't just have one bite for one note.
But we can have path compression.
And it has this watch channel.
And what happens is whenever we do, whenever we did the cloning.
Or we have a transaction.
And our transaction keeps track of which objects were replaced by a new version.
And whenever we commit that transaction,
we basically just loop that list of everything that's changed.
And we close the watch channels.
And because of the prefix, because we do the prefix searches.
Or specific one, we can just pick one of the notes.
And return that watch channel.
And when anything changes, that is relevance to your query.
That is the way you get notified.
So transactions, so I talked about transactions,
both having some commits.
So on abort, because we have this generational copying.
Whenever whenever you make a copy.
And you decide, oh, I don't want to use this copy.
You can just remove all references to the copy.
And let it be collected by the garbage collector.
There's no additional work in doing a abort.
Whenever you say, whenever you say, I don't want this transaction,
which is just as collected.
And the interesting bit, so I talked in the beginning about that looks.
We use something called a sortable mutex.
And I'm going to explain it with sort of mini animation.
So let's say we have five tables.
And I have some rights transaction,
and I want to take two, four, and five.
That's possible.
They are available, so they get taken.
And the rule with sortable mutex is that you always take them
from left to right.
So you first take two, then four, then five.
So let's say a second transactions come along.
That wants to lock three tables.
It can go, it can lock one.
That's no problem.
But two is already taken.
And it will block.
But because we always do it from left to right.
And the first one, unlocking.
It means that this will be okay.
Let's say another one comes along.
Three is still available.
So this one can be taken.
This thread will just go on.
So we don't only the middle transaction is waiting
until it can access the tables.
The, our old one goes away.
And then we can start looking to.
But now we still have to wait.
So, but we progress.
So every right transaction will always progress.
And then also ensures a level of fairness.
It's not perfect.
Scheduling wise.
But because you always lock an unlock in this ordering,
you can basically guarantee that you're never,
that you're never going the opposite direction.
You never have two people waiting for each other's looks
that are held.
And that's what our looking issue.
So the last thing I wanted to show is the change tracking,
which I find one of the best features in here.
So what you can do is you can say I have a table.
And I want to, I want to watch all of the, all of the changes
that happens since the last time that I did something.
So you can basically do one BigQuery process something
and then from then on only process the differences.
So you take, you need to take a right transaction to create
to get this change iterator.
And that's because it does a few things in the background
which you need a loop from the table.
But after you've done that, after you've done that,
we have the, we take a right transaction.
And with the right, sorry, a read transaction.
And with the read transaction, we just say,
we just say, okay, I'm, I'm at this point.
What happened between the last time I checked and this new point.
And you can iterate over all of the changes.
And it tells you, is it deleted?
Or, and what is the object that was there?
Or what's the new object that has been inserted or updated?
To do this, we have a hidden index called the revision index,
which always exists.
And it's every time you have a transaction,
every transaction gets an incrementing number,
and all changes made in that transaction are tracked.
So we can do this lower-bound search,
where you say, give me everything that is above this number,
above the, to, on the revision index,
to basically give us a sort of history from a certain provision.
This works for new objects, but not for the ones that are deleted.
Whenever you have a change, whenever you are watching changes,
we create, we, we mark that.
Whenever something then gets deleted,
it goes to a sort of soft delete state.
So the graveyard index, which is another primary index,
but for all objects that are deleted,
when you observe that something was deleted,
the background worker that we did with the DB.
Start will collect the, will remove these old ones.
So it's allowed you to basically temporarily store the deleted objects
until everyone that's interested in deleted objects has observed them,
and then they will automatically go away.
So that was all that I have time for.
I have so much more to show you.
Please have a look at state DB.
And I would like to, so I am here speaking,
but actually my colleague, you see,
the most of the legwork on this.
I was just his professional user,
and to, so I had some influence on the design,
and I'm working a book, but you see,
it's the real hero here.
Questions?
Of course.
Do you know if we have any questions, I'm ready.
I don't have time for questions.
If you have questions, Dylan is here.
Okay, just don't bother and you're in the busiest moments of today.
Thank you.