8 Replies Latest reply: Mar 19, 2007 8:57 AM by greybird RSS

    INCompressor sometimes seems to confuse Key and Value

    561794
      Hi,

      Sometimes, while inserting some hundred entries into a sorted database with supports sorted duplicates, the INCompressor tries to compare a key with a value, which obviously is no good idea. Is this a known problem? Is there a way to prevent this from happening? If it helps you in resolving this issue, I can try to create a TestCase to reproduce this problem (which might take some time as it does not seem to happen very deterministically). A more technical description of what happens during the error follows below.

      Regards,
      Luzius

      Library Version: Sleepycat Berkeley DB Java Edition 3.2.13
      Database Type: Sorted Keys & Sorted Duplicates

      Stack Trace (INCompressor):
      at com.sleepycat.je.tree.Key.compareKeys(Key.java:104)
      at com.sleepycat.je.tree.IN.findEntry(IN.java:1428)
      at com.sleepycat.je.tree.Tree.searchSubTreeInternal(Tree.java:1854)
      at com.sleepycat.je.tree.Tree.searchSubTree(Tree.java:1750)
      at com.sleepycat.je.tree.Tree.search(Tree.java:1615)
      at com.sleepycat.je.incomp.INCompressor.searchForBIN(INCompressor.java:648)
      at com.sleepycat.je.incomp.INCompressor.searchForBIN(INCompressor.java:640)
      at com.sleepycat.je.incomp.INCompressor.findDBAndBIN(INCompressor.java:805)
      at com.sleepycat.je.incomp.INCompressor.doCompress(INCompressor.java:403)
      at com.sleepycat.je.incomp.INCompressor.onWakeup(INCompressor.java:342)
      at com.sleepycat.je.utilint.DaemonThread.run(DaemonThread.java:191)
      at java.lang.Thread.run(Thread.java:619)

      State:
      The method at the top of the trace
      [public static int compareKeys(byte[] key1, byte[] key2, Comparator comparator);]
      got called with key1 being database value, key2 being a database key and comparator being the custom key-comparator of the database.

      At the same time, another thread was performing a get operation as part of a transaction:
      at com.sleepycat.je.log.FileManager.readFromFile(FileManager.java:1109)
      at com.sleepycat.je.log.FileSource.getBytes(FileSource.java:51)
      at com.sleepycat.je.log.LogManager.getLogEntryFromLogSource(LogManager.java:672)
      at com.sleepycat.je.log.LogManager.getLogEntry(LogManager.java:640)
      at com.sleepycat.je.log.LogManager.get(LogManager.java:766)
      at com.sleepycat.je.tree.IN.fetchTarget(IN.java:957)
      at com.sleepycat.je.dbi.CursorImpl.searchAndPosition(CursorImpl.java:1943)
      at com.sleepycat.je.Cursor.searchInternal(Cursor.java:1179)
      at com.sleepycat.je.Cursor.searchAllowPhantoms(Cursor.java:1148)
      at com.sleepycat.je.Cursor.search(Cursor.java:1014)
      at com.sleepycat.je.Cursor.getSearchKey(Cursor.java:556)
      at com.sleepycat.util.keyrange.RangeCursor.doGetSearchKey(RangeCursor.java:964)
      at com.sleepycat.util.keyrange.RangeCursor.getSearchKey(RangeCursor.java:591)
      at com.sleepycat.collections.DataCursor.doGetSearchKey(DataCursor.java:580)
      at com.sleepycat.collections.DataCursor.getSearchKey(DataCursor.java:562)
      at com.sleepycat.collections.StoredContainer.get(StoredContainer.java:287)
      at com.sleepycat.collections.StoredMap.get(StoredMap.java:219)
      at com.project.worker.Updater.doWork(Updater.java:124)
      at com.sleepycat.collections.TransactionRunner.run(TransactionRunner.java:229)
      at com.project.worker.Executor.run(Executor.java:45)
      at java.lang.Thread.run(Thread.java:619)
        • 1. Re: INCompressor sometimes seems to confuse Key and Value
          Charles Lamb
          Hi Luzius,

          In the case of duplicates, the sub-tree holding the duplicates is keyed on the data, rather than the key. So this behavior may not necessarily be incorrect. But there is always the possibility of a bug so I'll be happy to look at your test case if it's relatively small. Please email it to charles.lamb at NOSPAMoracleNOSPAM.com.

          I don't understand what your concern is with the second stack trace in your post.

          Regards,

          Charles Lamb
          • 2. Re: INCompressor sometimes seems to confuse Key and Value
            561794
            Hi Charles,

            I understand that the subtree is keyed on the values. However, it confuses me that my custom btree-comparator gets called to compare a key with a value. Is a btree-comparator supposed to be able to compare keys and values?

            As far as I understand the documentation, shouldn't the btree-comparator only be used to compare keys with keys and the duplicate-comparator to compare values with values?

            Since it might take a some effort to find a small and reliable test case, I'd like to have these questions confirmed before I start to create one.

            The second stacktrace was attached to indicate that the problem only seems to occur as long as there are simultanous other operations.

            Regards,
            Luzius
            • 3. Re: INCompressor sometimes seems to confuse Key and Value
              Charles Lamb
              As far as I understand the documentation, shouldn't
              the btree-comparator only be used to compare keys
              with keys and the duplicate-comparator to compare
              values with values?
              Yes, that is correct.

              >
              Since it might take a some effort to find a small and
              reliable test case, I'd like to have these questions
              confirmed before I start to create one.
              OK, that would be useful. The stack trace that you sent before didn't yield any clues.

              >
              The second stacktrace was attached to indicate that
              the problem only seems to occur as long as there are
              simultanous other operations.
              ok.
              • 4. Re: INCompressor sometimes seems to confuse Key and Value
                561794
                Unfortunately, I could not create a good test case to reproduce the problem, as it does not appear deterministically. However, while observing the behavior of the database in the debugger and examining its code, I could identify a potential bug in the IN class that seems to have been the cause of the problem. After having applied a small fix, the problem did not occur any more.

                Here is a short description of what I've done:

                In the splitInternal method of IN on line 1769 it says:

                if (isEntryPendingDeleted(i)) {
                if (!deletedEntrySeen) {
                deletedEntrySeen = true;
                binRef = new BINReference(newSibling.getNodeId(), databaseImpl.getId(), newIdKey);
                }
                binRef.addDeletedKey(new Key(thisKey));
                }

                IMO, in case the IN is a DBIN, we should no instantiate a BINReference here, but a DBINReference. Since the identifier key of a DBIN is a database value, the created BINReference in the code above will return this value instead of a database key when being asked for the key by the INCompressor which lead to the unfortunate behavior described in the first post.

                To test this idea, I've replaced the code above with the following quick hack:

                if (isEntryPendingDeleted(i)) {
                if (!deletedEntrySeen) {
                deletedEntrySeen = true;
                if (this instanceof DBIN) {
                byte[] dupKey = ((DBIN) this).getDupKey();
                binRef = new DBINReference(newSibling.getNodeId(), databaseImpl.getId(), newIdKey, dupKey);
                } else {
                binRef = new BINReference(newSibling.getNodeId(), databaseImpl.getId(), newIdKey);
                }
                }
                binRef.addDeletedKey(new Key(thisKey));
                }

                Since then, the database seems to work flawlessly. I hope that helps you.
                • 5. Re: INCompressor sometimes seems to confuse Key and Value
                  Charles Lamb
                  Hi Luzius,

                  Interesting. Please give me a few days to take a look at this fix and evaluate it.

                  Thanks very much for passing this along to us!

                  Regards,

                  Charles Lamb
                  • 6. Re: INCompressor sometimes seems to confuse Key and Value
                    Charles Lamb
                    We apparently don't have a unit test for this case (I guess that's why it took 3 years for someone to stumble on it). It'll take me a few days to come up with the unit test for it in order to test your fix (which looks plausible at first glance).

                    Thanks again for diagnosing this.

                    Charles Lamb
                    • 7. Re: INCompressor sometimes seems to confuse Key and Value
                      561794
                      Thank you for your prompt answers. I'm happy that I could contribute a little to the stability of one of my favorite databases.

                      Luzius Meisser
                      • 8. Re: INCompressor sometimes seems to confuse Key and Value
                        greybird
                        Hello all,

                        For the record, the fix for this problem is included in JE 3.2.21:

                        Berkeley DB Java Edition 3.2.21 is now available

                        Mark