Banana DB

Banana DB is a self-contained key/value pair database implemented in Java.

Features

  • Small, ~100KB .jar file with no dependencies.
  • Top level API similar to working with any Map<K, V> on to of core <byte[], byte[]> index.
  • Thread safe and write locking over multiple JVMs using extended Lucene locks.
  • Optionally transactional.
  • More or less ACID -compliant.
  • Simple annotational API.
  • Pluggable serialization strategies. (java.io.Serializable as default)

Upcoming features

  • Optimized generic serialization.
  • Secondary indices.

About the ACIDity

  • Atomicity, write all postings or no postings at all during commit. In cases of fatal shutdowns such as loss of power, this is not supported, but is ment to solve it by using the durabillity revision log.
  • Consistency, writes only valid data to the store.
  • Isolation, rules for accessing uncommited and locked data.
    • Last commit wins. Will write all changes of a transaction to the store, overwriting any changes committed between the transaction started and committed.
    • First commit wins. Throws you an exception when you try to commit an entity if someone managed to update and commit it prior to you.
    • Updated. (Read committed) Keeps your transaction synchronized with the store by accepting any changes to the store over your uncommitted updates.
  • Durability, abillity to access the data from older revisions.

Releases

There is no official release! You'll have to check it out from SVN, compile and install:

limax:bananadb kalle$ svn co http://svn.apache.org/repos/asf/labs/bananadb/trunk/
A    trunk/FILES.txt
A    trunk/LICENSE.txt
..

limax:bananadb kalle$ cd trunk
limax:trunk kalle$ mvn install

Performance and limitations

Banana DB uses an ad hoc data format that does not try to optimize the distance between postings. This means that the read speed is very much dependent on I/O seek of the storage media or the file cache of the operating system.

The hypothesis is that SSD is now a cheap medium that eliminates the need for more complex data formats such as B+tree or HTree.

There is no issue with read and write speed for small and medium-sized databases located on HDD with a modern operating system that does smart file caching. See benchmark further down in this document.

  • No limit on number of key/value postings in database.
  • No read speed penalty due to deleted or updated key/value postings in the store.

Compared to other databases

The Banana DB API is very similar to other key/value database implementations.

The main reason for the existence of Banana DB is the lack of a key value database implemented in Java with a very simple consumer API distributed under the Apache Software License.

I am not a lawyer. Please double-check any information regarding licensing models mentioned below.

Berkeley DB

http://www.oracle.com/database/berkeley-db.html

Berkeley DB is a key/value postings database with ancestry.

The Banana DB entity store consumer API has a consumer API not too different from the one in Berkeley DB Java Edition. Both are minimalistic and simple to use, Berkeley DB does however have a few restrictions on how to one is allowed to subclass and aggregate entity objects.

Berkeley DB handles huge data dataset on HDD well, Banana DB does not.

Berkeley DB has a dual license model.

The license model for proprietary projects allows you to use Berkeley DB at no cost when used in a service you provide, but not if your software is sold as a boxed product.

The license model for open source projects allows you to redistribute Berkeley DB.

JDBM

http://jdbm.sourceforge.net/

JDBM has similar features as Banana DB but a more complex consumer API compared to Banana DB.

JDBM has a pluggable storage and include support complex data formats such as B+Tree and HTree and thus handles huge data dataset on HDD well, Banana DB does not.

It is licensed with BSD open source license.

API examples

{
  EntityStore store = new EntityStore(new File("./bananadb"));
  store.getConfiguration().setUsingDurablePostings(true);

  PrimaryIndex<Long, User> users = store.getPrimaryIndex(Long.class, User.class);
  PrimaryIndex<Long, Message> messages = store.getPrimaryIndex(Long.class, Message.class);

  store.getTxn().begin();

  User user = new User();
  user.setPK(0l);
  user.setEmailAdress("foo@bar.org");
  user.setPassword("secret");

  users.put(user);
  assert users.containsKey(0l);

  Message message = new Message();
  message.setPK(0l);
  message.setFromUserFK(0l);
  message.setToUserFK(1l);
  message.setSubject("Hello, world.");
  messages.put(message);
  long worldRevision = store.getTxn().commit();

  store.getTxn().begin();
  message.setSubject("Hello, tellus.");
  messages.put(message);
  store.getTxn().commit();

  store.getTxn().begin();
  assert "Hello, tellus.".equals(store.getMessages(0l).getMessage());

  store.setDefaultReadRevision(worldRevision);
  assert "Hello, world.".equals(store.getMessages(0l).getMessage());
  store.getTxn().abort();

}

