CORBA - The Evictor Pattern

2001-03-15

Since CORBA doesn’t really support reliable reference counting implementations we’ll compare one of the recommended methods of servant life-time management with our reference counted iteration interface.

The problem

If you can’t trust the runtime to make sure that your clients behave themselves, then the server has to take object lifetime issues into its own hands. The evictor pattern does just that. The server decides how long your object can live, when the server decides you’ve had enough it simply destroys your object for you and your next call fails… It doesn’t matter if you forget to release your objects when you’re done, they’ll get cleaned up eventually. It doesn’t matter if you terminate without letting the server know and, well, it doesn’t matter if you have to write heaps of code to handle exceptional cases of object disappearance…

To me, this sort of idea seems to be the kind of thing that someone who “write’s the server” would come up with. If you’re responsible for the server running forever and never being brought down by malicious clients then you’d develop this kind of siege mentality. It doesn’t matter if your server becomes unusable because nobody gets a chance to use the objects you give out for long enough to do any work, at least you wont get overrun by clients who just request objects because they know they can crash your precious server eventually…

Of course it depends how you implement the evictor pattern, but on its own, it’s always going to make life easier for the server writer and harder for the person who has to write the clients. The usage patterns of the client determine how impossible it becomes…

You’re out…

The simplest evictor works along these lines. The server has finite resources, if those resources are about to be exceeded then the server should garbage collect existing objects that haven’t been used for a while to make way for new objects. The easiest implementation is probably something that uses a least recently used algorithm for eviction of “inactive” servants and is implemented in terms of a ServantLocator. As we saw in a previous article the ServantLocator gets called before and after each method call is dispatched to a servant object. It’s in the ideal place to manage a least recently used list of servant objects. In Evict1.zip we use the servant locator that we developed for the reference counting examples as a starting point for an evictor implementation that uses a least recently used list to determine when to evict servant objects.

Least recently used…

In our reference counting servant locator we have a vector of servant pointers and a list of free spaces within that vector. When a new servant is added to the servant locator we look in the free list and if we find a spare slot in the vector we store a pointer to the servant in that slot. If we don’t find a free slot we simply expand the vector to make space for the new servant.

The evictor implementation works a little differently. For a start, there’s a limit on how much we want to expand the array of servants. We also need to know which servant was used last so that we can evict it if we need to free up space for a new servant. To enable us to do this we need to add a list of servant pointers that is adjusted each time a method call occurs on a servant. As each call occurs we need to move the servant the call to the end of the list. This leaves the least recently used servant at the head of the list.

Evictor Pattern, least recently used list 2

When we wish to evict a servant object so that we can create room for a new servant we simply take the object that is pointed to by the head of the least recently used list and evict that.

All of the logic for accessing the servant objects from the servant locator, and for evicting servants when we run out of resources, is contained within the LRUList class. The example in Evict1.zip allows the server to provide up to 10 of each type of iterator at a time. If more are requested then the least recently used is deactivated. You can experiment with this server using the new client commands, “itx” - which creates an iterator and deliberately leaks it, i.e. it doesn’t call destroy when it’s done. If you call the server using the client’s itx method for more than 10 times you will begin to see the leaked iterators evicted and their resources released. The server displays the eviction queue after each manipulation to it.

Too simple by half

Unfortunately the implementation shown in Evict1.zip is too simplistic. Now that we allow the server to clean up servants whenever it desires, we need to protect ourselves from a client that attempts to use an object after the server has evicted it. Up until now our object id was simply the index into the servant pointer vector. That doesn’t work any more. If the server evicts servant 7 the client wont find out about it until it tries to make a call on the object, when it does so it will use the object id that the server gave it, 7, but inside the server that object id now refers to another servant…

We can get around this problem by constructing a slightly more complex object id. Instead of just including the index into the servant vector, we can include a timestamp as well. The timestamp is the time that the servant was added to the locator and is stored in the servant array along with the servant pointer. Now, when we evict a servant from a slot we reuse the slot index but the timestamp changes. When a client attempts to use an object id for an evicted servant the index portion will likely match an active servant, but the timestamp cannot be the same, this allows us to correctly fail the call by throwing a CORBA::OBJECT_NOT_EXIST exception. The fixed up code is presented in Evict2.zip along with client code that is adjusted to make exercising it easier - use the “holdit” client command to obtain and iterator and hold onto it for a number of seconds before using it. You can then obtain and leak, iterators so that the original, held, iterator is evicted. When the client times-out the invalid object id is used and the server throws the exception.

Note that in these examples we use time() to generate the creation timestamp. This only has a resolution of seconds so if the turn over of objects in the server is very rapid we could have problems. We might be better off, under Win32, using GetTickCount() instead.

Alternative eviction strategies

Evicting due to a fixed number of servants being exceeded is probably too harsh a strategy to use in a production system. No matter what number you choose the system will always get into a state where it starts to thrash (evicting servants before they can be used for useful work) if the number of active clients grows to one more than the number of servants that the server is willing to support. Far better to evict servants that have not been used for a specified period of time. In periods of heavy use the server will support as many servants as required but if objects are left idle - perhaps due to client failure - they will be evicted.

This requires that we associate a second timestamp with the servant. This timestamp is updated each time a method is called on the servant. When deciding whether to evict, we can now examine this timestamp to see if the least recently used servant has been inactive for the appropriate amount of time, if it has, we evict it. The value chosen for the timeout will effect how the eviction strategy works, too short and the client may not be able to do useful work, too long and the server will use more resources.

In Evict3.zip we change the eviction strategy to use the timeout scheme described above. We now have a maximum number of servants that we wish to support, in this case 10, and a timeout of 5 seconds - both values chosen to simplify the testing and demonstration of the evictor at work. Since we now evict due to lack of use, rather than lack of space we could remove the maximum servant restriction. In this example we leave it in place and refuse new requests for objects if we have reached our limit. The problem with doing this is that the server is then open to denial of service attacks from malicious clients that obtain objects simply to use up server resources. The malicious client can continue to obtain objects until it is refused and then continue to use the objects in some way to prevent them timing out…. The thing is, in the presence of such clients there’s not a lot you can do. If you don’t limit the number of servants then they can simply continue creating servants until your server fails due to lack of resources. If you evict servants that haven’t yet timed out then you’re back to the thrashing situation that we had with the previous example and genuine clients will be unable to get any work done anyway.

In the next article we give the client a little more control over exactly when their objects are evicted.

Java version

For a version of the evictor pattern in Java, see here

Download

The following source was built using Visual Studio 6.0 SP3 and tested with OmniORB - the open source Corba ORB from AT&T Cambridge. You need to add OMNI_HOME to your environment so that the idl compiler, headers and libraries can be found.

To compile the IDL files you will need to change the path used in the build command for the idl files - well, you will unless you happen to have installed OMNI ORB into exactly the same location as I have… Select the IDL files in the project workspace, right click on them, select settings and edit the path to the OMNIIDL compiler.

Revision history