.TH "doc_decisions_1_in_discussion_copy_on_write_md" 3elektra "Tue Nov 29 2022" "Version 0.9.11" "Elektra" \" -*- nroff -*-
.ad l
.nh
.SH NAME
doc_decisions_1_in_discussion_copy_on_write_md \- Copy On Write 
 
.SH "Problem"
.PP
One of Elektra's core goals is low memory usage\&. Currently, there are many places within Elektra where keys and keysets are duplicated and copied around\&. Most of those copied keys are never modified, but are required to be detached from the lifetime of the original instance\&. We want to introduce an in-memory copy-on-write mechanism to lower our memory usage\&.
.PP
In the near future, Elektra will also gain facilities for \fBchange tracking\fP and session recording, both of which will potentially again duplicate keys\&. There are also aspirations to create a new, simple \fBinternal cache\fP that would also benefit from a copy-on-write mechanism\&.
.SH "Constraints"
.PP
.IP "1." 4
The lifetime of a \fCKey\fP and a \fCKeySet\fP must be unaffected by copy-on-write\&.
.PP
.SH "Assumptions"
.PP
.SH "Considered Alternatives"
.PP
.SS "<tt>mmapstorage</tt>-like copy-on-write implementation"
There is already some kind of copy-on-write semantics within \fClibelektra-core\fP to support the \fCmmapstorage\fP plugin\&. We can build on this and add a more generic copy-on-write to it\&.
.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
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
.PP
\fBCons:\fP
.PP
.IP "\(bu" 2
Lifetime of a copied COW key MUST be less than the key it was copied from\&. We can not track how many keys point to the same data and name this way, so we can only free data and name if the key does not have the COW flag\&. If the original key gets deleted, using a COW key that points to the same data and name will lead to corrupt data\&. The same is true for updating values of the original key\&.
.PP
This is only problematic if we want to use COW for keys outside of \fCKDB\fP\&. If it is only for use within \fCKDB\fP, especially for usage as internal cache and in change tracking, we could always guarantee that the original keys are going to last as long as the \fCKDB\fP instance\&. However, we need to document for the users of Elektra that keys returned from \fCkdbGet\fP are only valid until \fCkdbClose\fP\&. If they want to continue using them afterwards, they'd have to deep copy them\&.
.PP
Triggering the delete problem:
.PP
.PP
.PP
.nf
Key * originalKey;
Key * copiedKey;
keyCopy (copiedKey, originalKey, ELEKTRA_CP_COW);

assert (keyString (copiedKey) == keyString (originalKey));
assert (keyName (copiedKey) == keyName (originalKey));

keyDel (originalKey);

keyString (copiedKey); // Error! Original value has been deleted\&. Pointer to data in copiedKey points to freed memory
keyName (copiedKey);   // Error! Original name has been deleted\&.
.fi
.PP
.PP
Triggering the update problem:
.PP
.PP
.nf
Key * originalKey;
Key * copiedKey;
keyCopy (copiedKey, originalKey, ELEKTRA_CP_COW);

assert (keyString(copiedKey) == keyString(originalKey));
keySetString (originalKey, "new value!");

