README.md

# REFIT-Framework
This framework implements multiple Byzantine fault-tolerant state machine replication
protocols and system architectures. It is written in the Java programming language.

The structure of this repository is as follows:
- `src`: The protocol implementation itself
- `test`: Unit tests for some components
- `lib`: External libraries
- `scripts/config`: The framework configuration
- `scripts/{analysis,exp,queue,test}`: Scripts to distribute and run the framework as well as  to collect and analyze the experiment results
- `experiments`: Sample configurations for the framework 

## Requirements
The framework requires the following packages:

- Java Development Kit (JDK) Version >= 11
- Python >= 3.5
- rsync
- tmux
- ssh
- moreutils

## Initial setup
The benchmark scripts automatically compile the source code using the Makefile.
To build the code manually run `make` or `make test`, where the latter also compiles
the unit tests.

The experiment framework needs to know on which hosts the experiments should
be run. For this we will use the helper script `exp` which serves as the central
command from which it is possible to configure the used servers, start experiments,
retrieve results and run analysis scripts. After calling `exp shell`, which starts
a subshell, the `exp` command can be called from within any folder while the commands
effects are bound to the current repository. Calling `exp` without further parameters
prints a list of available commands.
```
> scripts/exp/exp shell
> exp servers local
```
The `servers` subcommand creates a symlink in `scripts/config` which tells the
framework which server configuration to use. A plain call of `exp servers` prints
the currently active server configuration along with a list of other available
configurations. The `local` server configuration start all servers and clients on
the local host.

Before the first run it is also necessary to generate the asymmetric keys used in certain
configurations by calling `make keys`:
```
> make keys
[...]
mkdir -p scripts/keys
java -cp bin/java:lib/eddsa-0.3.0.jar:lib/sqlite-jdbc-3.23.1.jar refit.message.REFITKeyManager
Generating 504 keys
Generating 504 keys
[...]
```

## Benchmarking
`> exp run refit example 20`

This starts a _local_ test run using the refit script (`scripts/test/refit.py`) with
a duration of _20 seconds_. The number of clients, replicas, their location, the
actual replication protocol and system architecture are automatically determined from
the configuration files `scripts/config/refit-{defaults,overrides}`. The latter
file is used to only override configuration options relevant for the experiment
setting in order to keep the configuration compact. The parameter `example` is the
scenario name and is added to the result folder name.

The experiment script automatically opens a tmux sessions with separate windows
for each client and replica. These show a live output of the experiment progress,
which is also saved to a folder in `results`.

The client (in the first tmux window) will after the initial connection setup print
one line with average throughput and latency for the last second. The values in
brackets are the minimal and maximal latency.

