#Eunomia Tree Example
This is copy of source code of Eunomia Tree with several examples to show the effectiveness of such a tree design.
##Implementation
Most implementation code of Eunomia Tree is in memstore/memstore_eunotree.h
.
There is a copy of memstore_eunotree.h
in the top directory.
All the functions related to pseudocode issues are explained in detail in the source file.
##Core Algorithm Implementations
###Section 3.2.1 Splitting HTM Region In this section, we split the monolithic HTM scope into two parts: upper region and lower region.
Such design is implemented in GetWithInsert()
function in memstore/memstore_eunotree.h
.
###Section 3.2.2 Distributed Leaf Nodes This section relates the partitioned leaf node structure, including the write scheduler, segments, and reserved keys.
Such design is implemented in struct LeafNode
in memstore/memstore_eunotree.h
.
###Section 3.2.3 Conflict Control Module This section explains the data structure and mechanism of Conflict Control Module.
Such design is implemented in util/ccm.h
###Section 3.3.1 Get/Put Interfaces This section describes the Get/Put interfaces of Eunomia, including a piece of pseudocode (Algorithm 2).
Such algorithm is implemented in GetWithInsert()
and Get()
function in memstore/memstore_eunotree.h
.
###Section 3.3.2 Insertions This section elaborates the mechanism of inserting new keys in an existing leaf node, including a piece of pesudocode (Algorithm 3).
Such algorithm is implemented in ShuffleLeafInsert()
function in memstore/memstore_eunotree.h
.
###Section 3.3.3 Splits This section illustrates the mechanism of spliting a full leaf node.
Such algorithm is implemented in ShuffleLeafInsert()
and ScopeInsert()
function in memstore/memstore_eunotree.h
##Experimental Setup in Our Paper
- CPU: 2.30GHz Intel(R) Xeon(R) E5-2650
- Cores: 2 sockets, each with 10 cores
- Cache: 32KB L1-I Cache, 32KB L1-D Cache, 256KB L2 Cache, 25MB L3 Cache
- DRAM: 256GB
- Workloads: Yahoo! Cloud Serving Benchmark (YCSB)
##Building Eunomia Tree with YCSB Workloads ./make_ycsb.sh
##Running Exmaples
cd ./script
./run_example.sh