keyString(copiedKey); // Error! Original value has been deleted\&. Pointer to data in copiedKey points to potentially freed memory
.fi
.PP
.PP
The same problems in principle exist for \fCmmapstorage\fP where \fCkdbSet\fP frees (\fCmunmap\fP) the keyset\&. We can still let users access the flag \fCELEKTRA_CP_COW\fP, we just need to clearly document what is forbidden\&. Maybe set the \fCKEY_FLAG_RO_VALUE\fP on the original key, so that the API itself detects the error\&. There is, however, no flag for \fCkeyDel\fP that we could set\&.
.SS "Changes to <tt>libelektra-core</tt>"
The \fCstruct _Key\fP will be extended with two more pointers, if we want to eliminate the lifetime problem:
.PP
.IP "\(bu" 2
\fCstruct _Key * origData\fP: points to the key containing the referenced data
.IP "\(bu" 2
\fCstruct _Key * origName\fP: points to the key containing the referenced name
.PP
.PP
Those two pointers are needed for memory management\&. Each referenced key will also have its reference counter increased\&. This way, an original key can be \fC\fBkeyDel()\fP\fPd without impacting the copied keys\&.
.PP
Three new key flags will be added:
.PP
.IP "\(bu" 2
\fCKEY_FLAG_COW_VALUE\fP: the value points to a value of another key
.IP "\(bu" 2
\fCKEY_FLAG_COW_NAME\fP: the name points to the name of another key
.IP "\(bu" 2
\fCKEY_FLAG_COW_META\fP: metakeys are copy-on-write
.PP
.PP
A new copy flag will be added:
.PP
.IP "\(bu" 2
\fCKEY_CP_COW\fP: instructs \fCkeyCopy\fP to copy whatever it should copy as copy-on-write\&. This will NOT be part of \fCKEY_CP_ALL\fP\&. We don't want developers outside of Elektra to accidentally use this\&.
.PP
.PP
If \fC\fBkeyCopy()\fP\fP is instructed to do a copy-on-write copy:
.PP
.IP "\(bu" 2
\fCdest->data\&.v\fP and \fCdest->data\&.c\fP point to the exact same location as in the source\&. \fCdest->dataSize\fP is set to the same value as \fCsource->dataSize\fP\&. \fCKEY_FLAG_COW_VALUE\fP is set on \fCdest->flags\fP\&. \fCKEY_FLAG_RO_VALUE\fP is set on \fCsource->flags\fP\&. \fCdest->originalData\fP is set to \fCsource\fP\&. \fCsource->refs\fP is incremented\&.
.IP "\(bu" 2
\fCdest->key\fP points to \fCsource->key\fP\&. \fCdest->keySize\fP is set to the same value as \fCsource->keySize\fP\&. \fCdest->ukey\fP points to \fCsource->ukey\fP\&. \fCdest->keyUSize\fP is set to the same value as \fCsource->keyUSize\fP\&. \fCKEY_FLAG_COW_NAME\fP is set on \fCdest->flags\fP\&. \fCKEY_FLAG_RO_NAME\fP is set on \fCsource->flags\fP\&. \fCdest->originalName\fP is set to \fCsource\fP\&. \fCsource->refs\fP is incremented\&.
.IP "\(bu" 2
\fCdest->meta\fP points to a \fBnew\fP keyset\&. The keys in \fCdest->meta\fP are also copied with \fCKEY_CP_COW\fP, i\&.e\&. they are also copy-on-write keys\&. \fCKEY_FLAG_COW_META\fP is set on \fCdest->flags\fP\&. \fCKEY_FLAG_RO_META\fP is set on \fCsource->flags\fP\&.
.PP
.PP
The source key will remain as a read-only key\&. This constraint is needed, because the source key is the only key we can free the resources on\&. If the data or the name would change in the source key, all COW-copied keys would suddenly have another value\&. For the same reason, the source key will need to live longer than all COW-copied keys from it\&.
.PP
A \fC\fBkeyCopy()\fP\fP without \fCKEY_CP_COW\fP from an COW key will create a deep copy of the key\&. These keys are 'normal' non-COW keys and can live on their own\&.
.PP
Every \fCkey*()\fP method that modifies data on a COW-copied key will need to allocate new memory for this data and remove the \fCKEY_FLAG_COW_DATA\fP flag\&. Every \fCkey*()\fP method that modifies the name of a COW-copied key will need to allocate new memory for this name and remove the \fCKEY_FLAG_COW_NAME\fP flag\&. Every \fCkey*()\fP method that modifies metadata needs to make sure that the same happens for metakeys\&.
.PP
Keysets are not copy-on-write\&. A \fCksDeepDup()\fP of a keyset with COW keys will create a keyset with deep-copied non-COW keys\&. Internally we may need a \fCksCowDup()\fP function to create a keyset with copy-on-write keys from another keyset\&. Whether this function will be part of the public API is a point for discussion\&.
.SS "Full-blown copy-on-write implementation"
Make Elektra's \fCKey\fP and \fCKeySet\fP data structures copy-on-write\&. This requires some major refactoring of code within \fClibelektra-core\fP\&. Code that does only interact with the data structures via the public \fClibelektra-core\fP API should not notice any differences\&. The \fCmmapstorage\fP plugin needs to be updated\&.
.PP
Unlike 'mmapstorage-like COW implementation' keyDup, keyCopy, ksCopy and ksDup will always use COW\&. \fCksCopy\fP and \fCksDup\fP is needed for (de)duplication of metadata\&. Furthermore, the API has better usability if Key and KeySet behave the same, especially for bindings where duplication might happen implicitly\&.
.SS "Changes to <tt>Key</tt>"
For the \fCKey\fP, we need to extract everything for the data and name into their own structs\&. This is done for memory-management reasons, as we need to track how many keys point to the same data and/or name\&.
.PP
.PP
.nf
struct _KeyData {
    union {
        char * c;
        void * v;
    } data;

