# cl-mdb

**Repository Path**: bobwxc/cl-mdb

## Basic Information

- **Project Name**: cl-mdb
- **Description**: a simple memory key-value database in Common Lisp
- **Primary Language**: Common Lisp
- **License**: MulanPubL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-04-30
- **Last Updated**: 2023-05-09

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# cl-mdb

A memory key-value database for Common Lisp.

## quick start

depends-on: cffi

Haven't been test on Windows or Mac OS, if you find some problem, please
kindly tell me.

example:

```lisp
(ql:quickload "cl-mdb")

(mdb:test)

(setf root-list (mdb:init-root-list)

(mdb:insert root-list key value)
(mdb:update root-list key new-value)
(mdb:select root-list key)
(mdb:remov root-list key)
(mdb:gbc root-list)
(mdb:mdump root-list path)
(mdb:mload path)
```

type of key: `string`

type of value: `(or number character string sequence null)`

## basic function

### insert

action flow:

- select = nil and remove-flag check
- insert-value
- insert-index
- reverse-flag

### select

action flow:

- select /= nil
- check flag
- return value

### update

action flow:

- select /= nil
- check flag
- lock flag
- update-value / time / id
- reverse-flag

### remove

action flow:

- select /= nil
- check flag
- read / write lock
- remove-flag t
- op-id
- (wait for gc)

just flag it to deprecated, and use a lazy runtime to collect garbage

### gc

really remove the row in store-list which row-remove-flag is `t`

action flow:

- set all row which's remove-flag is t and collect their key
- using the gc-key-list to set associated index to nil
- remove all nil in index-array
- remove all nil in store-list

## additional function

### log

### dump

only save store-list to file to save space

```
(format fp "~S" (cadr root-list))
```

### load

`mload (path)`, read store-list from file and re-construct index

if does not hot construct the index, index ptr will not point to store-
list's row

## data structure design

### root list

```
'(#(index-array) (store-list))
```

### index array

index array: a array which length is 65536 for first 16 bits of hash from
`0x0000` to `0xffff`.

```
#(((keyhash ptr) () ...) () ...)
```

### store list

a simple list

using push to add new row, so the first is the newest

```
(#s(row) #s(row) ...)
```

### value row

``` lisp
(defstruct row
  (content nil :type (or number character string sequence null))
  (original-key nil :type (or string null))
  (uuid nil :type (or string null))
  (time 0 :type number) ;; last insert or update time
  (operation-id  nil :type (or number null)) ;; last insert or update or remove operation id
  (read-flag nil :type boolean)
  (write-flag nil :type boolean)
  (remove-flag nil :type boolean)
  )
```

### key hash

murmur3-x64-128

- hash size: 128 bits (64 bytes)
- max key number: 340282366920938463463374607431768211456

## license

MulanPubL-2.0

```
          __                    ____  
    _____/ /     ____ ___  ____/ / /_ 
   / ___/ /_____/ __ `__ \/ __  / __ \
  / /__/ /_____/ / / / / / /_/ / /_/ /
  \___/_/     /_/ /_/ /_/\__,_/_.___/ 
```

## TODO

- process (daemon)
- async -- coroutine
- log
  - insert, update, remove
  - (action, args, time, operation-id)
- socket
- compress / tar