Fixed sized storage.

[sergey-shandar]

One file of fixed size which contains a hash-table.

Minimal record (not optimal) has size 64 bytes.

struct Record {
    left: u256; // 32 bytes
    right: u256; // 32 bytes
}

Requirements:

• if file is corrupted, we should be able to restore all non-corrupted records.

Resizing

1. extend the file.
2. start copying the data from the end of the file.

Collision resolution

As additional hashing, we can use the rest of 224 hash bits. For example:

# of items	size	# of hashes
2**32 = 4_294_967_296	2**38 B = 274_877_906_944 B = 256 GiB	7 x u32
2**33 = 8_589_934_592	2**39 B = 549_755_813_888 B = 512 GiB	6 x u33
...
2**37 = 137_438_953_472	2**43 B = 8_796_093_022_208 B = 8 TiB	6 x u37
2**38 = 274_877_906_944	2**44 B = 17_592_186_044_416 B = 16 TiB	5 x u38

In this case, we can validate against all hashes.

https://en.wikipedia.org/wiki/Hash_table#Collision_resolution

Probability to find a slot when the table is 75% occupied:

# of tries	probability
1	25%
2	(16-9)/4 ~ 44%
3	(64-27)/64 ~ 57%
4	(256-81)/256 ~68%
5	(1024-243)/1024 ~76%
6	(4096-729)/4096 ~82%
7	(16384-2187)/16384 ~87%

If it's not enough, we can generate more hash bits. For example sha512::compress(hash, [0, 0]) will give 512 bits. Also, other hash functions can generate as many bits as needed. However, we should have a limit. Otherwise, we will not be able to validate if the record is correct.

If we would like to increase the size of a block, we need to store a tree structure.

# of leaves
1	1	1	0
2	1	1	0
3	2	2	1
4	2+1+2	5	2+
5	5+2+2+5	12	3+
6	12+5+4+5+12	38	5+
7	38+12+10+10+12+38	120	6+
8	120+38+24+25+24+38+120	389	8+
9	389+120+76+60+60+76+120+389	1_290	10+
10	2*(1290+389+240+190)+144	4_362	12+
11	2*(4362+1290+778+600+456)	14_972	13+