@Entity
public static class User implements Serializable {

private static final long serialVersionUID = 1l;

  @PrimaryKey
  private Long PK;

  private String emailAdress;
  private String password;

  public Long getPK() {
    return PK;

  ...
}

@Entity
public static class Message implements Serializable {

  private static final long serialVersionUID = 1l;

  @PrimaryKey
  private Long PK;

  private Long fromUserFK;
  private Long toUserFK;
  private String subject;
  private String text;

  ...
}

Benchmarks

org.apache.labs.bananadb.Benchmark takes the following arguments:

  • Minimum value posting byte[] size
  • Maximum value posting byte[] size
  • Number of postings
  • Debug interval

    This is what it does using a single thread:

    1. Creates all postings. byte[4] (java.lang.Long) key and random sized value according to your settings.

    2. Reads all postings in random order.

    3. Reads all postings in reverse chronological order. I.e. the postings that require maximum number of seeks in DB is executed first.

    The access is on the core byte[] store and not via transactions in the entity store! The latter is probably several times slower and needs a benchmark too!

    Below is the output from a 1M posting benchmark on a 2GB RAM, 2Ghz DualCore, 5400 RPM HDD, running OpenJDK on Ubuntu Linux.

    Note that random access writing is much more efficient than reading due to the fact that the file cache at write time contains all the parts that need to be seeked and written to, while the values partition (5GB) more or less never is in the file cache during random access reads.

    You can expect this to be true even for applications busy reading and writing at the same time as the value postings file is being written to in chronological order (i.e. very simple file format) and should thus be easy for the operating system to keep cached.

    limax:trunk kalle$ mvn install
    limax:trunk kalle$ java -cp target/bananadb.jar org.apache.labs.bananadb.Benchmark 1 10000 1000000 10000
    
    1237382243269  INFO  Benchmark: Arguments: [min value posting byte[] size] [max value posting byte[] size] [number of postings]  [debug interval]
    1237382243286  INFO  Benchmark: Random seed: 1237382243286
    1237382243287  INFO  Benchmark: Benchmarking store. minValueSize=1, maxValueSize=10000, benchmarkSize=1000000, debugInterval=10000
    1237382245256  INFO  Accessor: Creating new store..
    1237382245257  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.md..
    1237382245258  INFO  FileHandler: It took 1 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.md
    1237382245259  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.ht..
    1237382245608  INFO  FileHandler: It took 349 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.ht
    1237382245610  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.hc..
    1237382246249  INFO  FileHandler: It took 638 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.hc
    1237382246250  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.k..
    1237382247584  INFO  FileHandler: It took 1334 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.k
    1237382247585  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.v..
    1237382253025  INFO  FileHandler: It took 5440 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000000.v
    1237382253276  INFO  Accessor: New store has been created. Took 8020 milliseconds.
    1237382253276  INFO  Benchmark: Starting benchmark..
    1237382261851  INFO  Benchmark: Wrote 10000 postings in 8 seconds or 0.857 ms/posting. 0.856 ms/posting since the last report.
    1237382271343  INFO  Benchmark: Wrote 20000 postings in 18 seconds or 0.903 ms/posting. 0.949 ms/posting since the last report.
    1237382272212  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.v..
    1237382273825  INFO  FileHandler: It took 1612 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.v
    1237382282682  INFO  Benchmark: Wrote 30000 postings in 29 seconds or 0.980 ms/posting. 1.134 ms/posting since the last report.
    1237382292123  INFO  Benchmark: Wrote 40000 postings in 38 seconds or 0.971 ms/posting. 0.944 ms/posting since the last report.
    
    ...
    
