Distributed Tile Caching Model - Revision history

Wiki-SchuylerErle: /* Maintaining the local directory */

2006-11-13T22:32:00Z

Maintaining the local directory

Wiki-SchuylerErle: major reworking to allow non-caching clients access to the network

2006-11-13T22:26:28Z

major reworking to allow non-caching clients access to the network

Wiki-SchuylerErle: /* Directory service */

2006-11-13T20:45:05Z

Directory service

Wiki-SchuylerErle: /* Discovering other peers */ clarification

2006-11-12T09:21:48Z

Discovering other peers: clarification

Wiki-SchuylerErle: /* Message integrity */ typo

2006-11-12T09:19:45Z

Message integrity: typo

Wiki-SchuylerErle: /* Expiring a tile */ typo

2006-11-12T09:16:26Z

Expiring a tile: typo

Wiki-SchuylerErle: refactoring timeout description

2006-11-12T09:15:17Z

refactoring timeout description

Wiki-SchuylerErle: /* Message integrity */

2006-11-12T08:57:40Z

Message integrity

Wiki-SchuylerErle at 08:56, 12 November 2006

2006-11-12T08:56:49Z

Wiki-SchuylerErle: /* References */

2006-11-12T08:54:24Z

References

@@ Line 36: / Line 36: @@
 #* 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 ==

@@ Line 1: / Line 1: @@
-This design outlines a model for a [[Distributed Tile Caching|distributed tile cache]]. The primary design goals are minimizing response latency for tile requests, and maintaining redundant storage of tiles across the cache.
+This design outlines a model for a [[Distributed Tile Caching|distributed tile cache]]. The primary design goals are minimizing response latency for tile requests, and maintaining redundant storage of tiles across the cache. Secondary design goals are to allow non-caching clients to request tiles directly from the cache, and to protect tile integrity by only permitting whitelisted peers to store data in the cache.
 = Definitions =
@@ Line 6: / Line 6: @@
 Each ''peer'' has its own persistent ''peer key'', generated randomly.
 The ''directory'' of peers consists of a list of (key, IP, port, weight) tuples, where ''weight'' is the bandwidth that the peer is willing to serve in KB/s, expressed as an integer.
-The ''directory server'' will serve the directory via HTTP from a well-known URL in gzip compressed whitespace-separated text.
+The ''directory server'' will serve the directory and layer configuration via HTTP from well-known URLs in gzip compressed whitespace-separated text.
 = Peers =
@@ Line 29: / Line 31: @@
 == Maintaining the local directory ==
-# After ''d'' minutes have passed, request a new directory listing with an ''If-Modified-Since'' header.
+# After ''d'' seconds have passed, request a new directory listing with an ''If-Modified-Since'' header.
 # If the server responds with a 304, wait another ''d'' minutes and check again.
 # Otherwise:
@@ Line 38: / Line 40: @@
 * Concatenate ''layer'' + ''level'' + ''row'' + ''column'' and take the SHA-1 sum. This is the ''tile key''.
-* Until ''k'' distinct peers are selected:
+* Until at most ''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.
-*# Decrement the timeout value for each selected peer.
+*# If the selected peer's timeout counter is 0, unselect it.
 *# Set the tile key to the key of the peer just selected.
 == Issuing requests ==
@@ Line 58: / Line 59: @@
 # Select ''k'' peers for the tile.
 # Send a GET message for the given tile to each of the selected peers asynchronously.
 === Expiring a tile ===
@@ Line 68: / Line 68: @@
 === Pinging other peers ===
