From e6cb61cfc53cc379909c64396f338505011203d4 Mon Sep 17 00:00:00 2001 From: Cameron Dale Date: Thu, 21 Feb 2008 13:42:02 -0800 Subject: [PATCH] Use compact encoding of node contact info in the DHT. --- apt_dht_Khashmir/actions.py | 7 +++-- apt_dht_Khashmir/khashmir.py | 8 +++--- apt_dht_Khashmir/ktable.py | 4 +-- apt_dht_Khashmir/node.py | 13 ++++++--- apt_dht_Khashmir/util.py | 53 ++++++++++++++++++++++++++++++++++++ 5 files changed, 73 insertions(+), 12 deletions(-) diff --git a/apt_dht_Khashmir/actions.py b/apt_dht_Khashmir/actions.py index 27cb5d8..b8f5c8c 100644 --- a/apt_dht_Khashmir/actions.py +++ b/apt_dht_Khashmir/actions.py @@ -5,6 +5,7 @@ from twisted.internet import reactor from twisted.python import log from khash import intify +from util import uncompact class ActionBase: """ base class for some long running asynchronous proccesses like finding nodes or values """ @@ -50,7 +51,8 @@ class FindNode(ActionBase): return self.outstanding = self.outstanding - 1 self.answered[dict["id"]] = 1 - for node in l: + for compact_node in l: + node = uncompact(compact_node) n = self.caller.Node(node) if not self.found.has_key(n.id): self.found[n.id] = n @@ -125,7 +127,8 @@ class GetValue(FindNode): # go through nodes # if we have any closer than what we already got, query them if dict.has_key('nodes'): - for node in dict['nodes']: + for compact_node in dict['nodes']: + node = uncompact(compact_node) n = self.caller.Node(node) if not self.found.has_key(n.id): self.found[n.id] = n diff --git a/apt_dht_Khashmir/khashmir.py b/apt_dht_Khashmir/khashmir.py index 931c05e..5d40dee 100644 --- a/apt_dht_Khashmir/khashmir.py +++ b/apt_dht_Khashmir/khashmir.py @@ -210,7 +210,7 @@ class KhashmirBase(protocol.Factory): n = self.Node(id, _krpc_sender[0], _krpc_sender[1]) self.insertNode(n, contacted=0) nodes = self.table.findNodes(target) - nodes = map(lambda node: node.senderDict(), nodes) + nodes = map(lambda node: node.contactInfo(), nodes) return {"nodes" : nodes, "id" : self.node.id} @@ -249,7 +249,7 @@ class KhashmirRead(KhashmirBase): return {'values' : l, "id": self.node.id} else: nodes = self.table.findNodes(key) - nodes = map(lambda node: node.senderDict(), nodes) + nodes = map(lambda node: node.contactInfo(), nodes) return {'nodes' : nodes, "id": self.node.id} ### provides a generic write method, you probably don't want to deploy something that allows @@ -335,7 +335,7 @@ class SimpleTests(unittest.TestCase): reactor.iterate() reactor.iterate() self.got = 0 - self.a.storeValueForKey(sha('foo').digest(), 'foobar', datetime.utcnow()) + self.a.storeValueForKey(sha('foo').digest(), 'foobar') reactor.iterate() reactor.iterate() reactor.iterate() @@ -417,7 +417,7 @@ class MultiTest(unittest.TestCase): self.done = 0 def _scb(key, value, result): self.done = 1 - self.l[randrange(0, self.num)].storeValueForKey(K, V, datetime.utcnow(), _scb) + self.l[randrange(0, self.num)].storeValueForKey(K, V, _scb) while not self.done: reactor.iterate() diff --git a/apt_dht_Khashmir/ktable.py b/apt_dht_Khashmir/ktable.py index f3001a5..907263e 100644 --- a/apt_dht_Khashmir/ktable.py +++ b/apt_dht_Khashmir/ktable.py @@ -211,11 +211,11 @@ class KBucket: class TestKTable(unittest.TestCase): def setUp(self): - self.a = Node(khash.newID(), 'localhost', 2002) + self.a = Node(khash.newID(), '127.0.0.1', 2002) self.t = KTable(self.a, {'HASH_LENGTH': 160, 'K': 8, 'MAX_FAILURES': 3}) def testAddNode(self): - self.b = Node(khash.newID(), 'localhost', 2003) + self.b = Node(khash.newID(), '127.0.0.1', 2003) self.t.insertNode(self.b) self.failUnlessEqual(len(self.t.buckets[0].l), 1) self.failUnlessEqual(self.t.buckets[0].l[0], self.b) diff --git a/apt_dht_Khashmir/node.py b/apt_dht_Khashmir/node.py index 89845cb..9903b5a 100644 --- a/apt_dht_Khashmir/node.py +++ b/apt_dht_Khashmir/node.py @@ -5,8 +5,10 @@ from datetime import datetime, MINYEAR from types import InstanceType from twisted.trial import unittest +from twisted.python import log import khash +from util import compact # magic id to use before we know a peer's id NULL_ID = 20 * '\0' @@ -14,6 +16,7 @@ NULL_ID = 20 * '\0' class Node: """encapsulate contact info""" def __init__(self, id, host = None, port = None): + log.msg('New node: id=%r, host=%r, port=%r' % (id, host, port)) self.fails = 0 self.lastSeen = datetime(MINYEAR, 1, 1) @@ -29,7 +32,7 @@ class Node: self.num = khash.intify(id) self.host = host self.port = int(port) - self._senderDict = {'id': self.id, 'port' : self.port, 'host' : self.host} + self._contactInfo = None def updateLastSeen(self): self.lastSeen = datetime.now() @@ -39,8 +42,10 @@ class Node: self.fails = self.fails + 1 return self.fails - def senderDict(self): - return self._senderDict + def contactInfo(self): + if self._contactInfo is None: + self._contactInfo = compact(self.id, self.host, self.port) + return self._contactInfo def __repr__(self): return `(self.id, self.host, self.port)` @@ -74,7 +79,7 @@ class Node: class TestNode(unittest.TestCase): def setUp(self): - self.node = Node(khash.newID(), 'localhost', 2002) + self.node = Node(khash.newID(), '127.0.0.1', 2002) def testUpdateLastSeen(self): t = self.node.lastSeen self.node.updateLastSeen() diff --git a/apt_dht_Khashmir/util.py b/apt_dht_Khashmir/util.py index 7808857..fa1c2ee 100644 --- a/apt_dht_Khashmir/util.py +++ b/apt_dht_Khashmir/util.py @@ -1,6 +1,8 @@ ## Copyright 2002-2003 Andrew Loewenstern, All Rights Reserved # see LICENSE.txt for license information +from twisted.trial import unittest + def bucket_stats(l): """given a list of khashmir instances, finds min, max, and average number of nodes in tables""" max = avg = 0 @@ -21,3 +23,54 @@ def bucket_stats(l): avg = avg + c avg = avg / len(l) return {'min':min, 'max':max, 'avg':avg} + +def uncompact(s): + """Extract the contact info from a compact node representation. + + @type s: C{string} + @param s: the compact representation + @rtype: C{dictionary} + @return: the node ID, IP address and port to contact the node on + @raise ValueError: if the compact representation doesn't exist + """ + if (len(s) != 26): + raise ValueError + id = s[:20] + host = '.'.join([str(ord(i)) for i in s[20:24]]) + port = (ord(s[24]) << 8) | ord(s[25]) + return {'id': id, 'host': host, 'port': port} + +def compact(id, host, port): + """Create a compact representation of node contact info. + + @type id: C{string} + @param id: the node ID + @type host: C{string} + @param host: the IP address of the node + @type port: C{int} + @param port: the port number to contact the node on + @rtype: C{string} + @return: the compact representation + @raise ValueError: if the compact representation doesn't exist + """ + + s = id + ''.join([chr(int(i)) for i in host.split('.')]) + \ + chr((port & 0xFF00) >> 8) + chr(port & 0xFF) + if len(s) != 26: + raise ValueError + return s + +class TestUtil(unittest.TestCase): + """Tests for the utilities.""" + + timeout = 5 + myid = '\xca\xec\xb8\x0c\x00\xe7\x07\xf8~])\x8f\x9d\xe5_B\xff\x1a\xc4!' + host = '165.234.1.34' + port = 61234 + + def test_compact(self): + d = uncompact(compact(self.myid, self.host, self.port)) + self.failUnlessEqual(d['id'], self.myid) + self.failUnlessEqual(d['host'], self.host) + self.failUnlessEqual(d['port'], self.port) + \ No newline at end of file -- 2.39.5