Skip to content

Using Hegel for OCaml for Antithesis workloads

This is a simple test workload we call the bank test, which checks atomicity and isolation in a SQLite database and a functional correctness property on a model of a bank. Note that some code is omitted for brevity. See Further reading for the full code.

open Hegel
let busy_timeout_ms = 5_000
type config =
{ accounts : int
; initial_balance : int
; max_amount : int
}
type transfer_outcome =
| Committed
| Insufficient_funds
| Unknown
let string_of_outcome = function
| Committed -> "Committed"
| Insufficient_funds -> "Insufficient_funds"
| Unknown -> "Unknown"
;;
type t =
{ dir : string
; path : string
; mutex : Mutex.t
; mutable idle : Sqlite3.db list
; config : config
; attempted : int Atomic.t
; committed : int Atomic.t
; total : int
}

busy_timeout_ms is how long a connection waits on a locked database before it fails with SQLITE_BUSY.

The database has one accounts table with an account_id, a balance and an opCount for each account.

The database runs in WAL mode, which allows non-blocking reads while transfers are executing, and each read sees a consistent snapshot. Since writers are serialized, transfers must take the write lock first with BEGIN IMMEDIATE.

config sets the number of accounts, the starting balance of each account, and the largest transfer amount.

Transfers can have one of the following outcomes (transfer_outcome):

  • Committed: COMMIT returned successfully.
  • Insufficient_funds: the transaction was rolled back because the source balance was too low.
  • Unknown: SQLite returned an error, such as SQLITE_BUSY. The client does not know if the transaction committed.

The test state t consists of the database path, a pool of idle connections, counts of attempted and committed transfers, and the total balance. Mutable fields of t are atomic or guarded by a mutex since they may be modified concurrently.

let step db sql ?(params = []) () = ...
let int n = Sqlite3.Data.INT (Int64.of_int n)
let select_int db sql ?params () = Option.get (step db sql ?params ())
let execute db sql ?params () = ignore (step db sql ?params ())
let open_db path = ...
let with_db path f =
let db = open_db path in
Fun.protect ~finally:(fun () ->
ignore (Sqlite3.db_close db)) (fun () -> f db)
;;

step prepares a SQL statement, binds its parameters, runs it, and returns the first column of the first row or None if there is no row. select_int returns the integer from a query. execute executes a statement and throws away the resulting value. open_db opens a connection with the busy timeout set, and with_db opens a connection, runs a function on it, and closes the connection.

let init config =
let dir = Filename.temp_dir "sqlite_bank" "" in
let path = Filename.concat dir "bank.sqlite3" in
with_db path (fun db ->
execute db "PRAGMA journal_mode = WAL" ();
execute db "PRAGMA synchronous = FULL" ();
execute
db
"CREATE TABLE accounts (account_id INTEGER PRIMARY KEY, balance INTEGER NOT NULL, \
opCount INTEGER NOT NULL)"
();
execute db "BEGIN" ();
for id = 0 to config.accounts - 1 do
execute
db
"INSERT INTO accounts (account_id, balance, opCount) VALUES (?, ?, 0)"
~params:[ int id; int config.initial_balance ]
()
done;
execute db "COMMIT" ());
{ dir
; path
; mutex = Mutex.create ()
; idle = []
; config
; attempted = Atomic.make 0
; committed = Atomic.make 0
; total = config.accounts * config.initial_balance
}
;;
let close t =
List.iter (fun db -> ignore (Sqlite3.db_close db)) t.idle;
t.idle <- [];
Array.iter (fun file -> Sys.remove (Filename.concat t.dir file)) (Sys.readdir t.dir);
Sys.rmdir t.dir
;;
let with_bank config f =
let bank = init config in
Fun.protect ~finally:(fun () -> close bank) (fun () -> f bank)
;;
let with_conn t f = ...
;;

init creates the database in a temporary directory, switches it to WAL mode, and creates the accounts table with one row per account. Each account starts with the initial balance and an opCount of 0. init also records the expected total accounts * initial_balance. close closes the connections in the connection pool and deletes the database files.

with_bank wraps a function in init and close. with_conn takes an idle connection from the pool or opens a new one if the pool is empty, and returns it to the pool when the function returns.

let transfer t ~source ~dest ~amount =
Atomic.incr t.attempted;
let transaction db =
execute db "BEGIN IMMEDIATE" ();
try
let balance =
select_int
db
"SELECT balance FROM accounts WHERE account_id = ?"
~params:[ int source ]
()
in
if balance < amount
then (
execute db "ROLLBACK" ();
Insufficient_funds)
else (
execute
db
"UPDATE accounts SET balance = balance - ?, opCount = opCount + 1 WHERE \
account_id = ?"
~params:[ int amount; int source ]
();
execute
db
"UPDATE accounts SET balance = balance + ?, opCount = opCount + 1 WHERE \
account_id = ?"
~params:[ int amount; int dest ]
();
execute db "COMMIT" ();
Committed)
with
| exn ->
let backtrace = Printexc.get_raw_backtrace () in
ignore (Sqlite3.exec db "ROLLBACK");
Printexc.raise_with_backtrace exn backtrace
in
match with_conn t transaction with
| outcome ->
if outcome = Committed then Atomic.incr t.committed;
outcome
| exception (Sqlite3.Error _ | Sqlite3.SqliteError _) -> Unknown
;;

transfer increments attempted, then runs one transaction. If the source balance is less than the transfer amount, the transaction is rolled back. Otherwise, transfer subtracts the amount from the source, adds the amount to the destination, and increments opCount on both accounts. If a statement raises an exception, the transaction is rolled back and the exception is propagated.

