1 Star 0 Fork 0

bobwxc / cl-mdb

Create your Gitee Account
Explore and code with more than 8 million developers,Free private repositories !:)
Sign up
Clone or Download
Cancel
Notice: Creating folder will generate an empty file .keep, because not support in Git
Loading...
readme.md

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:

(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

(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

About

a simple memory key-value database in Common Lisp expand collapse
Common Lisp
MulanPubL-2.0
Cancel

Releases

No release

Contributors

All

Activities

Load More
can not load any more
Common Lisp
1
https://gitee.com/bobwxc/cl-mdb.git
git@gitee.com:bobwxc/cl-mdb.git
bobwxc
cl-mdb
cl-mdb
master

Search

挂件 关闭按钮