[tahoe-dev] share discovery and scalability

[Brian Warner]

On 7/22/10 10:22 PM, Ravi Pinjala wrote:
> Hi all,
> 
> So I have a few questions about how Tahoe scales. First, how well would
> it currently handle cases where there are thousands (or millions?) of
> clients? I remember reading in the documentation that a new client tries
> to connect to every node that the introducer knows, which seems like it
> would be a bottleneck, but I can't seem to find where I saw that anymore.

Probably not very well. Yes, currently it tries to establish a "full
mesh" of connections: every client keeps a TCP connection open to every
server (and usually each node behaves as both a client and a server).
This seems to work fine for a couple of hundred servers, but we expect
to see problems when a grid gets to thousands of servers (perhaps in NAT
boxes with limited connection tables, or in the traffic caused by all
the keepalives that get sent). I don't expect it to work at all in the
millions of nodes scale.

We've got some vague plans for that realm: more logN-based schemes like
Kademlia, and pushing more work onto the other servers (sending out a
request for a given share and letting it be forwarded from one server to
another until it finds the data it's looking for). But so far we've been
sticking to the smaller-scale problem space.

> Second, how does a node find shares that were uploaded to nodes it's not
> connected to? The situation I'm thinking of is a swarm large enough that
> there are two nodes which are looking at the same directory, but which
> are not connected directly to any of the same nodes. Would they be able
> to see each other's updates?

The current full-mesh design is specifically to avoid that case: there
needs to be sufficient overlap between the servers that were visible to
the uploader and the servers visible to the downloader. Since we won't
have any sort of recursive query until we move to something like
Kademlia, two clients who don't share enough servers may not be able to
download each other's files.

The current "permuted-ring" share-placement algorithm causes each file
to have a set of "preferred servers", where all the shares will be
uploaded (assuming those servers have enough room to accept the shares).
As long as all clients are connected to the same servers, this gives the
downloaders a really good chance of finding the necessary shares quickly
and efficiently.

hope that helps,
 -Brian