I'll just yell. But yeah, so this is effectively my talk. It started out as a really big thing
and then I realised 40 minutes wasn't actually that much time and so we sort of had to compress
it down into a bit of a slightly smaller talk but hopefully covering the most interesting
points in my opinion. So a bit about me. I'm Harrison. I come from London. I live in London
and I work for QuickWit where as Paul has said we build basically a distributed search
engine for logs. I am the creator of LNX which is a slightly different design of search engine
probably more akin to something like Elasticsearch or Algolia for all your lovely e-commerce
websites. And you can contact me at Harrison at QuickWit.io. A little bit about LNX since
this is basically the origin story of this talk really. It's a search engine built on
top of Tantrave. It's akin to Elasticsearch or Algolia as I've said. It's aimed at user
facing search. That's things like your e-commerce websites, your Netflix streaming platforms,
things like that. It's not aimed to be your cost effective log search engine. It doesn't
really handle those hundreds of terabytes a day type workloads but it will handle thousands
of queries a second per core. It's very easily configurable. It's designed to be really
fast out of the box because it uses Tantrave and it has an indexing throughput of about
30 to 60 megabytes a second on reasonable hardware. With high availability coming soon
which is the presence of this talk. So what is user facing search? I've stolen Crunchy
Well's website and I've typed some bad spelling in there and you see that a lot of the top
results actually account for the fact that I can't spell. That's basically the biggest
principle with these user facing search engines is you have this concept of typo tolerance.
This is a really good thing for users because users can't spell. The downside of this is
that it has a lot of CPU time when we're checking those additional words and it makes things
a lot more complicated and often documents are mutable and a lot of other things but
also when you have these nice search experiences and you want no latency something called search
as you type has become more popular now and that means your amount of search as you're
doing for a single user is increasing several times over because now every key stroke you
press is a search versus typing it all in one go hitting enter user gets a bunch of
results back goes oh no I've spelt something wrong or I can't see what I want on here
so I'm going to type it again. And so that is effectively the principle of these search
engines. You see we have Algolia at the bottom which is a very common one which I think most
people know very popular for document searching. But you know we decided hey we don't want
to use one of these pre-built systems we don't want to use Elasticsearch that's big that's
scary I don't like it. We don't want to use Algolia because I don't have that much money
I'm just a lonely paid software developer I can't be spending thousands of pounds on
that. And we look at some of the others but we're going there we're just going to write
it ourselves and that's where we have a little look because we hear something about Tantavi
we hear something about Rust that being blazingly fast as all things must be and so we go okay
I like this I like what it says it says yeah Apache Lucene I think I've heard that before
somewhere written in Rust I think I've definitely heard that before. And so we take a little
look at what it is and it is effectively akin to Lucene which if you don't know what that
is it's a full text search engine as it's called. Tantavi in particular supports things
like BM25 scoring which is just a fancy way of saying what words are relevant to this
query it supports something called incremental indexing which basically just means you don't
have to re-index all of your documents every time you change one thing. You have fasted
search you have range queries and we have things like JSON fields which allow for a
schemeless indexing as such. You can do aggregations which have some limitations in particular around
JSON fields being a little bit limited but in the biggest thing is it has a cheesy logo
with a horse which I believe Paul drew himself so I think that needs a clap on its own. But
there are other features which I just haven't yes. But there are more features which I couldn't
fit on this slide and timers of the essence. So you might be wondering what the basic
implementation of Tantavi looks like and because it's a library it's actually really quite
simple to do. So we have a couple of core things starting at the top is we define what's
called a schema. Since Tantavi was originally a schema based system still is we need some
way of telling Tantavi what the structure of our documents are and defining what properties
they have. We can use something like a JSON field to give the impression of a schemeless
index but you know schemas are good we should use them. They come with lots of nice bells
and whistles so in this case we've created a schema with the title field and you can
see there we've added the text and stored flag which all that really says is I'm going
to tokenize this field and then I'm going to store it so we can retrieve it later on
once we've done the search. The second thing we do once we've done that is we create our
index writer and in this case we're just letting Tantavi select the number of threads so by
default sorry when you create this index writer and we give it a memory buffer in this case
about 50 megabytes. Tantavi will allocate n number of threads I think up to eight threads
depending on what your system is using so you don't really have to put much thought
into the multi-threaded indexing and then we're just adding a document really so we've
created our document we've added the text field we've given it in this case the old
man of the sea and we're going to put it to our indexer which is essentially just adding
it to a queue for the threads to pull off process spit out onto disk and then if we
want to actually have that be visible to our users for searching and things like that we
need to commit the index so in Tantavi you can either commit or you can roll back and
if you have a power failure midway through indexing when you reload from disk it will
be at the point of that last commit which is very very useful so you don't leave with
partial state and all that all that nasty things and then once we've done that we can
actually search and in this case you can either build queries using traits which are very
nice and you can mash them all together with lots of boxing and things or you can use
the query parser which basically parses a nice little query language in this case we've
got a very simple phrase query as it's called trouble that up and it spits out a query for
us we then pass that into our search executor which in this case we're executing the query
and then we're passing what called collectors and they are effectively just a simple thing
to process the documents which are matched so in this case I believe we've got the count
collector and the top docs collector and the count collector does well it counts a big
surprise there and we have the top docs which collects the top k documents up to a given
limit so in this case we've selected 10 we only have one document to match so this doesn't
matter that much but if you have more you can limit your results you can adjust how things
are scored etc. Now that's all well and good in this example but this doesn't actually
really account for spelling and as we discussed earlier users aren't very good at spelling
or at least I'm not so we maybe we want a bit of typo tolerance and in this case Tanturi
does provide us with some additional way of doing this in the form of the fuzzy term query
it uses something called lever science distance it's a very common form of effectively working
out how much modification you need to do to a word in order to actually get it to match
and we call that the edit distance as such typically you're between one and two edits
so you're swapping a word around you're removing it you're adding a new word a bit of magic
there really and as you can see at the bottom this is effectively if we use just the regular
full text search well if we enter the term hello we'll only match with the word hello
if we go with the term hell we'll only match with the word hell if we use some fuzzy term
query here we can actually match hell and hello which is very useful especially for
the prefix search this is built upon Tanturi's inverted index which uses something called
a FST which is effectively a fancy word for saying we threw state machines at it and then
made them return results that's as much as I can describe how they work the person who
originally wrote the FST library in Rust burnt sushi he has a blog on this goes into a lot
of depth really really useful for that sort of thing but I can't elaborate any more on
that but all of this additional walking through our index and matching these additional words
does come at the cost of some additional CPU and once we've sort of got that what we're
left with is this nice block of data on our disks really so we have some metadata files
here in particular meta meta.json that contains your schema along with a couple other things
and we have our sort of core files which look very similar if they look very similar to
these scenes that's because they are in particular we have our field norms our terms our store
which is effectively a row level store log file our positions our IDs and our fast fields
and fast fields are effectively fast because we cut somewhat simple and equally vague name
but now that we've got all this stuff on disk if we wrap it up in an API we sort of we've
got that we've mostly we've got everything in this case we've got a demo of LNX working
here and we've got about I think 27 million documents and we're searching it with about
millisecond latency I think in total it's about 20 gigabytes on disk compressed which
is pretty nice but there's sort of a bit of an issue here which is if we deploy this production
and our site is very nice we get lots of traffic things increase we go hmm well search traffic
is increased our server is not coping let's just scale up the server and we can repeat
this for quite a lot and in fact things like AWS allow you a stupid amount of cores and
things like that which you can scale up very easily but you keep going along with this
and eventually something happens and in this case your data centers burnt down if anyone
remembers this this happened in 2021 OVH basically caught fire and that was an end of I think
a lot of sleeping people and so yeah your data centers on fire search isn't able to do anything
you're losing losing money no one's buying anything management's breathing down your
neck for a fix you're having to load from a backup what are you gonna do and well you
think ah I should have made some replicas I should have done something called high availability
and in this case what this means is we have instead of having one node on one server ready
to burn down we have three nodes available to burn down at any point in time and in this
case we hope that we put them in different what are called availability zones which
mean hey if one data center burns down there's a very small likelihood or at least as it
possible for another data center to burn down in the meantime and this allows us to effectively
operate even though one server is currently on fire or lost to the ether or I don't know
network has torn itself to pieces and this does also mean we can upgrade if we want to
tear a server down and we want to restart it with some newer hardware we can do that
without interrupting our existing system but this is sort of a hard thing to do because
now we've got to work out a way of getting the same documents across all of our nodes
in this case it's sort of a share nothing architecture this is done by elastic search
and basically most most systems so we're just replicating the documents we're not replicating
all of that process data we've just done we need to apply them to each node and doing
this approach makes it a bit simpler in reality LNX and QuickWit do something a little bit
different but this is this is easier I say this is easier because the initial solution
would be you know just just spin up more nodes you know what can add some RPC in there what
can go wrong and then deep down you work out it's like oh do you mean networks are reliable
what's a raft and things like that and so at that point you go okay this is this is harder
than I thought and you realize the world is in fact a scary place outside your happy little
data center and you need some way of organizing states independent on things catching on fire
and this is this is a hard problem to solve and so you have a little look around and you
go well Rust is quite a new system it's quite a young ecosystem we're quite limited so we
can't necessarily pick a Paxos implementation off the shelf we maybe have something called
raft so that's a leader-based approach and that means we elect a leader and we say okay
leader tell us what to do and it will say okay you you handle these documents go go do things
with them it's a very well-known algorithm very easy to understand it's probably the
only algorithm which is really implemented widely in Rust so there's two implementations
one of them by the pink cap group called raft RS and the other by data fuse labs called
open raft varying levels of completion or pre-made so in this case you think okay I don't really
know what I'm doing here so maybe I shouldn't be managing my own raft cluster and you hear
something about eventual consistency and you hear oh it's it's leaderless any any node can
handle the rights and then ship off to the other nodes as long as the operations are
idempotent and that's a very key point which means you can basically ship the same document
over and over and over again and they're not going to duplicate themselves or at least
they don't act like they duplicate and this gives us realistically a bit more freedom
if we want to change we can change and so we decide let's go with eventual consistency
because yeah I like an easy life and it seemed easier yes people laughing will agree that
yes things that seem easier probably aren't and so our diagram sort of looks something
like this and I'm scared to cross the white line so I'll try and point but we have step
one a client sends the documents to a any node it doesn't really care which one that
client then goes okay I'm going to send it to some of my peers and then wait for them
to tell me that they've got the document it's safe and then once we've got the majority
which is a very common approach in these systems we can tell the client okay your document
is safe even if OHV burns down again we're probably going to be okay it doesn't need
to wait for all of the nodes to respond because otherwise you're not really highly available
because if one node goes down you can't progress and so this system is this system is pretty
good there's just one small problem which is how in God's name do you do this many questions
need to be answered many things how do you test this or who's going to have the time
to do this and well luckily someone aka me spent the better part of six months of their
free time dealing with this and so I made a library and in this case it's called data
cake whoo yes in this case this is called data cake I originally was going to call it
data lake but unfortunately that already exists so we added cake at the end and called it
a day it is effectively a tooling to create your own distributed systems it doesn't have
to be eventually consistent but it just is designed to make your life a lot easier and
it only took about six rewrites to get it to the stage that it is because yeah things
are hard and trying to work out what you want to do with something like that is awkward
but some of the features it includes is it includes the zero copy RPC framework and this
is built upon the popular archive framework which is really really useful if you're shipping
a lot of data because you don't actually have to deserialize and allocate everything all
over again you can just treat an initial buffer as if it's the data which if that sounds wildly
and safe it is but there's a lot of tests and I didn't write it so you're safe.
We also add the membership and failure detection and this is done using chit chat which is a
library we made at quick quit it uses the same algorithm as something like Cassandra
or DynamoDB and this allows the system to essentially work out what nodes are actually
its friends and what it can do and in this case we've also implemented an eventually
consistent store in the form of a key value system which only requires one trait to implement
and the reason why I went with this is because if you implement anything more than one trait
people seem to turn off and frankly I did when I looked at the raft implementations.
So we went with one storage trait that's all you need to get this to work.
We also have some pre-built implementations I particularly like abusing SQLite so there
is an SQLite implementation and a memory version and it also gives you some CRDTs which
are conflict-free replicated data types I should say and also something called a hybrid
logical clock which means it's a clock which you can have across your cluster where the
nodes will stabilize themselves and prevent you from effectively having to deal with this
concept of causality and causality is definitely the biggest issue you will ever run into with
distributed systems because time is suddenly not reliable.
And so we go back to our original thing of well first we actually need a cluster and
this case it's really simple to do all we need to do is we just create our node builder
we tell data cake okay we've got your address is this your peers are this or you can start
with one peer and they'll discover themselves who their neighbors are and you give them
a node ID.
They're integers they're not strings and the reason for that is because there's a lot
of bit packing of certain data types going on and strings do not do well.
And here we can also effectively wait for nodes to come onto the system so our cluster
is stable and ready to go before we actually do anything else.
And by the time we get to this point our RPC systems are working nodes are communicating
your clocks have synchronized themselves mostly and you can actually start adding something
called extensions.
Now extensions essentially allow you to extend your existing cluster you don't you can do
this at runtime they can be added and they can be unloaded all at runtime without any
with state cleanup and everything else which makes life a lot easier especially for testing.
They have access to the running node on this local system which allows you to access things
like the cluster clock the RPC network as it's called which is the pre-established RPC
connections and you can essentially make this as simple or as complex as possible which
is essentially what I've done here so I've created this nice little extension which is
absolutely nothing other than print what the current time is which realistically I could
do without but nonetheless I went with it.
And this is what the eventual consistency store actually does under the hood is it's
just an extension and here we can see that we're passing in a I can't point that far
but we pass in a mem store which is our storage trait we pass in our create our eventual consistency
extension using this and we pass it to the data cake node and say okay go add this extension
give me the result back when you're ready and in this case our eventual consistency cluster
actually returns us a storage handle which allows us to do basically all of our lovely
key value operations should we wish including delete, put, get that's about all there is
on the key value store but there are also some bulk operations which allow for much
more efficient replication of data.
The only problem with this approach is it's not suitable for billion scale databases so
if you're trying to make the next Cassandra or Silla don't use this particular extension
because it keeps the key value or the keys sorry in memory which it uses to work out
what keys have and have not been processed and the reason for this is effectively because
I didn't really trust users implementing this on the storage site correctly which turned
out to be a good choice because the amount of unit tests that this failed initially
was a lot and so now we've sort of got this ability to replicate our key values our life
is a lot easier in particular we can actually go as far as essentially saying okay we've
established our data connection our key values let's just use Tantive as our persistence
store and this is effectively the simplest way to do it and I've made a little demo here
which you can go to that link I basically abused and slightly ignored certain things
in particular correctness but this will replicate your data you may end up with duplicate documents
because I didn't handle de-duping but in this case we can fetch we can delete and we can
index documents with Tantive and that's our persistence store and here you can see we're
doing about 20,000 documents in 400 milliseconds in the local cluster yes and that is effectively
the end so are there any questions how long do we have left how long do we have left 15
minutes so actually kind of so in there do you have like a way to provide from outside
to the Tantive transaction or links transaction an external ID that I can use to integrate
with the standard storage so change the question would be an easier way do you have a way to
say which which level of data has been indexed yes in this case I've sort of glossed over
it a little bit because in reality it's a little bit more complicated when you implement
it so in reality when you actually implement this you would probably have a essentially
use the replication to replicate the initial documents and then you would have a check
mark to essentially work out what documents have and have not been indexed yet or you
would add some additional step like a right ahead log so that way you know that as long
as the documents are there you can make sure that your check your commit point is always
updated to the latest thing in the next it's actually a little bit different again because
the way it creates indexes is they are per check point so in a new index is created every
commit effectively but you don't have to do that and in this method I didn't so you could
you can it doesn't do it here but you can add a right ahead log and do you can do basically
do anything as long as the trait is implemented hello hello hi yeah all right so congratulations
for the presentation sorry I think I can see you yes hello so let me see if I can
got that question right so you was is that about it sending time to me so if you want
to go beyond something like bm25 or leave a size distance and things like that things
like I think things like vector search or word embedding search is still something which
is quite far away and we need quite a big push to do with time to be specifically but
if you want to add additional queries or additional functionality it's quite easy to add with
time to be so it's actually just a query trait so one of the things that and the next does
it actually has another a query mode called fast fuzzy which actually uses another algorithm
for pre-computing dictionaries in order to do the edit distance lookup and that basically
is just involves creating another query and you can customize effectively all of your query
logic all of your collecting logic and things like that so providing your within the scope
of the API time to be will allow you to implement it yourself otherwise things like the word
embeddings which are a little bit more complicated and require a bit more on the storage side
would need to an issue and a very motivated individual to probably implement that which
currently we we don't really have so it's pretty little question on all your sketches
the network the subject network was fully connected is that important let me see if
I can find which one that was was it was it this one or was it this one well on this one
it's it does not look fully connected but I'm not sure if these diagram depicts kind
of connectivity connect home or just which messages has actually been dispatched so I'm
going to cross the forbidden white line here because we're doing questions and effectively
these are just indicating sending responses and getting things back so these notes don't
actually in a real system that you could have a network petition here and your node one
can no longer talk to no three it's effectively lost to the ether and maybe no two can also
not do it and in this case it doesn't actually really care all that you need to do is you
need to achieve what's called a consistency level so which means that if you want to progress
you have to reach that level otherwise things are counted as not happening and so in this
case if no three is down or can't be contacted as long as node one can contact node two and
no two acknowledges the messages things can still progress this is the same with raft
as well so raft operates on what's called a quorum which yeah but effectively any node
any one node can go down in a three node group and the other two nodes can still progress
providing they have what's called what's the majority so I understand full connection
of the network is not an important factor here well it's nice to know thank you thank
you for our talk I see here that there is basically a consistency mechanism for indexing
do you check as well for that on over nodes when there is a search request as well say
that again sorry I didn't quite pick that up do you check the data on over nodes when
there is a search request not an indexing request in this case we have relaxed reads
essentially so we don't do we're not it's searching across several nodes and getting
the most updated version from that which is part of the trade-off you make with the eventual
consistency you will have that with raft as well effectively unless you contact the leader
you won't have the most update data when searching but one of the things you do have to do if
you go with the eventual consistency eventual consistency approach like we do here is you
would need to effectively handle the idea that maybe you will have duplicate documents
because something's been recent in the meantime and so you'll need to be able to deduplicate
that when you're searching or have some other method of handling it and deleting it from
the index so that means that effectively every node must have a copy of the data like I cannot
have five nodes unlike a free with the car system or something about yeah so as long
as if you've got like a five node cluster and three nodes respond you can immediately
search from if those three nodes have got the data they can immediately be searched from
effectively if you want but the other nodes may take a little bit of time to catch up
which is the principle with eventual consistency they'll eventually align themselves but they're
not all immediately immediately able to reflect changes hello just simple one in hindsight
would you take the raft part in hindsight probably not still and the reason for that
is because the current state of the rust ecosystem with it means that there's a lot of black
holes effectively around it and so you either going with an implementation which is very
very stripped down just the state machine part or going with an implementation which
is very very trait heavy and is a little bit opaque around what you need to test what you
don't need to test and how it behaves under failure so in this case it's I like this
approach more because it may allow me to implement things like network simulation which the RPC
program supports so we can actually simulate network fit networks failing locally in tests
and things like that which makes me feel a little bit more confident than trying to just
have the state machine and implement everything and all the handling correctly but I think
in future yeah you could you could use it but it's just not not quite at that state
so I'm not sure I quite got how how if the engine actually does any data sharding or
there's a hatchery yeah in this so in this approach it's simplicity of time really we're
not actually doing any data sharding servers are really quite big nowadays so you can even
for your e-commerce website you can get a pretty huge server and the biggest issue tends
to be replication and the high availability the data sharding is something that some quick
wits is something that would be concerned about because you've got so much data you
need to spread it across machines and things like that when you're searching but in e-commerce
at the point in which you're searching across multiple machines you're probably going to
be looking at the higher latencies so you would you'd be better off dedicating one
machine per search rather than several machines per per search really.