Hi ! last week I was able to implement the delete operation with transaction support, this week I'm working on the next step : implementing the cache.
We don't want to store the whole B-trees in memory, that would not scale well... The problem being that Nodes have references to child pages (which may be Nodes or Leaves), and as soon as we use a reference to a Page instance, the GC cannot discard the instance. There are two solutions here : - use WeakReferences - use a cache I have ran some benchmarks with Weakeferences, and it seemed that as soon as the memory became scarce, performance quickly got really bad. The reason is that weakReferences are only reclaim when the GC needs some space, and also because when we create a lot of Pages in memory, that is detrimental to the other parts of the code which need memory. Atm, the cache seems a better approach. I'm using EHCache, with a Cache<long, Page> where the 'long' is the Page's offset. This cache can only hold a maximum number of pages, so when we reach this number, the oldest page is discarded from the cache, and become a target for the GC. If a Page is not present in the cache, ie if cache.get( offset ) returns null, we just need to load this Page using its offset. The drawback is that this cache has to be tuned, depending on the Database usage. This might be tricky, but at least the application is in charge. Of cours, the bigger the database, the higher is the risk we have to load page from the disk. OTOH, if performance is critical, it's quite cheap those days to add more memory in a machine. As the Cache use an offset to reference pages, each newly created Page needs to have a valid offset, so we have either to reuse the page offset if it's in the WAL, or access to a physical offset on disk (either a free page offset, or a new page at the end of the file). This is not the end of the story... Caching Page is one thing, we also need to be very careful in the way we process Pages here we read them from disk. Typically, we should avoid a deserialization of keys and values when it's not needed : most of the time, we will only access a few keys and one value per page. Deserializng all the keys and values is time consuming and unecessary. We use a Holder for keys and values which contain an offset to the data, and if this get sdeserialized, we also keep the instance of this key and value. Doing so save a *lot* of time. In any case, tis is what I'm woking on atm, and I hope to be done this week (and hopefully before teh end of this week). That would leave me with a few more steps : - free page management and reclaimer - bulk loaded - tests and code cleanup, documentation Last, not least, the ApacheDS Mavibot backend has to be updated. I think all of this might be completed in the next two weeks, or at least in a state not that far from being usable. I'll keep you updated. -- Emmanuel Lecharny Symas.com directory.apache.org
