To enhance client performance a simple LRU Cache was implemented for both synchronous and asynchronous client API. Cache is available since cynara 0.2.0 version.
Cache is keeping entries containing:
- user, client, privilege triple
- client session
- policy result got from cynara server
Contents are updated through client calls to cynara, so will be available to user in next requests for same access check (using user, client, privilege triple). Every new entry is put as most recently used. Client session is never interpreted by server side.
Cache capacity is set to given value (by default it's 10000 entries). This will be soon configurable through cynara_configuration structure. When Cache capacity is reached, the least recently used entries are deleted from cache (so checking them next time through client API will require call to cynara). This implementation provides balance between memory consumption and performance.
Cache supports multiple plugins loaded on client side. These plugins can be created and compiled into cynara client library or be loaded dynamically from shared objects in <cynara_lib_path>/plugin/client ( TODO : more on client-plugin ).
These plugins are responsible for (in terms of Cache):
- deciding wether PolicyResult is cacheable (e.g. policy allowing access only once should not be cached)
- usability of stored result (e.g. if policy is time based, check is required, if it's not out-of-date)
- result translation to client domain type (in our case - ALLOW/DENY, various checks can happen here also)
It is worth noting, that client_session parameter stored for every entry is only interpreted by plugin.
As some policy changes might occur and responses stored in cache are no longer valid, upon these events and disconnection of cynara server cache is cleared. This makes small impact on performance, as every check to cache needs also connection status checking, but it makes responses taken from it much more up-to-date and secure.
Searching for entry consists of:
- checking cache map for (user, client, privilege, client session) quadruple
- searching for compiled-in plugin supporting type of found result
- searching for dynamic plugin supporting type of found result (if no compiled-in found)
- plugin interpretation of policy usability and result
- if policy is usable marking its usage
Search complexity should be O(1) in average in terms of amount of cached entries. But every search operation requires searching for compatible plugin, which is O(logn), where n is number of plugins. The assumption is that amount of plugin is negligibly small, thus searching for them should not add much overhead.
Update of entry consists of:
- searching for compiled-in or dynamic plugin supporting type of updated result
- plugin interpretation of policy cacheability
- checking cache map if entry for (user, client, privilege, session) already exists
- if policy is cacheable and existing - updating result and marking usage
- if policy is cacheable and not existing - adding entry
- plugin interpretation of policy result
Update complexity should be O(1) in average in terms of amount of cached entries, but when cache size exceeds map capacity, rehashing of whole map will occur causing some updates to be O(n). Complexity of plugin searches could be omitted as in case of cache search operation.
Happens when cache capacity is reached. Every next entry update, if not previously stored, will trigger eviction of least recently used entry.
Complexity of this operation is amortized constant.
When update of policy will happen on cynara server side, whole cached needs to be cleared. This will instantly trigger deletion of every entry in cache. Its complexity is O(n), where n is amount of entries in cache.
Cache is based on hashed map for best search and update efficiency. Average complexity of these operation should be O(1). This is entirely dependent on implementation of stl containers. Moreover, most of operations require multiple character string comparations, which in worst case could also have impact on performance. It should be reminded, that every call to cache is preceded by syscall to check connection status on cynara server.
Few performance tests were performed for cache operations:
- cache size differs from 100 to 100000
- only one plugin is available (so plugin search does not impact cache performance)
- average length of every client, user, privilege string is 15 characters
- every element updated is unique
- every element is updated 2 times to cache (so when cache size is 100, there are 200 elements updated)
- every element previously updated is got from cache
- time of all elements update/get is measured
- time of one element update/get is measured
|Cache size||Update loop [µs]||Single update [µs]||Get loop [µs]||Single get [µs]||Update loop [µs]||Single update [µs]||Get loop [µs]||Single get [µs]|
As cache implementation is based on stl containers, so its memory consumption may differ with different stl implementations. Big impact also have sizes of parameters (user, client, privilege) as they are stored as full character strings.