maxogden / Level Row Versioning Benchmarks
various ways to store + retrieve versioned data in leveldb
Stars: ✭ 15
Programming Languages
javascript
184084 projects - #8 most used programming language
level-row-versioning-benchmarks
benchmarking different ways to store versioned data in leveldb.
the benchmarks store many ids each with many versions and then get the latest version of each id
to run them:
npm i
npm run bench
results
for 10,000 ids each with 25 versions
- forward.js: 987ms
- reverse.js: 924ms
- secondary.js: 475ms
benchmarks
reverse.js
- uses a single index
- stores data in format
IDÿVERSION
where bothID
andVERSION
sort lexicographically - algorithm:
- reverse read stream starting at end
- first hit is the latest revision of the highest sorting id
- end previous read stream (it had limit 1 anyway) and create a new one starting at current id
- repeat until done
number of keys required is: versions * number of ids
forward.js
- almost the same as reverse.js
- uses a single index
- stores data in format
IDÿVERSION
where bothID
andVERSION
sort lexicographically - algorithm:
- forward read stream starting at beginning
- first hit is the first sorting revision of the first sorting ID
- end current read stream, create new one at
currentId + 'ÿÿ'
- repeat until done
this requires you to store revisions in reverse lexicographical order!
number of keys required is: versions * number of ids
secondary.js
- uses two indexes,
d
which is data at each id + version andc
which is a pointer to the current version for an id - stores data in format
ÿdÿIDÿVERSION
andÿcÿID = VERSION
- algorithm:
- does a read stream of all
ÿcÿ
keys - latest revision is stored in value, combine that with key to get key of latest rev
- do db.get(latestKey) to get the current version
- does a read stream of all
number of keys required is: versions * number of ids + number of ids
Note that the project description data, including the texts, logos, images, and/or trademarks,
for each open source project belongs to its rightful owner.
If you wish to add or remove any projects, please contact us at [email protected].