Sunday, October 11, 2009

Xus Milestone 1 complete

According to my only somewhat extensive automated tests, Milestone 1 (Basic Xus) is now complete. That includes layers 1 and 2 and the property service (transient and persistent properties). Plexus relies heavily on its property service (currently backed by FreePastry) and I think it will be useful to other programs as well. It's kind of a persistent broadcast; it's really just for relatively small databases, like if you have to track a few hundred things for the topic, like player locations in a game or account credit, for instance. Plexus uses properties for player presence (nickname, which world they're connected to, etc.) and object information (location, orientation, costume, etc.) If you need to store large amounts of data, it might be appropriate to use the file storage service (coming soon and featuring optional Git integration) or maybe to add a database service (and contributing it back to the project would be nifty, too). DHT message routing is useful for this sort of thing, so you don't necessarily have to replicate all the data to all of the peers if you are storing a large amount.

When a peer successfully joins a topic, the topic owner sends it the current property values. Peers broadcast property settings or deletions to the topic and the topic owner keeps track of the properties for when new members join. This creates a very simple (some might even say simplistic) database for each topic. It's just key-value pairs of strings (like in Java's Properties object).

When you set a property, you specify whether the setting should be persistent. If a peer has storage turned on, persistent properties are stored in an XML file so that they are there next time the peer starts up. It usually only important for topic owners to store persistent properties, because other peers always get the latest properties for a topic when they connect to it (and they may have changed since the peer was last connected anyway).

Wednesday, October 7, 2009

Xus' file storage service and Git

Xus has a 2-pronged approach for integrating its file storage with Git:
  1. the basic file storage will just use ordinary file storage, with an approach similar to Git's, ensuring that Xus' model is "compatable" with Git's
  2. provide a plugin that uses JGit ( for people who want to maintain a local Git repository
Each peer can be optionally Git-enabled, since the peers will only interact with a local Git repository. It doesn't use Git's protocol to exchange data, because we want Xus to be able to swarm downloads, but a Git-enabled peer could use Git-clone to seed its cache. Since the file storage protocol doesn't have to interact with Git, Xus just needs #1 to make sure that a peer can fetch everything it needs over the net. Since Git uses SHA-1 hashes as keys for almost every type of object, this shouldn't bloat the protocol too much. Note that when I say "protocol" here, I'm talking about the file storage service protocol, which rides inside of layer 2 messages, not Xus' layer 1 or layer 2 protocols.

The file storage service will break files into chunks and use the DHT to spread the chunks around. This is how we do it right now in Plexus; the directory and chunk models are ours and Plexus uses PAST (Pastry's DHT file storage service) to store and retrieve the objects (chunks, file chunk lists, and directories). Xus DHT file service will be similar to PAST's but not entirely the same. The chunk/chunk list/directory model will be similar to Plexus' but it also needs branches, commits, and tags, in order to use Git.

The Git model has been a milestone on Plexus since last year because I think it's crucial to power an open, collaborative gaming environment. In a completely open environment where anyone can change anything, version history ensures that people can't destroy data; they can only create new versions without some of the data, and signed commits make spoofing very difficult, allow people to rate authors based on their work, etc.

This also has the side effect of making a p2p version of Git :).

I don't think totally reimplementing PAST is a good idea for small clouds, because I believe data copying would kill the network. If the cloud is small, with peers joining and leaving slowly over time but never getting larger than 5, each time a new peer joins, it gets a copy of all of the data in storage. PAST does have caching and it works very well for large clouds where storage is built up slowly over time, but I don't think it works well for small rings. For this reason, I'm planning on only having the topic space masters replicate automatically (hopefully starting with a Git-cloned cache seed), but having "ordinary" peers "fill in the holes" from the topic space master peers on-demand. This will slow down initial requests, but amortize the impact on the network.

In practice, I think JGit integration will probably be the default, but I still want to provide it as a plugin as a courtesy to projects so they don't have to link in yet another third party library if they don't require it. Also, I want non-Git-enabled peers to be able to work with Git-enabled ones seemlessly. At least this is what seems like a good idea at this time :).

This implements a form of swarming download, similar in spirit to bittorrent, but not similar in the way it actually functions; you can simultaneously download chunks of files from different peers and several peers will have the chunks, but it's organized quite differently.

Also :) I'm thinking that it would be a good idea to give each directory (with all of its versions) a separate "view" in Git; i.e. new directories are branched from HEAD in Git (like when you make static web pages for Github: This will give each directory an independent set of branches, allowing people to store many different directories in a single Git repository without having to check out a ton of stuff just to get the directory you want, AND it also allows you to reuse the files from other directories because they're all in one Git repository.

Sunday, October 4, 2009

Xus: Layers 1 and 2 work now

I have layers 1 and 2 working now, with automated tests (it's on github). Layer 1 is simple packets and layer 2 is p2p messaging. That covers:
  • strong authentication (challenge/response on connect with RSA keys & signatures)
  • direct peer-to-peer messages
  • broadcast messages
  • unicast messages
  • dht messages (delegated to the peer with the peer id closest to the dht key)
  • delegated peer-to-peer messages (one peer sending to another peer through a topic)
Right now, as long as your peer doesn't spoof its public key, it can connect to any topic (authorization is part of layer 3). I think one other thing I should add to layer 1 is a heart beat, so you can quickly detect dropped connections (TCP timeouts are notoriously unreliable).

Layer 3 is the service layer and has these components:
  • Properties
  • Topic authorization and management (including peer "accounts")
  • File sharing
  • Port configuration testing
  • Connect-back requests (for when only one peer can accept connections)
A note about topic management: the idea is to use topic space 0 as a "root" topic space for a cluster of spaces, with topic 1 in space 0 handling administrative concerns for the cluster, like id vending for topic spaces and small id vending for peers (so messages don't have to contain a giant peer ids). Topic 0,1 would contain a set of properties about accounts and topics which would also allow banning users from clusters and members-only clusters (allowing private and pay services).

I was thinking back to the very start of my peer-to-peer experiments, so I searched my email archives to see when I started with this. It was April, 2001 when I first started talking p2p architectures over with my friend Fritz. A little while later, I made the p2pmud project on source forge; for project paleontologists, here's a link to the old p2pmud forums.

The project transitioned through several languages and architectures, eventually adopting FreePastry in Plexus so that we didn't have to write and maintain our own peer-to-peer networking layer. So now we have to do that and, ironically, the architecture's pretty close to the one I came up with in 2001, except that it's simpler. In 2001, I had envisioned a set of peers that routed requests to other, natted peers, but now we just have one peer doing the routing for a "topic space" with a bunch of topic spaces clustering to form the entire peer-to-peer grid.