NetFS Overview
NetFS is a peer-to-peer protocol for distributing and
incrementally updating entire file systems of files. It can handle
many small files, mixed with really large ones with near optimal
download speed for most users most of the time. Like BitTorrent, it
allows a publisher to distribute files to very many peers with
minimal load on itself, since the peers upload mostly from each
other.
With NetFS, peers are typically not downloading anything at all.
Instead, they serve up the file pieces they've cached on-demand, as
needed at high bandwidth, and occasionally download a file when it's
accessed for the first time. Most of the time, the network
connection is idle. They are available to relay data that is in high
demand, however, enabling NetFS to be far faster than BitTorrent for
downloading large files when demand surges.
A peer "makes friends" with peers it is introduced to
through the publisher. When data is needed rapidly, good friends can
be asked to help you download data faster. If a peer obtains all of
a publisher's files, it becomes a mirror (much like a BitTorrent
seed), and peers may make the same requests of the mirror as they
would the publisher.
Message Format
All integers are 4-bytes, in network byte order. All IDs, random
values, and hashes are 20-bytes long. All hashes are SHA1 summaries.
Strings are zero-terminated, and encoded in UTF-8. Attribute
strings are strings with a single embedded non-escaped ':', such as
“ip:192.168.1.40\:2020”. All network addresses are represented
as strings. Both IPv4 and Ipv6 can be supported in traditional
formats, such as “my.domain.net” or “192.168.1.40:2020” or
“2001:db8::1428:57ab”. All keywords in messages are are 1-byte
values (see “Keyword Values” for their values).
All messages start with a 4-byte integer indicating the message
length, including these 4 bytes. The next byte is the message type,
and the rest is the message “load”. Messages can be signed.
Signed messages are created by appending a random number to the
message, and then the friendship key, computing the hash of the
entire message, including the random number and friendship key, and
overwriting the friendship key with the hash. This proves to your
peer that the message is from you, or at least from someone who knows
the friendship key. Authentication in NetFS is important for
maintaining friendships with peers. As you build good will by
uploading to them, they remember your kindness and repay it in the
future.
File Maps
Peers often tell each other what files they have, typically
shortly after they connect. Compressing this data is very important.
A given version of a file system has a fixed number of files. The
list of files is first the top level directory, then it's contents in
order listed. If a listed file is a directory, after it is listed,
it's contents are listed. In this depth-first listing order, every
file is assigned a position in a bit field. A '1' in the bitfield
indicates the peer has the file, and a '0' means they do not.
A file map is a compressed bitmap of files. Three kinds of fields
are supported in a file map:
repeat0 <length>
repeat1 <length>
bitmap <length><data>
Lengths are in terms of bytes, so
that a “repeat0 1” field means 8 zero bits. A file map is
prefixed with it's length.
File system Versions
NetFS is a file system, not just a way to share files. Further,
it has a simple revision control system, supporting updating to new
or reverting to older versions of the file system. Branches are
supported. When a peer requests to update to a version, the
publisher simply tells the peer what his new file map will be. When
a new file is added or an old one deleted, the directory containing
that file becomes stale, and needs to be updated. This also means
the directory containing that directory is also stale, all the way up
to the root of the file system (because hash values change).
Every committed change made to the file system by a publisher
creates a new version of the file system. Versions are identified by
the hash of their top-level directory. A tree of versions is
maintained by the publisher, and if he retains a version you want,
you can switch to it easily, even if it's on a different branch.
Local changes to the file system create a “local” version on a
branch rooted at the version where the changes started. By default
NetFS mounts of the local version, but it can alternatively mount any
locally tracked version. Local versions may be published as new file
systems. Sometimes, the user may wish to merge his local changes (or
changes along another branch) into another version. If this is the
case, changes are applied to the new version. Conflicts occur in
files that have been changed on both branches. In this case, the
file in the target version is retained, and the file from the source
branch is added in the same directory, with a .conflict extension. A
number is appended if needed to make it unique.
To conserve disk space, an LRU (lest-recently-used) heuristic is
used for deleting locally cached files, and any reasonable cap on
disk space can easily be enforced. Further, versions can be
forgotten to save disk space. Once a file is present in no locally
tracked version, it is deleted.
Publishers are really nothing more than peers who have local data
they author, and make available to other peers. It is possible for a
peer to subscribe to a file system, make local modifications, and
publish the new version, even if only a subset of the original file
system is hosted by the peer.
File and Directory Structure
Files are simply sequences of bytes, without any
presumed format. A directory is simply an ASCII (UTF-8 is allowed)
file containing a list of file information records, one per line. An
info record is has starts with the following fields, which separated
by single spaces:
<flags>
- as would be shown with ls -l
<owner> - user ID
number
<group> - group number
<size> - the size of
the file
<access time> -
integer from the time function
<modification time> -
integer from the time function
<name> - the file
name
In a string, whitespace must be preceded with a \. The sequence
\\ will be interpreted as a \ in the string. All other printable
characters are legal in a string, which is terminated by whitespace,
or '\n'. Unix style line terminations are used.
Regular files have an additional field: the SHA1 summary of the
file data:
<hash> - The SHA1
summary of the file data
Directories are listed with permissions starting with
"d". They also have a have the following additional
fields:
<hash>
- The SHA1 summary of the directory string
<subfiles> - The
total number of sub-files
Size is a number as a decimal string. The file hash is
hexadecimal encoded and is always 40 characters. The
subfiles field is the recursive total number of files within the
directory (including directory files, and symbolic links). An empty
directory has 0 subfiles.
Symbolic links have permissions “lrwxrwxrwx”, and
have one additional field:
<destination path>
- path name of destination
The destination path may be relative, or an absolute
path, and possibly not on the NetFS file system.
In addition to symbolic links, links to other NetFS
file systems are supported. Such links have permissions starting
with "f". They are listed like symbolic links, but the
destination will be a NetFS network address followed by a file system
name, and optionally a specific version hash. If the version hash is
not present, then the current version from the publisher is used. If
the specified version is no longer tracked by the publisher, then the
link is invalid. They have these additional fields:
<distination network address> <filesys name>
[<version hash>]
To support efficient downloading of larger files, a
single file can be broken into multiple chunks. In this case, a
directory representing the file is inserted with permissions starting
with "c". In the sub-directory file, each chunk must be
listed with the name "0", "1", "2", and
so on. A split file is treated exactly like a sub-directory, except
that when the NetFS system is mounted, it will appear as a single
file to the user. For really big files, the chunks can themselves be
further split. To support efficient downloading, files should be
recursively split into chunks not larger than about 100K bytes.
Directory files should not be split.
Directories may be signed with gpg (in Armor format),
to help insure that the files downloaded are genuinely from the
publisher, and have not been tampered with. In general, only the top
level directory needs to be signed to insure that the entire file
system is valid.
NetFS Protocol
There are three kinds of peers. The publisher is a
unique peer who publishes a given file system. A mirror is a peer
who is there simply to help route data faster, and can greatly
offload the publisher. Typically a mirror will download a file, then
upload it many times, donating their upload bandwidth to benefit the
swarm. A leech is a peer who just wants to download data, and has
little interest in helping the swarm.
Generally, a peer acts as a mirror for a while in
order to build up good will with some friends. Later, when they want
to download quickly, they ask their friends to mirror some data to
them, while they act as leeches. This friendship protocol is key to
enabling consistent high-bandwidth downloads.
Handshake messages:
File information and transfer messages:
file <file hash>
<data>
have_file <file
hash>
unhave_file
<file hash>
choke
File system messages:
Other Messages
mirror <ip> <port>
<mask> <command> <signature>
rate_peer <peer ID>
peer_rating <peer ID>
<attribute>...
invalid_message <reason string>
When a peer wants to download a file, he generally
first contacts either the publisher, or a mirror know from previous
contacts with the publisher. After a handshake,
When a NetFS connection is created between peers,
both send hello messages. In responds a hello_friend message or
form_friendship message is sent. After this handshake, one peer
usually says what file system and version he is updating. File maps
are typically exchanged after a filesys message. If the remote peer
is a publisher or mirror, then the need_files command should request
a number of good peers to help download the files, and a peer_list
message is sent in response. If the remote peer was recommended by a
publisher or mirror, then the need_files command should ask for no
additional peers. If the remote peer is simply a friend you need
help from, the friend can then go to the publisher to request a peer
group. As he downloads files you need, he will forward them to you.
NetFS applications must track information about peers
between sessions, including their ID, friendship key, statistics for
determining how worthy they are for upload bandwidth, their filesys
IDs, and file maps. Peers who don't show up for a while, or are just
poor peers can be forgotten.
There are no keepalive messages, as connections
should be closed if inactive for more than about 2 minutes.
Detailed Message Description
mirror <ip> <port> <mask> <command>
<signature>
Becoming a mirror is a great way to make friends and build up the
good will you will need for rapid downloads in the future. When a
publisher or mirror is informed that you wish to be a mirror, he may
include you automatically in peer groups in your requested IP range.
This message can also help ISPs keep their network traffic within
their networks. It allows an ISP to become a peer for anyone
matching their IP range. A mirror can register for multiple ranges.
A strategy for ISPs that may work well is to always claim to have all
files on a file system. If a file is requested which is not cached
by the ISP, it can be rapidly downloaded (faster than a DSL
connection), and provided to the peer with minimal latency. Since
file requests can be queued, an ISP should be able to easily fill a
client's download pipe to capacity, even with the small latency. A
peer acting as a mirror might also use this strategy. Commands are:
serve – Add the range to the
mirror's list of ip ranges to serve
clear – Remove the range from the
mirror's serve and block lists
block – Block requests from the ip range
Expected emergent behavior is for peers to mostly contact good
mirrors (relative to the publisher), then the publisher, then
poor-performing mirrors. By mirroring a popular mirror, you may get
more traffic (and thus good will) than if you mirror the publisher
directly. In this way, a well performing tree of mirrors should
naturally form. Note that peers are never directed towards any
particular mirror. If any peer tries to take advantage of the mirror
system, peers may tire of using that mirror and go elsewhere.
list_filesys <filesys
ID>...
This command asks a publisher, mirror, or peer to list information
about the file systems they have. In response, the peer will send a
filesys command, describing each file system listed. If no file
systems are listed, the peer may list of all file systems (each with
a separate filesys message).
filesys <attribute string>...
This command lists systems shared by a publisher, mirror, or peer.
Unrecognized attributes will be ignored. ID attributes, and hashes,
are 40-byte hexadecimal values. Required attributes are:
“filesys_name” - the name of the
file system.
“filesys_ID” - unique identifier
for the file system.
“publisher_ID” - the peer ID of the
publisher.
“publisher_address” - the network
address of the publisher.
“publisher_port” - listening port
of the publisher.
“current_version_name” - the name
of the current version hosted.
“last_publisher_contact” - how recent the current version is
known to be.
These attributes are only required if the file system is derived
from another file system and republished with changes locally:
“upstream_ID” - the upstream
publisher's ID.
“upstream_address” - the upstream
publisher's network address.
“upstream_port” - the upstream publisher's listening port.
A new file system starts with each filesys_name attribute.
list_version <filesys ID> <version name>
This command causes the peer to report information about the
specified version, and each of it's direct child versions. A version
message is sent in response for this message, and for each child.
version <filesys ID>
<version name> <version hash> <message> <drop
file map> <add file map> [<parent version name>]
This message is sent in response to a list_version
message, and tells a peer about a version. The message strings are
the commit messages. The drop file map in terms of the previous
version says which files in the previous version are no longer used,
and the add file map in terms of the new version says which files are
new. This allows a peer to determine locations in the new file map
of it's current files.
peer_list <network address>...
This command is sent to help a peer download files from other
peers. It should be computed to optimize his chances of finding
files he'll need, and peers of good standing and high file overlap
with the peer should be listed before others. Thus, mirrors and are
typically listed first, and high-bandwidth high-availability peers
after that, and peers with low availability and low upload bandwidth
at the end.
request_file <file hash> <signature>
This tells your peers that you are in the market for a particular
file. You can send this to peers whether or not they have it, but
should avoid sending requests to peers who have choked the
connection. To help prevent spoofing of your identity, which could
allow an unscrupulous peer to benefit from the good will you've
cultivated with friends, you sign this request. It is a good idea to
ask peers for multiple files, so they can queue file transfers more
efficiently.
need_files <file map>
If you can't find enough peers to fill
your download bandwidth, or if you need files that current unchoking
peers don't have, you can request more peers. This message is
normally sent to a publisher or mirror, since they will typically
have more peers, but it can be sent to any peer. If sent to a good
friend he might help you out by joining the swarm, and fetching files
for you.
have_file <file hash>
Use this message to let peers know that you have a new file. It
should only be sent if the hash of the file data matches the hash you
expected. In a very active swarm which is downloading a popular
file, you may wish to repress this message from being sent to peers
who already have the file, since it is unlikely that they will want
to download it from you. However, be sure to send this to each of
your peers who you have requested the file from, so they can cancel
the requests. In a low-activity group of peers, you probably should
send this to each connected peer.
unhave_file <file hash>
Occasionally, you may delete a file from your cache. This can
happen for several reasons, including trying to save disk space. If
you have joined a swarm at the request of a friend, you may not want
to save the files you download to disk, and instead cache them in
memory. In this case, you may want to delete the file from memory as
soon as it's no longer popular among your friends in the swarm.
file <file hash> <data>
With this message, a peer can send you a full file. If both peers
support compression the data will be compressed. You should check
the file hash against the data, and if it checks out and matches a
file in your file system, you should send a have_file message to your
peers.
choke
This message tells peers that there
will likely be a delay in uploading files to him. This can be due to
high network traffic on your end, or because you don't like the peer.
In any case, a choked peer should stop bothering you for a while.
Connections start out choked to give both parties a chance to review
the history of their friendship.
unchoke
Use this message to tell a peer that
you now have enough bandwidth to serve file requests to him. Upon
receiving an unchoke message, a peer is now free to send file
requests. When network activity is low, consider unchoking all
peers.
hello “NetFS file system” <peer ID>{<option
string>}...
This message initiates a handshake, and is sent by both peers when
they connect. If this message is garbled, terminate the connection.
If it is valid, see if you know the peer, and respond with
hello_friend if you do, and form_friendship otherwise. Anonymous
requests such as list_filesys may be sent before any response to your
hello message is received, but signed messages must wait until the
handshake is complete.
Two currently supported options are “IPv6:1”, and
“zlib_compression:1”. These attributes must be specified to
enable IPv6 support, or zlib compression.
form_friendship <20 random bytes>
Send this message if you form a connection with a peer you don't
recognize. XOR the 20 random bytes you sent with the 20 random bytes
you receive to obtain the friendship key. Save this key to sign
future messages.
hello_friend
Send this message when you connect to a peer that you recognize.
list_files <filesys ID> <version name>
Use this message to ask a peer what files he has. In response, he
should send a file map. Publishers may send you this message as
well, in case you've asked for help updating, in which case they need
to know what files you have.
files <filesys ID> <version name> <file map>
This message tells a peer what files you have in a given file
system.
rate_peer <peer ID>
This message asks a peer to tell you
what he thinks of another peer. This message may also be used to
determine what your friends think of you.
peer_rating <peer ID>
<attribute>... <signature>
Required attributes to be returned
include:
“download_speed”
- average download speed from the peer in bytes/second
“average_speed”
- your average download speed from all peers
“availability”
- percentage attempted connections that were made successfully, a
number from 0 to 100
“uploaded” - K
bytes of total uploaded data to peer
“downloaded” - K bytes of total downloaded data from peer
A publisher may used this kind of data
to help determine good sets of peers. How much he values your
opinion should be a function of how he values your friendship.
invalid_message <reason
string>
Whenever a message is received
that cannot be processed, and invalid_message should be sent in
response. In general, it is ok to then close the connection. The
reason should be a human readable diagnostic message.
 |
