Jofti

User Guide

5  Disk Overflow

For applications that cache large amounts of data or have data peaks that can temporarily overflow the allocated in-memory storage, it is necessary for Jofti to be able to spool its index data to and from disk in an efficient manner.

Being a B-Tree variant, the tree index stores its data in leaf nodes in a data structure we shall refer to as a Page. The disk overflow feature allows us to keep a certain number of pages in memory at any one time and the pages that we cannot fit into memory are be stored onto and read from disk as required.

The characteristics required by Jofti for this mechanism are:

• To make large data sets usable in restricted memory environments.
• To provide bounded times for storing and retrieving data pages, irrespective of random or ordered access patterns.
• To be able to provide good performance for both insert and retrieval.
• To optimise access to commonly used parts of index.
• To be thread safe and provide reasonable concurrency.

The module in Jofti that provides this mechanism is the store manager. There are various store managers supplied, which provide different storage strategies and therefore different performance characteristics. Apart from the PassThroughStoreManager, each store manager pins a configurable proportion of Pages in memory to optimise access to commonly used pages.

The simplest approach would seem to be to utilise the Cache implementation for the index itself for the page spooling and retrieval. In order to test this we created an implementation of a Store Manager backed by EHCache (v1.2 beta 4) and OSCache (v2.2). However, experimental results showed that EHCache-backed store, while performing adequtely for inserts and reads in an ordered manner (either ascending or decending) across a data set, performs extremely poorly for a random insert pattern which forces a lot of disk accesses. The results of the performance profile are shown in section 6.2 below.
The OSCache-backed store performance was, unfortunately, not within tolerable limits and we have not included those results below.

Disk Overflow configuration is covered in Chapter 2 in the section Configuring Disk Overflow.

 

5.1  StoreManager Types

The available managers are:

• PassThroughStoremanager
  • No pages are pinned in memnory for this strategy. All reads and writes are directly to disk and provides a useful benchmark for the other strategies. In addition, this mechanism is appropriate if memory is the main issue and speed is less important.
• HashedStoreManager
  • Pages are pinned as a function of the Page identifier in a storage table. Pages that hash to an already occupied space in the table replace any existing page. This strategy has a smoother performance decay curve for a random or well spread access pattern across a data space and is reasonable for ordered access patterns, where the number of pinned Pages is at least 40% of the total number of pages used.
• LRUStoreManager
  • Pages are pinned according to their access order. This strategy is useful in an ordered access manner where hits on recent pages are common but is not as useful for random accesses once the total number of pages greatly exceeds the proportion pinned in memory.

Obviously, no strategy can entirely compensate for applications that pin small proportions of the total pages in memory and such applications will rapidly degrade to behaviour you would expect from the PassThroughManager. However, pinning large numbers of the Pages relative to your available memory will also result in poor performance as the Garabage collector will end up running very frequently, slowing operations down considerably. It is recommended that you profile your intended data set sizes and access patterns to determine a reasonable percentage of Pages to retain in memory.

5.2  Performance Profile

The results presented here are to show the relative performance characteristics of the Stores available in Jofti to enable you to make a decision as to the type of Store to use. They are not intended to be actual performance timings you would obtain on your own hardware, which may well vary considerably, depending on OS used, CPU speed/number and disk configuration. However, they should be indicative of the relative performance.

The tests look at both medium scale (200,000 entries) and large scale (1,000,000 entries) data sets for a variety of usage patterns under the same memory restrictions. The results for each test are broken into two parts, with the first graph consisting of the timing per insertion of 10,000 elements, followed by the timing per read of 10,000 elements under the same access patterns.

The nature of the index means that the insert of a single dimension element. such as an Integer, results in at least two leaf node reads, one to obtain the page containing the key dimension of the index and one to retrieve the node the data is to be stored on, and two page stores, one for the key and one for the data dimension. For the random tests this count could be higher as if the key is already in the index the data associated with the key is first removed, and then the data and key is re-inserted. Depending on the strategy employed by the store manager not all of these operations result in a disk access.

It is important to realise that we are only testing the index performance, not the cache itself, so only the index nodes are paged to disk and the cache implementation used is a mock cache object that stores no data.

All tests were run with the following configuration:

• JVM: Sun JRE 1.4.2 -Xmx128M
  
• OS: Suse 9.1
  
• CPU: Pentium 4 2.4GHz
  
• Disk: Fujitsu MHT2060AT 60GB 4200rpm ATA100
  

5.2.1  Medium scale tests

For each test we configured 3000 pages in memory which represents around 90,000 data elements (about 50% of the total nodes).

Ordered Ascending Data.

Insert of 200,000 unique integers in the index in ascending order, immediately followed by retrieval of each entry in the index in the same order.

As expected, the PassThroughStoreManager offers the worst performance being an order of magnitude slower than an in memory index, although it does demonstrate a reasonable upper bound considering all access are directly to disk. Remember, that the PassThroughStoreManager may well be useful if you are operating a low memory environment and do not want to pin any pages into memory.

The Cache-backed store manager implementation show a distinct slow down when starting the read cycle as the pages at this point are accessed from disk, rather than being served from the Cache's in-memory store. Surprisingly, the HashedStoreManager shows a better performance than the LRUStoremanager given the ordered access pattern, although this may be because of the use of Sun's LinkedHashMap, which perhaps could be optimised further.

Ordered Descending Data.

Insert of 200,000 unique integers in the index in descending order, immediately followed by retrieval of each entry in the index in the same order.

The boundary condition at the end of the write cycle (where most disk access occurs), again results in the cache-backed store's significant slowdown. The PassThroughManager has, as expected, a relatively flat performance behaviour.

Random Data.

Insert 200,000 random, possibly non unique, integers in the index from a data space range of 0-2,000,000 equally likely numbers, immediately followed by attempted retrieval of 200,000 random integers in the same range, some of which would not be represented in the index.

The random data has the worst performance profile, and presents a degenerate case for the index access with the most limited scope for re-use of in memory pages. The cache-backed store manager has an extremly poor performance degredation once the number of pages exceeds the total amount that can be retained in memory, showing a rapidly steepening insert time to a maximum of just over 100 seconds.

The random order reads shows a relativley flat,but slower access pattern for the PassThroughStoreManager.

 

5.2.2  Large scale tests

For each test we configured 3000 pages in memory which represents around 90,000 data elements (about 10% of the total nodes). The average time per/10,000 presented is the time of the 50,000 section divided by 5.

The EHCache-backed store manager was excluded from these test as the performance in the random test became so poor in the 200,000-300,000 range that it ceased to present a reasonable comparison.

Ordered Ascending Data.

Insert of 1,000,000 unique integers in the index in ascending order followed by retrieval of each entry in the index in the same order.

Ordered Descending Data.

Insert of 1,000,000 unique integers in the index in descending order followed by retrieval of each entry in the index in the same order.

Random Data.

Insert 1,000,000 random, possibly non unique, integers in the index from a data space range of 0-10,000,000, followed by attempted retrieval of 1,000,000 random entries from the index.

Even for the random insertion of data with only a small percentage of nodes in memory we can see that all the algorithms maintain a bounded performance. The strategies that provide a pin functionality show a trend towards the performance of the PassThroughStoremanager as the number of pinned pages declines as percentage of the total.

We can see that the performance for the strategies shows a flat performance over time even though we are only able to keep a small percentage of pages in memory.