Querying Java Objects stored in Terracotta's NAM Part 3

First and Second part of this series I talked about Querying data structures available in Java. First part specifically talked about existing ones like JoSQL, JxPath and Quaere and discussed indexing problem. Second part specifically talked about lucene and jofti as indexing frameworks and wrote small framework to test and get some performance numbers. This test showed that B-tree index (memory and possibly disk based) is suitable and not lucene index. Third part of this series now I am discussing my own small framework- tcquerymap which is rewrite of Jofti. Jofti is old and not maintained and uses jdk14 libraries. Now even documentation link does not work : http://prism-index.com/guide.html.

querymap documentation link : Getting Started With Querymap
querymap source download : Complete Source Code with Eclipse Project
querymap TIM : Copy this TIM to terracotta modules directory to use it
querymap terracotta sample app : Download sample eclipse App. You can use Terracotta eclipse plugin to launch it within eclipse

So the basic idea is maintaining in-memory indexes which index String Ids with "Comparable" as Keys. All primitive wrappers in Java implement this interface so no special conversion is needed.


How it works
It scans java objects and makes comparable objects for each of the property mentioned to be indexed. It inserts these comparable objects in its own tree against String Ids assigned to the java object. So in-effect its nothing more than maintaining many in-memory Maps. In fact the implementation that I wrote uses JDK TreeMap and not b-tree map. But in-future it will be replaced by more performant B-tree.

Querying
One needs to understand that with in-memory object indexes its only possible to implement subset of SQL query and no join queries. To start with, small framework only implements following operations : arithmetic operands : <,>,<=,>=,==. Logical operands : AND , OR. Range : BETWEEN, Set : IN

To implement querying SQL parser needs to be implemented. I choose to avoid writing parser and implemented direct API kind of querying similar to Quaere. I find Domain specific languages more intuitive since when developer writes code for it he know what querying he writes. So interface looks like below. It is not as good as quaere. Quaere is DSL, below API is just few interfaces implemented. Here execute returns List of IDs put into index against the properties.


import static com.google.code.querymap.ObjectQuery.*;

Collection col = from(Domain.class).where(
gt("inner.property2", 60),
lt("inner.property2",89)
eq("inner.property3",random.nextInt(NUM_OBJECTs))
).execute();



So basically it is equivalent of follwing SQL

select from Domain
where inner.property2 > 60
and inner.property2 < property3=rand(NUM_OBJECTS)


How it performs
Naturally is not as performant as Jofti since it used JDK tree map which uses red-black tree. In future when I complete writing my own b-tree implementation I expect to perform as good as Jofti. Jofti further implemented node level locking so multiple concurrent insert opertations can work parellel. This can also be implemented too. But query performance is not bad and I expect it to improve with b-tree implementation.


Integration with Terracotta
Since it uses TreeMap it is cluster-able easily. Attached tc-config.xml has all correct declarations for it. One more advantage is with Terracotta is that object identifier are readily generated by Terracotta. See implementation TerracottaQueryMap. Please dont compare performance of TerracottaQueryMap against HashMap, CHM or Terracotta Distributed Map(Concurrent String Map old name) since all these are just single index maps so easy to stripe or employ mulitple locks.

For using it as TIM you need to add following lines to tc-config.xml


<modules>
<module id="com.google.code" name="querymap-1.0" version="1.0.0">
</module>


In code you can use it as queryable map as follows. Here propList is list of properties to be indexed.


TerracottaQueryMap map = new TerracottaQueryMap(Domain.class,proplist));

map.put(key,domain1);
map.put(key,domain2);
map.put(key,domain3);


To Query.


Collection col =map.entrySet(
from(Domain.class).
where(
eq("inner.property2",random.nextInt(NUM_OBJECTs))
)
);


Future directions planned
Java has hugh limitation for memory intensive application. So achieve scale two approaches : partition index and merge results or use disk to overflow index pages. Other thing I see can be implemented is that when query selects random elements these random elements need to be faulted from Terracotta server thus degrading performance, same elements can be read from local store too like EHCACHE. Later on this topic separately.

If you think this framework is useful please let me know. You can download its source as Eclipse project(sole dependency on tc.jar) and as Terracotta Integration Module here.

Tushar

Querying Java Objects stored in Terracotta's NAM Part 2

First part of this series, I talked about existing frameworks and what I found out is that they lack indexing hence rarely useful for large data-sets. So I tried finding out how to do indexing. My idea was simple : index objects and store reference to object in index then with Terracotta you can cluster objects and index as well. So it becomes "queryable" datastore. My first attempt was to find out how indexing is done. By book it says b-tree index. I found out this(jdbm) framework which is trying to do the persistent DB in Java by implementing B-tree indexes on disk.I took only b tree and implemented simple query parser. What it does is that it traverses b-tree and finds out tuples and then returns them.

