Discussions

News: BTrees on J2EE

  1. BTrees on J2EE (10 messages)

    BTrees are one of the best kept secrets in programming - despite almost everybody learning about them in college - they seem to feature in Computing 101 as an academic exercise then be forgotten.

    They have considerable value as an intermediate data storage mechanism lying between HashMaps and relational databases in terms of capacity, performance and management overhead.

    To mark the release of version 3 of their BTree product Virtual Machinery have prepared a paper outlining appropriate situations for the use of BTrees in the J2EE environment.

    In particular it focuses on the use of the Single Stateless Session Bean pattern proposed by Kyle Brown in the Websphere Technical Journal (see the section headed Does your application contain a relatively small set of objects that are very rarely, or never updated, but whose state is frequently read?).

    You can read Virtual Machinery's paper here and download full working code which implements the principles here .

    Virtual Machinery has been producing BTree implementations in Smalltalk and Java since 1990. The current Java release supports J2SE, J2EE and J2ME environments. A wide range of licensing and source code options are available. A Toolkit is also available for the maintenance and repair of BTrees created by the Virtual Machinery product. You can find out more details here and download demo code here .
  2. BerkleyDB Java edition[ Go to top ]

    Berkley DB Java Edition
  3. Berkley DB Java Edition
    As part of this release we undertook some comparative performance related tests with SourceForge and Berkeley BTree implementations. We did these tests as fairly as possible (sometimes to our own detriment) as they were only intended for internal consumption but since you put the challenge up to us -

    Comparison of performance of Virtual Machinery (VM), Source Forge (SF) and Berkeley Java BTree Implementations

    All were most recent implementations as of 20th April 2004.
    Timings based on equivalent code (as far as possible) and relate only to the actual database operation - preparation of keys and data was excluded. Times are in milliseconds.
    The tests were run on a Pentium 4 1.8Ghz Mobile with 512Mb RAM on Windows 2000 using Sun JDK 1.4.2


    VM SF Berkeley
    Jar Size 38k 72k 560k
    Resultant file size 1859k* 1475k 4320k

    All Entries Cached**
    Commit on each entry (ms)
    Add 0.039 43.67 46.77
    Del 0.033 50.33 46.64
    Get 0.011 0.41 0.09

    Commit at end
    Add 0.020 0.029 0.167
    Del 0.014 0.023 0.112
    Get 0.007 0.018 0.030

    No Entries Cached***
    Commit on each entry (ms)
    Add 0.68 46.14 59.90
    Del 0.65 53.28 58.49
    Get 0.37 0.52 5.77

    Commit at end
    Add 0.027 0.59 8.01
    Del 0.019 0.77 4.34
    Get 0.024 0.42 1.22



    *.IND + .DAT file

    **VM used page sizes of 512/4096 39 Index Pages cached, 337 Data pages cached. SF Used an MRU cache with 30000 entries. Berkeley had the default cache - 64Mb - which was bigger than the 4Mb dataset produced.

    ***SF used cache of 1 due to minimum requirement, Berkeley used cache of 1024 bytes due to minimum requirement

    In each case the databases were deleted prior to each test run
  4. Comparison figures - reformatted[ Go to top ]

    Sorry about the format in the previous method - I thought tabs might work - hopefully a table will!

    Comparison of performance of Virtual Machinery (VM), Source Forge (SF) and Berkeley Java BTree Implementations
    All were most recent implementations as of 20th April 2004.
    Timings based on equivalent code (as far as possible) and relate only to the actual database operation - preparation of keys and data was excluded. Times are in milliseconds.
    The tests were run on a Pentium 4 1.8Ghz Mobile with 512Mb RAM on Windows 2000 using Sun JDK 1.4.2

    <TABLE BORDER BGCOLOR="#808080"><FONT COLOR="#000000">

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER WIDTH="85" BGCOLOR="#FFFFFF" ></TD>
    <TD ALIGN=LEFT VALIGN=CENTER WIDTH="120" BGCOLOR="#FFFFFF" >VM</TD>
    <TD ALIGN=LEFT VALIGN=CENTER WIDTH="120" BGCOLOR="#FFFFFF" >SF</TD>
    <TD ALIGN=LEFT VALIGN=CENTER WIDTH="120" BGCOLOR="#FFFFFF" >Berkeley</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Jar Size</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>38k</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>72k</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>560k</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Resultant File Size</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>1859k*</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>1475k</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>4320k</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>All Entries Cached**</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>
    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Commit on each entry (ms)</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Add</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.039</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>43.67</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>46.77</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Del</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.033</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>50.33</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>46.64</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Get</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.011</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.41</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.09</TD>
    </TR>


    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Commit at end (ms)</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Add</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.020</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.029</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.167</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Del</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.014</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.023</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.112</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Get</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.007</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.018</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.030</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>No Entries Cached***</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Commit on each entry (ms)</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Add</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.68</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>46.14</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>59.90</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Del</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.65</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>53.28</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>58.49</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Get</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.37</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.52</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>5.77</TD>
    </TR>


    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Commit at end (ms)</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    <TD ALIGN=RIGHT VALIGN=CENTER><TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Add</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.027</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.59</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>8.01</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Del</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.019</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.77</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>4.34</TD>
    </TR>

    <TR>
    <TD ALIGN=LEFT VALIGN=CENTER>Get</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.024</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>0.42</TD>
    <TD ALIGN=RIGHT VALIGN=CENTER>1.22</TD>
    </TR>

    </FONT>
    </TABLE>


    *.IND + .DAT file

    **VM used page sizes of 512/4096 39 Index Pages cached, 337 Data pages cached. SF Used an MRU cache with 30000 entries. Berkeley had the default cache - 64Mb - which was bigger than the 4Mb dataset produced.

    ***SF used cache of 1 due to minimum requirement, Berkeley used cache of 1024 bytes due to minimum requirement

    In each case the databases were deleted prior to each test run
  5. All Entries Cached**
    Commit on each entry (ms)
    Add 0.039 43.67 46.77
    Del 0.033 50.33 46.64
    I did some tests with Berkeley DB myself. Your above numbers seems to be using disk syncs while your BTree numbers don't sync. That's not a proper comparision.

    Also, does BTree provide options to sync with the disk like Berkeley?

    -- Andreas
  6. Thanks for the feedback Andreas. I will re-run these tests with the sync off for Berkeley DB and also with ours on - this is one reason I hate publishing tests - even when you try to be fair you end up being unfair so apologies to the guys at Berkeley.

    I presume by syncing you mean that the complete data integrity is maintained and all data is flushed to the disk. When you do commit on our BTree all the page data is written to disk but the btree related data is not. We provide a flushBTree() method that does exactly that.

    Regards
    Ken Hall
    Virtual Machinery
  7. Thanks for the feedback Andreas. I will re-run these tests with the sync off for Berkeley DB and also with ours on - this is one reason I hate publishing tests - even when you try to be fair you end up being unfair so apologies to the guys at Berkeley.I presume by syncing you mean that the complete data integrity is maintained and all data is flushed to the disk. When you do commit on our BTree all the page data is written to disk but the btree related data is not. We provide a flushBTree() method that does exactly that.
    What I meant is to call fd.sync() to ensure all data in the OS write cache is saved on disk. If you do that then you should get appr. the same numbers as Berkeley and JDBM for single transactions. The interesting thing here is not the time of single transactions but the overall throughput (scalability) when using many transactions in parallel (group commit). Does it scale or is it just <single-tx-time>*<number-tx>?

    -- Andreas
  8. The Virtual Machinery does not use sync() on the File Descriptor but it is very simple to extend the File access methods (even without the source code) and over-ride the flush() method to do this.

    Our transaction control is scalable the commit only writes changed pages rather than caching the transactions and committing them one by one - which is what I think you meant by your question.

    I re-ran the tests with sync switched off which improves the Berkeley DB figures to give a fairer comparison. Virtual Machinery figures are in the left column, Berkeley DB on the right.


    Jar Size 38k 560k
    Resultant file size 1859k* 4320k

    All Entries Cached**
    Commit on each entry (ms)
    Add 0.039 0.12
    Del 0.033 0.26
    Get 0.011 0.05

    Commit at end
    Add 0.020 0.10
    Del 0.014 0.05
    Get 0.007 0.03

    No Entries Cached***
    Commit on each entry (ms)
    Add 0.68 5.08
    Del 0.65 2.61
    Get 0.37 0.48

    Commit at end
    Add 0.027 4.95
    Del 0.019 2.33
    Get 0.024 0.62


    Regards
    Ken Hall
    Virtual Machinery
  9. Thank you, lets do more of this.[ Go to top ]

    Ken,

        Thanks for taking the time to run such a comparison, we should do more of this. Healthy competition is good for all of us. Your second run of performance numbers shows us within a respectable range of your numbers, especially given that we are still in the beta period for the first version of this product. Was this a single threaded test? Have you run the same tests varying the number of threads? Berkeley DB JE is optimized for such use. Its why we choose the log based write once style for storage rather than the more traditional page based solution you're using. We gain concurrency and record level locking and ultimately application scalability and speed. Also, the difference in size between your final data file and ours is likely due to the fact that our cleaner thread had not triggered yet. As log file utilization reaches a threshold schedule such work and obsolete data is purged. As it is, you're measuring all data stored ever in the database.

        Please contact me directly if you are interested in working together to define performance tests that we can jointly publish.

    -greg

    Gregory Burd
    Product Manager
    Sleepycat Software, Inc.
    gburd@sleepycat.com
  10. BTrees on J2EE[ Go to top ]

    It looks very interesting, although the 4GB (64k x 64k) limit is very concerning. It would be nice to see a 281TB (16m x 16m) option, since occasionally you want larger pages, or more of them, e.g. to achieve 4GB with 8KB pages (524k x 8k). Any future plans for 24-bit or 32-bit referencing?

    The licensing choice seems very simple in terms of price. Also, that is the first time that I've ever seen an obfuscation requirement for distribution. What was the rationale behind that? (Particularly for a product that is so affordable!) I don't know if it makes a difference, but I would say that the obfuscation requirement would make it much less palatable for licensing.

    At any rate, congratulations on the new release, and good luck! I'll definitely keep this library in mind ....

    Peace,

    Cameron Purdy
    Tangosol, Inc.
    Coherence: Clustered JCache for Grid Computing!
  11. BTrees on J2EE[ Go to top ]

    It is relatively easy to modify the page size and number restrictions if you have the source code option. It is our hope to make this easier in the future (when we started in 1990 4Gb was an awful lot of memory!) as we realise that BTrees are ideal for storing BLOBs.

    Thank you for your kind words on the licensing policy - it is deliberately additive so that you can buy as you go - allowing developers to leave off purchasing a commercial distribution license until they have a saleable product.

    The restriction on obfuscation is really to encourage the distribution of extensions of classes in existing jar files rather than re-writing code. We've gone to a lot of effort to make sure that developers can extend the classes in our jars

    Thanks again for your comments
    Ken Hall
    Virtual Machinery