Changeset f73b3e5


Ignore:
Timestamp:
Oct 16, 2009 1:50:06 PM (11 years ago)
Author:
zzz <zzz@…>
Branches:
master
Children:
b701336, e21a172e
Parents:
fa6d17a
Message:
  • NetDb?: Rework part 1 of N:
    • Flood only to those closest to the key
    • Java 5 fixups
Location:
router/java/src/net/i2p/router/networkdb/kademlia
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • router/java/src/net/i2p/router/networkdb/kademlia/FloodfillNetworkDatabaseFacade.java

    rfa6d17a rf73b3e5  
    9595    }
    9696
     97    private static final int MAX_TO_FLOOD = 9;
     98
     99    /**
     100     *  Send to a subset of all floodfill peers.
     101     *  We do this to implement Kademlia within the floodfills, i.e.
     102     *  we flood to those closest to the key.
     103     */
    97104    public void flood(DataStructure ds) {
     105        Hash key;
     106        if (ds instanceof LeaseSet)
     107            key = ((LeaseSet)ds).getDestination().calculateHash();
     108        else
     109            key = ((RouterInfo)ds).getIdentity().calculateHash();
     110        Hash rkey = _context.routingKeyGenerator().getRoutingKey(key);
    98111        FloodfillPeerSelector sel = (FloodfillPeerSelector)getPeerSelector();
    99         List peers = sel.selectFloodfillParticipants(getKBuckets());
     112        List peers = sel.selectFloodfillParticipants(rkey, MAX_TO_FLOOD, getKBuckets());
    100113        int flooded = 0;
    101114        for (int i = 0; i < peers.size(); i++) {
     
    108121            DatabaseStoreMessage msg = new DatabaseStoreMessage(_context);
    109122            if (ds instanceof LeaseSet) {
    110                 msg.setKey(((LeaseSet)ds).getDestination().calculateHash());
    111123                msg.setLeaseSet((LeaseSet)ds);
    112124            } else {
    113                 msg.setKey(((RouterInfo)ds).getIdentity().calculateHash());
    114125                msg.setRouterInfo((RouterInfo)ds);
    115126            }
     127            msg.setKey(key);
    116128            msg.setReplyGateway(null);
    117129            msg.setReplyToken(0);
     
    126138            flooded++;
    127139            if (_log.shouldLog(Log.INFO))
    128                 _log.info("Flooding the entry for " + msg.getKey().toBase64() + " to " + peer.toBase64());
     140                _log.info("Flooding the entry for " + key.toBase64() + " to " + peer.toBase64());
    129141        }
    130142       
    131143        if (_log.shouldLog(Log.INFO))
    132             _log.info("Flooded the to " + flooded + " peers");
     144            _log.info("Flooded the data to " + flooded + " of " + peers.size() + " peers");
    133145    }
    134146
  • router/java/src/net/i2p/router/networkdb/kademlia/FloodfillPeerSelector.java

    rfa6d17a rf73b3e5  
    3333     */
    3434    @Override
    35     public List selectMostReliablePeers(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets) {
     35    public List<Hash> selectMostReliablePeers(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets) {
    3636        return selectNearestExplicitThin(key, maxNumRouters, peersToIgnore, kbuckets, true);
    3737    }
    3838
    3939    @Override
    40     public List selectNearestExplicitThin(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets) {
     40    public List<Hash> selectNearestExplicitThin(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets) {
    4141        return selectNearestExplicitThin(key, maxNumRouters, peersToIgnore, kbuckets, false);
    4242    }
    4343
    44     public List selectNearestExplicitThin(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets, boolean preferConnected) {
     44    public List<Hash> selectNearestExplicitThin(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets, boolean preferConnected) {
    4545        if (peersToIgnore == null)
    4646            peersToIgnore = new HashSet(1);
     
    5757    }
    5858   
    59     /** Returned list will not include our own hash */
    60     public List selectFloodfillParticipants(KBucketSet kbuckets) {
     59    /**
     60     *  @return all floodfills not shitlisted forever. list will not include our own hash
     61     *
     62     */
     63    public List<Hash> selectFloodfillParticipants(KBucketSet kbuckets) {
    6164        if (kbuckets == null) return new ArrayList();
    6265        FloodfillSelectionCollector matches = new FloodfillSelectionCollector(null, null, 0);
     
    6568    }
    6669   
     70    /**
     71     *  @return all floodfills not shitlisted foreverx
     72     *  @param maxNumRouters max to return
     73     *  Sorted by closest to the key if > maxNumRouters, otherwise not
     74     */
     75    public List<Hash> selectFloodfillParticipants(Hash key, int maxNumRouters, KBucketSet kbuckets) {
     76        List<Hash> ffs = selectFloodfillParticipants(kbuckets);
     77        if (ffs.size() <= maxNumRouters)
     78            return ffs; // unsorted
     79        TreeMap<BigInteger, Hash> sorted = new TreeMap();
     80        for (int i = 0; i < ffs.size(); i++) {
     81            Hash h = ffs.get(i);
     82            BigInteger diff = getDistance(key, h);
     83            sorted.put(diff, h);
     84        }
     85        List<Hash> rv = new ArrayList(maxNumRouters);
     86        for (int i = 0; i < maxNumRouters; i++) {
     87            rv.add(sorted.remove(sorted.firstKey()));
     88        }
     89        return rv;
     90    }
     91   
    6792    private class FloodfillSelectionCollector implements SelectionCollector {
    68         private TreeMap _sorted;
    69         private List _floodfillMatches;
     93        private TreeMap<BigInteger, Hash> _sorted;
     94        private List<Hash> _floodfillMatches;
    7095        private Hash _key;
    71         private Set _toIgnore;
     96        private Set<Hash> _toIgnore;
    7297        private int _matches;
    7398        private int _wanted;
    74         public FloodfillSelectionCollector(Hash key, Set toIgnore, int wanted) {
     99        public FloodfillSelectionCollector(Hash key, Set<Hash> toIgnore, int wanted) {
    75100            _key = key;
    76101            _sorted = new TreeMap();
    77             _floodfillMatches = new ArrayList(1);
     102            _floodfillMatches = new ArrayList(8);
    78103            _toIgnore = toIgnore;
    79104            _matches = 0;
    80105            _wanted = wanted;
    81106        }
    82         public List getFloodfillParticipants() { return _floodfillMatches; }
     107        public List<Hash> getFloodfillParticipants() { return _floodfillMatches; }
    83108        private static final int EXTRA_MATCHES = 100;
    84109        public void add(Hash entry) {
     
    116141        }
    117142        /** get the first $howMany entries matching */
    118         public List get(int howMany) {
     143        public List<Hash> get(int howMany) {
    119144            return get(howMany, false);
    120145        }
    121146
    122         public List get(int howMany, boolean preferConnected) {
     147        public List<Hash> get(int howMany, boolean preferConnected) {
    123148            Collections.shuffle(_floodfillMatches, _context.random());
    124             List rv = new ArrayList(howMany);
    125             List badff = new ArrayList(howMany);
    126             List unconnectedff = new ArrayList(howMany);
     149            List<Hash> rv = new ArrayList(howMany);
     150            List<Hash> badff = new ArrayList(howMany);
     151            List<Hash> unconnectedff = new ArrayList(howMany);
    127152            int found = 0;
    128153            long now = _context.clock().now();
  • router/java/src/net/i2p/router/networkdb/kademlia/FloodfillStoreJob.java

    rfa6d17a rf73b3e5  
    1818import net.i2p.router.RouterContext;
    1919
     20/**
     21 *  This extends StoreJob to fire off a FloodfillVerifyStoreJob after success.
     22 *
     23 */
    2024class FloodfillStoreJob extends StoreJob {   
    2125    private FloodfillNetworkDatabaseFacade _facade;
    2226    /**
    23      * Create a new search for the routingKey specified
     27     * Send a data structure to the floodfills
    2428     *
    2529     */
     
    3236     *               already know they have it).  This can be null.
    3337     */
    34     public FloodfillStoreJob(RouterContext context, FloodfillNetworkDatabaseFacade facade, Hash key, DataStructure data, Job onSuccess, Job onFailure, long timeoutMs, Set toSkip) {
     38    public FloodfillStoreJob(RouterContext context, FloodfillNetworkDatabaseFacade facade, Hash key, DataStructure data, Job onSuccess, Job onFailure, long timeoutMs, Set<Hash> toSkip) {
    3539        super(context, facade, key, data, onSuccess, onFailure, timeoutMs, toSkip);
    3640        _facade = facade;
  • router/java/src/net/i2p/router/networkdb/kademlia/PeerSelector.java

    rfa6d17a rf73b3e5  
    4444     */
    4545    /* FIXME Exporting non-public type through public API FIXME */
    46     public List selectMostReliablePeers(Hash key, int numClosest, Set alreadyChecked, KBucketSet kbuckets) {// LINT -- Exporting non-public type through public API
     46    public List<Hash> selectMostReliablePeers(Hash key, int numClosest, Set<Hash> alreadyChecked, KBucketSet kbuckets) {// LINT -- Exporting non-public type through public API
    4747        // get the peers closest to the key
    48         List nearest = selectNearestExplicit(key, numClosest, alreadyChecked, kbuckets);
    49         return nearest;
     48        return selectNearestExplicit(key, numClosest, alreadyChecked, kbuckets);
    5049    }
    5150   
     
    5857     */
    5958    /* FIXME Exporting non-public type through public API FIXME */
    60     public List selectNearestExplicit(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets) {// LINT -- Exporting non-public type through public API
    61         if (true)
     59    public List<Hash> selectNearestExplicit(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets) {// LINT -- Exporting non-public type through public API
     60        //if (true)
    6261            return selectNearestExplicitThin(key, maxNumRouters, peersToIgnore, kbuckets);
    6362       
     63/******
    6464        if (peersToIgnore == null)
    6565            peersToIgnore = new HashSet(1);
     
    8585                       + allHashes.size() + "]");
    8686        return peerHashes;
     87******/
    8788    }
    8889   
     
    9596     */
    9697    /* FIXME Exporting non-public type through public API FIXME */
    97     public List selectNearestExplicitThin(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets) { // LINT -- Exporting non-public type through public API
     98    public List<Hash> selectNearestExplicitThin(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets) { // LINT -- Exporting non-public type through public API
    9899        if (peersToIgnore == null)
    99100            peersToIgnore = new HashSet(1);
     
    110111   
    111112    private class MatchSelectionCollector implements SelectionCollector {
    112         private TreeMap _sorted;
     113        private TreeMap<BigInteger, Hash> _sorted;
    113114        private Hash _key;
    114         private Set _toIgnore;
     115        private Set<Hash> _toIgnore;
    115116        private int _matches;
    116         public MatchSelectionCollector(Hash key, Set toIgnore) {
     117        public MatchSelectionCollector(Hash key, Set<Hash> toIgnore) {
    117118            _key = key;
    118119            _sorted = new TreeMap();
     
    136137        }
    137138        /** get the first $howMany entries matching */
    138         public List get(int howMany) {
    139             List rv = new ArrayList(howMany);
     139        public List<Hash> get(int howMany) {
     140            List<Hash> rv = new ArrayList(howMany);
    140141            for (int i = 0; i < howMany; i++) {
    141142                if (_sorted.size() <= 0)
     
    152153     *
    153154     */
     155/********
    154156    private void removeFailingPeers(Set peerHashes) {
    155157        List failing = null;
     
    185187            peerHashes.removeAll(failing);
    186188    }
     189**********/
    187190   
    188191    public static BigInteger getDistance(Hash targetKey, Hash routerInQuestion) {
     
    200203     */
    201204    /* FIXME Exporting non-public type through public API FIXME */
    202     public List selectNearest(Hash key, int maxNumRouters, Set peersToIgnore, KBucketSet kbuckets) { // LINT -- Exporting non-public type through public API
     205    public List<Hash> selectNearest(Hash key, int maxNumRouters, Set<Hash> peersToIgnore, KBucketSet kbuckets) { // LINT -- Exporting non-public type through public API
    203206        // sure, this may not be exactly correct per kademlia (peers on the border of a kbucket in strict kademlia
    204207        // would behave differently) but I can see no reason to keep around an /additional/ more complicated algorithm.
  • router/java/src/net/i2p/router/networkdb/kademlia/StoreJob.java

    rfa6d17a rf73b3e5  
    5757   
    5858    /**
    59      * Create a new search for the routingKey specified
     59     * Send a data structure to the floodfills
    6060     *
    6161     */
     
    7070     */
    7171    public StoreJob(RouterContext context, KademliaNetworkDatabaseFacade facade, Hash key,
    72                     DataStructure data, Job onSuccess, Job onFailure, long timeoutMs, Set toSkip) {
     72                    DataStructure data, Job onSuccess, Job onFailure, long timeoutMs, Set<Hash> toSkip) {
    7373        super(context);
    7474        _log = context.logManager().getLog(StoreJob.class);
     
    147147        // the network to scale.
    148148        // Perhaps the ultimate solution is to send RouterInfos through a lease also.
    149         List closestHashes;
     149        List<Hash> closestHashes;
    150150        if (_state.getData() instanceof RouterInfo)
    151151            closestHashes = getMostReliableRouters(_state.getTarget(), toCheck, _state.getAttempted());
     
    166166            if (_log.shouldLog(Log.INFO))
    167167                _log.info(getJobId() + ": Continue sending key " + _state.getTarget() + " after " + _state.getAttempted().size() + " tries to " + closestHashes);
    168             for (Iterator iter = closestHashes.iterator(); iter.hasNext(); ) {
    169                 Hash peer = (Hash)iter.next();
     168            for (Iterator<Hash> iter = closestHashes.iterator(); iter.hasNext(); ) {
     169                Hash peer = iter.next();
    170170                DataStructure ds = _facade.getDataStore().get(peer);
    171171                if ( (ds == null) || !(ds instanceof RouterInfo) ) {
     
    216216     * @return ordered list of Hash objects
    217217     */
    218     private List getClosestRouters(Hash key, int numClosest, Set alreadyChecked) {
     218    private List<Hash> getClosestRouters(Hash key, int numClosest, Set<Hash> alreadyChecked) {
    219219        Hash rkey = getContext().routingKeyGenerator().getRoutingKey(key);
    220220        //if (_log.shouldLog(Log.DEBUG))
     
    226226    }
    227227
    228     private List getMostReliableRouters(Hash key, int numClosest, Set alreadyChecked) {
     228    private List<Hash> getMostReliableRouters(Hash key, int numClosest, Set<Hash> alreadyChecked) {
    229229        Hash rkey = getContext().routingKeyGenerator().getRoutingKey(key);
    230230        KBucketSet ks = _facade.getKBuckets();
  • router/java/src/net/i2p/router/networkdb/kademlia/StoreState.java

    rfa6d17a rf73b3e5  
    1616    private Hash _key;
    1717    private DataStructure _data;
    18     private final HashSet _pendingPeers;
    19     private HashMap _pendingPeerTimes;
    20     private final HashSet _successfulPeers;
    21     private final HashSet _successfulExploratoryPeers;
    22     private final HashSet _failedPeers;
    23     private final HashSet _attemptedPeers;
     18    private final HashSet<Hash> _pendingPeers;
     19    private HashMap<Hash, Long> _pendingPeerTimes;
     20    private final HashSet<Hash> _successfulPeers;
     21    private final HashSet<Hash> _successfulExploratoryPeers;
     22    private final HashSet<Hash> _failedPeers;
     23    private final HashSet<Hash> _attemptedPeers;
    2424    private int _completeCount;
    2525    private volatile long _completed;
     
    2929        this(ctx, key, data, null);
    3030    }
    31     public StoreState(RouterContext ctx, Hash key, DataStructure data, Set toSkip) {
     31    public StoreState(RouterContext ctx, Hash key, DataStructure data, Set<Hash> toSkip) {
    3232        _context = ctx;
    3333        _key = key;
     
    4949    public Hash getTarget() { return _key; }
    5050    public DataStructure getData() { return _data; }
    51     public Set getPending() {
    52         synchronized (_pendingPeers) {
    53             return (Set)_pendingPeers.clone();
    54         }
    55     }
    56     public Set getAttempted() {
    57         synchronized (_attemptedPeers) {
    58             return (Set)_attemptedPeers.clone();
    59         }
    60     }
    61     public Set getSuccessful() {
     51    public Set<Hash> getPending() {
     52        synchronized (_pendingPeers) {
     53            return (Set<Hash>)_pendingPeers.clone();
     54        }
     55    }
     56    public Set<Hash> getAttempted() {
     57        synchronized (_attemptedPeers) {
     58            return (Set<Hash>)_attemptedPeers.clone();
     59        }
     60    }
     61    public Set<Hash> getSuccessful() {
    6262        synchronized (_successfulPeers) {
    63             return (Set)_successfulPeers.clone();
    64         }
    65     }
    66     public Set getSuccessfulExploratory() {
     63            return (Set<Hash>)_successfulPeers.clone();
     64        }
     65    }
     66    public Set<Hash> getSuccessfulExploratory() {
    6767        synchronized (_successfulExploratoryPeers) {
    68             return (Set)_successfulExploratoryPeers.clone();
    69         }
    70     }
    71     public Set getFailed() {
     68            return (Set<Hash>)_successfulExploratoryPeers.clone();
     69        }
     70    }
     71    public Set<Hash> getFailed() {
    7272        synchronized (_failedPeers) {
    73             return (Set)_failedPeers.clone();
     73            return (Set<Hash>)_failedPeers.clone();
    7474        }
    7575    }
     
    9393        }
    9494    }
    95     public void addPending(Collection pending) {
     95    public void addPending(Collection<Hash> pending) {
    9696        synchronized (_pendingPeers) {
    9797            _pendingPeers.addAll(pending);
    98             for (Iterator iter = pending.iterator(); iter.hasNext(); )
     98            for (Iterator<Hash> iter = pending.iterator(); iter.hasNext(); )
    9999                _pendingPeerTimes.put(iter.next(), new Long(_context.clock().now()));
    100100        }
     
    114114        synchronized (_pendingPeers) {
    115115            _pendingPeers.remove(peer);
    116             Long when = (Long)_pendingPeerTimes.remove(peer);
     116            Long when = _pendingPeerTimes.remove(peer);
    117117            if (when != null)
    118118                rv = _context.clock().now() - when.longValue();
     
    129129        synchronized (_pendingPeers) {
    130130            _pendingPeers.remove(peer);
    131             Long when = (Long)_pendingPeerTimes.remove(peer);
     131            Long when = _pendingPeerTimes.remove(peer);
    132132            if (when != null)
    133133                rv = _context.clock().now() - when.longValue();
     
    160160        synchronized (_attemptedPeers) {
    161161            buf.append(_attemptedPeers.size()).append(' ');
    162             for (Iterator iter = _attemptedPeers.iterator(); iter.hasNext(); ) {
    163                 Hash peer = (Hash)iter.next();
     162            for (Iterator<Hash> iter = _attemptedPeers.iterator(); iter.hasNext(); ) {
     163                Hash peer = iter.next();
    164164                buf.append(peer.toBase64()).append(" ");
    165165            }
     
    168168        synchronized (_pendingPeers) {
    169169            buf.append(_pendingPeers.size()).append(' ');
    170             for (Iterator iter = _pendingPeers.iterator(); iter.hasNext(); ) {
    171                 Hash peer = (Hash)iter.next();
     170            for (Iterator<Hash> iter = _pendingPeers.iterator(); iter.hasNext(); ) {
     171                Hash peer = iter.next();
    172172                buf.append(peer.toBase64()).append(" ");
    173173            }
     
    176176        synchronized (_failedPeers) {
    177177            buf.append(_failedPeers.size()).append(' ');
    178             for (Iterator iter = _failedPeers.iterator(); iter.hasNext(); ) {
    179                 Hash peer = (Hash)iter.next();
     178            for (Iterator<Hash> iter = _failedPeers.iterator(); iter.hasNext(); ) {
     179                Hash peer = iter.next();
    180180                buf.append(peer.toBase64()).append(" ");
    181181            }
     
    184184        synchronized (_successfulPeers) {
    185185            buf.append(_successfulPeers.size()).append(' ');
    186             for (Iterator iter = _successfulPeers.iterator(); iter.hasNext(); ) {
    187                 Hash peer = (Hash)iter.next();
     186            for (Iterator<Hash> iter = _successfulPeers.iterator(); iter.hasNext(); ) {
     187                Hash peer = iter.next();
    188188                buf.append(peer.toBase64()).append(" ");
    189189            }
     
    192192        synchronized (_successfulExploratoryPeers) {
    193193            buf.append(_successfulExploratoryPeers.size()).append(' ');
    194             for (Iterator iter = _successfulExploratoryPeers.iterator(); iter.hasNext(); ) {
    195                 Hash peer = (Hash)iter.next();
     194            for (Iterator<Hash> iter = _successfulExploratoryPeers.iterator(); iter.hasNext(); ) {
     195                Hash peer = iter.next();
    196196                buf.append(peer.toBase64()).append(" ");
    197197            }
Note: See TracChangeset for help on using the changeset viewer.