PmMda.Net.Dog.Paging namespace

Introduction

pmMDA must support data objects graphs (DOGs) which consists of many heavyweight data objects. The memory used to handle this objects may be bigger as the memory which is available on the client but not on the server. Furthermore, the DOGs are transferred over a network and pmMDA wants to keep the latency as small as possible. Thus pmMDA must define mechanisms to handle such huge DOGs. This chapter describes the design decisions and implementation of paging. How to use paged indexed properties is written here.

Design desicions

• Lazy loading features of NHibernate are not used because the persistence handler should be exchangeable.
• Accessing items of paged collections may result in reloading items if they are not already in the local cache.
• The default paging amount can be specified in the pmmda.properties file. This amount can be adjusted for every paged indexed property.
• There is no prefetching of items. The items will not be reloaded until they are requested.
• If the owner of paged collection is loaded multiple times with different sort orders then the data objects will be stored multiple times in the local memory. There is no reference management.

How it works

Because there are different types of collection, there are also different implementations to offern an optimal performance and latency time.

Root objects

Because root objects are stored in a readonly collection (PagedReadOnlyCollection)it is not possible to add, insert or remove root objects. This makes the implementation quite simple.
The readonly collection stored the already loaded items in an array list. Furthermore the collection stores a list of ranges which specify the already loaded items. A range is specified through its first and last index. With the help of the range list, the read only collection can recognise very fast whether an item is already loaded.
If a not yet loaded item is requested, the paged collection checks whether the item right before the requested item is locally available. If the item right before the requested item is available then the readonly collection reloads the items using the IDataObjectHandlerImpl.Retrieve(Type type, object lastAvailableId, int count) method. Otherwise the paged collection uses the IDataObjectHandlerImpl.Retrieve(Type type, int startIndex, int count) method to reload the next porition of items.

Sets

Because the items of a set cannot be accessed through their indexes, the locally available items which represents the cache must be in the same order as on the server. Thus all items, expect the first and last item, in the cache must have the same ancestor and successor as the item on the server.

Paged sets store the retrieved items in a LinkedCollection. This allows to navigate fast through the already loaded items. The linked list operates like a hash table too. This allows to check whether an item is already in that list. The hash table makes that operation fast.
Added and removed items are saved in a LinkedCollection too.

Enumerating items

The enumerator gets the next element from a paged set, using the PagedSet.GetNext(IDataObject previous) method, by specifying the current element. This method returns the item that follows the specified element
The GetNext method first looks in the list of locally added items. If the current element is found in that list then the returned item is the item that follows the current element or null if the current element is the last item in the list of added items.
If the current item is not in the list of added items but in the local cache, and the item is not the last item in the cache, the item that follows the current item in this cache is returned. If the current item was not fund in the local cache or it is the last item in the cache then items must be reloaded.
Reloading is done using the IDataObjectHandler.Retrieve(Type, object, Type, object lastAvailableItemId, string, int, out DateTime) method. As you can see in the parameter list, the lastAvailableItemId is specified. This is the identifier of the current item. To get the right sequence of items, the data object manager requests the items by specifying an order using a HQL query. The default order is that the items are ordered by their identifiers. The requested item is the first returned item. If there are no items returned, or all returned items have been removed locally, the next item is the first item in the added item list.

Adding items

Locally added items are stored in an separate linked list. When items are reloaded, the paged set test whether the reloaded items are also part of the added items list. If a reloaded item is part of the added items, that item will be removed from the added items list because sets can only contain each item once.
If an item is added that was locally removed before, The item is removed from the list of removed items and it is not added to the list of added items.
The list of added items is not cleared when the maximum of items is reached. The list of added items is cleared if the owner of the paged set is stored.

Removing items

If an item is locally removed, the paged set will remove that item from the local cache if it is available. Then the removed item is added to a linked list of removed elements. When items are reloaded, the paged set will ignore the items in the removed list. It is possible that all reloaded items are ignored because they have been removed locally. In that case the paged set need to reload the next portion of items.

Clearing the list

Clearing the list will set the paged list to a separate state, because there are no persistent items anymore. A cleared paged set only works with the list of added items.

Bags and lists

Already retrieved items are stored in a sorted hash table which maps the index of the items to the local instance of the items.

The persistent items are accesed with the help of the PersistentItemList class which represents the local cache. This list allows to access the persistent items of an indexed property. But the PersistentItemList does not incorporate added, removed or replaced items. So the index of the paged list (or bag) is not the same as the index of the persistent item list. The paged list (or bag) may calculate the persistent index of a persietent item incorporating the added, inserted, removed or replaced items.

The PersistentItemList is responsible to remove items from the local cache if the "maximum loaded item count" is exceeded or to reload items if an unloaded item is requested. The items in the local cache must not be consecutively. The indexes of the loaded items are stored in a RangeList. The range list saves the ranges (start - end) of the already loaded items.

Paged lists or bags may reload an item at a specified index without reloading the items that are before the specified index. If an item is not local and not already loaded, the paged list (or bag) calculates the persistent index of the requested item. Then the PersistentItemList uses the IDataObjectHandler.Retrieve(Type, object, Type, int startIndex, string, int, out DateTime) method to reload the items. The persistence handler uses a HQL query to reload the items.

IQuery query = session.CreateQuery("select item from $itemType item, $ownerType owner" +
   "where owner.m_id=$ownerId AND item in elements(owner.$fieldName)" +
   "order by item.m_id asc"); // $ --> varaible
query.SetFirstResult(persistentIndex);
query.SetMaxResults(reloadAmount);
IList result = query.List();
// ...

Enumerating items

The enumerator for paged lists or bags use the GetAt(int index) to get the items of a paged list. When iterating through all items this index is incremented. The following diagrams demonstrates the GetNext method.

If the item at the specified index was added or inserted locally then the added or inserted item is returned. Otherwise the paged list (or bag) calculates the persistent index of the requested item and ask the persistent item list to return that item (PersistentItemList.GetAt method). The persistent item list checks whether the item at the requested index is already locally available. If so this item is returned. Otherwise the persistent item list reloads the next portion of items and returns the first item in the reloaded portion.

Adding and inserting items

Adding an item to a paged list (or bag) results in the same operation as inserting an item to the last index (index = list.Count). Inserted items are stored in a hash table which maps the index to the item instance. Already added items where the index is greather than the current index must be adjusted by incremeting their key value which represents their index. Thus adding elements may take some time if a lot of items were already added.

Removing items

Removing an item results in the same operation as removing the item at a specified index where the index is the first occurrence of the item to remove.
If an added or inserted item is removed then the addition or insertion is removed insead of removing the item. In that case the keys of the added and inserted hash table must be adjusted.
The persistent index of removed items are stored in a sorted list. This list only contains the persistent index (the instance of removed items are not used anymore) of the removed items.

Clear items

Design diagram

Descriptions for the classes, interfaces and types can be found in the API.