`> cat results/2020_06_30-14_45_23-refit-example-20/test.log`
```
[PARAM] Test run name: 2020_06_30-14_45_23-refit-example-20
[PARAM] Results directory: results/2020_06_30-14_45_23-refit-example-20
[PARAM] Testfile: refit
[PARAM] Scenario: example
[PARAM] Duration: 20
[BUILD] Building class files
make: Nothing to be done for `all'.
[BENCH] Starting server-0
[BENCH] Starting server-1
[BENCH] Starting server-2
[BENCH] Starting server-3
Number of clients: 100
ClientID offset: 4
1593521124530085 main [EVENT] BENCH: Startup delay: 0.77900004 s
[...]
1593521125294750 BENCH5 [EVENT] BENCH: OK
1593521125296458 BENCH5 [EVENT] BENCH: Start time: 1,552s
1593521125599493    1    264 163994 (  8890/813944)
1593521126608168    2   1515 103532 ( 14848/1245969)
1593521127599082    3   2150  45807 ( 18890/ 93178)
1593521128600094    4   2508  40255 (  9992/ 94144)
1593521129599925    5   2706  36658 (  8285/ 94732)
1593521130600066    6   4244  23910 (  7936/ 64995)
1593521131599183    7   4806  20773 (  7420/ 40461)
1593521132599057    8   6419  15645 (  7278/ 40885)
1593521133599279    9   8093  12400 (  6257/ 26569)
1593521134600176   10   8683  11445 (  5671/ 26666)
1593521135599403   11   8157  12306 (  6063/ 29231)
1593521136599369   12   6997  14249 (  5917/ 34595)
1593521137600348   13   8955  11221 (  4154/ 46973)
1593521138600990   14   7247  13808 (  5812/ 31575)
1593521139601636   15   8153  12224 (  6776/ 20913)
1593521140598308   16   9230  10850 (  5869/ 18810)
1593521141599036   17   9163  10890 (  5268/ 18486)
1593521142599221   18   8797  11369 (  5021/ 22746)
1593521143601304   19   9428  10642 (  5822/ 19012)
1593521144600497   20   9439  10587 (  5623/ 17408)
1593521144601042 main [EVENT] BENCH: END: 126954   6348  15760 ( 20)
=== Warmup histogram ===
Percentile 0%: 5,664000 ms
Percentile 25%: 11,775000 ms
Percentile 50%: 15,295000 ms
Percentile 75%: 26,367000 ms
Percentile 99%: 84,479000 ms
Percentile 100%: 1253,375000 ms
=== Histogram ===
Percentile 0%: 4,128000 ms
Percentile 25%: 9,855000 ms
Percentile 50%: 11,135000 ms
Percentile 75%: 12,927000 ms
Percentile 99%: 21,887000 ms
Percentile 100%: 47,103000 ms
=== Client progress ===
1105 - 1163: 14
1171 - 1228: 16
1235 - 1297: 24
1299 - 1361: 30
1370 - 1420: 16
Main client finished with return code 0
[BENCH] Waiting for clients
[BENCH] Closing screens
====================== Complete =======================
```

The servers are silent during regular operation and just print the execution progress
every few thousand executed sequence numbers.

```
1593521124679894 main [EVENT] RPLCA: READY
1593521124742943 RPLC3-0 [EVENT] ORDER: switch to REFITPBFTProtocol (view 0)
1593521124743660 RPLC3-0 [EVENT] ORDER: 0 is now the contact replica for group 0
1593521124757904 RPLC3-0 [EVENT] CLINT[0]: Configuration update (send replies: true contactReplica: 0)
1593521124782537 RPLC3-0 [EVENT] EXCTR: change checkpoint-creation setting to "regular"
1593521124782948 RPLC3-0 [EVENT] EXCTR: change update-creation setting to "disabled"
1593521125306946 RPLC3-0 [EVENT] EXCTR: Start time: 1,562s
1593521125307228 RPLC3-0 [EVENT] EXCTR:          0 @ 1593521125307092
1593521129028089 RPLC3-0 [EVENT] EXCTR:       1000 @ 1593521129027782
1593521131059981 RPLC3-0 [EVENT] EXCTR:       2000 @ 1593521131059783
1593521132405974 RPLC3-0 [EVENT] EXCTR:       3000 @ 1593521132405644
1593521133409633 RPLC3-0 [EVENT] EXCTR:       4000 @ 1593521133409460
1593521134302389 RPLC3-0 [EVENT] EXCTR:       5000 @ 1593521134302278
1593521135241370 RPLC3-0 [EVENT] EXCTR:       6000 @ 1593521135241204
1593521136316225 RPLC3-0 [EVENT] EXCTR:       7000 @ 1593521136316077
1593521137220909 RPLC3-0 [EVENT] EXCTR:       8000 @ 1593521137220707
1593521138263026 RPLC3-0 [EVENT] EXCTR:       9000 @ 1593521138262870
1593521139214084 RPLC3-0 [EVENT] EXCTR:      10000 @ 1593521139213940
1593521140143988 RPLC3-0 [EVENT] EXCTR:      11000 @ 1593521140143865
1593521140998286 RPLC3-0 [EVENT] EXCTR:      12000 @ 1593521140998166
1593521141922088 RPLC3-0 [EVENT] EXCTR:      13000 @ 1593521141921903
1593521142789127 RPLC3-0 [EVENT] EXCTR:      14000 @ 1593521142788968
1593521143625455 RPLC3-0 [EVENT] EXCTR:      15000 @ 1593521143625284
1593521144471547 RPLC3-0 [EVENT] EXCTR:      16000 @ 1593521144471374
```

The log output format of both clients and replicas always starts with a timestamp
in microseconds which is followed by the thread name (e.g. `RPLC1-0` is thread 0 on
replica 1), the log event type, the component that created the log output and the
output itself.

## Distributed execution
As a first step create a new `scripts/config/servers-*` file, for example
`servers-cloud`, and then activate it using `exp servers <name>`, for example
`exp servers cloud`. Subsequent calls to `exp run` will use this server configuration.

The server configuration file is used to resolve placeholders like `client0` configured
in `replica.network.addresses` and `client.network.addresses` of `refit-defaults` or
`refit-overrides`. Note that although the current configuration only uses placeholders
like `client0` or `server0` it is possible to use arbitrary names like `s-euw1`.
Each host entry must as a minimum contain a `client0 = <external ip>` entry with an
IP that is directly reachable from all used hosts (via ssh). By adding a suffix it
is possible to specify additional parameters for a host such as `loc` for the
location id (a zero-based counter, which should be identical for all hosts in the
same region) and `int` to specify the internal IP of a host which is accessible
for other hosts in the same region.

```
client0 = <external IP>
client0loc = 0
client0int = <internal IP>
```

The benchmarking scripts require a password-less login via SSH to each server. In
addition, the server configuration file must also contain the user name for the
remote servers and a path to where the framework repository should be copied on the
server. 

```
remote.user = username

