linhash 0.3.0

Linear Hashing implementation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# LinHash

[![Crates.io](https://img.shields.io/crates/v/linhash.svg)](https://crates.io/crates/linhash)
[![API doc](https://docs.rs/linhash/badge.svg)](https://docs.rs/linhash)
![CI](https://github.com/akiradeveloper/linhash/actions/workflows/ci-master.yml/badge.svg)

Linear Hashing implementation in Rust.

## What's good about Linear Hashing?

- It is a on-disk data structure to maintain key-value mappings.
- It doesn't use much RAM except temporary buffers.
- Since queries need only one or two reads from the disk, it is very fast.
- The query performance isn't affected by the database size.
- Concurrency is studied in [Concurrency in linear hashing](https://dl.acm.org/doi/10.1145/22952.22954).
- The algorithm is simple and elegant.

## What's good about this implementation?

- GETs and INSERTs are fully concurrent.
- Use rkyv's zero-copy deserialization for fast queries.
- Use RWF_ATOMIC flag for avoiding torn writes.

## Type-safe concurrency

Each operation is designed to take a hierarchy of locks before doing its work.
This is **type-checked** by Rust compiler.

| | Read Lock | Selective Lock | Exclusive Lock |
| -- | -- | -- | -- |
| Read Lock | ✅️ | ✅️ | ❌ |
| Selective Lock | ✅️ | ❌️ | ❌️ |
| Exclusive Lock | ❌️ | ❌️ | ❌️ |

| Operation | Root Lock | Bucket Lock |
| -- | -- | -- |
| Insert | Read Lock | Selective Lock |
| Delete | Read Lock | Exclusive Lock |
| Get | Read Lock | Read Lock |
| List | Exclusive Lock | |
| Split | Read Lock | Selective Lock |

## Limitations

- Key size and value size must be fixed.

## Example

The API is as same as `HashMap`.

```rust
use linhash::LinHash;

let dir = tempfile::tempdir().unwrap();
let ksize = 2;
let vsize = 4;
let db = LinHash::open(dir.path(), ksize, vsize).unwrap();

db.insert(vec![1, 2], vec![3, 4, 5, 6]).unwrap();
let old = db.insert(vec![1, 2], vec![7, 8, 9, 10]).unwrap();
assert_eq!(old, Some(vec![3, 4, 5, 6]));

assert_eq!(db.get(&vec![1, 2]).unwrap(), Some(vec![7, 8, 9, 10]));

let old = db.delete(&vec![1, 2]).unwrap();
assert_eq!(old, Some(vec![7, 8, 9, 10]));
assert_eq!(db.get(&vec![1, 2]).unwrap(), None);
```

## Cargo Features

| flag | default | description |
| -- | -- | -- |
| hash | on | If disabled, 64 bit from the given key is taken as a hash, eliminating the cost of hashing. |