memtable

MemTable is an in-memory data structure that holds the latest written records. It is a sorted list of records sorted by the key hash. When the MemTable reaches its capacity, it is flushed to disk as a Table (Sorted String Table or SSTable). See the sstable module for more details.

Types

MemTable

</>

MemTable holds a sorted list of the latest written records. Generally, we could implement a sorted list algorithm like skip list, but for simplicity we use a map instead.

MemTables have a max capacity and when that is reached, we flush the MemTable to disk as a Table (Sorted String Table or SSTable). See the sstable module for more details.

The MemTable structure is as follows:

entries: a map of key hash to MemTableEntry. The key hash is the hash of the key string.
size: the total size of the MemTable in bytes.
max_size: the maximum size of the MemTable in bytes.

pub type MemTable {
  MemTable(
    entries: Map(Int, MemTableEntry),
    size: Int,
    max_size: Int,
  )
}

Constructors

MemTable(
  entries: Map(Int, MemTableEntry),
  size: Int,
  max_size: Int,
)

MemTableEntry

</>

MemTableEntry is a single entry in the MemTable.

pub type MemTableEntry {
  MemTableEntry(key: String, value: Value)
}

Constructors

MemTableEntry(key: String, value: Value)

Reason

</>

Reason is the reason why a MemTable operation failed.

pub type Reason {
  CapacityExceeded
}

Constructors

```
CapacityExceeded
```
The MemTable is full and cannot accept more entries.

Constants

file_id_size_bytes

</>

pub const file_id_size_bytes: Int = 16

The file ID size is 128-bit integer corresponding to the UUID of the file in binary format.

file_offset_size_bytes

</>

pub const file_offset_size_bytes: Int = 4

The file offset size is 32-bit integer.

key_hash_size_bytes

</>

pub const key_hash_size_bytes: Int = 4

The key hash size is 32-bit integer

key_size_bytes

</>

pub const key_size_bytes: Int = 2

The key string size data is 16-bit integer

payload_size_bytes

</>

pub const payload_size_bytes: Int = 26

The payload size for the memtable entry, it is the sum of the key hash size, file ID size, file offset size and key size.

Functions

bitstring_to_entry

</>

pub fn bitstring_to_entry(bitstring: BitString) -> #(
  Int,
  MemTableEntry,
)

bitstring_to_entry converts a bitstring to a MemTableEntry. It is mainly used when we need to convert the binary representation of a MemTableEntry to a MemTableEntry.

contains

</>

pub fn contains(mem_table: MemTable, key: String) -> Bool

contains checks if the MemTable contains the given key.

delete

</>

pub fn delete(mem_table: MemTable, key: String) -> MemTable

deletes the given key from the MemTable. If the key does not exist, it returns the original MemTable. Otherwise, it returns the updated MemTable.

entry_to_bitstring

</>

pub fn entry_to_bitstring(entry: MemTableEntry) -> BitString

entry_to_bitstring converts a MemTableEntry to a bitstring. It is mainly used when we need to convert the MemTableEntry to its binary representation.

from_entries

</>

pub fn from_entries(entries: Map(Int, MemTableEntry), max_size: Int) -> MemTable

calculate_entries_size calculates the total size of the entries in the MemTable. It is mainly used when we load the MemTable from disk.

get

</>

pub fn get(mem_table: MemTable, key: String) -> Result(Value, Nil)

gets the value of the given key from the MemTable. If the key does not exist, it returns an error.

get_bounds

</>

pub fn get_bounds(mem_table: MemTable) -> #(Int, Int)

get_bounds returns the lower and higher bounds of the MemTable. If the MemTable is empty, it returns #(0, 0).

hash

</>

pub external fn hash(key: String) -> Int

generates a hash for the given key.

new

</>

pub fn new(max_size: Int) -> MemTable

search_pivot

</>

pub fn search_pivot(mem_table: MemTable) -> Int

search for a pivot in the MemTable. The pivot is the middle key in the MemTable.

set

</>

pub fn set(mem_table: MemTable, key: String, value: Value) -> Result(
  MemTable,
  Reason,
)

set sets the given key to the given value in the MemTable. If the MemTable reaches its capacity, it returns an error. Otherwise, it returns the updated MemTable.

split

</>

pub fn split(mem_table: MemTable, pivot: Int) -> #(
  MemTable,
  MemTable,
  Int,
)

splits the MemTable into two MemTables. The first MemTable contains MemTableEntries with keys less than the pivot. The second MemTable contains MemTableEntries with keys greater than or equal to the pivot. The pivot is the middle key in the MemTable.