►
From YouTube: Building Data Structures for Filecoin
Description
We’ll start with an overview of how IPFS builds graphs that represent files. From there we can work through some basic concepts and principals for representing any new data you’d like to create, make available everywhere w/ IPFS, and store in Filecoin.
Join us for Filecoin Liftoff Week, an action-packed series of talks, workshops, and panels curated by the web3 community to celebrate the Filecoin mainnet launch and chart the network’s future. https://liftoff.filecoin.io/
Events take place all week, October 19-23, 2020. #FilecoinLiftoff
For more information on Filecoin
- visit the project website: https://filecoin.io/
- or follow Filecoin on Twitter: https://twitter.com/Filecoin
Get Filecoin community news and announcements in your inbox, monthly: http://eepurl.com/gbfn1n
Chapters
00:00 Introduction
01:45 DAG Overview
03:35 Creating a DAG
07:00 Concept: Mutability
11:18 HAMT: Hash Array Mapped Tree
14: 12 FBL: Flexible Byte Layout
16:22 Products, Experimental Data Structures and Resources
A
Yeah,
I
I
run
the
team
that
does
a
lot
of
our
great
data
structures
work
and
not
all
of
our
data
structures
work.
We,
you
know,
data
structures
are
kind
of
everywhere,
but
ipld
is
really
like
the
lowest
layer
of
the
interplanetary
stack.
It
sits
beneath
filecoin
is
this
beneath
ipfs
and
it's
really
like
how
we
think
about
creating
data
searchers.
So
that's
what
I'm
gonna
share.
A
A
What
I'm
going
to
talk
about
the
the
sort
of
whole
class
of
data
structures
that
we're
talking
about
when
we
talk
about
building
stuff
for
falcon
we're
talking
about
this
thing
called
dags,
you
probably
if
you've
been
around
filecoin
enough,
you've,
probably
heard
people
say,
dag
a
lot.
Dag
stands
for
directed
acyclic
graph,
which
is
a
very
fancy
way
of
describing
this.
A
This
data
structure
that
is
really
useful
and
and
kind
of
wraps
up
the
whole
category
of
data
structures
that
you
create
with
hash
linking.
So
when
we
talk
about
content,
address
data
structures,
we're
talking
about
hash,
link
data
structures,
you
can
think
of
dags,
as
if
you
come
from
trees
and
b
trees.
You
can
think
of
it
as
a
tree
that
allows
you
to
reference
common
branches
and
leaves
from
other
nodes,
so
basically
a
tree
with
deduplication.
A
If
you
come
from
graphs,
you
can
think
of
it
more
as
graphs
that
don't
have
circular
references
you're
not
allowed
to
have
circular
references,
but
the
idea
is
that
it's
a
graph,
but
all
the
links
have
to
kind
of
direct
one
way,
there's
a
lot
of
different
visualizations.
But
I
actually
like
this
one's
up
here,
the
best
because,
while
the
links
are
going
right
to
left-
and
that
may
seem
weird,
it's
actually
really
in
the
order
that
you
would
create
this
data
structure.
A
So
you
would
start
with
the
node
on
the
left
and
start
to
work
your
way
right,
because
in
content
or
data
structures,
in
order
to
link
to
something
we
have
to
have
the
data
so
that
we
can
create
this
hash
based
link.
So
the
first
thing
you
create
is
that
one
that
says
g
and
then
you
you
create
everything
else
up
from
there
and
in
whatever
order,
makes
sense.
A
So
in
ipfs
we
have
two
main
deg
layouts
that
we
use
just
for
the
files.
One
is
called
a
balance:
dag
and
one's
called
trickle
dag.
So
when
you,
you
know
import
a
file
into
ipfs,
and
you
get
back
this
identifier-
that
identifier
isn't
a
hash
of
just
the
file
data.
It's
actually
the
file
data
broken
up
into
parts
and
then
assembled
into
one
of
these
structures.
A
So
you
can
kind
of
look
at
it
like
this,
where
you
have
the
actual
data,
as
you
know,
streams
of
different
binary
values
and
then
they're
all
linked
together
with
this
structure-
and
you
know,
ipfs
actually
uses
ipld
for
that.
Ipfs
was
created
and
this
was
created
actually
before
I
feel
d
was
broken
off.
As
a
project,
we
were
sort
of
like
an
an
armor
or
a
leg,
broken
off
from
ipfs
itself,
but
like
our
whole
layer
here
and
and
how
ipfs
thinks
about
this,
is
it's
all
ipld
data
structures.
A
So
here
we
have
like
just
a
file
with
with
two
chunks
and
then
that
file
is
inside
of
two
directories,
and
so
those
directories
just
linked
down
to
the
file
right
when
we
want
to
append
data
to
that
file.
What
we
do
is
we
create
a
new
chunk
and
then
we
create
a
new
file
node
that
links
to
all
of
those
chunks,
and
then
we
go
and
recreate
those
directories.
So
now
we've
actually
orphaned
some
blocks
here.
A
So
if
we
were
pinning
this
old
directory
and
then
we
stopped
pinning
it,
we
pinned
this
new
one
and
we
told
ipfs
to
gc.
It
would
actually
remove
those
three
blocks,
they're
not
necessary
anymore,
and
that
means
that
if
you
know,
if
you
want
to
track
the
history
of
changes
over
time,
you
might
create
a
data
structure
that
actually
links
between
these
two
things
and
says.
A
Oh
I'm
going
to
track
this
this
directory
over
time
and
I'm
going
to
keep
linking
to
each
part
getting
getting
data
block
data
into
ipf
or
sorry
getting
data
from
ivfs
into
lotus
is
documented.
Here,
don't
read
this
slide
just
go
to
the
link.
This
is,
you
know,
being
improved
all
of
the
time,
and
so
you
should
really
go
to
whatever
the
current
references
for
getting
data
out
of
ipfs
into
lotus.
But
the
important
thing
to
note
here
is
that
any
data
you
get
into
ipfs
you
can
get
into
filecoin.
A
A
I
don't
have
time
to
get
into
the
entire
structure
of
cids.
That's
literally
like
an
entire
other
talk,
but
if
you
want
to
go
and
look
up
some
stuff
about
this,
there's
a
great
proto-school
tutorial,
called
anatomy
of
a
cid
that
you
should
go
check
out
and
just
learn
how
these
content
identifiers
are
made
and
and
how
we
really
separate
a
lot
of
the
concerns
and
we
have
a
lot
of
future
proofing
in
these
identifiers.
A
So
they
really
do
become
like
the
url
of
web3,
the
url
of
a
content
addressed
data
layer
for
the
internet.
Let's
dive
right
in,
though
now,
let's
have
some
fun,
let's
like
create
a
little
dag.
So
first
we
start
with
our
first
leaf
node.
So
this
is
just
some
data
like
a
little
hello
world
object
here
and
that's
going
to
get
a
hash
based
address.
So
this
is
what
that
looks
like
in
javascript.
A
We
import
this
block
api.
We
decide
which
hashing
function
that
we
want
to
use
to
choose.
Sha-256
you'll
have
a
good
time
we're
going
to
import
a
codec.
We
suggest
that
you
use
this
this
codec
that
we
create
in
ipld
called
dagsebor.
This
is
actually
also
the
codec
that
filecoin
uses
internally
for
its
own
internal
chain,
but
you
can
use
it
for
creating
whatever
myriad
data
structures
that
you
want
to
create,
and
we
really
recommend
you
do
that
and
yeah.
So
you
just
you,
you
take
that
data
value.
A
You
create
a
block.
You
get
this
new
block
instance
and
then
that
block
is
gonna
have
a
couple
things:
it's
gonna
have
the
bytes.
So
it's
going
to
have
the
encoded
binary
data
of
that
that
sort
of
dxe
board
call
that
dxe
or
encode,
and
it's
going
to
have
an
address.
It's
going
to
have
this
the
cid
associated
with
it,
and
that's
really
all
that
we
need
to
store
this
in
ipfs
or,
frankly,
to
store
it
anywhere.
We
could
put
it
in
s3.
We
could
put
it
in
any
key
value.
A
Store
like
this
is
enough
right
here.
So,
let's,
let's,
let's
actually
start
using
this
a
little
bit,
let's
create
a
node
that
links
to
it,
so
we're
going
to
create
a
little
object
called
boo.
That's
just
gonna
have
a
value
that
actually
links
to
this
data
that
we've
just
created.
So
what
that
looks
like
in
javascript
is,
you
know,
you're,
just
gonna.
Take
that
c
id
and
you're
gonna
use
it
as
a
value
in
another
object
that
you're
gonna
encode.
A
A
So
that's
what
this
looks
like
we
just
we're
using
the
cid
again
as
another
link
in
another
structure
and
then
we're
taking
both
of
those
blocks
and
creating
the
the
root
block.
Now
this
ddd
block
that
links
everything
all
together
and
now
we
have
a
little
dag.
We
have
a
little
tree
structure
and
the
structure
of
this.
Can
you
know
we
can
do
different
things
with
that
we
can
create
indexes.
We
can
create
relationships.
A
We
can,
you
know,
describe
whatever
we
need
to
describe
in
the
world
so
that
our
applications
can
function.
Then
we
just
need
to
get
these
blocks
into
ipfs.
This
is
a
little
tricky
to
do
in
a
talk,
because
there's
so
many
different
ways
of
running
ipfs
that
you
can't
really
lock
in
one
way
of
getting
block
data
into
ipfs.
A
One
thing
that
I
will
say
is
that
every
way
that
you
can
run
and
use
ipfs
has
a
block
api,
so
you
can
see
the
main
sort
of
http
documentation
in
that
first
link.
There's
a
how-to
on
how
to
work
with
this
kind
of
data
and
there's
even
sort
of
like
an
ipfs
lite
that
in
go
that
just
serves
these
block
data,
doesn't
do
all
the
extra
file
stuff.
That's
out
there.
It's
really
just
working
with
these
kinds
of
data
structures.
A
A
It's
a
little
key
value
store
that
works
on
top
of
ipfs,
and
you
can
see
that
it's
really
only
like
five
lines
of
code
here
in
two
functions:
to
take
that
interface
that
we
were
using
before
to
create
those
blocks
and
just
wire
right
into
ipfs.
So
it's
really
really
easy
to
sort
of
plug
that
storage
layer
in
once
you're
building
data
structures.
This
way,
okay,
I'm
going
to
get
into
some
concepts.
Now
I'm
going
to
talk
a
little
bit
about
mutability.
A
So
here
we
have
two
directories,
one
directory
inside
of
another
and
then
a
bunch
of
different
files.
Okay,
so
content
address
data
structures
are
all
immutable.
You
know
you
can't
actually
change
them.
If
you
change
them,
you'll
get
a
new
address,
and
so
what
do
you
do
when
you
need
to
mutate
things?
When
you
mutate
things,
you
basically
just
create
a
new
immutable
state
that
you
arrive
at
from
some
mutation
over
a
prior
immutable
state.
A
So
in
this
case
we
wanted
to
change
the
first
file
in
this
to
a
different
file
and
what
we
did
was
we
just
created.
We
had
to
create
now
a
new
directory
that
links
to
all
the
same
things
in
the
root
node
and
links
to
this
new
file,
object
now,
and
so
we've
effectively
orphaned,
that
old
root
block
and
that
old
file.
A
A
For
the
purposes
of
this,
you
can
think
of
them
as
just
like
the
file
structures
in
ipfs,
not
really
in
git,
but
we'll
pretend
so
you
have
these
different
trees
of
just
the
whole
director.
The
whole
repository
state
right,
so
all
of
your
code
files
in
your
git
repository,
they
all
look
a
certain
way
at
each
commit.
A
A
It
just
links
to
the
old
commit
and
from
the
old
commit
it
can
get
the
old
file,
and
so,
as
you
sort
of
add
new
files
and
mutate
things
over
time,
you
can
see
that
these
just
keep
linking
back
to
the
same,
commit
messages
each
time
and
even
as
they're.
You
know
updating
these
trees
and
getting
new
trees.
A
All
of
this
leaf
data
here,
all
these
little
blobs
of
data
that
make
up
your
files
at
the
very
bottom
there,
those
all
remain
kind
of
unchanged,
and
so
that's
why
it's
like
a
really
efficient
structure
for
maintaining
this
history,
because
when
you
change
a
file
you're
only
storing
the
parts
of
that
file
that
you
changed
and
all
the
old
references
are
staying
around.
So
it's
a
form
of
deduplication
that
works
really
really
well.
A
When
you're
trying
to
maintain
a
history,
when
you
have
really
complex
structures,
sometimes
the
the
insertion
order
can
can
reorder
some
of
the
different
elements
and
you
have
a
lot
of
other
adjustment
problems.
There
are
a
lot
of
reasons
why,
if
you
mutate
a
structure
like
this
and
you
get
something
else,
that's
very
complex.
You
orphan
a
lot
of
data,
and
you
may
not
want
to
keep
that
data
around
forever.
You
know
not
everything
is
good.
Not
everything
needs
to
maintain
an
entire
history.
A
So
when
you're
thinking
about
and
you're
starting
to
design
these
data
structures
that
mutate
over
time,
you
need
to
think
about
what
a
mutation
operation
will
do,
not
just
in
terms
of
the
new
blocks
and
new
nodes
that
you
need
to
create,
but
also
how
much
data
is
being
left
behind.
How
much
garbage?
Are
you
essentially
generating
every
time
that
you
do
this,
and
there
are
other
considerations
too?
Like
you
know,
can
I
do
bulk
updates
to
this
structure?
You
know
if
you
can
bulk
all
your
updates
together.
A
I'll
talk
a
little
bit
about
the
hampt,
and
then
you
should
really
just
go
use
it
so
a
hand,
a
hash
array
map
tree.
It
is
a
big
big
map,
so
it
could
be
just
a
few
megabytes
or
it
could
be
terabytes.
It
could
be
petabytes.
It
could
really
just
get
huge.
You
know
you
can
have
millions
of
different
values
in
these
things.
I
think
I
think
we
have
one
somewhere,
that
is
millions
or
billions
of
values.
A
You
have
to
find
a
way
to
break
that
up
and
then,
as
you
break,
that
up,
one
of
the
problems
that
you
run
into
in
these
decentralized
networks
is
that
you
need
the
hash
of
the
entire
structure
to
be
consistent,
regardless
of
the
insertion
order
of
the
values
so
think
about
it.
This
way,
if
you
have
a
bunch
of
transactions
to
process
and
another
node
gets
those
same
transaction,
but
it
gets
them
in
a
slightly
different
order.
Maybe
it
was
processing
transactions
and
some
of
those
people
were
closer
to
it.
A
If
you
insert
those
in
a
different
order,
a
lot
of
different
data
structures
like
your
standard
b
tree,
that
that
will
end
up
creating
a
different
tree
structure
depending
on
what
order
that
you
manipulated
it
in
the
really
cool
thing
about
a
hampt.
Is
that,
regardless
of
that
insertion
order,
you
can
insert
them
in
whatever
you
want.
You
can
do
these
over
time
whatever.
If
you
have
the
same
data
in
that
hampt,
it
will
have
the
same
hash
address
as
anybody
else's
hand.
So
this
works
really
well
in
these.
A
In
these
consensus-driven
scenarios,
where
you
really
need
to
ensure
that
everybody
is
arriving
at
the
same
value,
another
really
cool
property
is
that
the
the
hemp
has
a
really
guaranteed
performance,
as
it
gets
larger.
So
you
can
really
sit
down
and
do
the
math
and
go
like
okay.
Well
as
as
this
gets
bigger,
how
many
hops
am
I
going
to
be
away?
How
many
links
do
I
have
to
diverse
in
order
to
get
at
a
particular
value
that
stays
very
constant,
regardless
of
how
big
the
structure
gets?
A
So
that's
also
another
really
really
good
thing
to
consider
when
you're
using
the
structure.
So,
like
I
said
we
in
ipld,
we
have
a
very
detailed
spec
on
the
hampt.
We
have
an
implementation
that
uses
our
new
go
upld,
prime
codegen
that
actually
uses
this.
This
ipl
schema
language
that
you
see
on
the
right
to
to
get
up
and
running,
and
also
I
mean
you
can
literally
look
at
the
the
file
coin
hamp,
the
ham
that
we
use
in
filecoin.
A
It
varies
a
little
bit
from
our
specification
because
our
specification
allows
for
some
optionality.
You
can
actually
change
the
hashing
function
that
you
use.
You
can
change
the
bucket
and
some
of
the
dimensions
of
the
structure.
So,
depending
on
your
performance
scenario,
you
may
want
to
tweak
those
values
a
little
bit
when
you
tweak
those
values,
obviously
you're
going
to
get
different,
consistent,
hashes
from
different
people.
So
that's
one
of
the
reasons
why
filecoin
differs
a
little
bit
from
our
spec.
It
doesn't
specify
those
you.
A
We
don't
want
people
in
the
file
coin
chain
to
try
to
change
those
values
that
will
arrive
at
different
hashes.
So
that's
also
documented
in
the
spec,
though
the
file
coin
variations
and
in
javascript
there's
a
bunch
of
modules,
one
that
just
really
implements
the
base,
algorithms,
another
that
that
has
really
use
reusable
utilities.
On
top
of
that
library
and
then
yeah.
I
would
really
encourage
you
to
just
go.
Look
at
this
little
library,
it's
not
more
than
maybe
100
or
200
lines
called
dkb.
A
It's
a
decentralized
key
value
store,
and
it's
really
it's
just.
This
mat
this
this
hand
mapped
on
top
of
ipfs
for
storage
and
then
with
some
sugar
on
it
to
just
make
it
look
nice
and
make
it
really
like
fun
to
use
if
you're
a
programmer,
and
you
want
a
little
key
value
store.
So
it's
a
really
good
example
of
how
you
can
take
some
of
these
lower
level
primitives
that
can
be
kind
of
hard
to
get
your
head
around.
A
Sometimes,
like
all
these
big
hashmap
trees-
and
you
can
just
kind
of
decorate
them
to
make
them
really
pretty
and
reusable
by
like
many
more
programmers
than
people
that
want
to
nerd
out
about
data
structures
and
and
rust
also
has
an
implementation
of
the
filecoin
amp
that
you
can
go
check
out.
If
that's
your
language,
another
data
structure
that
I
want
to
talk
about
this
one's
so
fun.
This
was
like
really
really
fun
to
build.
We
iterated
on
this
for
a
long
time
and
made
a
lot
of
tweaks
it.
A
That
way,
if
you
seek
in
the
file,
you
always
seek
to
a
unique
data
value
and
you
don't
have
to
get
an
entire
block
in
order
to
seek
to
the
middle
of
it.
It's
really
nice.
Anyway,
there
are
all
different
ways
to
like
cut
up
files
and
then
just
like
in
ipfs,
where
we
have
that
balance
dag
and
that
trickle
dag.
A
There
are
different
ways
to
do
the
layout
of
those
streams
of
data
to
give
you
different
sort
of
performance
profiles
and
one
of
the
issues,
with
the
way
that
we
had
kind
of
done.
That
in
the
past
is
that
if
you
came
up
with
a
new
layout
algorithm,
you
also
had
to
write
a
new
reader
and
so
all
of
the
old
code
and
all
the
old
stuff
that
was
already
in
production,
couldn't
read
the
new
data
structures.
So
the
thing
about
this
flexible,
byte
layout
is
that
it
really
is
flexible.
A
Like
the
name
says,
it
allows
you
to
lay
out
a
stream
of
different
binary
values,
and
you
can
use
them.
You
can
mix
and
match
inline
binary
values
and
links
to
binary
values.
You
can
really
vary
the
structure
based
on
whatever
algorithm
that
you
want
to
create
whether
you
want
to
do
balance
or
trickle
or
whatever,
and
there's
just
one
unified
way
to
read
this
data
structure.
So
you
only
ever
need
one
reader
function.
A
You
can
always
get
a
stream
of
bytes
out
of
it,
so
it's
really
really
powerful
we're
working
on
sort
of
the
next
generation,
unexpected
the
data
structures
underneath
ipfs
and
th.
This
is
really
like
the
the
data
stream
part
of
that
data
structure.
It's
it's
like
a
really
solid
spec.
Now,
there's
a
javascript
implementation
that
I'm
using
a
few
places
I'll
show
you
in
a
little
bit
but
yeah.
This
is
just
like
a
really
fun
data
structure
that
I
encourage
you
to
check
out.
A
A
First
of
all,
I
just
there
are
some
products
that
are
already
written
on
top
of
ipfs
that
if
your
use
case
fits
them,
you
should
really
just
use
these
products
instead
of
going
and
designing
a
bunch
of
new
data
structures
like
I'm
trying
to
encourage
you
to
do
right
now
so
yeah
I
mean
textile,
pier,
ghost
and
orbit
dtp
are
all
built
on
top
of
these
primitives.
They
all
store
data
in
ipfs.
A
If
you're
doing
something
that
looks
like
it
fits
these
use
cases
definitely
go
and
use
them,
and
I
mean
these
are
all
open
source
projects.
So,
if
you're
curious
about
how
they're
designing
this
or
how
they're
doing
something
definitely
go
check
it
out,
I
actually
I
look
at
the
textile
stuff
quite
a
bit.
A
They
have
some
really
great
specs
they've
done
a
lot
of
really
good
code
work
and
I
poke
at
their
code
all
the
time
to
see
what
they're
doing
and
and
some
of
their
their
their
folks
have
actually
been
peering
into
some
of
our
new
stuff
as
well
in
in
dagdab,
which
we'll
talk
about
now.
We've
also
been
building
some
some
new
experiments.
A
We
like
to
take
these
data
structures
that
we're
building
and
start
to
actually
assemble
them
into
something
like
a
database,
something
like
some
what
somebody
would
use
and
then
try
to
mature
that
into
a
project
over
time,
and
so
these
aren't
ready
for
sort
of
production
use,
but
they're
really
good
to
go.
Look
at
if
you're
going
to
go
design
data
structures
or
figure
out
how
to
take
some
of
the
data
structures
that
I
already
talked
about
and
put
them
into
whatever
application
that
you're
doing
so.
A
Dagdb
is
like
really
a
full
feature
database.
It
does
you
know
peer-to-peer
replication.
It
has
a
very
sort
of
get
like
push
and
pull
and
remote
structure.
It
has
a
secondary
indexing
system
built
on
top
of
it,
and
one
of
the
the
cool
things
is
that
this
is
really
where,
like
I
take
any
of
these
new
data
structures
that
we're
building-
and
I
start
to
see
what
they
they
look
like
when
we
start
to
like
actually
build
sugar
on
top
of
them.
A
So
as
an
example
in
dagdb,
you
can
take
any
async
generator
in
javascript,
so
any
stream
of
data
and
use
it
as
a
value
that
you
plug
into
in
into
degree
and
what
databab
will
do
is
it'll
go.
Oh,
that's
a
stream!
I'm
going
to
go
turn
that
into
an
fbl
and
it'll
store
that
as
one
of
these
flexible
byte
layouts
that
I
just
talked
about
and
then,
when
you
go
and
get
that
value
out,
it'll
convert
it
back
into
an
async
generator
that
you
can
then
iterate
over.
It's
really
cool
dkb.
A
I
talked
about
it
a
little
bit
before.
Definitely
look
at
that
before
daggedy,
because
it's
much
smaller,
it's
a
really
really
small
amount
of
code,
and
it
really
shows
you
what
it's
like
to
build
a
little
database
on
top
of
with
ipld
on
top
of
ipfs
and
and
unlike
the
adb,
which
has
like
its
own
storage,
abstraction
layer.
Dkb
is
just
on
top
of
ipfs.
So
it's
a
lot
simpler.
Also,
I
mean
I
mentioned
before
proto
school's
fantastic,
go
check
it
out
anything
anything
you're
trying
to
learn.
A
You
can
go
there
to
read
about
how
to
you
know,
use
some
of
the
the
code
samples
that
I
talked
about
before,
but
there
are
also
examples
in
go
and
in
rust
and
a
lot
of
sort
of
like
a
glossary
of
terminology
and
a
lot
of
other
useful
resources
when
you're
getting
started
with
using
ipld
building
these
data
structures,
and
we
also
have
a
specifications
website.
The
spec
site
is
great.
We
have
a
really
really
detailed
specification
and
docs
for
our
schema
language.