silo/masstree/README.md

   1 # Masstree #
   2
   3 This is the source release for Masstree, a fast, multi-core key-value
   4 store. This document describes how to run Masstree and interpret its
   5 results.
   6
   7 ## Contents ##
   8
   9 * `MTDIR`                     This directory
  10 * `MTDIR/doc`               Masstree algorithm specification
  11
  12 ## Installation ##
  13
  14 Masstree is tested on Debian, Ubuntu and Mac OS X. To build:
  15
  16     $ ./configure
  17     $ make
  18
  19 For performance measurements, you should disable assertions.
  20
  21     $ ./configure --disable-assertions
  22
  23 Masstree needs a fast malloc, and can link with jemalloc, Google’s
  24 tcmalloc, Hoard, or our own Flow allocator. It will normally choose
  25 jemalloc or tcmalloc, if it finds them. To use a specific memory
  26 allocator:
  27
  28     ./configure --with-malloc=<jemalloc|tcmalloc|flow|hoard>
  29
  30 Flow is our re-implementation of
  31 [Streamflow](http://people.cs.vt.edu/~scschnei/streamflow/) allocator,
  32 and may be open-sourced in future.
  33
  34 See `./configure --help` for more configure options.
  35
  36 ## Testing ##
  37
  38 The simplest way to try out Masstree is the `./mttest` program.
  39 This test doesn’t involve disk or network overhead.
  40
  41 <pre>
  42 $ ./mttest
  43 1/1 rw1/m
  44 0: now getting
  45 1: now getting
  46 0: {"table":"mb","test":"rw1","trial":0,"thread":0,"puts":13243551,"puts_per_sec":1324492.05531,"gets":13243551,"gets_per_sec":1497267.13928,"ops":26487102,"ops_per_sec":1405590.1258}
  47 1: {"table":"mb","test":"rw1","trial":0,"thread":1,"puts":13242601,"puts_per_sec":1324397.45602,"gets":13242601,"gets_per_sec":1481151.35726,"ops":26485202,"ops_per_sec":1398395.26601}
  48 EXPERIMENT x0
  49 </pre>
  50
  51 The test starts a process which hosts a Masstree, and generates and
  52 executes queries over the tree. It uses all available cores (two in
  53 the above example). The test lasts for 20 seconds. It populates the
  54 key-value store with `put` queries during first 10 seconds, and then
  55 issues `get` queries over the tree during the next 10 seconds. See
  56 `kvtest_rw1_seed` in `kvtest.hh` for more details about the workload.
  57 For a list of workloads, run `./mttest --help`.
  58
  59 The output summarizes the throughput of each core. The `1/1 rw1/m` line says
  60 that `mttest` is running the first trial (out of one trials), of the `rw1`
  61 workload using Masstree (`m` for short) as the internal data structure.
  62 When the run completes (the `now getting` lines are printed during the
  63 test), `mttest` generates a per-core throughput summary, as indicated by
  64 `0: {"table":"mb","test":"rw1",...}`.
  65
  66 If you redirect its standard output to a file or pipe, `mttest` will produce
  67 gnuplot source that plots the median per-core throughput. Each candlestick
  68 has five points for the min,20%,50%,70%,max of the corresponding metrics
  69 among all threads.
  70
  71 `mttest` also writes the output as JSON into file for further analysis. For
  72 example, after `./mttest`, `notebook-mttest.json` will contain:
  73
  74 <pre>
  75 {
  76   "experiments":{
  77     "x0":{
  78       "git-revision":"673994c43d58d46f4ebf3f7d4e1fce19074594cb",
  79       "time":"Wed Oct 24 14:54:39 2012",
  80       "machine":"mat",
  81       "cores":2,
  82       "runs":["x0\/rw1\/mb\/0"]
  83     }
  84   },
  85   "data":{
  86     "x0\/rw1\/mb\/0":[
  87       {
  88         "table":"mb",
  89         "test":"rw1",
  90         "trial":0,
  91         "thread":0,
  92         "puts":13243551,
  93         "puts_per_sec":1324492.05531,
  94         "gets":13243551,
  95         "gets_per_sec":1497267.13928,
  96         "ops":26487102,
  97         "ops_per_sec":1405590.1258
  98       },
  99       {
 100         "table":"mb",
 101         "test":"rw1",
 102         "trial":0,
 103         "thread":1,
 104         "puts":13242601,
 105         "puts_per_sec":1324397.45602,
 106         "gets":13242601,
 107         "gets_per_sec":1481151.35726,
 108         "ops":26485202,
 109         "ops_per_sec":1398395.26601
 110       }
 111     ]
 112   }
 113 }
 114 </pre>
 115
 116 Run `./mttest --help` for a list of tests and options.
 117
 118 ## Network testing ##
 119
 120 `mtclient` supports almost the same set of workloads that `mttest` does, but it
 121 sends queries to a Masstree server over the network.
 122
 123 To start the Masstree server, run:
 124
 125 <pre>
 126 $ ./mtd --logdir=[LOG_DIRS] --ckdir=[CHECKPOINT_DIRS]
 127 mb, Bag, pin-threads disabled, logging enabled
 128 no ./kvd-ckp-gen
 129 no ./kvd-ckp-0-0
 130 no ./kvd-ckp-0-1
 131 2 udp threads
 132 2 tcp threads
 133 </pre>
 134
 135 `LOG_DIRS` is a comma-separated list of directories storing Masstree
 136 logs, and `CHECKPOINT_DIRS` is a comma-separated list of directories
 137 storing Masstree checkpoints. Masstree will write its logs to the
 138 `LOG_DIRS` and periodic checkpoints to the `CHECKPOINT_DIRS`. (Both
 139 logging and multithreading are performed using multiple cores, so
 140 there are several log and checkpoint files.) Alternatively, run `./mtd
 141 -n` to turn off logging.
 142
 143 To run the `rw1` workload with `mtclient` on the same machine as
 144 `mtd`, run:
 145
 146 <pre>
 147 $ ./mtclient -s 127.0.0.1 rw1
 148 tcp, w 500, test rw1, children 2
 149 0 now getting
 150 1 now getting
 151 0 total 7632001 763284 put/s 1263548 get/s
 152 1 total 7612501 761423 put/s 1259847 get/s
 153 {"puts":7632001,"puts_per_sec":763284.211682,"gets":7632001,"gets_per_sec":1263548.30195,"ops":15264002,"ops_per_sec":951678.506329}
 154 {"puts":7612501,"puts_per_sec":761423.014367,"gets":7612501,"gets_per_sec":1259847.22076,"ops":15225002,"ops_per_sec":949182.006246}
 155 total 30489004
 156 puts: n 2, total 15244502, average 7622251, min 7612501, max 7632001, stddev 13789
 157 gets: n 2, total 15244502, average 7622251, min 7612501, max 7632001, stddev 13789
 158 puts/s: n 2, total 1524707, average 762354, min 761423, max 763284, stddev 1316
 159 gets/s: n 2, total 2523396, average 1261698, min 1259847, max 1263548, stddev 2617
 160 </pre>