1
# Twisted, the Framework of Your Internet
2
# Copyright (C) 2001 Matthew W. Lefkowitz
4
# This library is free software; you can redistribute it and/or
5
# modify it under the terms of version 2.1 of the GNU Lesser General Public
6
# License as published by the Free Software Foundation.
8
# This library is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11
# Lesser General Public License for more details.
13
# You should have received a copy of the GNU Lesser General Public
14
# License along with this library; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
28
from twisted.spread import pb
30
NBIT = 160 # Size (in bits) of Chord identifiers
31
vNodes = 1 # sure hope you dont want more than 256.
34
"""Check if n in interval(a, b) on the circle."""
35
if a == b: return n != a # n is the only node not in (n, n)
36
elif a < b: return n > a and n < b
37
else: return n > a or n < b
39
def betweenL(n, a, b):
40
"""Check if n in interval[a, b) on the circle."""
41
if a == b and n == a: return 1
42
elif a < b: return n >= a and n < b
43
else: return n >= a or n < b
45
def betweenR(n, a, b):
46
"""Check if n in interval(a, b] on the circle."""
47
if a == b and n == a: return 1
48
elif a < b: return n > a and n <= b
49
else: return n > a or n <= b
52
class Node(pb.Copyable, pb.Perspective):
53
"""A node in a Chord network."""
55
def __init__(self, address, perspectiveName, identityName, port=pb.portno):
57
pb.Perspective.__init__(self, perspectiveName, identityName)
58
self.id = sha.new(socket.inet_aton(address) + struct.pack('!h', port) + chr(vNodes)).digest()
59
self.address = (address, port, vNodes)
61
self.finger = [None] * (NBIT+1)
62
self.lastFixed = 1 # Needed for fixFingers
65
def getStateToCopyFor(self, persp):
66
return {"id": self.id, "address": self.address}
69
return "<Node " + `self.id` + ">"
72
"""Intialize finger tables of local node.
73
n2 is a node already on the network or None if we're the first."""
75
n2.findSuccessor(self.id).addCallback(lambda x, self=self: self.getNodeAt(x).addCallback(self._setFingerCallback, callbackArgs=(1,)))
76
self.finger[1].notify(self.address, pbanswer=0)
77
self.findPredecessor(self.id).addCallback(self._setPredCallback)
78
for i in range(1, NBIT):
79
if betweenL(self.id, self.start(i+1),
81
self.finger[i+1] = self.finger[i]
83
n2.findSuccessor(self.start(i+1)).addCallback(lambda x, self=self, i=i: self.getNodeAt(x).addCallback(self._setFingerCallback, callbackArgs=(i+1,)))
84
n2.notify(self.address, pbanswer=0)
89
def _setFingerCallback(self, x, i):
90
#CRUM! DEFEATED BY DISTANCE
93
def _setPredCallback(self, n):
97
def perspective_getSuccessor(self):
100
def perspective_getPredecessor(self):
103
def perspective_findSuccessor(self, id):
104
self.findPredecessor(id).addCallback(self.findSuccessor_1)
106
def findSuccessor_1(self, n2):
107
n2.getSuccessor().addCallbacks(self.findSuccessor_2, callbackArgs=n2)
109
def findSuccessor_2(self, address, n2):
115
def findPredecessor(self, id):
116
if self.finger[1] is None:
119
return self.findPredecessor_1(n2, id)
121
def findPredecessor_1(self, n2, id):
122
n2.getSuccessor().addCallback(self.findPredecessor_2, n2, id)
124
def findPredecessor_2(self, n3, n2, id):
125
if not betweenR(id, n2.id, n3.id):
126
n2.closestPrecedingFinger(id).addCallback(lambda a, id=id, self=self: self.getNodeAt(a).addCallback(lambda n, id=id, self=self: self.findPredecessor_1(n, id)))
130
def perspective_closestPrecedingFinger(self, id):
131
for i in xrange(NBIT, 0, -1):
132
if not self.finger[i]: continue
133
if between(self.finger[i].id, self.id, id):
134
return self.finger[i].address
137
def getNodeAt(self, address):
138
return pb.connect(address[0], address[1], "chord", "", "chord").addCallback(lambda n: n.getSelf())
141
# necessary to produce proper Copyable behaviour
145
"""Verify our immediate successor and tell them about us.
146
Called periodically."""
147
self.finger[1].getPredecessor().addCallback(self.stabilise_1)
149
def stabilise_1(self, p):
150
if p != self.address:
151
self.perspective_notify(p)
153
def fixFingers(self):
154
"""Refresh a random finger table entry.
155
Called periodically."""
156
i = random.randrange(1, len(self.finger)+1)
157
self.finger[i] = self.findSuccessor(self.start(i))
159
def perspective_notify(self, addr):
160
"""n thinks it might be our predecessor."""
161
self.getNodeAt(addr).addCallback(self.notify)
164
if (self.pred is self or self.pred is None or
165
between(n.id, self.pred.id, self.id)):
167
n.notify(self.address, pbanswer=0)
168
if self.finger[1] is None or between(n.id, self.id, self.finger[1].id):
170
n.notify(self.address)
171
for i in xrange(2, len(self.finger)):
172
if self.finger[i] is None or betweenL(n.id, self.start(i), self.finger[i].id):
176
assert 1 <= k <= NBIT
177
r = (self.id + 2L**(k-1)) % 2L**NBIT
183
class ChordService(pb.Service):
184
def __init__(self, address, port, serviceName, application=None):
185
pb.Service.__init__(self, serviceName, application)
186
self.address = address
189
def createPerspective(self, name):
190
p = Node(self.address, name, name, self.portno)
191
self.perspectives[name] = p
added
removed
sandbox/chord.py
