Changeset f6d2ac7


Ignore:
Timestamp:
Aug 24, 2011 2:25:58 PM (9 years ago)
Author:
zzz <zzz@…>
Branches:
master
Children:
546b668
Parents:
f22865a
Message:
  • Blockfile DB: Add reverse lookup table; bump DB rev to 2
Location:
core/java/src/net/i2p/client/naming
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • core/java/src/net/i2p/client/naming/BlockfileNamingService.java

    rf22865a rf6d2ac7  
    3737import net.metanotion.io.Serializer;
    3838import net.metanotion.io.block.BlockFile;
     39import net.metanotion.io.data.IntBytes;
    3940import net.metanotion.io.data.UTF8StringBytes;
    4041import net.metanotion.util.skiplist.SkipIterator;
     
    5051 * "%%__INFO__%%" is the master database skiplist, containing one entry:
    5152 *     "info": a Properties, serialized with DataHelper functions:
    52  *             "version": "1"
     53 *             "version": "2"
    5354 *             "created": Java long time (ms)
     55 *             "upgraded": Java long time (ms) (as of database version 2)
    5456 *             "lists":   Comma-separated list of host databases, to be
    5557 *                        searched in-order for lookups
    5658 *
     59 * "%%__REVERSE__%%" is the reverse lookup skiplist
     60 *     (as of database version 2):
     61 *     The skiplist keys are Integers, the first 4 bytes of the hash of the dest.
     62 *     The skiplist values are Properties.
     63 *         There may be multiple entries in the properties, each one is a reverse mapping,
     64 *            as there may be more than one hostname for a given destination,
     65 *            or there could be collisions with the same first 4 bytes of the hash.
     66 *         Each property key is a hostname.
     67 *         Each property value is the empty string.
    5768 *
    5869 * For each host database, there is a skiplist containing
     
    8394    private volatile boolean _isClosed;
    8495    private final boolean _readOnly;
     96    private boolean _needsUpgrade;
    8597
    8698    private static final Serializer _infoSerializer = new PropertiesSerializer();
    8799    private static final Serializer _stringSerializer = new UTF8StringBytes();
    88100    private static final Serializer _destSerializer = new DestEntrySerializer();
     101    private static final Serializer _hashIndexSerializer = new IntBytes();
    89102
    90103    private static final String HOSTS_DB = "hostsdb.blockfile";
     
    93106
    94107    private static final String INFO_SKIPLIST = "%%__INFO__%%";
     108    private static final String REVERSE_SKIPLIST = "%%__REVERSE__%%";
    95109    private static final String PROP_INFO = "info";
    96110    private static final String PROP_VERSION = "version";
    97111    private static final String PROP_LISTS = "lists";
    98112    private static final String PROP_CREATED = "created";
    99     private static final String PROP_MODIFIED = "modified";
    100     private static final String VERSION = "1";
     113    private static final String PROP_UPGRADED = "upgraded";
     114    private static final String VERSION = "2";
     115    private static final String OLD_VERSION = "1";
    101116
    102117    private static final String PROP_ADDED = "a";
     
    174189        _raf = raf;
    175190        _readOnly = readOnly;
     191        if (_needsUpgrade)
     192            upgrade();
    176193        _context.addShutdownTask(new Shutdown());
    177194    }
     
    194211            info.setProperty(PROP_LISTS, list);
    195212            hdr.put(PROP_INFO, info);
     213            rv.makeIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
    196214
    197215            int total = 0;
     
    222240                        if (d != null) {
    223241                            addEntry(rv, hostsfile, key, d, sourceMsg);
     242                            addReverseEntry(rv, key, d, _log);
    224243                            count++;
    225244                        } else {
     
    262281            if (info == null)
    263282                throw new IOException("No header info");
    264             String version = info.getProperty(PROP_VERSION);
    265             if (!VERSION.equals(version))
    266                 throw new IOException("Bad db version: " + version);
    267283
    268284            String list = info.getProperty(PROP_LISTS);
     
    276292                } catch (NumberFormatException nfe) {}
    277293            }
    278             if (_log.shouldLog(Log.INFO))
    279                 _log.info("Found database version " + version + " created " + (new Date(createdOn)).toString() +
    280                           " containing lists: " + list);
     294
     295            String version = info.getProperty(PROP_VERSION);
     296            _needsUpgrade = needsUpgrade(bf, version);
     297            if (_needsUpgrade) {
     298                if (_log.shouldLog(Log.WARN))
     299                    _log.warn("Upgrading from database version " + version + " to " + VERSION +
     300                              " created " + (new Date(createdOn)).toString() +
     301                              " containing lists: " + list);
     302            } else {
     303                if (_log.shouldLog(Log.INFO))
     304                    _log.info("Found database version " + version +
     305                              " created " + (new Date(createdOn)).toString() +
     306                              " containing lists: " + list);
     307            }
    281308
    282309            List<String> skiplists = getFilenames(list);
     
    284311                skiplists.add(FALLBACK_LIST);
    285312            _lists.addAll(skiplists);
     313
    286314            if (_log.shouldLog(Log.INFO))
    287315                _log.info("DB init took " + DataHelper.formatDuration(_context.clock().now() - start));
     
    291319            throw new IOException(e.toString());
    292320        }
     321    }
     322
     323    /**
     324     *  @return true if needs an upgrade
     325     *  @throws IOE on bad version
     326     *  @since 0.8.9
     327     */
     328    private boolean needsUpgrade(BlockFile bf, String version) throws IOException {
     329        if (VERSION.equals(version))
     330            return false;
     331        if (!OLD_VERSION.equals(version))
     332            throw new IOException("Bad db version: " + version);
     333        if (!bf.file.canWrite()) {
     334            if (_log.shouldLog(Log.WARN))
     335                _log.warn("Not upgrading read-only database version " + version);
     336            return false;
     337        }
     338        return true;
     339    }
     340
     341    /**
     342     *  Blockfile must be writable of course.
     343     *  @return true if upgraded successfully
     344     *  @since 0.8.9
     345     */
     346    private boolean upgrade() {
     347        try {
     348            // shouldn't ever be there...
     349            SkipList rev = _bf.getIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
     350            if (rev == null)
     351                rev = _bf.makeIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
     352            Map<String, Destination> entries = getEntries();
     353            long start = System.currentTimeMillis();
     354            int i = 0;
     355            for (Map.Entry<String, Destination> entry : entries.entrySet()) {
     356                 addReverseEntry(entry.getKey(), entry.getValue());
     357                 i++;
     358            }
     359            if (_log.shouldLog(Log.WARN))
     360                _log.warn("Created reverse index with " + i + " entries");
     361            SkipList hdr = _bf.getIndex(INFO_SKIPLIST, _stringSerializer, _infoSerializer);
     362            if (hdr == null)
     363                throw new IOException("No db header");
     364            Properties info = (Properties) hdr.get(PROP_INFO);
     365            if (info == null)
     366                throw new IOException("No header info");
     367            info.setProperty(PROP_VERSION, VERSION);
     368            info.setProperty(PROP_UPGRADED, Long.toString(_context.clock().now()));
     369            hdr.put(PROP_INFO, info);
     370            if (_log.shouldLog(Log.WARN))
     371                _log.warn("Upgraded to version " + VERSION + " in " +
     372                          DataHelper.formatDuration(System.currentTimeMillis() - start));
     373            return true;
     374        } catch (IOException ioe) {
     375            _log.error("Error upgrading DB", ioe);
     376        } catch (RuntimeException e) {
     377            _log.error("Error upgrading DB", e);
     378        }
     379        return false;
    293380    }
    294381
     
    381468    private static Object removeEntry(SkipList sl, String key) {
    382469        return sl.remove(key);
     470    }
     471
     472    ///// Reverse index methods
     473
     474    /**
     475     *  Caller must synchronize.
     476     *  @return null without exception on error (logs only)
     477     *  @since 0.8.9
     478     */
     479    private String getReverseEntry(Destination dest) {
     480        return getReverseEntry(dest.calculateHash());
     481    }
     482
     483    /**
     484     *  Caller must synchronize.
     485     *  Returns null without exception on error (logs only).
     486     *  Returns without logging if no reverse skiplist (version 1).
     487     *
     488     *  @return the first one found if more than one
     489     *  @since 0.8.9
     490     */
     491    private String getReverseEntry(Hash hash) {
     492        try {
     493            SkipList rev = _bf.getIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
     494            if (rev == null)
     495                return null;
     496            Integer idx = getReverseKey(hash);
     497            //_log.info("Get reverse " + idx + ' ' + hash);
     498            Properties props = (Properties) rev.get(idx);
     499            if (props == null)
     500                return null;
     501            for (Object okey : props.keySet()) {
     502                String key = (String) okey;
     503                // now do the forward lookup to verify (using the cache)
     504                Destination d = lookup(key);
     505                if (d != null && d.calculateHash().equals(hash))
     506                    return key;
     507            }
     508        } catch (IOException ioe) {
     509            _log.error("DB get reverse error", ioe);
     510        } catch (RuntimeException e) {
     511            _log.error("DB get reverse error", e);
     512        }
     513        return null;
     514    }
     515
     516    /**
     517     *  Caller must synchronize.
     518     *  Fails without exception on error (logs only)
     519     *  @since 0.8.9
     520     */
     521    private void addReverseEntry(String key, Destination dest) {
     522        addReverseEntry(_bf, key, dest, _log);
     523    }
     524
     525    /**
     526     *  Caller must synchronize.
     527     *  Fails without exception on error (logs only).
     528     *  Returns without logging if no reverse skiplist (version 1).
     529     *
     530     *  We store one or more hostnames for a given hash.
     531     *  The skiplist key is a signed Integer, the first 4 bytes of the dest hash.
     532     *  For convenience (since we have a serializer already) we use
     533     *  a Properties as the value, with a null string as the value for each hostname property.
     534     *  We could in the future use the property value for something.
     535     *  @since 0.8.9
     536     */
     537    private static void addReverseEntry(BlockFile bf, String key, Destination dest, Log log) {
     538        //log.info("Add reverse " + key);
     539        try {
     540            SkipList rev = bf.getIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
     541            if (rev == null)
     542                return;
     543            Integer idx = getReverseKey(dest);
     544            Properties props = (Properties) rev.get(idx);
     545            if (props != null) {
     546                if (props.getProperty(key) != null)
     547                    return;
     548            } else {
     549                props = new Properties();
     550            }
     551            props.put(key, "");
     552            rev.put(idx, props);
     553        } catch (IOException ioe) {
     554            log.error("DB add reverse error", ioe);
     555        } catch (RuntimeException e) {
     556            log.error("DB add reverse error", e);
     557        }
     558    }
     559
     560    /**
     561     *  Caller must synchronize.
     562     *  Fails without exception on error (logs only)
     563     *  @since 0.8.9
     564     */
     565    private void removeReverseEntry(String key, Destination dest) {
     566        //_log.info("Remove reverse " + key);
     567        try {
     568            SkipList rev = _bf.getIndex(REVERSE_SKIPLIST, _hashIndexSerializer, _infoSerializer);
     569            if (rev == null)
     570                return;
     571            Integer idx = getReverseKey(dest);
     572            Properties props = (Properties) rev.get(idx);
     573            if (props == null || props.remove(key) == null)
     574                return;
     575            if (props.isEmpty())
     576                rev.remove(idx);
     577            else
     578                rev.put(idx, props);
     579        } catch (IOException ioe) {
     580            _log.error("DB remove reverse error", ioe);
     581        } catch (RuntimeException e) {
     582            _log.error("DB remove reverse error", e);
     583        }
     584    }
     585
     586    /**
     587     *  @since 0.8.9
     588     */
     589    private static Integer getReverseKey(Destination dest) {
     590        return getReverseKey(dest.calculateHash());       
     591    }
     592
     593    /**
     594     *  @since 0.8.9
     595     */
     596    private static Integer getReverseKey(Hash hash) {
     597        byte[] hashBytes = hash.getData();       
     598        int i = (int) DataHelper.fromLong(hashBytes, 0, 4);
     599        return Integer.valueOf(i);
    383600    }
    384601
     
    484701                        return false;
    485702                addEntry(sl, key, d, props);
    486                 if (changed)
     703                if (changed) {
    487704                    removeCache(hostname);
     705                    addReverseEntry(key, d);
     706                }
    488707                for (NamingServiceListener nsl : _listeners) {
    489708                    if (changed)
     
    528747                if (sl == null)
    529748                    return false;
    530                 boolean rv = removeEntry(sl, key) != null;
     749                Object removed = removeEntry(sl, key);
     750                boolean rv = removed != null;
    531751                if (rv) {
    532752                    removeCache(hostname);
     753                    try {
     754                        removeReverseEntry(key, ((DestEntry)removed).dest);
     755                    } catch (ClassCastException cce) {
     756                        _log.error("DB reverse remove error", cce);
     757                    }
    533758                    for (NamingServiceListener nsl : _listeners) {
    534759                        nsl.entryRemoved(this, key);
     
    644869
    645870    /**
     871     * @param options ignored
     872     * @since 0.8.9
     873     */
     874    @Override
     875    public String reverseLookup(Destination d, Properties options) {
     876        return reverseLookup(d.calculateHash());
     877    }
     878
     879    /**
     880     * @since 0.8.9
     881     */
     882    @Override
     883    public String reverseLookup(Hash h) {
     884        synchronized(_bf) {
     885            if (_isClosed)
     886                return null;
     887            return getReverseEntry(h);
     888        }
     889    }
     890
     891    /**
    646892     * @param options If non-null and contains the key "list", return the
    647893     *                size of that list (default "hosts.txt", NOT all lists)
     
    9411187        int found = 0;
    9421188        int notfound = 0;
     1189        int rfound = 0;
     1190        int rnotfound = 0;
    9431191        long start = System.currentTimeMillis();
    9441192        for (String name : names) {
    9451193             Destination dest = bns.lookup(name);
    946              if (dest != null)
     1194             if (dest != null) {
    9471195                 found++;
    948              else
     1196                 String reverse = bns.reverseLookup(dest);
     1197                 if (reverse != null)
     1198                     rfound++;
     1199                 else
     1200                     rnotfound++;
     1201             } else {
    9491202                 notfound++;
     1203             }
    9501204        }
    9511205        System.out.println("BFNS took " + DataHelper.formatDuration(System.currentTimeMillis() - start));
    9521206        System.out.println("found " + found + " notfound " + notfound);
     1207        System.out.println("reverse found " + rfound + " notfound " + rnotfound);
     1208
     1209        //if (true) return;
    9531210
    9541211        System.out.println("Removing all " + names.size() + " hostnames");
  • core/java/src/net/i2p/client/naming/NamingService.java

    rf22865a rf6d2ac7  
    6262
    6363    /**
    64      * Reverse look up a destination
     64     * Reverse lookup a destination
     65     * @param dest non-null
    6566     * @return a host name for this Destination, or <code>null</code>
    6667     * if none is known. It is safe for subclasses to always return
     
    7172    }
    7273
    73     /** @deprecated unused */
     74    /**
     75     * Reverse lookup a hash
     76     * @param h non-null
     77     * @return a host name for this hash, or <code>null</code>
     78     * if none is known. It is safe for subclasses to always return
     79     * <code>null</code> if no reverse lookup is possible.
     80     */
    7481    public String reverseLookup(Hash h) { return null; }
    7582
     
    371378    /**
    372379     *  Same as reverseLookup(dest) but with options
     380     *  @param d non-null
    373381     *  @param options NamingService-specific, can be null
    374382     *  @return host name or null
Note: See TracChangeset for help on using the changeset viewer.