Copyright (c) 2011-2013 by Joseph Wayne Norton
Authors: Joseph Wayne Norton ([email protected]
).
LETS is an alternative Erlang Term Storage using LevelDB as the storage implementation. LETS tries to address some bad properties of ETS and DETS. ETS is limited by physical memory. DETS is limited by a 2 GB file size limitation and does not implement ordered sets. LETS has neither of these limitations. Data can also be automatically compressed using the Snappy compression library. In addition, the name of a LETS table can be any Erlang term.
LETS is not intended to be an exact clone of ETS. The currently supported ETS APIs are:
-
all/0
-
delete/1
-
delete/2
-
delete_all_objects/1
only ets implementation -
first/1
-
foldl/3
-
foldr/3
-
info/1
only a subset of items -
info/2
only a subset of items -
insert/2
-
insert_new/2
only ets implementation -
last/1
-
lookup/2
-
lookup_element/3
-
match/1
-
match/2
-
match/3
-
match_delete/2
-
match_object/1
-
match_object/2
-
match_object/3
-
member/2
-
new/2
-
next/2
-
prev/2
-
select/1
-
select/2
-
select/3
-
select_count/2
-
select_delete/2
-
select_reverse/1
-
select_reverse/2
-
select_reverse/3
-
tab2list/1
For testing and comparison purposes, LETS supports three backend implementations:
-
drv
C++ Driver with LevelDB backend (default) -
nif
C++ NIF with LevelDB backend -
ets
Erlang ETS backend
This repository is experimental in nature - use at your own risk and please contribute if you find LETS useful.
To download and build the lets application in one shot, please follow this recipe:
$ mkdir working-directory-name
$ cd working-directory-name
$ git clone https://github.com/norton/lets.git lets
$ cd lets
$ make deps clean compile
OR if QuickCheck is available then follow this recipe:
$ mkdir working-directory-name
$ cd working-directory-name
$ git clone https://github.com/norton/lets.git lets
$ cd lets
$ make deps clean eqc
$ (cd .qc; erl -smp +A 5 -pz ../deps/sext/ebin -pz ../deps/gen_ets/ebin -pz ../deps/qc/ebin)
1> qc_statem_lets:qc_run(5000).
....
OK, passed 5000 tests
9.022% {delete,ok}
7.800% {new,ok}
4.535% {match_delete,ok}
4.491% {lookup,ok}
4.399% {select,ok}
4.352% {select_delete,ok}
4.348% {tab2list,ok}
4.341% {member,ok}
4.334% {last,ok}
4.315% {foldl,ok}
4.308% {select_reverse,ok}
4.301% {select_count,ok}
4.293% {select31,ok}
4.264% {first,ok}
4.216% {foldr,ok}
4.202% {match_object,ok}
4.184% {match,ok}
4.056% {insert,ok}
3.997% {prev,ok}
3.774% {next,ok}
3.416% {lookup_element,{error,badarg}}
1.298% {insert_new,ok}
0.757% {lookup_element,ok}
0.516% {next,{error,badarg}}
0.483% {prev,{error,badarg}}
true
.......
For an alternative recipe with other "features" albeit more complex, please read further.
This README is the only bit of documentation right now.
The QC (a.k.a. QuickCheck, PropEr, etc.) tests underneath the "tests/qc" directory should be helpful for understanding the specification and behavior of ETS and LETS. These QC tests also illustrate several strategies for testing Erlang Driver-based and NIF-based implementations.
ETS and DETS are Erlang/OTP's standard library modules for Erlang term storage. ETS is a memory-based implementation. DETS is a disk-based implementation.
See http://www.erlang.org/doc/man/ets.html and http://www.erlang.org/doc/man/dets.html for further details.
LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values.
See http://code.google.com/p/leveldb/ for further details.
Snappy is a fast compression/decompression library written at Google.
See http://code.google.com/p/snappy/ for further details.
-
Configure your e-mail and name for Git
$ git config \--global user.email "[email protected]" $ git config \--global user.name "Your Name"
-
Install Repo
$ mkdir -p ~/bin $ wget -O - https://dl-ssl.google.com/dl/googlesource/git-repo/repo > ~/bin/repo $ chmod a+x ~/bin/repo
-
Create working directory
$ mkdir working-directory-name $ cd working-directory-name $ repo init -u https://github.com/norton/manifests.git -m lets-default.xml
Note Your "Git" identity is needed during the init step. Please enter the name and email of your GitHub account if you have one. Team members having read-write access are recommended to use "repo init -u [email protected]:norton/manifests.git -m lets-default-rw.xml". Tip If you want to checkout the latest development version, please append " -b dev" to the repo init command. -
Download Git repositories
$ cd working-directory-name $ repo sync
For further information and help for related tools, please refer to the following links:
-
Erlang - http://www.erlang.org/
-
R16B or newer, R16B has been tested most recently
-
-
Git - http://git-scm.com/
-
Git 1.5.4 or newer, Git 1.8.2 has been tested most recently
-
required for Repo and GitHub
-
-
GitHub - https://github.com
-
Python - http://www.python.org
-
Python 2.4 or newer, Python 2.7.3 has been tested most recently (CAUTION: Python 3.x might be too new)
-
required for Repo
-
-
Get and install an erlang system http://www.erlang.org
-
Build
$ cd working-directory-name $ make compile
-
Dialyzer Testing basic recipe
-
Build Dialyzer's PLT (required once)
$ cd working-directory-name $ make build-plt
Tip Check Makefile and dialyzer's documentation for further information. -
Dialyze with specs
$ cd working-directory-name $ make dialyze
Caution If you manually run dialyzer with the "-r" option, execute "make clean compile" first to avoid finding duplicate beam files underneath rebar's .eunit directory. Check Makefile for further information. -
Dialyze without specs
$ cd working-directory-name $ make dialyze-nospec
-
-
Make sure QuickCheck is in your Erlang code path. One simple way to accomplish this is by adding the code path to your
~/.erlang
resource file.true = code:add_pathz(os:getenv("HOME")++"/.erlang.d/deps/quviq/eqc-X.Y.Z/ebin").
-
Compile for QuickCheck
$ cd working-directory-name $ make clean $ make compile-for-eqc
-
Run 5,000 QuickCheck tests
$ cd working-directory-name/deps/lets/.qc $ erl -smp +A 5 -pz ../../sext/ebin -pz ../../gen_ets/ebin -pz ../../qc/ebin 1> qc_statem_lets:qc_run(5000). .... OK, passed 5000 tests 9.022% {delete,ok} 7.800% {new,ok} 4.535% {match_delete,ok} 4.491% {lookup,ok} 4.399% {select,ok} 4.352% {select_delete,ok} 4.348% {tab2list,ok} 4.341% {member,ok} 4.334% {last,ok} 4.315% {foldl,ok} 4.308% {select_reverse,ok} 4.301% {select_count,ok} 4.293% {select31,ok} 4.264% {first,ok} 4.216% {foldr,ok} 4.202% {match_object,ok} 4.184% {match,ok} 4.056% {insert,ok} 3.997% {prev,ok} 3.774% {next,ok} 3.416% {lookup_element,{error,badarg}} 1.298% {insert_new,ok} 0.757% {lookup_element,ok} 0.516% {next,{error,badarg}} 0.483% {prev,{error,badarg}} true .......
Tip For testing LevelDB directly using the C bindings, try qc_statemc_lets:qc_run(5000)
.
-
Make sure PropEr is in your Erlang code path. One simple way to accomplish this is by adding the code path to your
~/.erlang
resource file.true = code:add_pathz(os:getenv("HOME")++"/.erlang.d/deps/proper/ebin").
-
Compile for PropEr
$ cd working-directory-name $ make clean $ make compile-for-proper
-
Run 5,000 PropEr tests
$ cd working-directory-name/deps/lets/.qc $ erl -smp +A 5 -pz ../../sext/ebin -pz ../../gen_ets/ebin -pz ../../qc/ebin 1> qc_statem_lets:qc_run(5000). .... OK: Passed 5000 test(s). 11% {new,ok} 8% {delete,ok} 4% {member,ok} 4% {select,ok} 4% {select_count,ok} 4% {select_reverse,ok} 4% {lookup,ok} 4% {match_object,ok} 4% {tab2list,ok} 4% {last,ok} 4% {match,ok} 4% {foldl,ok} 4% {match_delete,ok} 3% {prev,ok} 3% {select31,ok} 3% {select_delete,ok} 3% {foldr,ok} 3% {insert,ok} 3% {first,ok} 3% {next,ok} 3% {lookup_element,{error,badarg}} 1% {insert_new,ok} 0% {prev,{error,badarg}} 0% {lookup_element,ok} 0% {next,{error,badarg}} true .......
-
Documentation
-
Explain how to run QuickCheck/PropEr tests using a new rebar plugin.
-
Explain how to build and to run lets with valgrind enabled OTP/Erlang virtual machine
-
-
Testing - Black Box
-
Functional
-
Update test model to include LevelDB's database, read, and write options. These options have not been tested.
-
Update test model to include LevelDB's destroy and repair operations. These operations have not been tested.
-
-
Performance (TBD)
-
Stability (TBD)
-
-
Testing - White (or more like "Grey") Box
-
Goals
-
Test normal, abnormal, and corner test cases without having to actually use "big data" or invoke lots of operations. Invoke operations using small inputs but with varying sizes, ranges, and patterns.
-
Learn about what special parameters exist, their default values and ranges, and the difficulty to control these parameters on a request-by-request basis (at best case).
-
-
Functional (TBD)
-
Enable/disable background compaction
-
Invoke/suspend manual compaction
-
Force new memtable creation
-
Force new level creation
-
Database Recovery (i.e. closing/reopening the db)
-
Large keys (e.g. 1KB)
-
Adjacent keys that share a long prefix (e.g ~1KB); useful since file format has prefix compression
-
Snapshots that are live across compactions and are read from after compaction
-
Iterators that are live across compactions and are read from after compaction
-
File system writes return errors (e.g., disk-full)
-
-
-
New APIs (TBD)
-
insert_new/2
(http://code.google.com/p/leveldb/issues/detail?id=42) -
delete_all_objects/1
(http://code.google.com/p/leveldb/issues/detail?id=43) -
Add custom (i.e. not supported by native ETS) APIs for providing access to LevelDB's iterators for
drv
andnif
backend implementations.
-
-
Existing APIs (TBD)
-
delete/1
(http://code.google.com/p/leveldb/issues/detail?id=48) -
new/2
- (http://code.google.com/p/leveldb/issues/detail?id=49) -
new/2
- investigate if LevelDB's snapshot feature is useful (or not) for LETS -
info/2
- investigate if LevelDB's implementation can (easily) support size and memory info items -
consider adding explicit read_options and write_options for LET's operations (rather than just
new/2
,destroy/2
, andrepair/2
operations).
-
lets |
lets_impl_drv |
lets_impl_nif |