Distributed Tile Caching Model

This design outlines a model for a distributed tile cache.

Definitions

A key is a 20 byte SHA-1 sum.

Each peer has its own persistent peer key, generated randomly.

The directory of peers consists of a list of (key, IP, port, weight), where weight is the bandwidth that the peer is willing to serve in KB/s.

The directory server will serve the directory via HTTP from a well-known URL in gzip compressed whitespace-separated text.

Peers

Discovering other peers

1. Request the directory listing from the server, passing the peer's directory tuple.
2. Normalize the weights of each peer.
3. Create an empty balanced binary tree.
4. For every other peer listed:
   1. Set the peer's timeout value to v.
   2. Add the peer to the tree using its key.
   3. Calculate r = normalized weight x 64.
   4. For i in range(1, r):
      • Calculate a subsidiary key by concatenating the peer key with the binary value of i, and take the SHA-1 sum of the result.
      • Insert the peer into the tree using the subsidiary key.

Maintaining the local directory

1. After d minutes have passed, request a new directory listing with an If-Modified-Since header.
2. If the server responds with a 304, wait another d minutes and check again.
3. Otherwise:
   • For every peer in the binary tree not in the new listing, remove it.
   • For every peer in the directory listing not in the binary tree, add it.

Selecting peers for a given tile

1. Concatenate layer + level + row + column and take the SHA-1 sum. This is the tile key.
2. If there are fewer than k peers in the directory, select all other known peers.
3. Otherwise, until k distinct peers are selected:
   • Select the first peer from the binary tree with key greater than or equal to the tile key.
   • If there are no matching peers in the tree, select the first peer in tree.
   • Set the tile key to the key of the peer just selected.

Seeding a tile

1. Fetch the tile from the data source (or render the tile or whatever).
2. Select k peers for the tile.
3. If the storing peer is selected, discard it.
4. Send a PUT message to each peer asynchronously.

Receiving a PUT request

When a peer receives a PUT request from another peer, it should reset that peer's timeout value to v.

Fetching a tile

1. Select k peers for the tile.
2. Send a GET message for the given tile to each of the selected peers asynchronously.
3. Decrement the timeout value for each selected peer.
4. If a peer's timeout value drops to zero, remove that peer from the binary tree.
5. If no peer responds within t seconds, seed the tile in the network.

Responding to a GET request

1. If the tile is present in the local cache, send a PUT message in response.
2. Select k peers for the tile.
3. If the peer's own key is between the original tile key and the first peer selected, seed the tile in the network.
4. Otherwise, attempt to fetch the tile from the network.

Receiving a DELETE request

1. Remove the tile(s) from the local cache.
2. Select k peers for the lower left tile of the DELETE request.
3. If the tile key is between the peer's key and the first peer selected, stop.
4. Otherwise, propagate the DELETE request to the k peers asynchronously.

Sending PINGs

If the peer is behind a NAT gateway, it can use PING messages to keep the UDP port open on the firewall:

1. Every 60 seconds, select a random peer from the binary tree and send it a PING message.
2. If the peer responds with a PONG message within t seconds, reset its timeout value to v.
3. Otherwise, remove the peer from the binary tree.

Receiving PINGs

Every PING message should be responded to with a matching PONG message.

Directory service

1. When a peer requests the directory listing, store its directory tuple in the database, along with the time it made the request.
2. Every d x 2 minutes, remove any peers from the database that have not made a directory request since the last check.
3. Peers can be whitelisted to insure data integrity over the network.
4. The directory listing should be about 60 bytes per peer. With 10,000 peers, and assuming a 6:1 gzip compression ratio, a fresh listing should be at most 100k compressed.
5. The directory service can seek high availability through a shared database backend and round-robin DNS.

Plausible protocol parameter values

• d = 5
• v = 5
• t = 1
• k = 3

Protocol format

Protocol messages will be served via UDP.

Each message is a tuple consisting of (Peer Key, Type, Sequence, Checksum, Payload), for a total of 29 + n bytes.

Message type may be one of:

1. PING
2. PONG
3. GET
4. PUT
5. DELETE

Message sequence must be a monotonically increasing 32-bit number.

Message checksum is a CRC-32 checksum of the data payload

The message payload takes up the remainder of the message.

Message sequence

When a message is received, the message sequence should be checked against the sending peer's most recent sequence ID. If none was previously set, set it. Otherwise, if the message sequence is less than or equal to the previously set sequence ID, discard the message. Otherwise, update the peer's sequence ID.

PING messages

PING messages have a checksum of 0 and no payload.

PONG messages

A PONG message payload consists of the sequence number from the corresponding PING packet.

GET messages

A GET message payload consists of the tuple (Layer, Level, Row, Column). The layer value is a zero-terminated string. The row and column values are 32-bit integers.

PUT messages

A PUT message payload consists of the tuple (Layer, Level, Row, Column, Data).

DELETE messages

A DELETE message payload consists of the tuple (Layer, Level, MinRow, MinCol, MaxRow, MaxCol).