.TH "doc_decisions_0_drafts_internal_cache_md" 3elektra "Sat Nov 12 2022" "Version 0.9.11" "Elektra" \" -*- nroff -*-
.ad l
.nh
.SH NAME
doc_decisions_0_drafts_internal_cache_md \- Internal KeySet Cache 
 
.SH "Problem"
.PP
\fCkdbGet\fP might return more or fewer keys than requested\&. This was found confusing several times\&.
.SS "More Keys"
Even if calling \fCkdbGet\fP with a parent key below a mountpoint, \fCkdbGet\fP will nevertheless return all keys of the mountpoint\&. Pseudo code example, assuming there is a mountpoint at \fC/mountpoint\fP and a key \fC/mountpoint/other\fP:
.PP
.PP
.nf
kdbGet (kdb, ks, keyNew("/mountpoint/below"));
assert (ksLookup (ks, "/mountpoint/other") == NULL);
.fi
.PP
.PP
It was found unexpected that this assert will fail\&.
.SS "Fewer Keys"
When doing a second \fCkdbGet\fP with a new keyset no keys will be returned when no backends report changed data, because kdb internally thinks the data is already up-to-date\&. A unit test by @atmaxinger:
.PP
.PP
.nf
static void test_doubleGet (void)
{
        printf("running %s\n", __func__);

        // Setup
        Key * parentKey = keyNew("/somewhere", KS_END);
        KeySet * ks = ksNew(0, KS_END);
        KDB * kdb = kdbOpen (ksNew(0, KS_END), parentKey);
        kdbGet (kdb, ks, parentKey);
        ksAppendKey (ks, keyNew ("user:/somewhere", KEY_VALUE, "abc", KEY_END));
        ksAppendKey (ks, keyNew ("user:/somewhere/key", KEY_VALUE, "xyz", KEY_END));
        kdbSet (kdb, ks, parentKey);
        kdbClose (kdb, parentKey);

        // Scenario
        kdb = kdbOpen (ksNew(0, KS_END), parentKey);

        KeySet * ks1 = ksNew (0, KS_END);
        KeySet * ks2 = ksNew (0, KS_END);

        kdbGet (kdb, ks1, keyNew("/somewhere", KEY_END));
        succeed_if (ksLookupByName (ks1, "/somewhere/key", 0) != NULL, "should find key (1)");
        kdbGet (kdb, ks2, keyNew("/somewhere", KEY_END));
        succeed_if (ksLookupByName (ks2, "/somewhere/key", 0) != NULL, "should find key (2)");
}
.fi
.PP
.PP
.RS 4
It actually outputs should find key (2) so the assertion fails\&. 
.RE
.PP
It was found unexpected that the second assert will fail\&.
.SH "Constraints"
.PP
.IP "\(bu" 2
memory consumption must be low for \fCkdbGet\fP, see \fB4\&. Goal: Performance\fP, in particular, deep duplication is too expensive
.PP
.SH "Assumptions"
.PP
.SH "Considered Alternatives"
.PP
.SS "Keep Current Situation"
Improve documentation to make people more aware of these two problems:
.PP
.IP "\(bu" 2
add a tutorial about \fCkdbGet\fP semantics
.IP "\(bu" 2
add full examples how to correctly work with \fCkdbGet\fP
.PP
.SS "Cachefilter Plugin"
Naively one would simply cache the whole keyset and use \fCksBelow\fP to always get the keyset\&.
.PP
This idea was implemented and later on discarded: a3d95f07160d792fdd0f169d8543138c32a2f580
.PP
The main problems are:
.PP
.IP "\(bu" 2
very high memory consumption (duplication of KeySets)
.IP "\(bu" 2
problems specific to \fBhooks\fP, see \fC#1072\fP
.PP
.SS "MMAP Cache with parent key"
We make the mmap cache non-optional so that we always have a keyset of configuration data internally\&. From this keyset, we use \fCksBelow\fP to return the correct keyset\&.
.PP
\fBCons:\fP
.PP
.IP "\(bu" 2
invalidation of OPMPHM
.PP
.SS "MMAP Cache without parent key"
We make the mmap cache non-optional and only use a single cache, caching everything\&. We remove the parent key of \fCkdbGet\fP and \fCkdbSet\fP and always return the keyset of the whole KDB\&.
.SS "In-Memory COW Cache"
We keep a duplicated keyset in-memory and tag the keys as copy-on-write (COW)\&. From this keyset, we use \fCksBelow\fP to return the correct keyset\&. If the user tries to change the value or metadata of these keys, the data gets duplicated\&. I\&.e\&. the original keyset is not changed\&. The name is not relevant\&. It is always read-only, because the key is in at least one keyset (the internal one)\&. Pseudo code example:
.PP
.PP
.nf
Key * key = keyNew ("dir:/something", KEY_VALUE, "my value", KEY_END);
keyCopy (key_dup, key, ELEKTRA_CP_COW);
assert (keyString(key) == keyString(key_dup));
keySetString (key_dup, "other value"); // COW done here
assert (keyString(key) != keyString(key_dup));
assert (keySetName (key_dup, "dir:/valid") == -1); // must fail, as we have a COW key
assert (keyName(key) == keyName(key_dup)); // stays always valid
.fi
.PP
.PP
This is already implemented for the MMAP cache, so the implementation should be straightforward: Do the same COW duplications as done for MMAP but with a different flag\&.
.PP
@kodebach wrote:
.PP
.RS 4
What I wanted to say is that mmap already does COW, so we can reuse the code and probably the flag\&. If there is some code that is only needed for mmap and not COW, we could make mmap set two flags one for mmap and one for the general COW code\&. 
.RE
.PP
For the metadata, however, also COW KeySets might be needed (at least with the current API)\&. Example:
.PP
.PP
.nf
keyCopy (cow, key, ELEKTRA_CP_COW);
KeySet * cowMeta = keyMeta (cow);
ksAppendKey (cowMeta, keyNew ("meta:/whatever", KEY_VALUE, "abc", KEY_END));
ksRemoveByName (cowMeta, "meta:/type");
.fi
.PP
.PP
\fBPros:\fP
.PP
.IP "\(bu" 2
Elektra doesn't require MMAP
.PP
.SS "Data restrictions"
@kodebach wrote:
.PP
.RS 4
Make all the keys returned by kdbGet completely read-only\&. To change the data you need to append an entirely new key to replace the existing one\&. Then we just need to keep a shallow copy internally\&. 
.RE
.PP
.SS "API restrictions"
@kodebach wrote:
.PP
.RS 4
Change the API and remove KeySet from kdbGet and kdbSet also option 4 in \fBthe operation sequences decision\fP\&. If the keyset is owned by the KDB handle, it should not be as big surprise, if there is extra data in there\&. I certainly wouldn't try to asset anything on the contents of a KeySet that I don't own directly, unless the condition is explicitly documented somewhere\&. 
.RE
.PP
@markus2330 wrote:
.PP
.RS 4
I disagree, it is actually the same kind of surprise for 'More Keys'\&. Only the 'Fewer Keys' would get fixed\&. 
.RE
.PP
.SH "Decision"
.PP
Not yet decided\&.
.SH "Rationale"
.PP
Semantics can be provided without additional code or overhead in the core\&.
.SH "Implications"
.PP
.SH "Related Decisions"
.PP
.IP "\(bu" 2
\fBGlobal Validation\fP
.PP
.SH "Notes"
.PP
Problem 'Fewer Keys' was found to be a \fC'horrible problem'\fP
.PP
Issues where the problem described here was found confusing:
.PP
.IP "\(bu" 2
\fC#760\fP
.IP "\(bu" 2
\fC#1363\fP
.PP
.PP
@mpranj wrote about the performance for \fCMMAP Cache without parent key\fP:
.PP
.RS 4
in my benchmarks the pointer correction was never a bottleneck\&. 
.RE
.PP