# {} expands to the remote.user name; paths starting with ~/ are interpreted
# relative to the users home directory no futher path variable expansion will
# take place!
remote.path = remote-runner
```

The `terraform` folder contains configuration files and further instructions on how
to setup servers for measurements in EC2. 

## Variants generator and execution queue
The config files use an ini-like format containing `key = value` assignments.
Values spanning multiple lines must use trailing backslashes ` \ ` to mark line
continuations. The `REFITConfig` class checks that each setting in `refit-overrides`
actually overrides one in `refit-defaults` and that there are no unused settings.

The experiment framework provides two features to simplify the evaluation of
configuration variants. The base component is the experiment queue (`scripts/queue`)
It continuously checks a queue folder for new experiments and once a new one is found,
unpacks it and runs each command from an accompanying list. Building on that, the
variants generator provides a simple way to generate and run configuration variants,
that run the experiment using different values for a setting and are able to handle
basic conflicts and requirements between different settings.

The experiment queue consists of the `queue_runner.py` which should be started on a
server (preferably in tmux/screen) and which continuously checks the `queue/normal`
and `queue/prio` folders for queued experiments. The execution of an experiment
`<experiment-name>.tgz` works by unpacking the archive of the repository to the
`runner` folder and executing the commands listed in `<experiment-name>.tgz.commands`
(one per line) in that folder. To ensure that the execution of an experiments waits
until the upload is complete, the queue requires the creation of an empty
`<experiment-name>.tgz.marker` file. To simplify aborting failing experiments, the
queue waits for one seconds between failed experiments (according to their exit code).
Press 'Ctrl-C' during this time to abort the execution of the current experiment.

The `upload.py` script uploads the current state
of the local repository to the server and folder configured in `scripts/config/queue`.
The command list is taken from `scripts/generated-config/commands`. The upload script
is usually not called manually but rather implicitly by `exp remote ...` (see below).

Configuration variants must be specified in the `refit-overrides` configuration file.
An variants configurations for `application.request_size` could look as follows:
```
application.request_size.variants = \
    Value("1024", "data1024") \
    Value("4096", "data4096")
```
The setting's key must be suffixed with `.variants` followed by a list of values for
this key. The line containing the key must not contain a value, as shown in the
example. Each `Value(value[, name])` contains a value for a setting as first parameter
and a name as optional second parameter. The value name gets appended to the scenario
name and can be referred to as requirement `requires` or conflict `conflicts` by
later variant settings:
```
application.reply_size.variants = \
    Value("1024", requires=("data1024",)) \
    Value("4096", requires=("data4096",))
