# whether this node is a bootstrap node
BOOTSTRAP_NODE = no
-# Kademlia "K" constant, this should be an even number
-K = 8
-
-# SHA1 is 160 bits long
-HASH_LENGTH = 160
-
# interval between saving the running state
CHECKPOINT_INTERVAL = 5m
# for everybody to download
'OTHER_DIRS': """""",
- # User name to try and run as
- 'USERNAME': '',
-
# Whether it's OK to use an IP address from a known local/private range
'LOCAL_OK': 'no',
# whether this node is a bootstrap node
'BOOTSTRAP_NODE': "no",
- # Kademlia "K" constant, this should be an even number
- 'K': '8',
-
- # SHA1 is 160 bits long
- 'HASH_LENGTH': '160',
-
# checkpoint every this many seconds
'CHECKPOINT_INTERVAL': '5m', # five minutes
'KEY_EXPIRE': '1h', # 60 minutes
# whether to spew info about the requests/responses in the protocol
- 'SPEW': 'yes',
+ 'SPEW': 'no',
}
class AptP2PConfigParser(SafeConfigParser):
from apt_p2p.interfaces import IDHT, IDHTStats, IDHTStatsFactory
from khashmir import Khashmir
from bencode import bencode, bdecode
+from khash import HASH_LENGTH
try:
from twisted.web2 import channel, server, resource, http, http_headers
self.bootstrap_node = self.config_parser.getboolean(section, 'BOOTSTRAP_NODE')
for k in self.config_parser.options(section):
# The numbers in the config file
- if k in ['K', 'HASH_LENGTH', 'CONCURRENT_REQS', 'STORE_REDUNDANCY',
+ if k in ['CONCURRENT_REQS', 'STORE_REDUNDANCY',
'RETRIEVE_VALUES', 'MAX_FAILURES', 'PORT']:
self.config[k] = self.config_parser.getint(section, k)
# The times in the config file
self.joined = False
self.khashmir.shutdown()
- def _normKey(self, key, bits=None, bytes=None):
+ def _normKey(self, key):
"""Normalize the length of keys used in the DHT."""
- bits = self.config["HASH_LENGTH"]
- if bits is not None:
- bytes = (bits - 1) // 8 + 1
- else:
- if bytes is None:
- raise DHTError, "you must specify one of bits or bytes for normalization"
-
# Extend short keys with null bytes
- if len(key) < bytes:
- key = key + '\000'*(bytes - len(key))
+ if len(key) < HASH_LENGTH:
+ key = key + '\000'*(HASH_LENGTH - len(key))
# Truncate long keys
- elif len(key) > bytes:
- key = key[:bytes]
+ elif len(key) > HASH_LENGTH:
+ key = key[:HASH_LENGTH]
return key
def getValue(self, key):
"""Simple 2-node unit tests for the DHT."""
timeout = 50
- DHT_DEFAULTS = {'PORT': 9977, 'K': 8, 'HASH_LENGTH': 160,
+ DHT_DEFAULTS = {'PORT': 9977,
'CHECKPOINT_INTERVAL': 300, 'CONCURRENT_REQS': 4,
'STORE_REDUNDANCY': 3, 'RETRIEVE_VALUES': -10000,
'MAX_FAILURES': 3,
timeout = 80
num = 20
- DHT_DEFAULTS = {'PORT': 9977, 'K': 8, 'HASH_LENGTH': 160,
+ DHT_DEFAULTS = {'PORT': 9977,
'CHECKPOINT_INTERVAL': 300, 'CONCURRENT_REQS': 4,
'STORE_REDUNDANCY': 3, 'RETRIEVE_VALUES': -10000,
'MAX_FAILURES': 3,
from twisted.python import log
from khash import intify
+from ktable import K
from util import uncompact
class ActionBase:
This implementation is suitable for a recurring search over all nodes.
"""
self.sortNodes()
- return self.sorted_nodes[:self.config['K']]
+ return self.sorted_nodes[:K]
def generateArgs(self, node):
"""Generate the arguments to the node's action.
def generateResult(self):
"""Result is the K closest nodes to the target."""
self.sortNodes()
- return (self.sorted_nodes[:self.config['K']], )
+ return (self.sorted_nodes[:K], )
class FindValue(ActionBase):
## Copyright 2002-2003 Andrew Loewenstern, All Rights Reserved
# see LICENSE.txt for license information
-"""Functions to deal with hashes (node IDs and keys)."""
+"""Functions to deal with hashes (node IDs and keys).
+
+@var HASH_LENGTH: the length of the hash to use in bytes
+"""
from sha import sha
from os import urandom
from twisted.trial import unittest
+HASH_LENGTH = 20
+
def intify(hstr):
"""Convert a hash (big-endian) to a long python integer."""
- assert len(hstr) == 20
+ assert len(hstr) == HASH_LENGTH
return long(hstr.encode('hex'), 16)
def stringify(num):
if len(str) % 2 != 0:
str = '0' + str
str = str.decode('hex')
- return (20 - len(str)) *'\x00' + str
+ return (HASH_LENGTH - len(str)) *'\x00' + str
def distance(a, b):
"""Calculate the distance between two hashes expressed as strings."""
def newID():
"""Get a new pseudorandom globally unique hash string."""
h = sha()
- h.update(urandom(20))
+ h.update(urandom(HASH_LENGTH))
return h.digest()
def newIDInRange(min, max):
class TestNewID(unittest.TestCase):
"""Test the newID function."""
def testLength(self):
- self.failUnlessEqual(len(newID()), 20)
+ self.failUnlessEqual(len(newID()), HASH_LENGTH)
def testHundreds(self):
for x in xrange(100):
self.testLength
class TestIntify(unittest.TestCase):
"""Test the intify function."""
- known = [('\0' * 20, 0),
- ('\xff' * 20, 2L**160 - 1),
+ known = [('\0' * HASH_LENGTH, 0),
+ ('\xff' * HASH_LENGTH, 2L**(HASH_LENGTH*8) - 1),
]
def testKnown(self):
for str, value in self.known:
class TestDisantance(unittest.TestCase):
"""Test the distance function."""
known = [
- (("\0" * 20, "\xff" * 20), 2**160L -1),
+ (("\0" * HASH_LENGTH, "\xff" * HASH_LENGTH), 2L**(HASH_LENGTH*8) -1),
((sha("foo").digest(), sha("foo").digest()), 0),
((sha("bar").digest(), sha("bar").digest()), 0)
]
self.node = self._loadSelfNode('', self.port)
self.table = KTable(self.node, config)
self.token_secrets = [newID()]
- self.stats = StatsLogger(self.table, self.store, self.config)
+ self.stats = StatsLogger(self.table, self.store)
# Start listening
self.udp = krpc.hostbroker(self, self.stats, config)
class SimpleTests(unittest.TestCase):
timeout = 10
- DHT_DEFAULTS = {'PORT': 9977, 'K': 8, 'HASH_LENGTH': 160,
+ DHT_DEFAULTS = {'PORT': 9977,
'CHECKPOINT_INTERVAL': 300, 'CONCURRENT_REQS': 4,
'STORE_REDUNDANCY': 3, 'RETRIEVE_VALUES': -10000,
'MAX_FAILURES': 3,
timeout = 30
num = 20
- DHT_DEFAULTS = {'PORT': 9977, 'K': 8, 'HASH_LENGTH': 160,
+ DHT_DEFAULTS = {'PORT': 9977,
'CHECKPOINT_INTERVAL': 300, 'CONCURRENT_REQS': 4,
'STORE_REDUNDANCY': 3, 'RETRIEVE_VALUES': -10000,
'MAX_FAILURES': 3,
def make(port):
from stats import StatsLogger
af = Receiver()
- a = hostbroker(af, StatsLogger(None, None, {}), {'SPEW': False})
+ a = hostbroker(af, StatsLogger(None, None), {'SPEW': False})
a.protocol = KRPC
p = reactor.listenUDP(port, a)
return af, a, p
## Copyright 2002-2003 Andrew Loewenstern, All Rights Reserved
# see LICENSE.txt for license information
-"""The routing table and buckets for a kademlia-like DHT."""
+"""The routing table and buckets for a kademlia-like DHT.
+
+@var K: the Kademlia "K" constant, this should be an even number
+"""
from datetime import datetime
from bisect import bisect_left
import khash
from node import Node, NULL_ID
+K = 8
+
class KTable:
"""Local routing table for a kademlia-like distributed hash table.
assert node.id != NULL_ID
self.node = node
self.config = config
- self.buckets = [KBucket([], 0L, 2L**self.config['HASH_LENGTH'])]
+ self.buckets = [KBucket([], 0L, 2L**(khash.HASH_LENGTH*8))]
def _bucketIndexForInt(self, num):
"""Find the index of the bucket that should hold the node's ID number."""
nodes = list(self.buckets[i].l)
# Make sure we have enough
- if len(nodes) < self.config['K']:
+ if len(nodes) < K:
# Look in adjoining buckets for nodes
min = i - 1
max = i + 1
- while len(nodes) < self.config['K'] and (min >= 0 or max < len(self.buckets)):
+ while len(nodes) < K and (min >= 0 or max < len(self.buckets)):
# Add the adjoining buckets' nodes to the list
if min >= 0:
nodes = nodes + self.buckets[min].l
# Sort the found nodes by proximity to the id and return the closest K
nodes.sort(lambda a, b, num=num: cmp(num ^ a.num, num ^ b.num))
- return nodes[:self.config['K']]
+ return nodes[:K]
def _splitBucket(self, a):
"""Split a bucket in two.
otherBucket = i+1
# Decide if we should do a merge
- if otherBucket is not None and len(self.buckets[i].l) + len(self.buckets[otherBucket].l) <= self.config['K']:
+ if otherBucket is not None and len(self.buckets[i].l) + len(self.buckets[otherBucket].l) <= K:
# Remove one bucket and set the other to cover its range as well
b = self.buckets[i]
a = self.buckets.pop(otherBucket)
removed = True
# Insert the new node
- if new and self._bucketIndexForInt(new.num) == i and len(self.buckets[i].l) < self.config['K']:
+ if new and self._bucketIndexForInt(new.num) == i and len(self.buckets[i].l) < K:
self.buckets[i].l.append(new)
elif removed:
self._mergeBucket(i)
return
# We don't have this node, check to see if the bucket is full
- if len(self.buckets[i].l) < self.config['K']:
+ if len(self.buckets[i].l) < K:
# Not full, append this node and return
if contacted:
node.updateLastSeen()
return self.buckets[i].l[0]
# Make sure our table isn't FULL, this is really unlikely
- if len(self.buckets) >= self.config['HASH_LENGTH']:
+ if len(self.buckets) >= (khash.HASH_LENGTH*8):
log.err("Hash Table is FULL! Increase K!")
return
def setUp(self):
self.a = Node(khash.newID(), '127.0.0.1', 2002)
- self.t = KTable(self.a, {'HASH_LENGTH': 160, 'K': 8, 'MAX_FAILURES': 3})
+ self.t = KTable(self.a, {'MAX_FAILURES': 3})
def testAddNode(self):
self.b = Node(khash.newID(), '127.0.0.1', 2003)
from util import compact
# magic id to use before we know a peer's id
-NULL_ID = 20 * '\0'
+NULL_ID = khash.HASH_LENGTH * '\0'
class Node:
"""Encapsulate a node's contact info.
from datetime import datetime, timedelta
from StringIO import StringIO
+from ktable import K
from util import byte_format
class StatsLogger:
"""Store the statistics for the Khashmir DHT.
- @type config: C{dictionary}
- @ivar config: the configuration parameters for the DHT
@ivar startTime: the time the program was started
@ivar reachable: whether we can be contacted by other nodes
@type table: L{ktable.KTable}
generated an error
"""
- def __init__(self, table, store, config):
+ def __init__(self, table, store):
"""Initialize the statistics.
@type table: L{ktable.KTable}
@param table: the routing table for the DHT
@type store: L{db.DB}
@param store: the database for the DHT
- @type config: C{dictionary}
- @param config: the configuration parameters for the DHT
"""
# General
- self.config = config
self.startTime = datetime.now().replace(microsecond=0)
self.reachable = False
if datetime.now() - self.lastTableUpdate > timedelta(seconds = 15):
self.lastTableUpdate = datetime.now()
self.nodes = reduce(lambda a, b: a + len(b.l), self.table.buckets, 0)
- self.users = self.config['K'] * (2**(len(self.table.buckets) - 1))
+ self.users = K * (2**(len(self.table.buckets) - 1))
return (self.nodes, self.users)
def dbStats(self):
from twisted.trial import unittest
+from khash import HASH_LENGTH
+
def bucket_stats(l):
"""Given a list of khashmir instances, finds min, max, and average number of nodes in tables."""
max = avg = 0
@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):
+ if (len(s) != HASH_LENGTH+6):
raise ValueError
- id = s[:20]
- host = '.'.join([str(ord(i)) for i in s[20:24]])
- port = (ord(s[24]) << 8) | ord(s[25])
+ id = s[:HASH_LENGTH]
+ host = '.'.join([str(ord(i)) for i in s[HASH_LENGTH:(HASH_LENGTH+4)]])
+ port = (ord(s[HASH_LENGTH+4]) << 8) | ord(s[HASH_LENGTH+5])
return {'id': id, 'host': host, 'port': port}
def compact(id, host, port):
(Default is false)</para>
</listitem>
</varlistentry>
- <varlistentry>
- <term><option>K = <replaceable>number</replaceable></option></term>
- <listitem>
- <para>The <replaceable>number</replaceable> of the Kademlia "K" constant.
- It should be an even number.
- (Default is 8.)</para>
- </listitem>
- </varlistentry>
- <varlistentry>
- <term><option>HASH_LENGTH = <replaceable>number</replaceable></option></term>
- <listitem>
- <para>The <replaceable>number</replaceable> of bits in the hash to use.
- (Default is 160.)</para>
- </listitem>
- </varlistentry>
<varlistentry>
<term><option>CHECKPOINT_INTERVAL = <replaceable>time</replaceable></option></term>
<listitem>
# for everybody to download
# OTHER_DIRS =
-# User name to try and run as
-# USERNAME =
-
# Whether it's OK to use an IP addres from a known local/private range
LOCAL_OK = yes
# whether this node is a bootstrap node
BOOTSTRAP_NODE = %(BOOTSTRAP_NODE)s
-# Kademlia "K" constant, this should be an even number
-K = 8
-
-# SHA1 is 160 bits long
-HASH_LENGTH = 160
-
# checkpoint every this many seconds
CHECKPOINT_INTERVAL = 5m
projects / quix0rs-apt-p2p.git / commitdiff