Bytes count does not accurately represent size of RB Tree in memtable

[anarmanafov1]

Within the set method of memtable, the self.bytes += len(k) + len(v) is performed without checking if the values already exist in the RB Tree. If the values already exist in the RB Tree, the RB tree will not grow, however self.bytes will be increased.

The bug that this creates can be seen during flushing of a memtable to a disk segment.

To reproduce:

1. Open the KVS file and set MT_MAX_SIZE to something small like 20.
2. Create an instance of KVS.
3. Try inserting varying key value pairs until a disk segment is created. Inspect the disk segment.
4. Try inserting identical key value pairs until a disk segment is created. Inspect the disk segment.
5. The first disk segment will be near the MT_MAX_SIZE because it will contain all of the unique key value pairs. The second disk segment will hold 1 key value pair and therefore be significantly smaller.

The solution should prevent the self.bytes from growing when the memtable does not grow. Memtables should be flushed when the MT_MAX_SIZE is reached.

[robbassi]

I also realized that we are only computing the string length, and not the actual byte length. For example:

$ len('驚いた')
3
$ len(bytes('驚いた', encoding='utf-8'))
9

We'll need to fix that as well.

[amackillop]

After looking into this a bit more, this may not be desirable as the overhead of the check will slow down writes. It seems that keeping equal size segments is ideal but generally not done in practice and this may be why. Videos I've seen on compaction mention in practice that segments will vary in size.

[robbassi]

@amackillop The overhead of the key lookup?

[anarmanafov1]

Adding this for documentation.

After the discussions we all had regarding this issue, we agreed that we are OK with the overhead of checking if the key exists in the RB Tree.

We want to proceed with a fix for the inaccurate byte count for now.

Performance optimizations will be visited later.