```
`requires` must be followed by a list of value names that are the prerequisite for
this Value. `conflicts` matches when any of the listed value names is part of the
scenario name. The list of value names with a single entry must be written as
`("nameA",)` whereas the trailing comma is optional with multiple entries
`("nameA", "nameB")`. 

The variant settings are evaluated from first to last in a depth-first manner. That
is the order of variant entries is relevant (the ini file format allows you to use
whatever order of settings necessary), and the last option usually changes after
between consecutive experiment variants whereas the first option only changes to each
value once.

A single experiment run with the current configuration (i.e. ignoring the variants
settings) can be queued by calling `exp remote refit example 20`. To queue the
configuration variants of an experiment call `exp remote --multi refit example 20`.
The script will run `scripts/test/helper/config-variants-generator.py` to validate
the config file syntax and generate a list of variants which is then used to create
the command list for the experiment. The results of an experiment run queued via
`exp remote` are stored on the server running the queue in the directory specified
by `queue.results`.

These experiments can be synced to a local folder via `exp result <foldername>`. The
script polls for new results every 60 seconds or immediately after pressing 'return'.

## Reproducible experiments
The results folder for an experiment run contains the configuration files that were
used by that experiment run. To repeat the execution of a specific experiment
configuration for futher analysis or debugging, `exp apply-config <result-dir>`
applies the configuration of the experiment run to `scripts/config` after creating a
backup of the current configuration. To revert to the previous configuration run
`exp apply-config --revert`.

The repository contains a set of predefined experiments in the `experiments` folder.
Each experiment contains a `run.sh` script that temporarily copies the configuration
to `scripts/config`, enqueues the experiment using the current `servers` configuration
and reverts the temporary changes. The script can either be called directly via
`./run.sh` or by calling `exp experiment <experimentA> <experimentB> ...`. Note that
an experiment configuration takes no further parameters to enforce that all settings
are stored in the configuration.

## Analysis scripts
`scripts/analysis` contains several scripts to help with the analysis of the generated
log files. `parse-logs.py` is the main analysis script and should be called from a
folder which contains the results of the experiment runs that should be analysed.
It automatically checks the logfile lengths and suggests which timespan of the
experiments runs should be used to avoid warmup / shutdown effects. For a proper
analysis it is necessary to select the exact timespan via the `--range <from> <to>`
parameter. The log parsing script currently only handles log files for experiment
runs of the `refit` script, whose results folders also contain the word `refit` at 
the start of their scenario part. 

In a nutshell the script works as follows: First it uses the parsers in
`scripts/analysis/parser` to extract useful data from various log files. Each parser
can specify which types of logfiles it is able to process. The extracted data consists
of a timestamp in microseconds (which the logfile should contain) and either a warning
message or log type dependent data fields. The analysis script assumes a reasonable
clock synchronization (using NTP) on all servers, that is clocks that diverge only by
a few milliseconds from each other.

The analysis script then converts the timestamps into relative durations since the
start of the experiment and checks the log files for warnings. The logfiles of the
client and servers are checked against a whitelist by
`scripts/analysis/transformer/{client,server.py}`. Afterwards the 10 first remaining
warnings per logfile are printed.

The next step is to group the results by their scenario and calculate the average
throughput and several latency percentiles. Then the results are trimmed to the
configured time range and are finally output in the current folder.

A fine-grained request latency analysis requires that the `client.statistics.latency`
option is set to true.

The `preview-results.py` generates preview plots of the analysis results.

## Experiment script details
The standard execution steps of an experiment script in `scripts/test` are as follows:
_repository_ refers to the current folder which also includes the README file and
if appropriate all contained files and folders.
0. Redirect the console output to a `test.log` file for the current experiment run
   in the `results` directory.
1. Build the framework locally by running `make` in the _repository_.
   This also copies the configuration files listed in `self.config_files` and
   `self.extra_files` of the experiment script to the `results` folder.
2. Read the hostnames of the servers used in the experiment from the configuration
   files (i.e. `refit-{defaults,overrides}`) by resolving all hostnames contained
   in the `DISTRIBUTE_TO_TYPES` variable of the experiment script. The usual behavior
   is to use hosts listed in `replica.network.addresses` and
   `client.network.addresses`. Then _rsync_ will copy the repository except for a
   few excluded folder (e.g. `.git`, `terraform`) to the configured hosts.
4. A benchmark usually starts multiple remote processes using the
   `scripts/test/helper/exec_helper` script which ensures that the command is
   stopped/killed after a given timeout, runs the command in the repository folder
   on the remote host and sets the `OUTPUT_DIRECTORY` and `OUTPUT_ID` environment
   variables. The directory specified by the former variable is automatically
   collected once the benchmark has completed. The helper script also automatically
   logs CPU/RAM usage, and network usage (only on EC2). The `refit` benchmark script
   first starts all replicas, then all clients, waits until the main client exits
   and stop all other processes after a short delay. The options to run java are
   read from `scripts/config/java`.
5. The log files from each hosts' `OUTPUT_DIRECTORY` are collected using `rsync`.
   At this point the files from each host are in a subfolder whose name is given
   by `OUTPUT_ID`. In case there are no colliding filenames, then the experiment
   will flatten the results folder. 

## Debugging help
To debug problems with an experiment run, take a look at log files in the results
folder, especially `test.log` and the `client*.log` and `server*.log` files.

Useful configuration options:
- `system.debug_checks` should always be set to true to enable several sanity checks
- `system.trace_messages` captures a stacktrace whenever a `REFITMessage` is created
  and thus provides information on the source of a message that caused an exception.
- `system.track_scheduler_hangs` prints a warning if a scheduler run which executes
   the actors (`REFITStage` and `REFITSchedulerTask`) takes longer than half a second.
   A hung scheduler prevents actors from receiving new messages from the network.

For debugging it is possible to run all clients and replicas in a single process by
running `REFITLocalSystem` which expects a test run duration in seconds as first
parameter. The access the state of all replicas pause the process in a debugger,
select the "main" thread and choose the stack frame pointing to REFITLocalSystem.
There all replicas are available via the "replicas" array.