    size_t dataSize;

    uint16_t refs;
};

struct _KeyName {
    char * key;
    size_t keySize;

    char * ukey;
    size_t keyUSize;

    uint16_t refs;
};

struct _Key {
    struct _KeyData * keyData;
    struct _KeyName * keyName;
    KeySet * meta;
    keyflag_t flags;

    uint16_t refs;
};
.fi
.PP
.PP
@mpranj's thoughts regarding moving name and data to separate structures:
.PP
.RS 4
1\&. If they [key name and data] are a separate entity, \fCmmapstorage\fP will need a flag once again for each of those\&. This is used to mark whether the data is in an mmap region or not\&. (or we find some bit somewhere that we can steal for this purpose)
.PP
.IP "2." 4
Adding more indirections is probably not going to help performance\&. (I understand that we save memory here) 
.PP
.RE
.PP
.SS "Changes to <tt>KeySet</tt>"
For \fCKeySet\fP, we need to split out everything to do with the stored keys into a separate datastructure\&. This includes the array itself, the sizes and the hashmap\&.
.PP
Why don't we just add the number of references to the original \fCKeySet\fP?
.PP
.IP "\(bu" 2
If we delete a copied KeySet, we don't know which KeySet is the original, so we couldn't decrement the counter\&. This could be dealt with storing a pointer to the original KeySet\&.
.IP "\(bu" 2
If the original KeySet is deleted, we don't know which other KeySets point at the data, so updating their count would not work
.IP "\(bu" 2
In similar fashion, if you update the original KeySet, the copied KeySets will also contain the new data (if the memory address does not change)\&. This is unexpected behavior\&.
.PP
.PP
.PP
.nf
struct _KeySetData {
    struct _Key ** array;
    size_t size;  
    size_t alloc; 
    Opmphm * opmphm;
    OpmphmPredictor * opmphmPredictor;

    uint16_t refs; 
};

struct _KeySet {
    struct _KeySetData * data;

    ksflag_t flags;

    uint16_t refs; 
};
.fi
.PP
.PP
API notes:
.PP
.IP "\(bu" 2
\fC\fBksNew()\fP\fP: 
.PP
.nf
if size is 0, `data` will be NULL

.fi
.PP

.IP "\(bu" 2
\fC\fBksDup()\fP\fP: creates a new instance of \fCstruct _KeySet\fP, points its \fCdata\fP to the \fCsource->data\fP, increases \fCsource->data->refs\fP by 1\&.
.IP "\(bu" 2
\fCksCopy(dest, source)\fP: 
.PP
.nf
if `dest->data` is NULL, then point `dest->data` to `source->data` and increase `source->data->refs` by 1
if `dest->data` is NOT NULL:
  if `dest->data->refs` == 1 (meaning no other keysets points to it):
    deallocate `dest->data`
    point `dest->data` to `source->data`, increase `source->data->refs` by 1\&.
  else if `dest->data->refs` > 0: (there are other keysets sharing the same data):
    decrease `dest->data->refs` by 1\&.
    allocate new `dest->data`
    copy the keys from old to `dest->data`
    copy the keys of `source->data->array` over to `dest->data->array`

.fi
.PP

