Prepare

1
2
3
4

mkdir kickstart
cd kickstart
npm init # create package.json file
npm install --save ganache-cli mocha solc fs-extra web3@1.0.0-beta.26

Overview

1
2
3
4
5
6
7
8
9
10
11

Lottery Contract

# Variables
Name            Purpose
manager:    Address of person who created the contract
players:    Array of addresses of people who entered

# Function
Name            Purpose
enter:      Enters a player into lottery
pickWinner: Randomly picks a winner and sends them the prize pool

Overview

The fold tree is like following:

1
2
3
4
5
6

--| contracts
----| Inbox.sol
--| test
----| Inbox_test.js
--| compile.js
--| package.json

Big question

Current leveldb implementation uses uniform setting for all Bloom filters for hot and cold SSTable, which is not efficient to reduce unnecessary I/O.

Background

In leveldb, in order to reduce unnecessary I/O for non-exist data, bloom filter about SSTables are cached in the memory. When user search for a key, the key is first checked in related bloom filter. Then if bloom filter returns true, that SSTable is fetched from disk (one I/O) and leveldb uses binary search to locate that key.

Since bloom filter has a parameter, called false positive rate (FPR). It may tell a lie when the key is not exist in SSTable. This will cause unnecessary I/O. In order to reduce those I/O, we must reduce FPR and use more memory.

$$ P = \left( 1 - e ^ { - k n / m } \right) ^ { k } $$

Big question

Cloud databases should support dynamic allocation of hot and cold data to fast and slow device. So the client can get the best performance within their budget.

The author introduced a system that support dynamic allocation of storage system based on LSM-tree.