If the transaction commits, transfer increments committed. Any SQLite error becomes Unknown.

let verify_total_balance t =
let sum =
with_conn t (fun db -> select_int db "SELECT SUM(balance) FROM accounts" ())
in
if sum <> t.total
then
Printf.ksprintf
failwith
"money was created or destroyed: SUM(balance) = %d, expected %d"
sum
t.total
;;
let verify_ops_not_lost t =
let committed = Atomic.get t.committed in
let sum =
with_conn t (fun db -> select_int db "SELECT SUM(opCount) FROM accounts" ())
in
let attempted = Atomic.get t.attempted in
if sum mod 2 <> 0
then
Printf.ksprintf failwith "SUM(opCount) = %d is odd: a transfer was half-applied" sum;
if sum < 2 * committed
then
Printf.ksprintf
failwith
"committed transfers were lost: SUM(opCount) = %d < 2 * %d committed"
sum
committed;
if sum > 2 * attempted
then
Printf.ksprintf
failwith
"phantom transfers: SUM(opCount) = %d > 2 * %d attempted"
sum
attempted
;;
let verify_no_negative t =
let negative =
with_conn t (fun db ->
select_int db "SELECT COUNT(*) FROM accounts WHERE balance < 0" ())
in
if negative <> 0
then Printf.ksprintf failwith "%d account(s) have a negative balance" negative
;;

verify_total_balance checks that SUM(balance) equals the starting total (i.e. no money was created or destroyed).

verify_ops_not_lost checks SUM(opCount). Each transfer increments two counts, so the sum must be even. The sum must be at least 2 * committed, or a committed transfer was lost. It can be higher because some transfers can commit without the client knowing, but it cannot exceed 2 * attempted.

verify_no_negative checks that no account has a balance below zero. If two transfers both read the old balance before either withdraws, the account can be overdrawn.

module%hegel_concurrent_state_machine Machine = struct
let total_balance_preserved _tc bank = verify_total_balance bank [@@invariant]
let no_committed_transfer_lost _tc bank = verify_ops_not_lost bank
[@@invariant { always_check = true }]
;;
let no_negative_balance _tc bank = verify_no_negative bank [@@invariant]
let transfer tc () bank =
let n = bank.config.accounts in
let source = draw tc (integers ~min_value:0 ~max_value:(n - 1) ()) in
let dest = draw tc (integers ~min_value:0 ~max_value:(n - 1) ()) in
let amount = draw tc (integers ~min_value:0 ~max_value:bank.config.max_amount ()) in
let outcome = string_of_outcome (transfer bank ~source ~dest ~amount) in
note tc (Printf.sprintf "transfer %d from %d to %d: %s" amount source dest outcome)
[@@rule { groups = [ "bank" ]; weight = 6 }]
;;
let verify_total_balance _tc () bank = verify_total_balance bank
[@@rule { groups = [ "bank" ] }]
;;
let verify_ops_not_lost _tc () bank = verify_ops_not_lost bank
[@@rule { groups = [ "bank" ] }]
;;
let verify_no_negative _tc () bank = verify_no_negative bank
[@@rule { groups = [ "bank" ] }]
;;
end

We can now define our workload.

We are required to define actions on the state, which are called rules in Hegel. Rules can belong to one or more groups. Only rules in the same group may execute concurrently. If no group is provided, the rule belongs to a default group. In this case, all the rules belong to the bank group for demonstration, but the group could have been omitted. Rules also have a weight, which gives Hegel a hint of how frequently a rule should run relative to other rules in its group(s). The default weight is 1.

We can optionally define statements about the system that should always be true, which are called invariants. By default, invariants are sampled for performance. For example, if we had 1 million accounts instead of 16, we might not want check no_negative_balance after every single round because it requires checking all accounts. Setting always_check = true forces the invariant to always be checked between rounds.

Notice that we define the verification functions both as invariants and rules. Invariants check the state of the system at some settled state when no actions are running. When we define the verification function as a rule, they can run while other actions are mutating the state.

For example, the invariant total_balance_preserved checks that after all transfers are done, the total amount of money has not changed. The rule verify_total_balance checks that while transfers are executing, we never see a state in which the total amount of money has changed.

let%hegel_main workload tc =
with_bank { accounts = 16; initial_balance = 1_000; max_amount = 10_000 } (fun bank ->
Machine.run
tc
~init:bank
~step_count:Int.max_int
~min_concurrency:2
~max_concurrency:8)
;;
let () = workload ()

let%hegel_main to turns the workload into a standalone program, which allows us to pass test settings as command line options, such as dune exec workload.exe -- --seed 1 --verbosity verbose.

init represents the initial state of the workload. Since the account balances are stored in the database, we only pass the bank handle, which holds the database path, the connection pool, the transfer counters, and the configuration. step_count sets how many rounds execute within a test. Inside of Antithesis, this number should be very high to allow the fuzzer ample time to explore a branch. Finally, min_concurrency and max_concurrency set the bounds for the number of concurrent workers, which can be threads, domains, or any other unit of concurrency. Hegel spawns some number of workers within those bounds.

Worker 1 Worker 2 Worker 3 Round 1: group “bank” transfer, transfer, transfer transfer, verify_no_negative verify_total_balance, transfer invariants Round 2: group “bank” transfer, verify_ops_not_lost transfer, transfer transfer, transfer, transfer invariants …

The diagram above shows how the workload is executed. In each round, Hegel chooses a group, then gives each worker a set of rules to run. Each worker executes its rules concurrently with other workers. Once all workers have finished executing their rules in a round, Hegel runs the invariants.

For the full runnable workload, see the GitHub repository.

For more information on concurrent stateful testing, see the documentation.