.IP "\(bu" 2
\fCksAppend(dest, source)\fP: 
.PP
.nf
if `dest->data` is NULL, then point `dest->data` to `source->data` and increase `source->data->refs` by 1
if `dest->data` is NOT NULL:
  if `dest->data->refs` == 1 (meaning no other keysets points to it):
    if `dest->data->size` == 0 (no keys are in this keyset):
      deallocate `dest->data` and point `dest->data` to `source->data`, increase `source->data->refs` by 1\&.
    else if `dest->data->size` > 0 (meaning there are already keys in this keyset):
      copy the keys of `source->data->array` over to `dest->data->array`
  else if `dest->data->refs` > 1: (there are other keysets sharing the same data):
    if `dest->data->size` == 0 (no keys are in this keyset):
      decrease `dest->data->refs` by 1\&.
      point `dest->data` to `source->data`, increase `source->data->refs` by 1\&.
    else if `dest->data->size` > 0 (meaning there are already keys in this keyset):
      decrease `dest->data->refs` by 1\&.
      allocate new `dest->data`
      copy the keys from old to `dest->data`
      copy the keys of `source->data->array` over to `dest->data->array`

.fi
.PP

.IP "\(bu" 2
\fCksAppendKey(dest, key)\fP:
.IP "  \(bu" 4
Pretty much the same \fC\fBksAppend()\fP\fP but only for a single key
.IP "  \(bu" 4
if \fCdest->data\fP is NULL, allocate \fCdest->data\fP and put the key there
.PP

.IP "\(bu" 2
\fCksClear(dest)\fP:
.PP
.PP
.PP
.nf
if `dest->data->refs` == 1 (meaning no other keysets points to it):
  deletes the keys in `dest->data`
else if `dest->data->refs` > 1: (there are other keysets sharing the same data):
  decrease `dest->data->refs` by 1
  point `dest->data` to NULL
.fi
.PP
.PP
.IP "\(bu" 2
\fCksCut(dest, key)\fP: 
.PP
.nf
if `dest->data->refs` == 1 (meaning no other keysets points to it):
  perform the cutting algorithm directly on these keys
else if `dest->data->refs` > 1: (there are other keysets sharing the same data):
  decrease `dest->data->refs` by 1
  create a new `dest->data`
  copy over the non-cut keys into `dest->data` from the old `dest->data`

.fi
.PP

.IP "\(bu" 2
\fCksPop(dest)\fP:
.PP
.PP
.PP
.nf
if `dest->data->refs` == 1 (meaning no other keysets points to it):
  pop the last key directly on the keys
else if `dest->data->refs` > 1: (there are other keysets sharing the same data):
  decrease `dest->data->refs` by 1
  create a new `dest->data`
  copy over all but the last keys from the old `dest->data`
.fi
.PP
.PP
.IP "\(bu" 2
\fC\fBksLookup()\fP\fP:
.IP "  \(bu" 4
if the \fCDEL\fP or \fCPOP\fP flag is specified, do the COW-stuff as described multiple times now in the operations above
.PP

.PP
.SS "Reference Counting"
We need reference counting for the internal COW datastructures\&. We do it the same way reference counting currently works for \fCKey\fP and \fCKeySet\fP\&. One tweak though is that the refcount should never be 0, as this does not make sense for internal datastructures\&.
.PP
This means we always increment the refcount after creation and always decrement before deletion, so that the refcount is never zero\&. An example implementation is shown below:
.PP
.PP
.nf
static void keySetValue(Key * key, void * value, size_t size) {
  // [\&.\&.\&.] removal of current value from key
  struct _KeyData data = keyDataNew (value, size);
  keyDataIncRef (data);
  key->data = data;
}

static void keyDel(Key * key) {
  keyDataDecRef (key->data);
  keyDataDel (key->data);
  // [\&.\&.\&.] other cleanup
}
.fi
.PP
.SS "Variation 1 - RcBuffer"
Instead of using different structs for \fC_KeyData\fP, and \fC_KeyName\fP use a more generic struct for reference counting\&. This would avoid some duplication on the reference counting code for the key\&. Keysets will still have their own data struct, as it contains more than just a pointer and a size\&.
.PP
.PP
.nf
typedef struct {
        void * data;
        size_t size;
        uint16_t refs;
} RcBuffer;