-If the peer is behind a NAT gateway, it can use PING messages to keep the UDP port open on the firewall:
+# Every ''p'' seconds, select the peer with the largest key less than our peer key, whose timeout counter is greater than 0. If there are no such peers, select the peer with the largest key whose timeout counter is greater than 0.
-# Every 60 seconds, select a random peer from the binary tree.
+=== Reseeding ===
-# Decrement the timeout value for each selected peer.
-# If a peer's timeout value drops to zero, remove that peer from the binary tree, and start over.
+Every 2''p'' seconds, a peer should select a random tile from its local cache and reseed it in the network (if the local peer's cache supports random access).
 == Receiving requests ==
@@ Line 79: / Line 80: @@
 === Responding to a GET request ===
-# If the tile is present in the local cache, send a PUT message in response.
+* If the tile is present in the local cache, send a PUT message in response.
-# Otherwise, send a PONG message in response.
+* Otherwise:
 === Receiving a PUT request ===
-# Store the tile in the local cache.
+* If the tile does not belong to a layer that the peer is configured to cache, discard it.
-# Reset the sending peer's timeout value to ''v''.
+* Otherwise, store the tile in the local cache.
 === Receiving a DELETE request ===
@@ Line 101: / Line 109: @@
 Every PING message should be responded to with a matching PONG message.
 = Directory service =
-* When a peer requests the directory listing, store its directory tuple in the database, along with the time it made the request.
+* When a peer requests the directory listing, store its tuple in the directory, along with the time it made the request.
-* Every ''d'' x 2 minutes, remove any peers from the database that have not made a directory request since the last check.
+* Every 2''d'' seconds, remove any peers from the directory that have not made a directory request since the last check.
 * Peers can and perhaps should be whitelisted to insure data integrity over the network. Peers not on the whitelist should not be added to the directory.
 * 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.
@@ Line 117: / Line 121: @@
 = Plausible parameter values =
 * ''k'' = 3
 = Protocol format =
@@ Line 150: / Line 155: @@
 To ensure message integrity, a peer should make the following checks when a message is received:
-# Compare the peer key embedded in the message with the sending IP's recorded peer key. If they do not match, discard the message.
+# Compare the peer key embedded in the message with the sending IP's recorded peer key. If they do not match, and the message is a PUT or DELETE message, discard it.
 # Compare the checksum embedded in the message with the checksum of the payload. If they do not match, discard the message.
 # Check the message sequence against the sending peer's most recent sequence ID.
 #* If the message sequence is less than or equal to the previously set sequence ID for that peer, discard the message.
-#* Otherwise, update the peer's sequence ID.
+#* Otherwise, update the peer's sequence ID and reset its timeout counter to ''v''.
 == PING messages ==

@@ Line 112: / Line 112: @@
 * Peers can and perhaps should be whitelisted to insure data integrity over the network. Peers not on the whitelist should not be added to the directory.
 * 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.
 * The directory service can seek high availability through a shared database backend and round-robin DNS.

@@ Line 16: / Line 16: @@
 # Request the directory listing from the server, passing the peer's directory tuple.
-# Normalize the weights of each peer.
+# Normalize the weights of each peer to a float in the range [0, 1).
 # Create an empty balanced binary tree.
 # For every other peer listed:

@@ Line 150: / Line 150: @@
 # Compare the peer key embedded in the message with the sending IP's recorded peer key. If they do not match, discard the message.
-# Compare the checksum embeeded in the message with the checksum of the payload. If they do not match, discard the message.
+# Compare the checksum embedded in the message with the checksum of the payload. If they do not match, discard the message.
 # Check the message sequence against the sending peer's most recent sequence ID.
 #* If the message sequence is less than or equal to the previously set sequence ID for that peer, discard the message.

@@ Line 64: / Line 64: @@
 * A DELETE request can cover a rectangular range of tiles at a given level for a given layer.
 * Start by selecting ''k'' peers for the lower left tile in the expiration request.
-* Send a DELETE message for the given tile to each of the selected peers asynchronously.
+* Send a DELETE message for the given tiles to each of the selected peers asynchronously.
 === Pinging other peers ===

@@ Line 145: / Line 145: @@
 == Message integrity ==
-* Compare the peer key embedded in the message with the sending IP's recorded peer key. If they do not match, discard the message.
+To ensure message integrity, a peer should make the following checks when a message is received:
-* Compare the checksum embeeded in the message with the checksum of the payload. If they do not match, discard the message.
-* Check the message sequence against the sending peer's most recent sequence ID.
+# Compare the peer key embedded in the message with the sending IP's recorded peer key. If they do not match, discard the message.
-** If the message sequence is less than or equal to the previously set sequence ID for that peer, discard the message.
+# Compare the checksum embeeded in the message with the checksum of the payload. If they do not match, discard the message.
-** Otherwise, update the peer's sequence ID.
+# Check the message sequence against the sending peer's most recent sequence ID.
 == PING messages ==

@@ Line 20: / Line 20: @@
 # For every other peer listed:
 ## Set the peer's timeout value to ''v''.
-## Add the peer to the tree using its key.
+## Set the peer's message sequence ID to 0.
 ## Calculate ''r'' = ''normalized weight'' x 64.
 ## 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.
+##* Insert a reference to the peer into the tree using the subsidiary key.
 == Maintaining the local directory ==
@@ Line 137: / Line 138: @@
 The message ''payload'' takes up the remainder of the message.
 == Message integrity ==

@@ Line 168: / Line 168: @@
 = References =
-* This model is based largely on the Kademlia algorithm discussed at length in [Distributed Tile Caching], with the addition of a directory server to keep latency down.
+* This model is based largely on the Kademlia algorithm discussed at length in [[Distributed Tile Caching]], with the addition of a directory server to keep latency down.
 * [http://www8.org/w8-papers/2a-webserver/caching/paper2.html Web Caching with Consistent Hashing] is a seminal work in distributed caching.
 * [http://code.sixapart.com/svn/memcached/trunk/api/perl/dev/cons-hash.pl A pure-Perl implementation] of the algorithm described in the above paper.