It's four o'clock, so let's look at our preview, sorry, now next talk.
I have been doing some mattings in Go, but building a database, I honestly have strong
respect for.
So next up is Etienne, who is going to tell us everything about Crazy Kitchen is in Go.
Thank you, thank you, yeah, welcome to our mad journey of building a database in Go,
and yeah, it's pretty mad to build a database at all, it may be even worse or even a matter
to build a database in Go when most are built in Go.
Let me start over in case you didn't hear it, so hi, my name is Etienne, welcome to
our mad journey of building a vector database in Go.
So building a database at all could already be pretty mad, doing it in Go when most are
built in C or C++ could be even matter or even more exciting, and we definitely encountered
a couple of unique problems that led us to create creative solutions, and there's lots
of shout outs in there and also a couple of wish lists, so we just released Go 1.20,
and of course the occasional madness.
So let's get one question out of the way right away, why does the world even need yet another
database?
There's so many out there already, but probably you've seen this thing called chat GPT, because
that was pretty much everywhere and it's kind of hard to hide from it, and chat GPT is a
large language model and it's really good at putting text together that sounds really
sophisticated and sounds nice and sometimes is completely wrong, and so in this case we're
asking you, is it mad to write a database and go, I might disagree with that, but either
way, basically we're now in a situation where on the one hand we have these machine learning
models that can do all the cool stuff and do this sort of interactively and on the fly,
and on the other side we have traditional databases, and those traditional databases,
they have the fact, because that's kind of what databases are for, right?
So wouldn't it be cool if we could somehow combine those two?
So for example on the query side, if I ask Wikipedia, why can airplanes fly?
Then the kind of passage that I want that has the answer in it is titled the physics
of flight, but that is difficult for a traditional search engine, because if you look at keyword
overlap there's almost none in there, but a vector search engine can use machine learning
models basically that can tell you these two things are the same, and searching through
that at scale is a big problem.
Then there's that sort of chat GPT side where you don't just want to search through it,
but maybe you also want to say like take those results, summarize them, and also translate
them to German.
So basically not just return exactly what's in the database, but do something with it
and basically generate more data from it.
And that is exactly where VV8 comes in, so VV8 is a vector search engine which basically
helps us solve this kind of searching by meaning instead of keywords without sort of losing
what we've done in 20 plus years of search engine research.
And now most recently you can also interact with these models such as chat GPT, GPT3,
and of course also the open source versions of it.
So VV8 is written in go.
Is that a good idea?
Is that a bad idea?
Or have we just gone plain mad?
So we're not alone, that's good.
So you probably recognize these things, they're all bigger brands at the moment than VV8,
so VV8 is growing fast.
And some of those vendors have really great blog posts where you see some of the like
optimization topics and some of the crazy stuff that they have to do.
So if you've contributed to one of those, some of the things I'm going to say might
sound familiar, if not then buckle up, it's going to get mad.
So first stop on our mad journey memory allocation, then that also brings us to our friend the
garbage collector.
So for any high performance go application, sooner or later you're going to talk about
memory allocations and definitely consider a database a high performance application
or at least consider VV8 a high performance application.
And if you think of what databases do, like in essence basically you have something on
disk and you want to serve it to the user, that's like one of the most important user
journeys in a database.
And here this is represented by just a number, so it went for UN32, so that's just four bytes
on disk and basically you can see sort of these four bytes.
If you parse them into Go they would have the value of 16 in that UN32 and this is essentially
something very much simplified that a database needs to do and it needs to do it over and
over again.
So the standard library gives us the encoding slash binary package and there we have this
binary dot read method which I think looks really cool.
To me it looks like idiomatic Go because it has the io dot reader interface like everyone's
favorite interface and you can put all of that stuff in there and if you run this code
and there's no error then basically you get exactly what you want.
You could turn those sort of four bytes that were somewhere on disk, turn them into our
in-memory representation of that UN32.
So is this a good idea to do that exactly like well if you do it once or maybe twice
could be a good idea.
If you do it a billion times this is what happens.
So for those of you who are new to CPU profiles in Go this is madness.
This is pretty bad.
So first of all you see it in the center parsing those 1 billion numbers took 26 seconds and
26 seconds is not the kind of time that we ever have in the database but worse than that
if you look at that profile we have stuff like runtime, malloc, gc, runtime, mem, move,
runtime, m, advice.
So all these things they're related to memory allocations or to garbage collection.
What they're not related to is parsing data which is what we wanted to do.
So how much time of that 20 seconds did we spend what we wanted to do?
Don't know.
It doesn't even show up in the profile.
So to understand why that is the case we need to quickly talk about the stack and the heap.
So you can think of the stack as basically your function stack so you call one function
that calls another function and then at some point basically you go back through the stack
and this is very short lift and this is cheap and fast to allocate and why is it cheap?
Because you know exactly the runtime of your variables or the life cycle of your variables
so you don't even need to involve the garbage collector.
So no garbage collector cheap and fast.
Then on the other side you have the heap and the heap is basically this sort of long lift
kind of memory and that's expensive and slow to allocate and why because and also to deallocate
and why because it involves the garbage collector.
So if the stack is so much cheaper then we can just always allocate on the stack right.
So warning this is not real go please do not do this.
This is sort of a fictional example of allocating a buffer of size 8 and then we're going to
say like yeah please put this on the stack and that is not how it works and for most
of you you probably say like this is pretty good that it's not that it works that way
because why would you want to deal with that.
But for me just trying to build a database and go sometimes like this something like
this may be good or maybe not.
So how does it work?
Go does something that's called escape analysis.
So if you compile your code with gcflags-m then go annotates your code basically and
tells you sort of what's happening there.
So here you can see in the second line that this num variable that we used was moved to
the heap and then in the next point you see the bytes.reader which represents our io.reader
escaped to the heap.
So two times we see that something happened to the or went to the heap.
We don't exactly know what happened yet but at least there's proof that we have this kind
of allocation problem.
So what can we do?
Well we can simplify a bit.
Turns out that the binary or encoding binary package also has another method that looks
like this which is just called view in 32 on the little endian package and it kind of
does the same thing.
You just put in the buffer on the one side so no reader this time you just put in the
raw buffer basically with the position offset and on the other side you get the number out.
And the crazy thing is this one line needs no memory allocations.
So if we do that again our one billion numbers that took 26 seconds before now take 600 milliseconds
and now we're starting to get into a range where like this is acceptable for a data basis.
And more importantly what we see on that profile, the profile is so much simpler right now.
There's basically just this one function there and that is what we wanted to do.
So admittedly we're not doing much other than parsing the data at the moment but at least
we got sort of rid of all the noise and you can see the speed up.
Okay so quickly to recap.
If we say a database is nothing but reading data and sort of parsing it to serve it to
the user then we do that over and over again then we need to take care of memory allocations.
And the fix in this case was super simple.
We changed two lines of code and reduced it from 26 seconds to 600 milliseconds.
But why we had to do that wasn't very intuitive like that it wasn't very obvious.
In fact I haven't even told you yet why this binary dot little nvn dot read why that escaped
to the heap.
And in this case it's because we passed in a pointer and we passed in an interface and
that's kind of a hint basically that something might escape to the heap.
So what I would wish is yes this is not a topic that you need every day you write go
but maybe if you do need this would be cool if there was better education.
Okay so second step delay the coding so this is kind of the idea that we wouldn't want
to do the same work twice.
And we're sticking with our example of serving data from disk but now while the number example
was a bit too simple so let's make it slightly more complex.
We have this nested array here basically a sort of slice off slice view in 64 and that's
representative now for a more complex object on your database.
Of course in reality you'd have like string props and other kind of things but just sort
of to show that there's more going on than a single number.
And let's say we have 80 million of them so 10 million of the outer slice and then eight
elements in each inner slice and our task is just to sum those up.
So these are 80 million numbers and we want to know what is the sum of them.
So that is actually kind of a realistic database task for an OLAP kind of database.
But we need to somehow represent that data on disk and we're looking at two ways to do
this.
The first one is JSON representation and then the second one would be the sort of binary
encoding and then there'll be more.
So JSON is basically just here for completeness aid.
We can basically rule it out immediately so when you're building a database you're probably
not using JSON to store stuff on disk unless it's sort of a JSON database.
Why because it's space inefficient so if you want to represent those numbers on disk like
JSON basically uses strings for it and then you have all these control characters like
your curly braces and your quotes and your columns and everything that takes up space.
So in our fictional example that would take up 1.6 gigabyte and you'll see soon that we
can do that more efficient.
But also it's slow and part of why it's slow is again because we have these memory allocations
but also the whole parsing just takes time.
So in our example this took 14 seconds to sum up those 80 million numbers and as I said
before you just don't have double digit seconds in a database.
So we can do something that's a bit smarter which is called length encoding.
So we're encoding this basically as binary and we're spending one in this case one byte
so that's basically a U and 8 and we're using that as a length indicator.
So basically that tells us that when we're reading this from disk that just tells us
what's coming up.
So in this case it says we have eight elements coming up and then we know that our elements
in this example is U and 32 so that's four bytes each.
So basically the next 32 bytes that we're reading are going to be our eight inner arrays
and then we just continue.
Then we basically read the next length indicator and this way we can encode the stuff sort
of in one contiguous thing.
Then of course we have to decode it somehow and we can do that because we've learned from
our previous example right so we're not going to use binary.lnlndian.read but we're doing
this in an allocation free way, you can see that in the length line basically and yeah
our goal is to take that data and put it into our nested sort of go slice of slice of slice
of U in 64 and the code here basically you see we're reading the length and then we're
increasing our offset so we know where to read from and then we're basically repeating
this for the inner slice which is just hinted at here by the decode inner function.
So what happens when we do this?
First of all the good news, 660 megabytes that's way less than our 1.6 gigabyte before
so basically just by using a more space efficient way to represent data we've yeah done exactly
that we've reduced our size also it's much much faster so we were at 14 seconds before
and now it's down to 260 milliseconds but this is our mad journey of building a database
so we're not done here yet because there's some hidden madness and the hidden madness
is that we actually spend 250 milliseconds decoding while we spend 10 milliseconds summing
up those 80 million numbers so again we're kind of in that situation where we're doing
something that we never really set out to do like we wanted to do something else but
we're spending our time on yeah doing something that we didn't want to do so where does that
come from and the first problem is basically that what we did what we set out to do was
fought from the get go because we said we want to decode so we're basically thinking
in the same way that we're thinking as we were with Jason we said that we want to decode
this entire thing into this go data structure but that means that you see we need to allocate
this massive slice again and that also means that we need to in each inner slice we also
need to allocate again so we're basically allocating and allocating over and over again
where our task is not to allocate our task was to sum up numbers so we can actually just
simplify this a bit and we can basically just not decode it like while we're looping over
that data anyway instead of storing it in an array we can just do with it what we plan
to do and in this case this would be summing up the data so basically getting rid of that
decoding step helps us to make this way faster so now we're at 46 milliseconds of course our
footprint of the data on disk hasn't changed because it's the same data that we're reading
we're just reading it in a slightly more efficient way but yeah we don't have to allocate slices
and also because we don't have these like nested slices we don't have like slices that
basically have pointers to other slices so we have better memory locality and now we're
at 46 milliseconds and that is that is cool so 46 milliseconds is basically the time frame
that can be acceptable for a database okay so quickly in recap we immediately ruled out
JSON because it just wasn't space efficient and we knew that we needed something more
space efficient and also way faster binary encoding already made it much faster which
is great but if we decode it upfront then yeah we still lost a lot of time and it can
be worth it in these kind of high-performance situations if you either sort of delay the
decoding as late as possible until you really need it or just don't do it at all or do it
in sort of small parts where we need it no wish list here but an honor we mentioned
so go 1.20 they've actually removed it from the from the release notes because it's so
experimental but go 1.20 has support for memory arenas the idea for memory arenas is basically
that you can bypass the garbage collector and sort of manually free that data so if
you have something that you know has the same sort of life cycle then you can say okay put
it in the arena and basically in the end free the entire arena which would sort of bypass
the garbage collector so that could also be a solution in this case if that ever makes
it like right now it's super experimental and they basically tell you we might just
remove it so don't use it third stop is something that when I first heard it almost sounded
like too good to be true so something called SIMD we'll get to what that is in a second
but first question to the audience who here remembers this thing raise your hands okay
cool so you're just as old as I am so this is the Intel Pentium 2 processor and this
came out in late 90s I think 1997 and was sold for a couple of couple of years and back then
I did not build databases definitely not in go because that also didn't exist yet but
what I would do was sort of try to play 3d video games and I would urge my parents to
get one of those new computers with an Intel Pentium 2 processor and one of the arguments
that I could have used in that discussion was hey it comes with MMX technology and of
course I had no idea what that is and it probably took me 10 or so more more years to find out
what MMX is but it's the first in a long list of SIMD instructions I haven't explained what
SIMD is yet but I will in a second some of those especially the one in the in the top
line they're not really used anymore these days but the the bottom line like AVX2 and AVX512
you may have heard them in in fact for for many open source project they sometimes just sort of
slap that label in the read me like yeah yeah has AVX2 optimizations and that kind of signals you
yeah we care about speed because it's like low level optimized and VVA does the exact same thing
by the way so to understand how we could make use of that I quickly need to talk about vector
embeddings because I said before that VVA doesn't doesn't search through data by keywords but rather
through its meaning and it uses vector embeddings as a tool for that so this is basically just a
long list of numbers in this case floats and then a machine learning model comes in and basically it
says do something with my input and then you get this vector out and if you do this on all the
objects then you can compare your vectors so you basically can do a vector similarity comparison
and that tells you if something is close to to one another or not so for example the query and the
the object that we had before so without any simd we can use something called the dot product the
dot product is a simple calculation where basically you use you multiply each element of the first
vector with the same corresponding element of the second vector and then you just sum up all of
those elements and we can think of this like multiplication and summing as two instructions
so if we look out first shout out here to the compiler explorer which is a super cool tool to
see like what your go code compiles to we can see that this indeed turns into two instructions so
this is a bit of a lie because there's more stuff going on because it's in a loop etc but let's just
pretend that indeed we have these two instructions to multiply it and to add it so how could we
possibly optimize this even further if we're already at such a low level well we can because
this is our mad journey so all we have to do is introduce some madness and what we're doing now
is a practice that's called unrolling so the idea here is that instead of looping over one
element at a time we're now looping over eight elements at a time but we've got we've gained
nothing like this is we're still doing the same kind of work like we're doing 16 instructions now
in a single loop and we're just doing fewer iterations so by this point nothing gained but
why would we do that well here comes the part where I thought it was too good to be true what if
we could do those 16 operations for the cost of just two instructions sounds crazy right well no
because simd I'm finally revealing what the acronym stands for it stands for single instruction
multiple data and that is exactly what we're doing here so we want to do the same thing over and over
again which is multiplication and then additions and this is exactly what these simd instructions
provide so in this case we can multiply eight floats with other eight floats and then we can
add them up so all this perfect here maybe not because there's a catch of course it's our mad
journey how do you tell go to use these avx two instructions you don't you write assembly code
because go has no way to do that directly the good part is that assembly code integrates really
nicely into go and in the in the standard library it's used over and over again so it's kind of a
standard practice and there is tooling here so shout out to avo really cool too that helps you
basically you're you're still writing assembly with with avo but you're writing it in go and then
it generates the assembly so you still need to know what you're doing but it's like it it
protects you a bit so it definitely helped us a lot so simd recap using avx instructions or
other simd instructions you can basically trick your cpu into doing more work for free but you
need to sort of also trick go to use assembly and with this tooling such as avo it can be better
but it would be even nicer if the language had some sort of support for it and you made my saying
now okay this is this mad guy on stage that wants to build a database but no one else does
needs that but we have this issue here that was open recently and unfortunately also closed recently
because no consensus could be reached but it comes up back and back basically that go users are
saying like hey we want something in the language such as intrinsic so intrinsics are basically the
idea of having high level language instructions to do these these sort of avx or simd instructions
and c or c++ has that for example one way to do that and maybe you're wondering like okay if you
have such a performance hot path like why don't you just write that in c and you see go or write it
in rust or something like that sounds good in theory but the problem is that the call overhead
to call c or c++ is so high that you actually have to outsource quite a bit of your code for that to
to pay off again so if you do that you basically end up writing more and more and more in that
language and then you're not writing go anymore so fortunately that's not or it can be in some
ways but it's not always a great idea so demo time um this was going to be a live demo and
maybe it still is because i prepared this running nicely in a docker container and then my docker
network just broke everything and it didn't work but i just rebuilt it without docker and i think
it might work if not i have screenshots basically that um that do a backup so example query here
i'm a big wine nerd so what i did is i put wine reviews into vv8 and i want to search them now
and one way to do it to show you basically that the keyword um that you don't need a keyword
match but can search by meaning is for example if i go for an affordable italian wine let's see if
the internet connection works it does so what we got back um is basically this this wine review
that i wrote about a barolo that i recently drank and you can see it doesn't say italy
anywhere it doesn't say affordable what it says like without breaking the bank so this is a vector
search that basically happened in the in the background we can take this one step further by
using the generative side so this is basically the the chat gpt part um we can now ask our
database based on the review which is what i wrote when is this wine going to be ready to drink so
let's see you saw before that was the fail query when the internet didn't work now now it's actually
working so that's nice um and here in this case you can see that so this is using open ai but you
can plug in other tools can plug in open source versions of it um this is using open ai because
that's nice to be hosted at a at a service i don't have to run the machine learning model on my
laptop then you can see it tells you the wine is not ready to drink yet we will need at least five
more years which is sort of a good summary of this and then you can see another wine is ready
to drink right now it's in the perfect drinking window so for the final demo let's combine those
two let's do a semantic search to identify something and then do an ai generation basically
so in this case we're saying find me an aged classic riesling best best wine in the world
riesling um and based on the review would you consider this wine to be a fruit bomb so let's
have sort of an opinion from the machine learning model in it and um here we got one of my favorite
wines and the the model says no i would not consider this a fruit bomb while it does have
some fruity notes it is balanced by the mineralogy and acidity which keeps it from being overly sweet
or fruity which is um if you read the text like this is nowhere in there so this is kind of cool
that the that the model was was able to do this okay so let's go back now it's the the demo time
by the way have a github repo with like this example so you can run it yourself and um and
yeah try it out yourself so this was our mad journey and are we mad at go are we mad to do this
well i would pretty much say no because yes there were a couple of parts where we have to give
a get really creative and had to do some some yeah rather unique stuff but that was also basically
like the highlight reel of building a database and all the other parts like i didn't even show the
parts that went great like concurrency handling and the powerful standard library and of course
all of you basically representing the gopher community which is super helpful and yeah this
was my way to basically give back to all of you so if you ever want to build a database or run into
other kind of high performance problems then maybe some of those