struct _Key {
        RcBuffer * uname;
        RcBuffer * ename; // will be removed soon
        RcBuffer * value;

        KeySet * meta;
        keyflag_t flags;
        uint16_t refs;
};
.fi
.PP
.SS "Possible Edge Cases"
In general, it should be possible to always do copy-on-write\&. From a users perspective, copy-on-write copies of a key (and a keyset) should behave the same\&. There is, however, one edge case: the user modifying the value of a key directly\&. This is shown in the following example:
.PP
.PP
.nf
Key * key;
struct foo myFoo = {
  \&.x = 0
};
keySetBinary (key, &myFoo, sizeof(myFoo));

Key * dup = keyDup (key);

((struct foo *)keyValue (key))->x = 1;

// with COW
assert (((struct foo *)keyValue (dup))->x == 1);
// without COW
assert (((struct foo *)keyValue (dup))->x == 0);
.fi
.PP
.PP
This edge case can be accounted for by providing a private function \fCkeyDetach\fP, that forces that the key has its very own copy of the data\&.
.PP
.PP
.nf
((struct foo *)keyValue (keyDetach(key)))->x = 1;

// with COW
assert (((struct foo *)keyValue (dup))->x == 0);
// without COW
assert (((struct foo *)keyValue (dup))->x == 0);
.fi
.PP
.SS "Compatibility with <tt>mmapstorage</tt> plugin"
If we do change the internal data structures it makes much more sense to fix the cache and mmapstorage afterwards (or in tandem)\&. The most important constraint for mmap is that any structure (or bytes) that is an allocation unit (e\&.g\&. we malloc() the bytes needed for KeySet struct, so this is an unit) needs to have a flag to determine whether those bytes are actually malloc()ed or they are mmap()ed\&. Thus all the newly added structures as proposed will need some kind of an mmap flag\&.
.PP
\fCmmapstorage\fP only calls \fCmunmap\fP in some error cases, so basically \fCmunmap\fP is almost never done and the keyset is never invalidated\&.
.PP
During \fCkdbSet\fP the storage plugins always write to a temp file, due to how the resolver works\&. We also don't need to mmap the temp file here: when doing \fCkdbSet\fP we already have the \fCKeySet\fP at hand, mmap-ing it is not needed at all, because we have the data\&. We just want to update the cache file\&. The \fCmmap\fP/\fCmunmap\fP in kdbSet are just so we can write the KeySet to a file in our format\&. (\fCmmap()\fP is just simpler, but we could also \fCmalloc()\fP a region and then \fCfwrite()\fP the stuff)
.PP
Therefore the only case where we return a \fCmmap()\fPed KeySet should be in \fCkdbGet\fP\&.
.PP
When the \fCmmapstorage\fP was designed/implemented, not all structures had refcounters, so there was no way to know when a \fCmunmap\fP is safe\&. This was simply out of scope at that point in time\&.
.PP
If refcounting is now implemented for all structures, we might be able to properly \fCmunmap\fP in future\&.
.PP
Two ideas to deal with this in conjunction with our reference counting implementation:
.PP
If we have \fCfree\fP function-pointer along side the refcount, \fCmmapstorage\fP (and also other plugins with different allocators) could set it to their own implementation\&. To mimic the current behavior of \fCmmapstorage\fP this would point to a no-op function\&. However, we could also improve things and keep track of when all data has been freed and only then call \fCmunmap\fP\&.
.PP
Another simpler way to avoid the flag, which doesn't really allow for further improvements, would be using the refcount\&. \fCmmapstorage\fP could set the refcount to a value that is otherwise illegal\&. This would allow us to detect the keys\&. Depending on the refcount implementation good values would probably be 0 or UINT16_MAX\&. The special value would have to ignored by all refcounting functions (inc, dec, del) and turn the functions into no-ops\&.
.SS "Possible Optimizations"
.IP "\(bu" 2
This approach requires more allocations than previously\&. We have not fully benchmarked whether this is a big issue\&. One optimization could be an expanding 'pool' of \fC_KeySetData\fP, \fC_KeyData\fP and \fC_KeyName\fP\&. We could then allocate multiple of them at the same time, and borrow and give back instance from and to the pool\&.
.IP "\(bu" 2
Embed the \fCKeySet * meta\fP directly in \fCstruct _Key\fP\&. This may help with performance in cases we need metadata\&. It will, however, increase memory usage\&. This should only be considered after some benchmarking shows this is a real issue\&.
.PP
.SH "Memory comparison of COW approaches"
.PP
The following calculations are based on the AMD64 platform\&. All results are in bytes unless stated otherwise\&.
.PP
Example key: \fCuser:/hosts/ipv6/example\&.com = 2606:2800:220:1:248:1893:25c8:1946\fP
.PP
We want to measure the following properties for the key:
.PP
.IP "\(bu" 2
Empty Key: size of a simple malloc of the key struct
.IP "\(bu" 2
Empty Key (with name): size of simple malloc of all structs, so that the key has a name, but without including the size of the name
.IP "\(bu" 2
Empty Key (with name + data): size of a simple malloc of all structs, so that the key has a name and data, but without including the size of the name or data
.IP "\(bu" 2
Single Example Key: a single instance of the key defined above
.IP "\(bu" 2
Example Key + 1 Duplicate: two instances of the key defined above, one of them is a duplication of the first
.IP "\(bu" 2
Example Key + 2 Duplicates: three instances of the key defined above, two of them are duplications of the first
.PP
.PP
Approach   Empty Key   Empty Key (with name)   Empty Key (with name + data)   Single Example Key   Example Key + 1 Duplicate   Example Key + 2 Duplicates    Current Implementation   64   64   64   153   306   459    mmapstorage-like COW implementation (without additional pointers)   64   64   64   153   217   281    mmapstorage-like COW implementation (with additional pointers)   80   80   80   169   249   329    Full-blown COW implementation   32   72   96   185   217   249    Full-blown COW implementation - Variant 1 (RcBuffer)   40   88   112   201   241   281   
.PP
We want to measure the following properties for the keyset:
.PP
.IP "\(bu" 2
Empty KeySet: size of a simple malloc of the keyset struct
.IP "\(bu" 2
Empty KeySet (with data): size of a simple malloc of all structs
.IP "\(bu" 2
Example KeySet: size of a keyset with 15 keys + NULL byte
.IP "\(bu" 2
Example KeySet + 1 Duplicate: two instance of Example KeySet, one of them is a duplication
.IP "\(bu" 2
Example KeySet + 2 Duplicates: three instances of Example KeySet, two of them are duplications
.PP
.PP
Approach   Empty KeySet   Empty KeySet (with data)   Example KeySet   Example KeySet + 1 Duplicate   Example KeySet + 2 Duplicates    Current Implementation   64   64   192   384   576    mmapstorage-like COW implementation (without additional pointers)   64   64   192   384   576    mmapstorage-like COW implementation (with additional pointers)   64   64   192   384   576    Full-blown COW implementation   16   64   192   208   224   
.SS "Calculations"
Raw data size:
.PP
.IP "\(bu" 2
keyname : \fC28 + 1\fP = \fC29\fP
.IP "\(bu" 2
unescaped keyname (measured): \fC25\fP
.IP "\(bu" 2
data: \fC34 + 1\fP = \fC35\fP
.PP
.PP
Current Implementation:
.PP
.IP "\(bu" 2
Empty Key [measured via \fCsizeof\fP]: \fC64\fP
.IP "\(bu" 2
Empty Key (with name): \fC64\fP
.IP "\(bu" 2
Empty Key (with name + data): \fC64\fP
.IP "\(bu" 2
Single Example Key = \fCEmpty Key + keyname + unescaped keyname + data\fP = \fC64 + 29 + 25 + 35\fP = \fC153\fP
.IP "\(bu" 2
Single Example Key + 1 Duplicate = \fCSingle Example Key * 2\fP = \fC153 * 2\fP = \fC306\fP
.IP "\(bu" 2
Single Example Key + 2 Duplicates = \fCSingle Example Key * 3\fP = \fC153 * 3\fP = \fC459\fP
.IP "\(bu" 2
Empty KeySet [measured via \fCsizeof\fP]: \fC64\fP
.IP "\(bu" 2
Empty KeySet (with data): \fC64\fP
.IP "\(bu" 2
Example KeySet: \fCEmpty KeySet (with data) + 16 * pointer to keys\fP = \fC64 + 16 * 8\fP = \fC192\fP
.IP "\(bu" 2
Example KeySet + 1 Duplicate: \fCExample KeySet * 2\fP = \fC192 * 2\fP = \fC384\fP
.IP "\(bu" 2
Example KeySet + 2 Duplicates: \fCExample KeySet * 3\fP = \fC192 * 3\fP = \fC576\fP
.PP
.PP
mmapstorage-like COW implementation (without additional pointers):
.PP
.IP "\(bu" 2
Empty Key [measured via \fCsizeof\fP]: \fC64\fP
.IP "\(bu" 2
Empty Key (with name): \fC64\fP
.IP "\(bu" 2
Empty Key (with name + data): \fC64\fP
.IP "\(bu" 2
Single Example Key = \fCEmpty Key + keyname + unescaped keyname + data\fP = \fC64 + 29 + 25 + 35\fP = \fC153\fP
.IP "\(bu" 2
Single Example Key + 1 Duplicate = \fCSingle Example Key + Empty Key\fP = \fC153 + 64\fP = \fC217\fP
.IP "\(bu" 2
Single Example Key + 2 Duplicates = \fCSingle Example Key + Empty Key * 2\fP = \fC153 + 64 * 2\fP = \fC281\fP
.IP "\(bu" 2
KeySets are not COW in this approach --> same as current implementation
.PP
.PP
mmapstorage-like COW implementation (with additional pointers):
.PP
.IP "\(bu" 2
Empty KeySet [measured via \fCsizeof\fP]: \fC64\fP
.IP "\(bu" 2
Empty Key [measured via \fCsizeof\fP]: \fC80\fP
.IP "\(bu" 2
Empty Key (with name): \fC80\fP
.IP "\(bu" 2
Empty Key (with name + data): \fC80\fP
.IP "\(bu" 2
Single Example Key = \fCEmpty Key + keyname + unescaped keyname + data\fP = \fC80 + 29 + 25 + 35\fP = \fC169\fP
.IP "\(bu" 2
Single Example Key + 1 Duplicate = \fCSingle Example Key + Empty Key\fP = \fC169 + 80\fP = \fC249\fP
.IP "\(bu" 2
Single Example Key + 2 Duplicates = \fCSingle Example Key + Empty Key * 2\fP = \fC169 + 80 * 2\fP = \fC329\fP
.IP "\(bu" 2
KeySets are not COW in this approach --> same as current implementation
.PP
.PP
Full-blown COW implementation:
.PP
.IP "\(bu" 2
Empty Key [measured via \fCsizeof\fP]: \fC32\fP
.IP "\(bu" 2
Empty Key (with name) [measured via \fCsizeof\fP]: \fCEmpty Key + sizeof(KeyName)\fP = \fC32 + 40\fP = \fC72\fP
.IP "\(bu" 2
Empty Key (with name + data) [measured via \fCsizeof\fP]: \fCEmpty Key + sizeof(KeyName) + sizeof(KeyData)\fP = \fC32 + 40 + 24\fP = \fC96\fP
.IP "\(bu" 2
Single Example Key = \fCEmpty Key (with name + data) + keyname + unescaped keyname + data\fP = \fC96 + 29 + 25 + 35\fP = \fC185\fP
.IP "\(bu" 2
Single Example Key + 1 Duplicate = \fCSingle Example Key + Empty Key\fP = \fC185 + 32\fP = \fC217\fP
.IP "\(bu" 2
Single Example Key + 2 Duplicates = \fCSingle Example Key + Empty Key * 2\fP = \fC185 + 32 * 2\fP = \fC249\fP
.IP "\(bu" 2
Empty KeySet [measured via \fCsizeof\fP]: \fC16\fP
.IP "\(bu" 2
Empty KeySet (with data): \fCEmpty KeySet + sizeof(KeySetData)\fP = \fC16 + 48\fP = \fC64\fP
.IP "\(bu" 2
Example KeySet: \fCEmpty KeySet (with data) + 16 * pointer to keys\fP = \fC64 + 16 * 8\fP = \fC192\fP
.IP "\(bu" 2
Example KeySet + 1 Duplicate: \fCExample KeySet + Empty KeySet\fP = \fC192 + 16\fP = \fC208\fP
.IP "\(bu" 2
Example KeySet + 2 Duplicates: \fCExample KeySet + Empty KeySet * 2\fP = \fC192 + 16 * 2\fP = \fC224\fP
.PP
.PP
Full-blown COW implementation - Variant 1 (RcBuffer):
.PP
.IP "\(bu" 2
Empty Key [measured via \fCsizeof\fP]: \fC40\fP
.IP "\(bu" 2
Empty Key (with name) [measured via \fCsizeof\fP]: \fCEmpty Key + sizeof(RcBuffer)*2\fP = \fC40 + 24*2\fP = \fC88\fP
.IP "\(bu" 2
Empty Key (with name + data) [measured via \fCsizeof\fP]: \fCEmpty Key + sizeof(RcBuffer)*3\fP = \fC40 + 24*3\fP = \fC112\fP
.IP "\(bu" 2
Single Example Key = \fCEmpty Key (with name + data) + keyname + unescaped keyname + data\fP = \fC112 + 29 + 25 + 35\fP = \fC201\fP
.IP "\(bu" 2
Single Example Key + 1 Duplicate = \fCSingle Example Key + Empty Key\fP = \fC201 + 40\fP = \fC241\fP
.IP "\(bu" 2
Single Example Key + 2 Duplicates = \fCSingle Example Key + Empty Key * 2\fP = \fC201 + 40 * 2\fP = \fC281\fP
.IP "\(bu" 2
Empty KeySet [measured via \fCsizeof\fP]: \fC16\fP
.IP "\(bu" 2
Empty KeySet (with data): \fCEmpty KeySet + sizeof(KeySetData)\fP = \fC16 + 48\fP = \fC64\fP
.IP "\(bu" 2
Example KeySet: \fCEmpty KeySet (with data) + 16 * pointer to keys\fP = \fC64 + 16 * 8\fP = \fC192\fP
.IP "\(bu" 2
Example KeySet + 1 Duplicate: \fCExample KeySet + Empty KeySet\fP = \fC192 + 16\fP = \fC208\fP
.IP "\(bu" 2
Example KeySet + 2 Duplicates: \fCExample KeySet + Empty KeySet * 2\fP = \fC192 + 16 * 2\fP = \fC224\fP
.PP
.SS "Allocations & Indirections comparison of COW approaches"
For allocations want to measure the following properties:
.PP
.IP "\(bu" 2
Empty key: how many objects to allocate for an empty key
.IP "\(bu" 2
Empty Key (with name): how many objects to allocate for an empty key + name
.IP "\(bu" 2
Empty Key (with name + data): how many objects to allocate for an empty key + name + data
.IP "\(bu" 2
Duplication: how many objects to allocate for a duplication
.IP "\(bu" 2
Key + 1 Duplication: how many objects to allocate for a full key + 1 duplication
.IP "\(bu" 2
Key + 2 Duplications: how many objects to allocate for a full key + 2 duplications
.PP
.PP
Approach   Empty Key   Empty Key (with name)   Empty Key (with name + data)   Duplication   Key + 1 Duplication   Key + 2 Duplications    Current Implementation   1   1   1   1   2   3    mmapstorage-like COW implementation (without additional pointers)   1   1   1   1   2   3    mmapstorage-like COW implementation (with additional pointers)   1   1   1   1   2   3    Full-blown COW implementation   1   2   3   1   4   5   
.SH "Decision"
.PP
Implement the full-blown COW approach\&.
.SH "Rationale"
.PP
.SH "Implications"
.PP
.IP "\(bu" 2

.IP "\(bu" 2

.IP "\(bu" 2

.PP
.SH "Related Decisions"
.PP
.IP "\(bu" 2
\fBchange tracking\fP
.IP "\(bu" 2
\fBinternal cache\fP
.PP
.SH "Notes"
.PP