Posts tagged ‘memoization’

Introduction

In this post I’ll revisit memoization topic described some time ago in this post, with slight modification:

  • playground – ejb3.1 compilant container
  • resolve key-generation problem only tackled in previous installment.

Requirements

I want to be able to cache calls to my method in a way that is transparent with configurable cache duration.

Solution description

EJB3 Interceptor

In ejb3+ environment, the ability to put transparent wrapper to a method call is called interceptor – it lets you access target method as well as parameters. It’s even possible to communicate with your target using context but we’re not going to need it in this call.

So a CachingInterceptor aggregates both CacheManager as well as KeyGeneratorEJB3 and as you can see both are just interfaces meant to be used with any caching solution and any key generation algorigth of you choice. Currently CacheManger is a generic interface that lets user impose limitations on the type of keys used for cache.

Currently our cache implementation uses EHCache which gives user ability to do configuration in a separate file, so we’re going to stick with that.

As you can see there are different patterns for ehcache integration. We’re going to use cache-aside because this one is the easiest way to replace ehcache with any other caching mechanism.

KeyGeneratorEJB3 defines just one method that should be used as entry point for interaction with CachingInterceptor.

Cache key generation

As mentioned previously key generation was not taken under serious consideration in my previous entry  – that’s why I ended up with semantical toString which was easy way to go – but in case there’s no access to the underlying code might be an issue.

So this time I decided to use a slightly modified Visitor pattern* – I want to have a stateless bean so my keygenrator is supposed to return a value from its visit method (named generate in my case) which should be used as a key. This implies that all accept methods (named generate in my case) need to return string as well, which makes things not so transparent.

Summary

As you can see in this post EJB3 environment gives you even more flexibility to use a caching middle-man and with improved key-generation policy it’s finally in a right place.

 

*I did not put any hyperlink so it wont confuse anyone looking for a valid visitor pattern.

Problem description

Another approach to the memoization topic mentioned previously came to me quite recently based on a problem with webservice call.

Imagine you have a webservice request/response exchange that’s taking a long time not only due to network latency but also due to the fact that your ws-logic performs a complicated ldap query.

So there are at least 3 reasons that might cause you a headache:

  1. slow internet connection
  2. slow ldap search
  3. big number of results that need to downloaded

In order to improve this situation results of method call might be cached inside ws-client’s code using ehacache. Cached entries will be identified based on method’s signature and passed arguments. The arguments should implement Serializable interface but this is already fulfilled since objects are passed through webservice calls.

Caching should be transparent to the caller – which should not know whether results he got were fetched from remote server or local cache. Additionally it should be configurable which methods calls should be cached or not and last but not least – since cached entries are identified by some key – it should be possible to define custom key-generator that would give the user freedom in defning key algorithm.

All the above requirements are summarized below:

  • webservice client api defined as interface
  • webservice client implementation that performs call to server
  • methods are chosen based on annotations
  • wraper defined as dynamic proxy so calls to client api are transparently may be cached and user is not aware if results come from cache or real call

Solution description

The solution will be spring-specific since Spring supports ehacache out-of-the-box.

Existing solutions

There exists already at least 3 solutions:

and somehow all of them combined fill the picture of what I’d expect from such a library:

Requirements
  1. Easy configuration with possibly as little xml as possible – smth like <context:component-scan> element with reasonable defaults
  2. Defining one annotation that enables method caching
  3. Including/Excluding methods from caching using annotation
Solution description

The approach descried in this post is realised by providing 3 main elements:

  1. Custom namespace handler implementing NamespaceHandlerSupport
  2. Custom bean definition parser extending AbstractSingleBeanDefinitionParser
  3. Custom BeanPostProcessor implmenting BeanFactoryAware interface
  4. Custom xsd

All points above respond to the requrements:

Points 1 and 2 let you declare usage of method cache with just one line of xml (after defining memoize namesapace) and creates EhCacheManagerFactoryBean and EhCacheFactoryBean behind-the-scenes freeing you from writing these explicitly inside you xml application context.

<memoize:use-method-cache
   config-location="classpath:ehcache.xml"
   cache-name="pl.bedkowski.code.memoize.sample.METHOD_CACHE" />

Point 3 finds classes annotated with Memoize annotation inside current context and wraps them inside Memoizer proxy, as well as fetches EhCacheFactoryBean instance created in the previous step.

@Component("wsClient")
@Memoize
public class WebServiceClientImpl implements WebServiceClient {

The Memoize annotation contains 2 properties:

  • keyGenerator – key generator class (must implement KeyGeneratorinterface)
  • type – one of Type.INCLUDE_ALL/Type.EXCLUDE_ALL

I think the last one needs some further explanation – it lets you define strategy for handling methods.

  • Default is Type.INCLUDE_ALL – which means that all methods that have non-void return type will be cached unless explicitly marked with Exclude annotation.
  • The reverse is Type.EXCLUDE_ALL which means that no method call will be cached unless marked with Includeannotation.

Sources, packages

Source available on github
Binaries available in repo

UPDATE: See updated version using ejb 3.1 compilant with any application server here.

Jednym z problemów z którym trzeba się zmierzyć podczas pracy programisty to spadek wydajności, na który standardowy środek zaradczy to prosty cache oparty o HashMap’e, w której kluczami są parametr(-y) przesłany do metody. Myślę, że zasada działania jest dość powszechnie znana, ale tak dla pewności ją powtórzę:

– sprawdź czy dal danego argumentu (argumentów) wpis znajduje się w mapie
– jeżeli nie wykonaj metodę
– jeżeli jest to zwróć wartość znalezioną w mapie

Mapa sprawdza się znakomicie, jednak pozostawia mały niesmak w ustach, bo co jeżeli zechcemy zrezygnować z cache’owania tego typu, albo wymyślimy super algorytm dzięki któremu cache nie będzie już potrzebny?

Te i inne problemy opisuje w swoim artykule „Memoization in Java” Tom White, przedstawiając także elegancka refaktoryzację powyższego algorytmu w celu oddzielenia mechanizmu cache’owania od obiektu docelowego. Jednak jego celem jest technika idąca krok dalej, a oparta  o wywołaniu metody przez dynamicznie zbudowane proxy (dynamic proxy), które wewnętrznie zbuforuje wynik dla danych argumentów i następnym razem już nie trzeba będzie czekać nieskonńczenie długo na wynik. Jest to szczególnie przydatne w sytuacji, gdy identyczne wyniki są zwracane przez metodę operująca na innej instancji obiektu, porozwalanych w różnych miejscach w kodzie, a poprzednie wywowałnie dawno zgineło w czeluściach garbage-collectora.

I jeszcze jedno – artykuł jest datowany na 2003, więc może się rodzić pytanie skąd ta Java5 w tytule? Otóż wraz z tą wersją jezyka, usprawniono mechanizm dynamicznego proxy na tyle, że działa on 1,5 do 2 razy wolniej od zwykłego wywolłania metody w porównaniu z 40-to krotnym opóźnieniem w przypadku starszych wersji. Wyglada na to, że warto się z tym zmierzyć 🙂