    1237383003175  INFO  Benchmark: Wrote 470000 postings in 749 seconds or 1.596 ms/posting. 2.692 ms/posting since the last report.
    1237383019220  INFO  Benchmark: Wrote 480000 postings in 765 seconds or 1.596 ms/posting. 1.604 ms/posting since the last report.
    1237383022560  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000023.v..
    1237383024617  INFO  FileHandler: It took 2057 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000023.v
    1237383046559  INFO  Benchmark: Wrote 490000 postings in 793 seconds or 1.619 ms/posting. 2.734 ms/posting since the last report.
    1237383065630  INFO  Benchmark: Wrote 500000 postings in 812 seconds or 1.625 ms/posting. 1.907 ms/posting since the last report.
    1237383070151  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000024.v..
    1237383072161  INFO  FileHandler: It took 2010 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000024.v
    1237383088374  INFO  Benchmark: Wrote 510000 postings in 835 seconds or 1.637 ms/posting. 2.274 ms/posting since the last report.
    1237383112307  INFO  Benchmark: Wrote 520000 postings in 859 seconds or 1.652 ms/posting. 2.393 ms/posting since the last report.
    ...
    1237383608557  INFO  Benchmark: Wrote 740000 postings in 1355 seconds or 1.831 ms/posting. 2.318 ms/posting since the last report.
    1237383628946  INFO  Benchmark: Wrote 750000 postings in 1375 seconds or 1.834 ms/posting. 2.039 ms/posting since the last report.
    1237383638670  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000036.v..
    1237383640570  INFO  FileHandler: It took 1900 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000036.v
    1237383657785  INFO  Benchmark: Wrote 760000 postings in 1404 seconds or 1.848 ms/posting. 2.884 ms/posting since the last report.
    1237383676019  INFO  Benchmark: Wrote 770000 postings in 1422 seconds or 1.848 ms/posting. 1.823 ms/posting since the last report.
    ...
    1237384190548  INFO  Benchmark: Wrote 980000 postings in 1937 seconds or 1.977 ms/posting. 2.010 ms/posting since the last report.
    1237384198252  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000047.v..
    1237384199390  INFO  FileHandler: It took 1138 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000047.v
    1237384214242  INFO  Benchmark: Wrote 990000 postings in 1960 seconds or 1.981 ms/posting. 2.369 ms/posting since the last report.
    1237384234525  INFO  Benchmark: Wrote 1000000 postings in 1981 seconds or 1.981 ms/posting.
    
    
    
