Skip to content

Instantly share code, notes, and snippets.

@tav

tav/old_dht.py

Created October 25, 2009 18:58
Show Gist options
  • Save tav/218191 to your computer and use it in GitHub Desktop.
Save tav/218191 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
old_dht.py
"""Distributed Hash Tables (DHT)."""
__all__ = ['chord', 'dictionary', 'kademlia', 'koorde']
__metaclass__ = type
class DHT:
pass
class Dictionary(DHT):
"""
A simple Dictionary-based Distributed Hash Table (DHT).
Way back in early 2001, before the Chord papers were published and DHT
became a trendy term, oierw and myself had worked out a similar scheme. We
didn't have a funky name for it and simply referred to it as an underlying
aspect of the Mesh Routing Protocol.
04:07:19 <tav> i presume everyone here is familiar with a dictionary? ;p
04:07:26 <sbp> a what?
04:07:36 <deltab> sbp: a less detailed ontology
04:07:37 * sbp looks up that word in his dictionary
04:07:52 <deltab> er, less rigorous
The term ``Dictionary`` DHT is used because of the dictionary metaphor that
was often employed when explaining the term to others.
>>> d = Dictionary()
"""
pass
# the following is from earlier plexdev:
# ------------------------------------------------------------------------------
# chord circle math
# ------------------------------------------------------------------------------
def between(n, a, b):
"""Check if n in interval(a, b) on a circle."""
if a == b: return n != a # n is the only node not in (n, n)
elif a < b: return n > a and n < b
else: return n > a or n < b
def betweenL(n, a, b):
"""Check if n in interval[a, b) on a circle."""
if a == b and n == a: return 1
elif a < b: return n >= a and n < b
else: return n >= a or n < b
def betweenR(n, a, b):
"""Check if n in interval(a, b] on a circle."""
if a == b and n == a: return 1
elif a < b: return n > a and n <= b
else: return n > a or n <= b
# ------------------------------------------------------------------------------
# some konstants
# ------------------------------------------------------------------------------
NBIT = 5 # num of bits in identifiers
nodeList = [] # list of all nodes
class Node:
"""
An implementation of the Chord_ algorithm in Python.
.. _Chord: http://pdos.lcs.mit.edu/chord/
This class creates nodes in a network.
# Create a bootstrap node:
>>> bootstrapNode = Node(1)
>>> bootstrapNode.join(None)
>>> import random
>>> for i in xrange(5): # Create 5 randomly placed nodes
... j = random.randrange(1, 2**NBIT)
... x = Node(j)
... x.join(bootstrapNode)
>>> for i in xrange(2): # fix their finger tables
... for node in nodeList:
... node.stabilize()
... node.fixFingers()
>>> for node in nodeList:
... print node.f
... #node.f.test()
<Finger object>
<Finger object>
<Finger object>
<Finger object>
<Finger object>
<Finger object>
>>> nodeList.sort()
>>> firstNode = nodeList[0]
>>> firstNode.id
1
>>> firstNode.fixFingers()
Sources:
Chord TR <http://pdos.lcs.mit.edu/chord/chord-tn.ps>
Chord SIGCOMM Paper <http://pdos.lcs.mit.edu/papers/chord:sigcomm01/>
Chord Source Code <http://www.fs.net/cvs/sfsnet/chord/?cvsroot=CFS-CVS>
"""
def __init__(self, id):
BadID = "ValueError: ID is too big, must be less than " + str(2L**NBIT)
if id > 2**NBIT: raise BadID
self.id = id # Needs to be an integer of NBIT bits
self.f = Finger(self) # Keeps track of other nodes
global nodeList
nodeList.append(self) # Add us to the big nodeList
def __repr__(self):
"""Return a pretty text representation of a node."""
return "<Node " + `self.id` + ">"
def join(self, n2):
"""Intialize finger tables of local node.
n2 is a node already on the network or None if we're the first."""
if n2:
self.f[1] = n2.getSucc(self.id) # Get our successor
self.f.pred=self.getPred(self.id) # Get our predecessor
for i in xrange(1, NBIT):
if betweenL(self.id, # If the last finger
self.f.start(i+1), self.f[i].id): # is still good
self.f[i+1] = self.f[i] # use it again.
else:
self.f[i+1] = n2.getSucc( # Get a new one.
self.f.start(i+1))
n2.notify(self) # Hi to our 1st friend
self.f[1].notify(self) # and say hello.
self.f.pred.notify(self) # and say hello.
else: # If we're all alone
self.f[1] = self # then leave our
self.f.pred = self # tables empty.
def getSucc(self, id):
"""Find the successor of id on the circle.
This is the key function of the algorithm and its main interface."""
n2 = self.getPred(id) # Get its predecessor.
if n2.f[1]: # If it has a successor
return n2.f[1] # use that.
else: return n2 # Else, use the pred.
def getPred(self, id):
"""Find the predecessor of id on the circle."""
if self.f[1] is None: # If we have no succ
return self # use ourselves.
n2 = self
while not betweenR(id, n2.id, n2.f[1].id): # Iteratively find
n2 = n2.closestPrecedingFinger(id) # the closest finger
return n2 # and use it.
def closestPrecedingFinger(self, id):
"""Find the closest finger that precedes id.
This is the key to the algorithm."""
for i in xrange(NBIT, 0, -1):
if not self.f[i]: continue
if between(self.f[i].id, self.id, id):
return self.f[i]
return self
def notify(self, n2):
"""n2 introduces itself. Add them to finger table."""
self.f.add(n2)
def stabilize(self):
"""Verify our immediate successor and tell them about us.
Call periodically."""
x = self.f[1].f.pred # Find our pred's succ
if x is not self: # If it's not us
self.f.add(x) # make them a finger.
def fixFingers(self):
"""Refresh the finger table entries. Call periodically.
@@ The current implementation fixes all nodes at once.
@@ This is really slow, replace with random or generators."""
for i in xrange(1, len(self.f)): # For every finger
self.f[i] = self.getSucc(self.f.start(i)) # find the best node.
class Finger(list):
"""A node's finger table."""
def __init__(self, parent):
list.__init__(self)
self.parent = parent # parent node
self.id = parent.id # chord ID
self.pred = None # predecessor
# Fill up the list:
self.append('ignore first value')
for i in xrange(1, NBIT+1):
# @@ This wastes memory. Need to override setattr, getattr.
self.append(None)
def __repr__(n):
"""Make a nice printout of the finger table. Good for debugging."""
return '<Finger object>'# @@ doesn't deal with unfilled predicates and such
from cStringIO import StringIO
out = StringIO()
print >> out, "------------------------"
print >> out, " P:", n.pred.id
print >> out, " M:", n.id
i = 0
for e in n:
if type(e) is type(''): continue
i += 1
if e is None:
print >> out, " "+`i`+": None"
continue
print >> out, " "+`i`+":", e.id, '|', n.parent.getSucc(n.start(i)).id, '|', n.start(i)
print >> out, "------------------------"
return out.getvalue()
def test(self):
"""Makes sure finger tables are correct for a saturated network.
@@ Make it work for random networks too."""
i = 0
for e in n.f:
if type(e) is type(''): continue
i += 1
assert e.id == n.f.start(i)
def start(self, k):
"""Find the starting point of a finger table entry."""
assert 1 <= k <= NBIT # Check assumptions
r = (self.id + 2**(k-1)) % 2**NBIT # Get the number
if r == 0: return 2**NBIT # Fix funniness with %
else: return r # Return the value
def add(self, n):
"""Add this new node to our tables.
Eventually this should also put it in the node cache."""
results = [] # Stores what we did
if (self.pred is self or self.pred is None or # If our pred is empty
between(n.id, self.pred.id, self.id)): # or this is better
self.pred = n # use it
#n.notify(self.parent) # and say hello
results.append('pred') # Keep track.
if self[1] is None or between(n.id, self.id, # Repeat for successor
self[1].id):
self[1] = n
#n.notify(self.parent)
results.append(1)
for i in xrange(2, len(self)): # Repeat for the rest
if self[i] is None or betweenL(n.id, self.start(i), self[i].id):
self[i] = n
results.append(i)
return results # Return what we did
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment