xenial (7) elektra-data-structures.7.gz
NAME
elektra-data-structures - data structures
For an introduction, please read first about elektra classes elektra-classes.md. You might want to read
about architecture first elektra-architecture.md.
Introduction
Data structures define the common layer in Elektra. They are used to transfer configuration between
Elektra and applications, but also between plugins.
ADT
Both the KeySet and the interface to metadata within a Key are actually ADT (abstract data types). The
API is designed so that different implementations of the data structures can be used internally.
A hash data structure presents a good candidate as alternative data structure, especially for the
metadata interface. It is believed to be much faster on lookup, but considerably slower on sorted
enumeration.
A AVL tree also serve as a competitor. AVL trees are expected to be faster for inserting keys at any
place, but may be slower for appending because of the needed reorganisations. Their disadvantage is that
they need to allocate a large number of small pieces of memory. Further investigations, namely
implementation and benchmarks, are required to decide.
A trie could also be used for lookup of key names. It performs well for lookup, but needs more memory
allocations.
Currently the KeySet is implemented as a sorted array. It is fast on appending and iterating, and has
nearly no size-overhead. To improve the lookup-time, an additional hash will be used.
ABI compatibility
Application binary interface, or ABI, is the interface to all data structures of an application or
library directly allocated or accessed by the user.
Special care has been taken in Elektra to support all changes within the data structures without any ABI
changes. ABI changes would entail the recompilation of applications and plugins using Elektra. The
functions keyNew(), ksNew() and kdbOpen() allocate the data structures for the applications. The user
only gets pointers to them. It is not possible for the user to allocate or access these data structures
directly when only using the public header file <kdb.h>. The functions keyDel(), ksDel() and kdbClose()
free the resources after use. Using the C++ binding deallocation is done automatically.
Meta data
Read here elektra-meta-data.md.
KeySet
This subsection describes what has changed between 0.7 and 0.8 and deals with some general implementation
issues.
Operations
KeySet resembles the classical mathematical set. Operations like union, intersection or difference are
well defined. In mathematics typically every operation yields a new set. Instead, we try to reuse sets in
the following ways:
• A completely new and independent KeySet as return value would resemble the mathematical ideal
closely. This operation would be expensive. Every Key needs to be duplicated and inserted into a new
KeySet.
Such a deep duplication was only needed in kdbSet().
• The resulting KeySet is created during the operation, but only a flat copy is made. This means that
the keys in it are actually not duplicated, but only their reference counter is increased. This
method is similar to the mathematical model. Compared with a deep copy it can achieve good
performance. But all changes to the values of keys in the resulting KeySet affect the original
KeySet, too.
ksDup(const KeySet *source) produces a new KeySet that way. The source is not changed as shown by the
const modifier.
• The result of the operation is applied to the KeySet passed as argument directly. This is actually
quite common, but for this situation other names of the operations are more suitable.
For example, a union which changes the KeySet is called ksAppend().
• A new KeySet is created, but the KeySet passed as parameter is reduced by the keys needed for the new
KeySet. This is useful in situations where many operations have to be applied in a sequence reducing
the given KeySet until no more keys are left. None of the reference pointers changes in this
situation.
ksCut(KeySet *ks, const Key *cutpoint) works that way. All keys below the cutpoint are moved from ks
to the returned key set.
Consistency
There are several ways to define consistency relations on key sets. For strict consistency every parent
key must exist before the user can append a key to a key set. For example, the key set with the keys
system
system/elektra
system/elektra/mountpoints
would allow the key system/elektra/mountpoints/tcl to be added, but not the key system/apps/abc because
system/apps is missing. File systems enforce this kind of consistency.
These semantics are however not useful for configurations. Especially for user configurations often only
some keys need to be overwritten. It is not a good idea to copy all parent keys to the users
configuration. For this reason we use a less strict definition of consistency supporting such holes.
We also evaluated a form of weak consistency. It avoids adding some unnecessary keys. A constraint is
that a key can be added only if it has a parent key. But the constraint does not apply if no other key
exists above the key about to be inserted. From that moment it will serve as parent key for other keys.
With the current implementation of KeySet, however, it is not possible to decide this constraint in
constant time. Instead its worst-case complexity would be $log(n) * x$ where $n$ is the number of keys
currently in the key set and $x$ is the depth of the key. The depth is the number of / in the key name.
The worst-case of the complexity applies when the inserting works without a parent key. For example, with
the keys
user/sw/apps/abc/current/bindings
user/sw/apps/abc/current/bindings/key1
user/sw/apps/abc/current/bindings/key2
the weak consistency would allow inserting user/sw/apps/abc/current/bindings/key3 because it is directly
below an existing key. It would also allow adding user/sw/apps/xyz/current because it does not have any
parent key. But it would not allow user/sw/apps/abc/current/bindings/dir/key1 to add. The worst-case
complexity was found to be too expensive, and hence KeySet has no consistency check at all.
This means any key with a valid key name can be inserted into KeySet. The KeySet is changed so that it is
now impossible to append keys without a name. ksAppendKey(ks, Key *toAppend) takes ownership of the key
toAppend and will delete the key in that case. The caller does not have to free toAppend: either it is in
the key set or it is deleted.
Binary search determines the position where to insert a key. The C version of binary search bsearch()
cannot tell where to insert a key when it is not found. So the algorithm has to be reimplemented. Java´s
binary search binarySearch() uses a trick to both indicate where a key is found and where to insert it
with the same return code by returning the negative value ((-insertion point) - 1) indicating where the
new value should be inserted when the key is not found. Elektra now also uses this trick internally.
Internal Cursor
KeySet supports an external iterator with the two functions ksRewind() to go to the beginning and
ksNext() to advance the internal cursor to the next key. This side effect is used to indicate a position
for operations on a KeySet without any additional parameter. This technique is comfortable to see which
key has caused an error after an unsuccessful key database operation.
Elektra only has some functions to change the cursor of a key set. But these allow the user to compose
powerful functions. Plugins do that extensively as we will see later in ksLookupRE(). The user can
additionally write more such functions for his or her own purposes. To change the internal cursor, it is
sufficient to iterate over the KeySet and stop at the wanted key. With this technique, we can, for
example, realise lookup by value, by specific metadata and by parts of the name. Without an additional
index, it is not possible that such operations perform more efficiently than by a linear iteration key by
key. For that reason, Elektra´s core does not provide such functions. The function ksLookupByName(),
however, uses the more efficient binary search because the array inside the KeySet is ordered by name.
External Cursor
External cursor is an alternative to the approach explained above. Elektra provides a limited external
cursor through the interface ksGetCursor() and ksSetCursor(). It is not possible to advance this cursor.
The difference to the internal cursor is that the position is not stored within KeySet.
We considered providing an external cursor for performance reasons. But we found out that the speed of
iteration is mainly limited because of safety checks. The investigated methods become slower proportional
to the ease of use and safety. When using null pointers and range checks, the function is noticeably
slower than without. With the same amount of checks, using an external cursor is not much faster than the
ksNext(). External cursor with checks is in a benchmark about 10\% faster.
But an external cursor directly accessing the array can be much faster. Using an unchecked external
cursor can be about 50% faster than using the internal cursor with ksNext(). For this endeavour,
Elektra´s private header files need to be included. Including private header files, however, should not
be done with levity because ABI compatibility will be gone on any changes of the data structures. This
fact means the application or plugin needs to be recompiled when any of the internal structures of
Elektra are changed. We strongly discourage including these header files.
Nevertheless, the overall performance impact for iteration is minimal and should not matter too much.
Even if only a single keySetMeta() is used inside the iteration loop, the iteration costs are
insignificant. Only for trivial actions such as just changing a variable, counter or marker for every key
the iteration costs become the lion´s share. In such situations an internal iterator yields better
results. For example, ksForEach() applies a user defined function for every key in a KeySet without
having null pointer or out of range problems.
Trie vs. Split
Up to now, we have discussed external data structures visible to the user of the library. The application
and plugin programmer needs them to access configuration. Last, but not least, we will show two internal
data structures. The user will not see them. To understand the algorithm, however, the user needs to
understand them as well.
Trie
Trie or prefix tree is an ordered tree data structure. In Elektra, it provides the information to decide
in which backend a key resides. The algorithm, presented in algorithm elektra-algorithm.md, also needs a
list of all backends. The initial approach was to iterate over the Trie to get a list of all backends.
But the transformation of a Trie to a list of backends, contained many bugs caused by corner cases in
connection with the default backend and cascading mount points.
Split
So, instead of transforming the trie to a list of backends, we introduced a new data structure
\intro[Split@\lstinline{Split}]{Split}. The name Split comes from the fact that an initial key set is
split into many key sets. These key sets are stored in the Split object. Split advanced to the central
data structure for the algorithm:
typedef struct _Split Split;
struct _Split {
size_t size;
size_t alloc;
KeySet **keysets;
Backend **handles;
Key **parents;
int *syncbits;
};
The data structure Split contains the following fields:
• size: contains the number of key sets currently in Split.
• alloc: allows us to allocate more items than currently in use.
• keysets represents a list of key sets. The keys in one of the key sets are known to belong to a
specific backend.
• handles: contains a list of handles to backends.
• parents: represents a list of keys. Each parentKey contains the root key of a backend. No key of the
respective key set is above the parentKey. The key name of parentKey contains the mount point of a
backend. The resolver writes the file name into the value of the parentKey.
• syncbits: are some bits that can be set for every backend. The algorithm uses the syncbits to decide
if the key set needs to be synchronised.
Continue reading with the error handling elektra-error-handling.md.
November 2015 ELEKTRA-DATA-STRUCTURES(7)