Derby
  1. Derby
  2. DERBY-3092

Use java.util.concurrent in TransactionTable to improve scalability

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 10.3.1.4
    • Fix Version/s: 10.6.1.0
    • Component/s: Store
    • Labels:
      None
    • Bug behavior facts:
      Performance

      Description

      Running scalability tests with the client and buffer manager from DERBY-2911 shows that access to the TransactionTable.trans (a Hashtable) and XactFactory.tranId (a shared long) are the next major sources of contention.

      1. derby-3092-5a-dynamic-loading.diff
        16 kB
        Knut Anders Hatlen
      2. derby-3092-5a-dynamic-loading.stat
        0.5 kB
        Knut Anders Hatlen
      3. derby-3092-4a-more-visitors.diff
        16 kB
        Knut Anders Hatlen
      4. derby-3092-3a-xa-visitor.diff
        5 kB
        Knut Anders Hatlen
      5. derby-3092-2a-count.diff
        1.0 kB
        Knut Anders Hatlen
      6. derby-3092-1b-map.diff
        11 kB
        Knut Anders Hatlen
      7. derby-3092-1a-map.diff
        11 kB
        Knut Anders Hatlen
      8. xact-concept.png
        7 kB
        Knut Anders Hatlen
      9. xact-concept.diff
        7 kB
        Dyre Tjeldvoll

        Issue Links

          Activity

          Hide
          Dyre Tjeldvoll added a comment -

          The test was performed on a SunFire T2000 with 8 cores and 4
          hardware threads per core, using jvm version 1.6.0_02. The client
          was run (in embedded mode) for 300 seconds with a 30 second
          warmup, with 32 clients. The CPU utilization of the jvm process
          was observed with top:

          10.3.1.4:
          CPU utilization: 35.3%
          Throughput: 37,512.6 TPS

          With new buffer manager:
          CPU utilization: 82.8%
          Throughput: 132,444 TPS

          With new buffer manager and java.util.concurrent in
          TransactionTable and XactFfactory:
          CPU utilization: 97.4%
          Throughput: 159.720 TPS

          Show
          Dyre Tjeldvoll added a comment - The test was performed on a SunFire T2000 with 8 cores and 4 hardware threads per core, using jvm version 1.6.0_02. The client was run (in embedded mode) for 300 seconds with a 30 second warmup, with 32 clients. The CPU utilization of the jvm process was observed with top: 10.3.1.4: CPU utilization: 35.3% Throughput: 37,512.6 TPS With new buffer manager: CPU utilization: 82.8% Throughput: 132,444 TPS With new buffer manager and java.util.concurrent in TransactionTable and XactFfactory: CPU utilization: 97.4% Throughput: 159.720 TPS
          Hide
          Dyre Tjeldvoll added a comment -

          Attaching a proof of concept patch a showing the changes. I cannot be committed in its present form, however, since it doesn't compile with java 1.4. Could perhaps be fixed with some reflection magic?

          Show
          Dyre Tjeldvoll added a comment - Attaching a proof of concept patch a showing the changes. I cannot be committed in its present form, however, since it doesn't compile with java 1.4. Could perhaps be fixed with some reflection magic?
          Hide
          Bryan Pendleton added a comment -

          Could you describe the test you are running a little bit? Does "TPS" mean
          Transactions Per Second? Are you really seeing 37 thousand transactions per second?

          Show
          Bryan Pendleton added a comment - Could you describe the test you are running a little bit? Does "TPS" mean Transactions Per Second? Are you really seeing 37 thousand transactions per second?
          Hide
          Dyre Tjeldvoll added a comment -

          Hi Bryan,
          yes, TPS=Transactions Per Second. The client used is the d2911perf.java client Knut attached to that issue:
          https://issues.apache.org/jira/secure/attachment/12365001/d2911perf.java

          Yes, those are the numbers I'm seeing, but the client has been carefully constructed to avoid any "data contention". That is,
          each client (connection) selects a single record from its own table. So there is no contention for locks or latches. It is admittedly a pretty unrealistic load for a database, but the goal was to identify "non-data-related" contention in the engine. The idea being that if the engine doesn't scale with this type of load, it isn't much point in trying to address scalability issues for other types of load...

          Show
          Dyre Tjeldvoll added a comment - Hi Bryan, yes, TPS=Transactions Per Second. The client used is the d2911perf.java client Knut attached to that issue: https://issues.apache.org/jira/secure/attachment/12365001/d2911perf.java Yes, those are the numbers I'm seeing, but the client has been carefully constructed to avoid any "data contention". That is, each client (connection) selects a single record from its own table. So there is no contention for locks or latches. It is admittedly a pretty unrealistic load for a database, but the goal was to identify "non-data-related" contention in the engine. The idea being that if the engine doesn't scale with this type of load, it isn't much point in trying to address scalability issues for other types of load...
          Hide
          mike bell added a comment -

          backport-java.util.concurrent COULD be used, and provides java.util.ConcurrentHashMap semantics and JDK 1.4 compatibility.

          Dunno if that's helpful.

          Show
          mike bell added a comment - backport-java.util.concurrent COULD be used, and provides java.util.ConcurrentHashMap semantics and JDK 1.4 compatibility. Dunno if that's helpful.
          Hide
          Dyre Tjeldvoll added a comment -

          That could be very helpful! I'll keep it in mind.

          Unfortunately, it turns out that simply replacing the old Hashtable with ConcurrentHashMap had some undesirable side-effects. They did not show up when running the simple d2911 client, but caused strange hangs with more complicated load. I do believe it is possible to work around that with better locking of the elements in the hash (as opposed to locking the entire hash), but I've not had time to try that out yet...

          Show
          Dyre Tjeldvoll added a comment - That could be very helpful! I'll keep it in mind. Unfortunately, it turns out that simply replacing the old Hashtable with ConcurrentHashMap had some undesirable side-effects. They did not show up when running the simple d2911 client, but caused strange hangs with more complicated load. I do believe it is possible to work around that with better locking of the elements in the hash (as opposed to locking the entire hash), but I've not had time to try that out yet...
          Hide
          Knut Anders Hatlen added a comment -

          I reran Dyre's experiment on the same kind of machine, but with a newer JVM (early access release of JDK 7) and head of trunk. I used a slightly different test client that's available in derbyTesting.jar (java org.apache.derbyTesting.perf.clients.Runner -load sr_select_multi). It still looks like the patch improves the scalability for this kind of load.

          The xact-concept.diff patch actually consists of two independent changes:

          1) The tranId field in XactFactory is changed into an AtomicLong, and the synchronization that protects it is removed. This looks like a safe change (but some extra work is required to make it also work on pre-Java 5).

          2) The Hashtable in TransactionTable is changed into a ConcurrentHashTable. As Dyre noted, this change was not safe the way it appeared in the patch, and some more synchronization is needed (hopefully most of it can be added on the entry level to avoid locking the entire map). Making it work on pre-Java 5 platforms is required for this change too.

          When I ran the experiment, I tried to run with these two changes separately as well as combined. I was not able to detect any changes in the performance with change (1), whereas (2) seemed to give a good improvement. Based on that, I think it's best to focus on (2) first. Perhaps it would also make sense to split this JIRA issue into two separate issues.

          Show
          Knut Anders Hatlen added a comment - I reran Dyre's experiment on the same kind of machine, but with a newer JVM (early access release of JDK 7) and head of trunk. I used a slightly different test client that's available in derbyTesting.jar (java org.apache.derbyTesting.perf.clients.Runner -load sr_select_multi). It still looks like the patch improves the scalability for this kind of load. The xact-concept.diff patch actually consists of two independent changes: 1) The tranId field in XactFactory is changed into an AtomicLong, and the synchronization that protects it is removed. This looks like a safe change (but some extra work is required to make it also work on pre-Java 5). 2) The Hashtable in TransactionTable is changed into a ConcurrentHashTable. As Dyre noted, this change was not safe the way it appeared in the patch, and some more synchronization is needed (hopefully most of it can be added on the entry level to avoid locking the entire map). Making it work on pre-Java 5 platforms is required for this change too. When I ran the experiment, I tried to run with these two changes separately as well as combined. I was not able to detect any changes in the performance with change (1), whereas (2) seemed to give a good improvement. Based on that, I think it's best to focus on (2) first. Perhaps it would also make sense to split this JIRA issue into two separate issues.
          Hide
          Knut Anders Hatlen added a comment -

          For the record, I'm attaching a graph showing the results from my test run (xact-concept.png).

          I ran the test as

          java org.apache.derbyTesting.perf.clients.Runner -load sr_select_multi -wt 20 -rt 40 -threads N

          The sr_select_multi client works on a set of 32 tables with a single row in them, with each client thread randomly picking tables to read from. (The large set of tables eliminates the data contention that would have been seen if all threads read from the same table. With a small number of tables, data contention would have been the dominating scalability bottleneck, and the issues in the transaction table would not be observable.)

          Show
          Knut Anders Hatlen added a comment - For the record, I'm attaching a graph showing the results from my test run (xact-concept.png). I ran the test as java org.apache.derbyTesting.perf.clients.Runner -load sr_select_multi -wt 20 -rt 40 -threads N The sr_select_multi client works on a set of 32 tables with a single row in them, with each client thread randomly picking tables to read from. (The large set of tables eliminates the data contention that would have been seen if all threads read from the same table. With a small number of tables, data contention would have been the dominating scalability bottleneck, and the issues in the transaction table would not be observable.)
          Hide
          Knut Anders Hatlen added a comment -

          I've filed a separate issue for the XactFactory part of this issue. See DERBY-4478.

          Show
          Knut Anders Hatlen added a comment - I've filed a separate issue for the XactFactory part of this issue. See DERBY-4478 .
          Hide
          Knut Anders Hatlen added a comment -

          I went through the TransactionTable class to get a picture of how the
          synchronization is used there. It synchronizes on two different
          objects: this (the TransactionTable) and trans (the Hashtable within
          the TransactionTable). Many methods don't use any explicit
          synchronization because they're guaranteed to be called only during
          recovery, which is single-threaded.

          • The explicit and implicit synchronization on the Hashtable is
            basically used to prevent removal of elements from the Hashtable
            between calls to Enumeration.hasMoreElements() and
            Enumeration.nextElement(). (In addition to the obvious task of
            protecting the consistency of the Hashtable's internal data structures
            when modifying it from multiple threads.)

          I think that ConcurrentHashMap's iterator gives the necessary
          guarantees for most of these usages without any synchronization.

          One potential problem is the method getTableForXA() which returns the
          internal Hashtable. The caller then synchronizes on the returned
          Hashtable while looping through it. If we are to provide two different
          implementations, one of which not based on Hashtable, we probably need
          to rethink how this is done.

          • Synchronization on the TransactionTable is used to prevent
            transaction table entries from state transitions between read
            transactions and update transactions. This protection is needed when
            writing the tx table during the checkpoint, since it scans the
            transaction table twice, and the number of update transactions must be
            equal both times. This synchronization probably needs to be preserved
            in some way.
          Show
          Knut Anders Hatlen added a comment - I went through the TransactionTable class to get a picture of how the synchronization is used there. It synchronizes on two different objects: this (the TransactionTable) and trans (the Hashtable within the TransactionTable). Many methods don't use any explicit synchronization because they're guaranteed to be called only during recovery, which is single-threaded. The explicit and implicit synchronization on the Hashtable is basically used to prevent removal of elements from the Hashtable between calls to Enumeration.hasMoreElements() and Enumeration.nextElement(). (In addition to the obvious task of protecting the consistency of the Hashtable's internal data structures when modifying it from multiple threads.) I think that ConcurrentHashMap's iterator gives the necessary guarantees for most of these usages without any synchronization. One potential problem is the method getTableForXA() which returns the internal Hashtable. The caller then synchronizes on the returned Hashtable while looping through it. If we are to provide two different implementations, one of which not based on Hashtable, we probably need to rethink how this is done. Synchronization on the TransactionTable is used to prevent transaction table entries from state transitions between read transactions and update transactions. This protection is needed when writing the tx table during the checkpoint, since it scans the transaction table twice, and the number of update transactions must be equal both times. This synchronization probably needs to be preserved in some way.
          Hide
          Knut Anders Hatlen added a comment -

          Dyre, do you happen to remember the nature of the tests that hung when you tested the patch?

          Show
          Knut Anders Hatlen added a comment - Dyre, do you happen to remember the nature of the tests that hung when you tested the patch?
          Hide
          Knut Anders Hatlen added a comment -

          Dyre told me the test that hung was an appserver benchmark application, but he hadn't investigated whether the hang was caused by the patch or by something else. I'll see if I can get the application up and running myself and reproduce the hang.

          I don't see anything obvious that could cause a hang in the patch. As far as I've understood how the synchronization in TransactionTable works, the changes suggested in xact-concept.diff look fine. (Except, of course, that we need to make it work on older Java versions too, and that some for loops are still unnecessarily synchronized on trans.)

          Show
          Knut Anders Hatlen added a comment - Dyre told me the test that hung was an appserver benchmark application, but he hadn't investigated whether the hang was caused by the patch or by something else. I'll see if I can get the application up and running myself and reproduce the hang. I don't see anything obvious that could cause a hang in the patch. As far as I've understood how the synchronization in TransactionTable works, the changes suggested in xact-concept.diff look fine. (Except, of course, that we need to make it work on older Java versions too, and that some for loops are still unnecessarily synchronized on trans.)
          Hide
          Knut Anders Hatlen added a comment -

          A good first step would be to change the declaration of TransactionTable.trans from Hashtable to Map, which is the common interface implemented by both Hashtable and ConcurrentHashMap. Such a change should be harmless, and it will make it easier to get TransactionTable to support different underlying Map implementations (which will be needed in order to work on platforms that don't support java.util.concurrent).

          The attached patch (derby-3092-1a-map.diff) makes the proposed change. Since the Map interface does not have an elements() method, all calls to that method are replaced with the equivalent iterator() method. Also, a couple of unused variables that I came across are removed by the patch.

          TransactionTable.trans is still a Hashtable. The patch only changes which interface we use to access the Hashtable.

          I'm running regression tests now.

          Show
          Knut Anders Hatlen added a comment - A good first step would be to change the declaration of TransactionTable.trans from Hashtable to Map, which is the common interface implemented by both Hashtable and ConcurrentHashMap. Such a change should be harmless, and it will make it easier to get TransactionTable to support different underlying Map implementations (which will be needed in order to work on platforms that don't support java.util.concurrent). The attached patch (derby-3092-1a-map.diff) makes the proposed change. Since the Map interface does not have an elements() method, all calls to that method are replaced with the equivalent iterator() method. Also, a couple of unused variables that I came across are removed by the patch. TransactionTable.trans is still a Hashtable. The patch only changes which interface we use to access the Hashtable. I'm running regression tests now.
          Hide
          Knut Anders Hatlen added a comment -

          The 1a patch made StressMultiTest fail consistently in sane builds because of ConcurrentModificationExceptions. The reason for this was that some debug code called from getTransactionTable() iterated through the transaction table without synchronizing on the Hashtable while doing that. What changed with the patch, was that an Iterator was used instead of an Enumeration. Hashtable's Iterators are fail-fast and raise CME as soon as they detect concurrent modification, whereas Hashtable's Enumerations are not fail-fast (see comment about this in Hashtable's class-level javadoc).

          Patch 1b moves the failing debug code into the synchronized block that starts right below it so that no concurrent modification of the Hashtable is possible while it's going through it. This code may have failed before too, but not as consistently as with the fail-fast Iterators, and probably with stack traces so similar to DERBY-3916 that they were believed to be the same issue.

          suites.All ran cleanly with 1b. Running derbyall now.

          Show
          Knut Anders Hatlen added a comment - The 1a patch made StressMultiTest fail consistently in sane builds because of ConcurrentModificationExceptions. The reason for this was that some debug code called from getTransactionTable() iterated through the transaction table without synchronizing on the Hashtable while doing that. What changed with the patch, was that an Iterator was used instead of an Enumeration. Hashtable's Iterators are fail-fast and raise CME as soon as they detect concurrent modification, whereas Hashtable's Enumerations are not fail-fast (see comment about this in Hashtable's class-level javadoc). Patch 1b moves the failing debug code into the synchronized block that starts right below it so that no concurrent modification of the Hashtable is possible while it's going through it. This code may have failed before too, but not as consistently as with the fail-fast Iterators, and probably with stack traces so similar to DERBY-3916 that they were believed to be the same issue. suites.All ran cleanly with 1b. Running derbyall now.
          Hide
          Knut Anders Hatlen added a comment -

          All the regression tests ran cleanly with patch 1b.

          Show
          Knut Anders Hatlen added a comment - All the regression tests ran cleanly with patch 1b.
          Hide
          Knut Anders Hatlen added a comment -

          Committed 1b with revision 901100.

          Show
          Knut Anders Hatlen added a comment - Committed 1b with revision 901100.
          Hide
          Knut Anders Hatlen added a comment -

          I was a little too aggressive in trimming down the code in the previous patch. In writeExternal() there used to be an "if (count > 0)" surrounding the second for loop, and it got removed by the 1b patch. This is just a tiny optimization that prevents a second scan of the transaction table if it only contains read-only transactions, so its removal should not cause any harm. But it was not supposed to be removed, so here's another patch (2a) that adds it back.

          Show
          Knut Anders Hatlen added a comment - I was a little too aggressive in trimming down the code in the previous patch. In writeExternal() there used to be an "if (count > 0)" surrounding the second for loop, and it got removed by the 1b patch. This is just a tiny optimization that prevents a second scan of the transaction table if it only contains read-only transactions, so its removal should not cause any harm. But it was not supposed to be removed, so here's another patch (2a) that adds it back.
          Hide
          Knut Anders Hatlen added a comment -

          Committed revision 901162.

          Show
          Knut Anders Hatlen added a comment - Committed revision 901162.
          Hide
          Knut Anders Hatlen added a comment -

          I think the next step is to encapsulate the Hashtable inside the TransactionTable class. Currently, this internal data structure is exposed through the method getTableForXA(). XactXAResourceManager uses this method to get a reference to the Hashtable, and synchronizes on the Hashtable while iterating over it. It will be easier to replace the Hashtable with a ConcurrentHashMap if no other classes depend on it being a Hashtable.

          In the attached patch (derby-3092-3a-xa-visitor.diff) I have removed the getTableForXA() method and instead introduced a visitor that can be used to go through the elements of the transaction table. The patch also makes XactXAResourceManager use the visitor instead of accessing the Hashtable directly.

          I believe that the proposed patch also fixes a bug in XactXAResourceManager.recover(). That method initializes an array with the same size as the transaction table outside the synchronized block. If a new entry is added to the tx table in the window between the call to Hashtable.size() and the start of the synchronized block, an ArrayIndexOutOfBoundsException may be raised while populating the array. With the patch, we no longer use Hashtable.size() to initialize an array, so this situation can't occur anymore.

          Running regression tests...

          Show
          Knut Anders Hatlen added a comment - I think the next step is to encapsulate the Hashtable inside the TransactionTable class. Currently, this internal data structure is exposed through the method getTableForXA(). XactXAResourceManager uses this method to get a reference to the Hashtable, and synchronizes on the Hashtable while iterating over it. It will be easier to replace the Hashtable with a ConcurrentHashMap if no other classes depend on it being a Hashtable. In the attached patch (derby-3092-3a-xa-visitor.diff) I have removed the getTableForXA() method and instead introduced a visitor that can be used to go through the elements of the transaction table. The patch also makes XactXAResourceManager use the visitor instead of accessing the Hashtable directly. I believe that the proposed patch also fixes a bug in XactXAResourceManager.recover(). That method initializes an array with the same size as the transaction table outside the synchronized block. If a new entry is added to the tx table in the window between the call to Hashtable.size() and the start of the synchronized block, an ArrayIndexOutOfBoundsException may be raised while populating the array. With the patch, we no longer use Hashtable.size() to initialize an array, so this situation can't occur anymore. Running regression tests...
          Hide
          Knut Anders Hatlen added a comment -

          Regression tests ran cleanly.

          Show
          Knut Anders Hatlen added a comment - Regression tests ran cleanly.
          Hide
          Knut Anders Hatlen added a comment -

          Committed revision 901597.

          Show
          Knut Anders Hatlen added a comment - Committed revision 901597.
          Hide
          Knut Anders Hatlen added a comment -

          Now there are only a few places in the code that synchronize explicitly on trans. These are methods doing linear search of the transaction table, primarily during checkpoint and for diagnostics, as well when a global XA transaction is started.

          These are the methods doing linear search with explicit synchronization on trans:

          findTransactionContextByGlobalId
          writeExternal
          getFirstLogInstant
          getTransactionInfo

          In addition you have hasActiveUpdateTransaction() whose comments indicate that synchronization on trans is needed, but it currently only synchronizes on "this". And in sane builds, toString() is called from within the synchronized block in getTransactionInfo() and performs a linear search.

          If we change the above mentioned methods so that they use visitors instead of iterating through the transaction table themselves, we will have explicit synchronization on trans in just one method - visitEntries(). Having just a single method to override when adding ConcurrentHashMap sounds attractive, so I will attempt to make such a change.

          There are more methods that search the Hashtable linearly, but without synchronization because they are only called during boot/recovery, according to their comments. These methods are:

          hasRollbackFirstTransaction
          hasPreparedXact
          getMostRecentRollbackFirstTransaction
          getMostRecentTransactionForRollback
          getMostRecentPreparedRecoveredXact

          These methods do not need any changes when switching between Hashtable and ConcurrentHashMap, because they are only used when the engine is running single-threaded, and they do not depend on the synchronization properties of Hashtable.

          Show
          Knut Anders Hatlen added a comment - Now there are only a few places in the code that synchronize explicitly on trans. These are methods doing linear search of the transaction table, primarily during checkpoint and for diagnostics, as well when a global XA transaction is started. These are the methods doing linear search with explicit synchronization on trans: findTransactionContextByGlobalId writeExternal getFirstLogInstant getTransactionInfo In addition you have hasActiveUpdateTransaction() whose comments indicate that synchronization on trans is needed, but it currently only synchronizes on "this". And in sane builds, toString() is called from within the synchronized block in getTransactionInfo() and performs a linear search. If we change the above mentioned methods so that they use visitors instead of iterating through the transaction table themselves, we will have explicit synchronization on trans in just one method - visitEntries(). Having just a single method to override when adding ConcurrentHashMap sounds attractive, so I will attempt to make such a change. There are more methods that search the Hashtable linearly, but without synchronization because they are only called during boot/recovery, according to their comments. These methods are: hasRollbackFirstTransaction hasPreparedXact getMostRecentRollbackFirstTransaction getMostRecentTransactionForRollback getMostRecentPreparedRecoveredXact These methods do not need any changes when switching between Hashtable and ConcurrentHashMap, because they are only used when the engine is running single-threaded, and they do not depend on the synchronization properties of Hashtable.
          Hide
          Knut Anders Hatlen added a comment -

          Attaching new patch derby-3092-4a-more-visitors.diff.

          This patch replaces the for loops that use explicit synchronization on trans, with visitors (in addition to the two methods hasActiveUpdateTransaction() and toString() that probably should have used synchronization in the first place). Now, visitEntries() is the only method that explicitly synchronizes on trans.

          I think most of the changes are pretty straightforward, and don't look too ugly... Some details that might be worth mentioning:

          • the return type of the visit() method was changed from void to boolean, so that the visitor has a way to stop the scan. This is useful if we're looking for the first entry to match a certain condition, and we don't want to continue scanning the transaction table once we've found the entry of interest.
          • for brevity, the visitors don't check whether entries are null. Most of the for loops did, but since a Hashtable cannot contain null as key or value, those checks are unnecessary and misleading.
          • hasActiveUpdateTransaction() and writeExternal() use the same visitor class to count the number of update transactions, with a parameter to tell whether it should stop as soon as it finds one update transaction (for hasActiveUT) or if it should count all update transactions (for writeExternal)
          • in writeExternal() an ASSERT was added to verify that the number of transactions written to the log is equal to the number of transactions we expected to write (otherwise, the log will most likely be corrupted)

          All the regression tests passed with this patch.

          Show
          Knut Anders Hatlen added a comment - Attaching new patch derby-3092-4a-more-visitors.diff. This patch replaces the for loops that use explicit synchronization on trans, with visitors (in addition to the two methods hasActiveUpdateTransaction() and toString() that probably should have used synchronization in the first place). Now, visitEntries() is the only method that explicitly synchronizes on trans. I think most of the changes are pretty straightforward, and don't look too ugly... Some details that might be worth mentioning: the return type of the visit() method was changed from void to boolean, so that the visitor has a way to stop the scan. This is useful if we're looking for the first entry to match a certain condition, and we don't want to continue scanning the transaction table once we've found the entry of interest. for brevity, the visitors don't check whether entries are null. Most of the for loops did, but since a Hashtable cannot contain null as key or value, those checks are unnecessary and misleading. hasActiveUpdateTransaction() and writeExternal() use the same visitor class to count the number of update transactions, with a parameter to tell whether it should stop as soon as it finds one update transaction (for hasActiveUT) or if it should count all update transactions (for writeExternal) in writeExternal() an ASSERT was added to verify that the number of transactions written to the log is equal to the number of transactions we expected to write (otherwise, the log will most likely be corrupted) All the regression tests passed with this patch.
          Hide
          Knut Anders Hatlen added a comment -

          Committed 4a with revision 903200.

          Now, the next step is to make TransactionTable use a ConcurrentHashMap if supported by the platform. I think we can define a new interface with two methods

          Map newMap() - which returns a Hashtable or a ConcurrentHashMap, depending on platform

          void visitEntries(Map, EntryVisitor) - which performs thread-safe iteration over the Map

          and put some magic into modules.properties to load different implementations on the different platforms.

          Show
          Knut Anders Hatlen added a comment - Committed 4a with revision 903200. Now, the next step is to make TransactionTable use a ConcurrentHashMap if supported by the platform. I think we can define a new interface with two methods Map newMap() - which returns a Hashtable or a ConcurrentHashMap, depending on platform void visitEntries(Map, EntryVisitor) - which performs thread-safe iteration over the Map and put some magic into modules.properties to load different implementations on the different platforms.
          Hide
          Dag H. Wanvik added a comment -

          Sounds like a good approach.

          Show
          Dag H. Wanvik added a comment - Sounds like a good approach.
          Hide
          Knut Anders Hatlen added a comment -

          Attached is a new patch (derby-3092-5a-dynamic-loading.diff) that implements the dynamic loading of the correct Map implementation for the platform.

          Ideally, I would have just added a couple of helper methods in XactFactory and create a sub-class of XactFactory that overloaded the helper methods in order to use ConcurrentHashMap instead of Hashtable, and then give the parent XactFactory as an argument to TransactionTable's constructor. This could not be done because TransactionTable is externalizable and it must be possible to read it from a stream during recovery. When being read from a stream, it doesn't know anything about which XactFactory it belongs to.

          Instead, I made the first instance of XactFactory that's being created set a static field in XactFactory to point to a TransactionMapFactory object. TransactionMapFactory contains helper methods to create and iterate over a map, and there are two implementations (one for Hashtable and one for ConcurrentHashMap). Then TransactionTable's constructor can call a static accessor method in XactFactory to get hold of that object, and create a map of the type that gives the highest level of concurrency on that platform.

          I've run all the regression tests on Java 1.4.2, Java 1.5.0 and Java 1.6.0 with no failures, and the d2911perf test shows improvements similar to those seen with Dyre's initial patch.

          I don't think the patch is ready for commit yet, but I'm posting it here for reference. Now it is possible that multiple threads access fields in the same TransactionTableEntry object concurrently, which was not possible before when all iteration over the values would be protected by synchronization on trans. It might be that some entry-level synchronization will be needed, as Dyre suggested in an earlier comment. I'll do some more investigation on whether the mutable state of TransactionTableEntry is still protected, or if we have to add another level of synchronization. I'm optimistic, though, that even if we have to add synchronization on the entry level, it should not affect the performance gain seen in the earlier patches very much, since those monitors will not be nearly as contended as the one on the Hashtable.

          Show
          Knut Anders Hatlen added a comment - Attached is a new patch (derby-3092-5a-dynamic-loading.diff) that implements the dynamic loading of the correct Map implementation for the platform. Ideally, I would have just added a couple of helper methods in XactFactory and create a sub-class of XactFactory that overloaded the helper methods in order to use ConcurrentHashMap instead of Hashtable, and then give the parent XactFactory as an argument to TransactionTable's constructor. This could not be done because TransactionTable is externalizable and it must be possible to read it from a stream during recovery. When being read from a stream, it doesn't know anything about which XactFactory it belongs to. Instead, I made the first instance of XactFactory that's being created set a static field in XactFactory to point to a TransactionMapFactory object. TransactionMapFactory contains helper methods to create and iterate over a map, and there are two implementations (one for Hashtable and one for ConcurrentHashMap). Then TransactionTable's constructor can call a static accessor method in XactFactory to get hold of that object, and create a map of the type that gives the highest level of concurrency on that platform. I've run all the regression tests on Java 1.4.2, Java 1.5.0 and Java 1.6.0 with no failures, and the d2911perf test shows improvements similar to those seen with Dyre's initial patch. I don't think the patch is ready for commit yet, but I'm posting it here for reference. Now it is possible that multiple threads access fields in the same TransactionTableEntry object concurrently, which was not possible before when all iteration over the values would be protected by synchronization on trans. It might be that some entry-level synchronization will be needed, as Dyre suggested in an earlier comment. I'll do some more investigation on whether the mutable state of TransactionTableEntry is still protected, or if we have to add another level of synchronization. I'm optimistic, though, that even if we have to add synchronization on the entry level, it should not affect the performance gain seen in the earlier patches very much, since those monitors will not be nearly as contended as the one on the Hashtable.
          Hide
          Knut Anders Hatlen added a comment -

          As far as I can see, none of the code that currently synchronizes on the Hashtable modifies any shared state outside of the Hashtable itself, so the only purpose of this synchronization appears to be to make the Hashtable operations atomic. This is also ensured by ConcurrentHashMap, so I've come to the conclusion that we don't need to add any new synchronization level when we remove "synchronized (trans)" around the for loops. Setting the Patch Available flag to record that I think the patch is ready for review.

          I will need to run more tests in order to fully convince myself that the changes are fine. Should we however commit the patch earlier in order to get as much testing as possible? If it's getting closer to the release date and we feel that we don't yet have the required level of confidence in the new code, it could easily be disabled by commenting out a couple of lines in modules.properties and we would fall back to the old, well-tested code on all platforms.

          Show
          Knut Anders Hatlen added a comment - As far as I can see, none of the code that currently synchronizes on the Hashtable modifies any shared state outside of the Hashtable itself, so the only purpose of this synchronization appears to be to make the Hashtable operations atomic. This is also ensured by ConcurrentHashMap, so I've come to the conclusion that we don't need to add any new synchronization level when we remove "synchronized (trans)" around the for loops. Setting the Patch Available flag to record that I think the patch is ready for review. I will need to run more tests in order to fully convince myself that the changes are fine. Should we however commit the patch earlier in order to get as much testing as possible? If it's getting closer to the release date and we feel that we don't yet have the required level of confidence in the new code, it could easily be disabled by commenting out a couple of lines in modules.properties and we would fall back to the old, well-tested code on all platforms.
          Hide
          Knut Anders Hatlen added a comment -

          If there are no objections, I will commit the 5a patch tomorrow. As mentioned in the previous comment, if it's getting closer to the release and we don't have enough confidence in the new code, it can be disabled by commenting out four lines in modules.properties.

          Show
          Knut Anders Hatlen added a comment - If there are no objections, I will commit the 5a patch tomorrow. As mentioned in the previous comment, if it's getting closer to the release and we don't have enough confidence in the new code, it can be disabled by commenting out four lines in modules.properties.
          Hide
          Kristian Waagan added a comment -

          I had a look at patch 5a, it looks solid. I also applied it and built Derby.
          +1 to commit.

          Show
          Kristian Waagan added a comment - I had a look at patch 5a, it looks solid. I also applied it and built Derby. +1 to commit.
          Hide
          Knut Anders Hatlen added a comment -

          Thanks for looking at the patch, Kristian!
          Committed revision 908473.

          I'll leave the issue open until I've had a chance to run the test where Dyre saw some unexplained behaviour with the concept patch.

          Show
          Knut Anders Hatlen added a comment - Thanks for looking at the patch, Kristian! Committed revision 908473. I'll leave the issue open until I've had a chance to run the test where Dyre saw some unexplained behaviour with the concept patch.
          Hide
          Kristian Waagan added a comment -

          I have been running the test where Dyre had some issues with the concept patch, but I have not observed any problems with the current patch committed to the code line (I ran with revision 935400, insane build).

          Show
          Kristian Waagan added a comment - I have been running the test where Dyre had some issues with the concept patch, but I have not observed any problems with the current patch committed to the code line (I ran with revision 935400, insane build).
          Hide
          Knut Anders Hatlen added a comment -

          Thank you very much for running these tests, Kristian! No other problems related to this fix have been seen after the commit, as far as I'm aware, so I'm resolving the issue.

          Show
          Knut Anders Hatlen added a comment - Thank you very much for running these tests, Kristian! No other problems related to this fix have been seen after the commit, as far as I'm aware, so I'm resolving the issue.
          Hide
          Knut Anders Hatlen added a comment -

          [bulk update] Close all resolved issues that haven't been updated for more than one year.

          Show
          Knut Anders Hatlen added a comment - [bulk update] Close all resolved issues that haven't been updated for more than one year.

            People

            • Assignee:
              Knut Anders Hatlen
              Reporter:
              Dyre Tjeldvoll
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development