    1237384717428  INFO  Benchmark: Begin retrieving postings in random order
    1237384907614  INFO  Benchmark: Retrieved (random order) 10000 postings in 190 seconds or 19.018 ms/posting. 19.018 ms/posting since the last report.
    1237385036614  INFO  Benchmark: Retrieved (random order) 20000 postings in 319 seconds or 15.959 ms/posting. 12.900 ms/posting since the last report.
    1237385149594  INFO  Benchmark: Retrieved (random order) 30000 postings in 432 seconds or 14.406 ms/posting. 11.298 ms/posting since the last report.
    1237385261029  INFO  Benchmark: Retrieved (random order) 40000 postings in 543 seconds or 13.590 ms/posting. 11.144 ms/posting since the last report.
    1237385373218  INFO  Benchmark: Retrieved (random order) 50000 postings in 655 seconds or 13.116 ms/posting. 11.219 ms/posting since the last report.
    1237385486088  INFO  Benchmark: Retrieved (random order) 60000 postings in 768 seconds or 12.811 ms/posting. 11.287 ms/posting since the last report.
    1237385601175  INFO  Benchmark: Retrieved (random order) 70000 postings in 883 seconds or 12.625 ms/posting. 11.509 ms/posting since the last report.
    ...
    1237395567837  INFO  Benchmark: Retrieved (random order) 940000 postings in 10850 seconds or 11.543 ms/posting. 11.422 ms/posting since the last report.
    1237395682805  INFO  Benchmark: Retrieved (random order) 950000 postings in 10965 seconds or 11.543 ms/posting. 11.497 ms/posting since the last report.
    1237395796728  INFO  Benchmark: Retrieved (random order) 960000 postings in 11079 seconds or 11.541 ms/posting. 11.392 ms/posting since the last report.
    1237395910212  INFO  Benchmark: Retrieved (random order) 970000 postings in 11192 seconds or 11.539 ms/posting. 11.348 ms/posting since the last report.
    1237396023759  INFO  Benchmark: Retrieved (random order) 980000 postings in 11306 seconds or 11.537 ms/posting. 11.355 ms/posting since the last report.
    1237396137397  INFO  Benchmark: Retrieved (random order) 990000 postings in 11419 seconds or 11.535 ms/posting. 11.364 ms/posting since the last report.
    1237396251174  INFO  Benchmark: Retrieved (random order) 1000000 postings in 11419 seconds or 11.420 ms/posting. 11.378 ms/posting since the last report.
    
    
    1237397304222  INFO  Benchmark: Begin retrieving postings in inverse chronological order (i.e. maximum number of seeks in order to get a post first)
    1237397321664  INFO  Benchmark: Retrieved (inverse chronologial order) 10000 postings in 17 seconds or 1.744 ms/posting. 1.744 ms/posting since the last report.
    1237397339067  INFO  Benchmark: Retrieved (inverse chronologial order) 20000 postings in 34 seconds or 1.742 ms/posting. 1.740 ms/posting since the last report.
    1237397356277  INFO  Benchmark: Retrieved (inverse chronologial order) 30000 postings in 52 seconds or 1.735 ms/posting. 1.721 ms/posting since the last report.
    1237397373485  INFO  Benchmark: Retrieved (inverse chronologial order) 40000 postings in 69 seconds or 1.732 ms/posting. 1.721 ms/posting since the last report.
    1237397390635  INFO  Benchmark: Retrieved (inverse chronologial order) 50000 postings in 86 seconds or 1.728 ms/posting. 1.715 ms/posting since the last report.
    1237397407837  INFO  Benchmark: Retrieved (inverse chronologial order) 60000 postings in 103 seconds or 1.727 ms/posting. 1.720 ms/posting since the last report.
    ...
    1237398618712  INFO  Benchmark: Retrieved (inverse chronologial order) 910000 postings in 1314 seconds or 1.444 ms/posting. 1.044 ms/posting since the last report.
    1237398628788  INFO  Benchmark: Retrieved (inverse chronologial order) 920000 postings in 1324 seconds or 1.440 ms/posting. 1.008 ms/posting since the last report.
    1237398638361  INFO  Benchmark: Retrieved (inverse chronologial order) 930000 postings in 1334 seconds or 1.435 ms/posting. 0.957 ms/posting since the last report.
    1237398647883  INFO  Benchmark: Retrieved (inverse chronologial order) 940000 postings in 1343 seconds or 1.429 ms/posting. 0.952 ms/posting since the last report.
    1237398657182  INFO  Benchmark: Retrieved (inverse chronologial order) 950000 postings in 1352 seconds or 1.424 ms/posting. 0.930 ms/posting since the last report.
    1237398666443  INFO  Benchmark: Retrieved (inverse chronologial order) 960000 postings in 1362 seconds or 1.419 ms/posting. 0.926 ms/posting since the last report.
    1237398675435  INFO  Benchmark: Retrieved (inverse chronologial order) 970000 postings in 1371 seconds or 1.414 ms/posting. 0.899 ms/posting since the last report.
    1237398684210  INFO  Benchmark: Retrieved (inverse chronologial order) 980000 postings in 1379 seconds or 1.408 ms/posting. 0.878 ms/posting since the last report.
    1237398692941  INFO  Benchmark: Retrieved (inverse chronologial order) 990000 postings in 1388 seconds or 1.403 ms/posting. 0.873 ms/posting since the last report.
    1237398701489  INFO  Benchmark: Retrieved (inverse chronologial order) 1000000 postings in 1388 seconds or 1.389 ms/posting. 0.855 ms/posting since the last report.
    
    
    1237398701489  INFO  Benchmark: Rehashing with factor 1.7
    1237398701523  INFO  Store: Rehashing hashtable postings capacity from 8,000,000 -> 13,600,000
    1237398701523  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.ht..
    1237398703445  INFO  FileHandler: It took 1921 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.ht
    1237398703446  INFO  FileHandler: Formatting /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.hc..
    1237398704234  INFO  FileHandler: It took 788 milliseconds to format /home/kalle/projekt/bananadb/trunk/benchmark/1237382245206/00000001.hc
    1237399208524  INFO  Benchmark: Rehashing took 507 seconds
    1237399208613  INFO  Store: Closing store..
    1237399208614  INFO  Store: Store has been closed.