I hope you just moved on.
So many people contributed to this project, the one on bottom line are people from software
heritage, my students, the three main people you see are the people who are invested
more time probably in the project.
What we want to do is graph analytics at scale, huge graph, huge means hundreds of billions
of arcs, okay, hundreds of billions of edges, not millions or billions.
Graphs are everywhere, okay, I assume you know what a graph is or we won't go very far
with this web snapshots, social networks, biological graph, you name it, oh sorry,
wrong key, I'll start in very one here.
Okay, there is some delay between what I do and what my Mac does.
Okay, sorry.
Okay, the standard representation like adhesion,
solicit will not work if you have hundreds of billion of edges.
And you can do distributed approaches which usually spend most of the time
around if you have a followed Mac sure is cost idea, cost over a single thread.
You take any graph task, you run it on a single thread and the cost is the number of
MapReduce servers you need to replicate the speed of a laptop.
And the cost of some algorithm is infinite.
No matter how many server you add to your MapReduce cluster, it's slower than a laptop.
So that doesn't work really.
What we do we've been for some times is compression, okay.
So web graph is a framework to do compressed representation of graphs.
It's a very long lead project, it's more than 20 years now.
And there are hundreds of publications, image on conferences and journals that you've
had used the web graph of the data with this review.
It's all open.
I mean open source, open data, we gather web crawls, we gather data from, you know,
the structure of Twitter or DBLP or Wikipedia and we make it public.
In 2011, that was a long time ago.
And I think of it.
There was news that Facebook had four degrees of separation with, wow,
this is there is a long delay which actually was featured on the newer times
and then there was three dots for 74, not four.
It's a long story because the degrees of separation in distances in graph and runoff by one.
And then your time got the off by one.
Okay, I don't want to talk about it, it's very sad.
But at that time we measured that at Facebook, I mean, people at Facebook did the measurement with our software.
And at that time Facebook was 700 million nodes and it was 70 billion links.
It was represented in just 200 gigabytes.
Like common crawl, if you know the nonprofit that distributes web graph and does all their internal analytics using web graph.
So the motivation for this was the software heritage, history graph.
So what is this?
It's the largest public archive of its style version control history.
This is a UNESCO sponsored project to create a library of software.
All the software ever created.
And the data model is a miracle, direct a cyclic graph.
So basically you have like a gigantic git repository with all the development of all public code.
Even very old code, I mean they gather code for a number of sources.
And this is one of the largest graphs, a human activity available.
Like presently we are at 44 billion nodes and seven more than 700 billion arcs, which are basically committing dependencies,
which presently is represented by web graph into 150 gigabytes instead of more than six terabytes,
which makes it possible to do things in memory.
Now previously, software heritage is using a pipeline based on our Java historical 20 of Java implementation of a web graph.
And being able to store the graph explicitly, I mean you can do visits, you can run any kind of normal implementation algorithm we have in mind,
because you don't have to write something specific for a distributed implementation.
But clearly, at this scale, start Java was getting in the way.
I was looking for an excuse to learn Rust.
Tomazo was in Rust.
Stefan wanted to do this, so essentially that was the time to move to Rust.
Of course, it's hyperformas and safe.
There are zero cross abstractions, you know this.
Now this might look to you a minor issue, but if you ever try to manage something with hundreds of billions of items in Java,
having two billion elements array, it's a major problem, okay?
Not even two billions, two billions minus one in theory.
In reality, two billions minus eight don't get me into that, it's very sad.
So I shouldn't complain because I used Java happily for at least a decade.
It was just around 2010 that it became almost impossible to do this, probably, sensibly in Java.
Another thing that might be obvious, lazy, truly lazy iterators.
The whole framework is based on lazy iterators.
If you ever wrote an iterator in Java, you know what I'm talking about, nightmare.
You ask, fortunately, we have actual lazy iterator.
And moving to Rust required porting, or I think it completely several keys idea,
that resulted in a number of crates.
So what I'm trying to do today is to show you what we did,
and maybe it can be useful for you too.
And a couple of ideas that we met during the writing.
So, absurdity is an epsilon copy, serialization, serialization framework,
and I will tell you what it means because we invented the word for this thing.
The MNDBG is a system for fast memory footprint analysis.
This is a crate with succinct data structure.
Who knows what is succinct data structure? Raise your hands.
Nobody.
Seriously. Okay, there is a two-line introduction.
These streams, which streams for instantaneous,
instantaneous code, gamma code, compression, variable byte.
Okay, now someone knows, I know.
Well, and of course, a web graph.
Let's start with the first idea, which took a lot of time to work out.
So, our purpose, keep in mind, because it's called an epsilon copy, blah, blah, blah.
The purpose is to memory map very large data structures directly from disk.
You have data structure that are 300 gigabytes wide.
Loading them into memory takes half an hour, literally, half an hour.
What can we do to have fact census?
I mean, the thing they do at Facebook Google, the data center name,
is to have them in a specific format on this, memory map then
and access them directly from the memory mapping.
Okay, so we wanted to do something like that in Rust.
And essentially, to do that, what you do is something called zero copy.
Zero copy means that instead of this serializing something,
you load the bytes in memory, and then those bytes are already the object you want.
More or less, so there is no DC realization happening.
And in that case, you can even directly memory map the file.
So instead of DC realizing an object, you memory map the file,
and it's already the object you want.
There are a few crazy to do this, but they didn't do what we needed.
One is abomination from Framac Sherry.
Abomination rewrites all the references into memory to make it work,
because you don't know where the object is.
Out of, we cannot do that because we want to do memory mapping of a mutable
data structure, we cannot write.
Zero rec is a popular create to do that.
It has a special type that you use instead of rec,
that essentially does relative indexing.
Huge performance impact.
We are shading every cycle, not possible.
Another one that is very popular is Archive.
Archive is some impact, not very clear on performance,
but the main problem with Archive, what you DC realize, zero DC realize,
is not what you see realize, it's a different structure.
So you have to re-implement every single method on the DC realized structure,
and we have a lot of algorithmic things going on.
There was not working for us.
So we developed this idea.
Let's say that I show you now.
The concept of our ideas that you need some collaboration
from the data structure.
You cannot just let a derived absurdity and it will work for you.
In exchange, we have something that we didn't have from this crate.
So there are two types of data, zero copy and the copy.
There are two traits.
And what we do is, if you have any kind of sequence,
vector, boxes, license of zero copy types,
when you DC realize, instead of the vector,
you get a reference to the memory.
So this is the zero copy part.
But the point is that the rest of the structure,
which is very small with respect to the large arrays,
is allocated normally.
So it's, we copy a little bit, an epsilon part of the structure.
It's not entirely zero copy.
Zero copy means we don't allocate anything.
The memory is your structure.
We take the memory, we use like 99% of it,
and then we allocate a little bit.
And to do that, we use the enjoying to create implementation
based on a societate type that I show you later.
Maybe how many people are asked, like,
when you're programming it, listen to us here.
Okay, so there is some people who probably met the problem.
But again, the idea is that you get something that I write for us.
Let me just keep a second.
This, and I'll show you, first of all,
how you do these joint implementations.
So the idea is that you want to implement a trait differently,
depending on another trait, which you cannot do, of course,
because the rules.
So the way you do it is, like this,
you create a selector, basically.
So a trait that is an associated type,
that is, in this case, just two possible values.
Phase one.
Phase two, you put in my direction your trait
with a specific instance of the first trait.
So zero copy depends on being a copy type,
with copy equals zero,
but anything with copy type,
copy equals zero, will be zero copy.
So now zero copy and the other trait,
with internal value zero, are the same thing.
Now, what we would like to write is this.
Oh, this is, okay, my keyboard, okay.
What we would like to write is this.
I can write to different implementation of my trait,
like this you like for t, depending on whether t,
and this will not compile, because it won't.
It used to, like if you were to go,
but now it doesn't anymore,
but it will be the small helper trait,
you can make this work.
So you can add a digital implementation of a trait,
depending on another trait.
And this is how we manage the whole,
something is deep copy, something is zero copy thing.
Okay, if you are interested,
there is a PR going on to make this work in the compiler,
and the PR contains the RSIato trait we're using here.
So this is a very interesting technique,
that without which we could never be able to write,
exactly, example.
Okay, so what happened here is that you declare the structure
with an ID, an integer, and some data.
Okay, and you derive, absurdly.
Unfortunately, there is a procedural macro.
Now, you create a structure with a vector inside,
and you serialize it somewhere.
Okay, you store it, easy.
Now, what you do is you load the serialized form
in a buffery memory.
So it's now with a piece of memory.
Okay, and at that point, you can add
a single serialized structure,
and what you get is a structure that instead of a vector
contains a reference to a slice,
there is in your serialized data.
Okay, you can also do a full serialization
like a normal serialization framework,
and it would be very, very fast
because all zero copy are just one red exact.
There's no looping,
or you can even directly memory map it.
And, okay, let me show what's happening here.
You have your structure, a phase one.
The structure is an ID, okay.
I don't know why that is cut like a two-second delay
between, okay, whatever.
Consection time, you have your structure,
there is an AD, a vector, a known pointer,
length cap, okay.
I think this is pretty obvious.
Then we serialize, and you just have ID length
and the data, plus a lot of headers, checks,
some verification, okay.
But this is the data we write.
When you do the epsilon DC realization,
you get a structure that contains
just a reference to the data.
So you see, IDLN are being effectively copied,
because we allocate space for them.
But the huge amount of data in the stars
is not copied, it's just reference.
Okay.
This is basically what, like Facebook or Google does,
in C++, in a more in a less safe manner, let's say.
But for us, it worked very well,
because now the serialized data is on disk,
memory map pin takes nothing, takes just a memory map,
and will be that very small structure,
but the epsilon complex structure.
Okay.
Of course, you have to write your methods,
so they work both with a vector and a slice,
but that's what everybody does,
so that should be too difficult.
And once you have things supporting,
absolutely, you can put them as a type parameter,
and they will work flawlessly, recursively, up to the leaves.
The only problem is that if you have a lot of fields,
all of different types, and they all should support
absurdity, you will have a lot of parameter types,
type parameters.
Sorry.
Okay.
So that's it.
If you need to memory map, larger structure,
this serialized, very quickly things,
have a look at absurdity.
I think we did a nice job.
And notice that since the structure,
you decelerize, is exactly the structure,
you serialize, you can basically
exchange the two things without problem,
it's not a different structure,
and the impact on performance is zero,
because it's exactly the same structure
simply instead of a vector,
you have a reference to a slice.
Contrarily two, the other one.
Okay.
Very quickly,
Mandy Biji is a high performance memory
compensate detector,
and the question is,
how can be slow a memory detector?
Very easy.
These are some of the most common
aspects for memory detection.
I mean, I want to know how much memory
and object use is including the memory
it references, not just a size of.
This is a very large 2GB Ashmap allocated,
and the first three frameworks
are what you can find now on crates.
The point is that the measure will be
off for very reason,
but the point is that they take
almost two tenths of a second to establish the size,
because they have to loop through two billion elements.
Man's side leverages on this joint trade thing,
and we'll give you the answer in,
I mean, 200 nanoseconds, nothing.
And if you start managing structure
that are 100 gigabytes waiting
to 30 seconds to get an answer,
it's not very nice.
Also, we can print memory layouts,
including padding,
so you can have a complete breakout
of a data structure,
knowing which part occupies more occupies less.
We can even use padding in enums using
the unstable feature offset of enums.
So if you're interested in looking inside
your data structure that is used.
Sox, I will skip a little bit on this
because nobody knows anything about this.
Soxin data structure,
but let me just expose to the idea.
Soxin to the data structure,
they use the space of the information
theoretical lower bound,
but with operation that asymptotically
are the same of standard structures.
Let me just make an example.
There are four to the power of en binary trees.
There's a number.
So it should be possible to represent
binary tree using log four to the power of en two en bits.
But we use two en log en bits
because we have n nodes,
and it's known as two pointers.
The two pointers are at least log n bits.
So Jacob's own representation
uses two en bits.
And give you parent and child in constant time.
So you shave off a log n factor.
This is very important because, oh,
but, okay.
Now that you're sorry,
complete, I was seeing things you were not seeing.
So there is something really bad going on.
I'm so sorry.
Okay, now it's on the screen,
but not on my screen.
So, never happened before with keynote in my life.
I'll try to make it look represents everything
internally using alias funnel.
They index the graph.
It's pervasive throughout the infrastructure.
We also have something else like sort of
recompression blah blah, but I'm going to skip
because I want to have some times for web graph.
Okay, let me just skip this because I don't think it's.
Super interesting in this context.
Let me just make one complaint.
Okay.
We have a comprehensive set of traits for indexed dictionaries.
And indexed dictionary is a set of integers.
You can know the iF integers in increasing order.
And you can do predecessor and successor.
So list up or bound.
Creates lower bound computations.
Our main implementation is yes funnel.
The main problem we have is that there is no index get in rust.
And there is a pr going on, but it's stalled.
What I mean is that if you know it works,
if you want to overload the square bracket operator,
you have to implement index.
Okay.
Index must return reference.
That's not good.
Imagine you have to implement functionally a vector that
returns is squared for index side.
You can.
So in general, rust and intentional representation do not work
well together at the moment.
If your representation of the data is extension of,
so you actually have the data.
Like in a binary tree of integers, the integers are in the tree.
If you need to expose one of the integers,
you can offer a reference.
But anything that is implicit, succinct, compressed anything
that is intentional in which the description of the data is
in the data structure.
But the data is not in the data structure.
It's impossible to use any kind of overloading a rust.
We really hope someone at some point makes,
at least in the index get work,
that would be the ideal trait that overloads square brackets
but returns a value, not a reference.
Okay.
If you can push this through any body to the component team,
that would be very nice to us.
Or the other PR or the other PR.
Okay.
Another component that might be useful will be strings.
So, bit strings let you read the instead of the stream of bytes,
stream of bits.
Why you want to do that?
Well, because to do compression, a lot of compression happens
in bit strings like even jpeg and peg, whatever.
Essentially, we have codes that let you write small integers with few bits
and large integers with many bits.
These are called instantaneous codes.
And there's the side bit stream, implements many of them.
The main thing that is different from other crates, we read by word.
This is like a major change in efficiency.
So, we don't read byte by byte and then we the code.
We read like, you can say, you can set your own read word
from 8 to 64 bits.
And that speeds up enormously.
The code in it's very easy to enrast in Java impossible.
We have a lot of instantaneous code and it's very easy to add yours.
Like a gamma code, if you're familiar with that, we can read it in less than two
or no seconds with cheese, believe me, pretty good.
You have two basic traits, bit right, which you can imagine,
can read bits and write bits, not surprisingly.
And then we have extension traits for the codes.
You can write your own extension traits for the code you want using the infrastructure.
And we have implementation of a reader and a writer that are buffered
with selectable writer read word.
Okay, this is a little bit too much.
But one observation presently, the best read word is U32
and the writer is U64 for implementation problem.
When you want to read bits and you want to have the code in tables,
you need to be able to pick bits in the stream.
To do that, your internal bit buffer must be at least twice the word you're reading from the file.
Usually, people read 8 bit at a time, so that is not an issue.
But we are reading a word at a time.
If we were to read 64 bit at a time,
the internal buffer would be 120 bit, and 120 bits, 120 bits,
integer are very slow.
Now, I guess in two three years we'll be able to have read word of U64,
but for the time being on Intellit list 128, you are very slow.
Okay, so if you're interested in bit stream, have a look at the outside bit stream.
Now, more interestingly, finally web graph.
What does that can it do for you?
Okay, graphs are usually represented by bit streams.
Obviously, otherwise, you wouldn't have all those crates,
and we use the SI bit stream for the code,
and then we use sucks for pointer into the bit stream.
Because using the list funnel, we can store the pointers in the bit stream in very little space.
That's a classical usage of the list funnel.
Like on an old software heritage graph with 34 billion nodes,
and more or less half a trillion arcs,
a BFS is completed in three hours.
On standard hardware, I mean, half a terabyte of RAM, of course,
but fairly standard hardware.
And it's three time faster than it was in Java.
We expected 50% more, maybe 100% more,
three time faster was really nice.
Consider that everything else is faster.
I mean, in Java, for instance, when you have an array,
there is a hundred like 50, 40 billion elements,
you have to simulate it through many small arrays.
There's loads of down things a lot.
In the rest, all these things are fairly easy.
What I'm also found obvious that the ergonomics of the API
are unbelievably better with respect to Java,
and just to let you have a look,
Xographs and N nodes numbered from zero to N, period.
There is no specific data structure for node of arts.
Everything is done with integer.
If you have your own index space,
you have to bijectively multiply into a zero N.
It's your job.
We work with indices in a compact space space zero N.
And when you want to access the graph structure,
you get successors.
So you take a node and you know the successors of the node.
The other node that are connected by an arc.
So there is no data structure,
materializing a node on an edge arc, however you call it.
Everything is done with view size.
And this is what you do if you want to work with a half a trillion edges graph.
Otherwise, anything you try to represent set of edges, set of nodes,
stacks, becomes immense because these structures,
representing nodes of edges are usually,
not using much more space than just a use size.
I should look there.
So how does compression happens?
These are complicated topics, but just as an idea,
gap compression.
So if you have list of successors,
you take the gaps, differences.
These are small numbers, because they are just gaps.
And you use instantaneous code.
If you're familiar with inverted indices,
I mean, standard techniques in 30 years, this how you do it.
But with graphs, we can do a little bit more because these large graphs
are often very redundant.
Like the successful list of a node,
is very similar to the successful list of another node.
Imagine a web snapshot, two pages from the same level of a website.
They have very similar links.
So what we do, we compress by reference.
So instead of storing entirely my success list, my out links.
First, I check if I can copy most of them from another node,
then I already stored, and then I store the difference.
This is a major game changing in web,
in web, in particular in web snapshots,
where you can get easily to one, one and a half bit per link.
Instead of 64.
Because web snapshots are impressively redundant.
You can also intervalize.
So if you have consecutive successors,
maybe you can store them as intervals.
We have labels on edges.
And the way we do it is very elegant.
I can say that because it's tomato's idea, not mine.
So I can say a lot of nice things about that.
So a label is like a graph that instead of returning successors
returns labels.
And then we have zip operators, like a generator,
you can zip your graph with your label,
and now you have a label graph.
And this is very nice because if you have several set of labels,
you can zip them and create your own custom labels,
zip it with a graph, and get your custom labeling without any programming.
You just have to write zip this and this,
and you will get a label graph.
The whole thing is based on landers.
And this is the 10 minutes of the talk that will be pure rust problems.
So it took us a while to get this working.
So you might, do you know what the lander is in rust,
or landing a generator?
Anybody, never heard of it?
Okay.
Okay, iterators give you things.
You know what a generator is, right?
Okay, iterator give you things, right?
And you can take two things from the iterator and do things
with the two things you got from the iterator.
With a lander, you can't.
In a lander, you take a thing, you do something with the thing.
You throw you the way, and then you can take another thing.
Okay, landers are iterators that have relevant internal state.
It cannot provide you with two items at the same time.
For instance, because they go over a file,
and they move the pointer as they return item.
Okay.
Now imagine a situation.
We are returning iterator on the graph,
and we are scanning a bit stream.
We cannot use an iterator.
I mean, we return a lander that we call an iterator,
but it should be a lander.
And these are computations and complicated.
Okay, let me just skip this.
Let me go just go to the trades,
because we don't have much time.
I thought they would have been faster.
So the basic trade you access is a sequential labeling.
So you have labels, and you have a lander,
and node labels, lander is the thing I'm going to talk later.
It's something that gives you nodes and iterator of successors.
So you iterate on a graph, and you get node zero,
as these successors, node two as these successors, and so on.
And these are labeling.
A graph is just a labeling with you size labels.
Phase one.
Phase two, random axis.
You will random axis.
So what you go do is something like this.
And you get a labels method that tells you which are the labels,
and an out-degree method.
And then a random axis graph is a random axis labeling with you size labels.
If you have an actual labeling and you zip it, then you get a label to graph.
So everything is a labeling.
If you're labeling returns your size, you get a graph.
You can zip labeling together.
If you zip together a graph and a labeling, you have a label to graph.
But everything is composable like legal.
Now the main thing to make this work properly is in famous lander.
Okay, let me just explain you the idea.
When GAT is, you know what is a generic associated type.
Raise your hand if you know what a generic associated.
Okay, someone knows.
Okay.
If you look around when people were introduced in generic associated types,
these will be examples everywhere.
So this is a lander.
So you see the item as a lifetime.
Sorry that this should be an A, that is, I mean, taking the slide.
Now what happens is that when you get an element from the lander,
it borrows exclusively from self.
So until you have, until the item you get get out of scope,
you cannot call next, which is exactly what you want.
You want an iterator, the give you things.
But until you get rid of the thing, you cannot get another thing.
Okay.
That seems very nice and it's totally not working.
Why?
Because as soon as you start to use it, you need to pass a lander to a function.
And if you want to condition the type of the item, you have to write a condition,
a trade bound on item with a lifetime.
The only way to do it is with a four with a hiring trade bound.
And at that point that four can be compensated with static,
which means that the lander must be static.
So the only way to do it to use this is with a static lander.
And of course, our landers are not static.
We need landers, they give you the graph,
and they read the graph from another source to each of the ever reference.
So Sabine and Jusos came with this idea, which actually works.
And the idea is, if I can make it work, because sorry guys,
that's okay.
I'll wait three seconds, and maybe this will happen.
Okay.
Okay, this is only for very interesting people.
So here what happens is that we have a trade lander.
There is a type parameter with a default value.
You will never write this.
There is a reference to self.
And they contains the thing you will let the item, with a dependency on it.
Now what we write here now to create the letter trade,
we write this four-on-lending next, blah, blah, like before.
What happens now, the interesting part is that the compiler,
sees a higher rank trade bound for A,
but because of the reference, there is an implicit where self.
Okay.
So implicitly, we're saying that this is outleased by self.
And I will be very nice to have this syntax.
One day, maybe we will have this syntax, and all this will be easier.
But this is a way you create a higher rank trade bound
with a limitation on the lifetime.
Once you do this, everything works.
And you can pass the lander to every function you want,
just writing, yeah, perfect.
Just writing that three minutes now.
I'm over anyway.
Anyway, this is, okay, this is an interesting technique.
If you need to do landers, have a look at Sabina Juson's blog.
Juson's blog or at the lander create, which we are maintaining now,
because the original writer is like no longer interested.
We have slightly more complicated problem,
because we need the iterator,
literally third by the lander to be referencing the data.
So we need something horrible like this,
that I'm not going to explain.
But thanks to Quindot and the last language form,
we were able to write this, which is horrible.
I never remember why it works, but it actually works and does the job.
Okay, performance, amazing.
These are various kinds of graphs of their sizes.
And you can see the speed up of us with respect to the job implementation
in the order of two, three times.
They are fairly small except the last one,
because they are graphs.
We stopped to do crawls in the 2015,
because common crawls was taking the lead,
and it was not really necessary to continue this activity.
But anyway, conclusion.
Fantastic journey, since April 2023.
I was very surprising that we could do all these
on a enormous cloud base developed over 20 years.
A graph traversal arriving.
I would like to thank Valenti Lawrence,
a software heritage that suggested a lot of improvement.
Could and generally was our guinea pig for everything.
The last language form,
without which none of these would have happened.
I mean, we've got so many suggestions
who they never thought about,
that I cannot even count them.
And my students, which also wrote a lot of code.
And thank you, if you have any questions.
The talk is all right.
Thank you.
Thirty seconds, four questions.
Hi.
So you have this huge data set,
221 gigabytes.
Yeah, I know.
Was your thing bit compatible
with the Java version or was it a different
dismember representation?
I'm also probably a little bit dangerous.
Oh, yeah.
The rest version is totally compatible with Java.
It generates bit by bit.