After this first attempt, then I experimented with Lucene. Lucene is not tree-index, its inverted index but it has lot of capability and its fast, supports in-memory and disk-based indexes.

So here is my little framework for queryable datastore :



 public interface TCQueryMap extends Map{
  void init();
  Map query(String query);
 }




Naturally its extension of Map which is single index. My implementation wraps a HashMap with ReadWrite locks and Lucene RAMDirectory index. So all get/puts hit index within lock boundaries and then you can query index. This is very simple, I have not gone into complexities like spill-over of index onto disk etc.



 LuceneIndexingConfig config = new LuceneIndexingConfig();
 List propList = new ArrayList();
 // index three properties only
 propList.add("accountName");
 propList.add("person.age");
 propList.add("person.name.firstName");
 
 config.setIndexPropertyList(propList);
 
 TCQueryMap indexer = new LuceneQueryStore(config);
 
 // add object
 Acccount account .....
 indexer.put("user99",account);
  
 // query object 
 Map col = indexer.query("person.age:21");




I also came to know about Jofti from one of comments. Jotfi is what I would eventually like to write. I don't know why its not used by many people. One reason could be its not maintained. I found it pretty useful so I plugged in Jofti as well in my framework.

Now lets compare it with simple Hibernate-JDBC based solution. Obviously its not perfect. SQL is way more complex and expressive language. But here we are talking about cached data and I am sure once data is cached ( it means objectified from join query on relational DB) very few times you will require join, its mostly "where clause" of one or more conditions. Lucene does that very well.

So lets see numbers. I have not done any tuning apart from standard lucene stuff. One of main parameters is how many properties you want to index. This determines index size, memory and speed.

Below is small benchmark showing 60K objects inserts with three properties indexed and then random queries on three properties

Lucene Inserts/Sec = 1000
Jofti Inserts/Sec = 8793.78
Lucene Queries/Sec = 5172
Jofti Queries/Sec =13636.36

Results for 14 properties indexed :

Lucene Inserts/Sec = 740
Jofti Inserts/Sec = 4866.96
Lucene Queries/Sec = 3750
Jofti Queries/Sec = 12500

Since Jofti is Tree index it outperforms Lucene Index. The problem with Lucene is that once index gets bigger insert performance slows down. Also these numbers are taken with one commit on one put operation. If you index lot of objects together and then commit, lucene is also fast, that's how it is to be used - Batch API. On the other hand Jotfi is fast, I could not find any details about being thread-safe and other concurrency issues so I wrapped it around Lock. I don't know why Jofti is not used by many people.

Also what if you can run Hibernate/JPA queries on Map? that would be great. Its already done by hibernate team. They run query against Second level cache but it would big task to find out and extract idea out of it. Just a thought. Second Level Query cache gets invalidated when you modify single entity, imagine if we update the same object in QueryMap cache you dont need Query cache of course querying capability is not great.

Another thought that comes in my mind is clustering in-memory databases like H2 or HSQLDB. Imagine the benefits of it. But then its anti-terracotta. Why? it would be Relational DB with baggage of ORM mismatch.

Entire source code you can download it from here : http://code.google.com/tc-querymap/. Tar file is just bunch of java files and its very early
prototype. Stay tuned to project, I will update it once I finish with proper integration with Terracotta.

So if you find it useful please leave comments, I would love to hear from you.

Links : Kill Your Database with Terracotta

I am going to start a new series from this post. Many times you find great article on the internet that you would like to share with others. "Links" is one such series.


And very first link here is an Article written on Terracotta : An amazing technology for java application clustering. Its here : Kill Your Database. Terracotta is clustering technology with built-in support for HA. Clustering is all about shared data and when you talk about HA, you are actually caring for the shared data, its availability. Terracotta implements it by writing every change to shared data to disk in transactional manner. So if your data whose life is short or medium, (often you need to store derived data from the temporary data which is very large, and we use RDBMS for all of this) you can use terracotta to store it in very fast manner : since you don't have to convert data to relational model its all java. Pretty powerful!!. Other use case is Database off-loading which means you can use terracotta to store all data temporarily and then write to your database in manner which would not affect end-user response time. By doing this you remove database access and operation time from response time ( which mostly is the very significant part of the response time). Article mentioned above touches all these concepts. I will add one more link on terracotta org-site which describes this case ( and all other wonderful use-cases for terracotta). Here it is : Write Behind SOR. If you read my previous post, I had exactly discussed the same idea : Write Behind or Asynchronous writes. That time I knew only coherence supported this. Then I came to know that Gigaspaces also supports it. ( See comments below on the same post). But terracotta would be the most exciting among them all. Why? One reason is all existing application can easily integrate this pattern in there application with very small change in code-base. Second reason terracotta supports lot of java framework out of the box.

..
Tushar