Performance Modeling
When designing any system, besides evaluating the behavioral properties like will the system become consistent and produce correct results, the other key aspect to consider is the performance of the system. For example,
- Response latency: Mean and tail latencies
- Error rates
- Throughput: How many requests can the system handle per second
- Resource utilization
- Cost
- Scalability and so on.
We will see how to model these in FizzBee.
This article assumes, you have gone through Probabilistic modeling. We will use the same examples probabilistic modeling and add performance characteristics to it.
The performance metrics are called counters in FizzBee.
In the literature or in other tools like PRISM, usually the two terms used are either
costorreward. Unfortunately, they have either positive or negative meaning. So, we chose to usecounter.That way,
latencyis not called areward.
Let us start with the naivest example as in the probabilistic modeling - a single coin toss.
Create a folder for this example. Let’s call it simple_coin.
samples/simple-coin/CoinToss.fizz:
action Toss:
oneof:
`head` return "head"
`tail` return "tail"
Since we just want to limit to a single coin toss, the easiest way to do is, say that in fizz.yaml file.
samples/simple-coin/fizz.yaml:
options:
maxActions: 1
As we saw before, both has equal probability of 0.5 by default, that can be changed as needed.
Now, lets define te performance model config.
Here, you have a counter called points that is numeric (int or float).
samples/simple-coin/perf_model.yaml:
configs:
Toss.head:
probability: 0.5
counters:
points:
numeric: 2
Toss.tail:
probability: 0.5
counters:
points:
numeric: 1
Now, run the model checker as usual, and then run the performance model checker as well.
./fizz samples/simple-coin/CoinToss.fizz
Model checking samples/simple-coin/CoinToss.json
configFileName: samples/simple-coin/fizz.yaml
StateSpaceOptions: options:{max_actions:1 max_concurrent_actions:1}
Nodes: 4, elapsed: 80.416µs
Time taken for model checking: 85.792µs
Writen graph dotfile: samples/simple-coin/out/run_2024-05-08_22-19-26/graph.dot
To generate svg, run:
dot -Tsvg samples/simple-coin/out/run_2024-05-08_22-19-26/graph.dot -o graph.svg && open graph.svg
Max Depth 2
PASSED: Model checker completed successfully
Writen 1 node files and 1 link files to dir samples/simple-coin/out/run_2024-05-08_22-19-26
Use this, to run the performance model checker.
bazel-bin/performance/performance_bin \
--states samples/simple-coin/out/run_2024-05-08_22-19-26/ \
--source samples/simple-coin/CoinToss.json \
--perf samples/simple-coin/perf_model.yaml
Metrics(mean={'points': 1.5}, histogram=[(1.0, {'points': 1.5})])
2: 0.50000000 state: {} / returns: {"Toss":"\"head\""}
3: 0.50000000 state: {} / returns: {"Toss":"\"tail\""}
It will also show a graph, but that is not very interesting for this case.
Here, it says that the mean points is 1.5. That is because, the head gives 2 points and tail gives 1 point, with equal probability. So, the mean is 1.5.
Let us, change the probability to, say, 0.8 and 0.2.
Metrics(mean={'points': 1.2000000000000002}, histogram=[(1.0, {'points': 1.2000000000000002})])
2: 0.20000000 state: {} / returns: {"Toss":"\"head\""}
3: 0.80000000 state: {} / returns: {"Toss":"\"tail\""}
That is, expected number of points is 1.2. (0.2 * 2 + 0.8 * 1)
Using the same example from the probabilistic modeling, let us see how to add performance metrics to it.
Use the same code, but add the perf_model.yaml file.
samples/die/perf_model.yaml:
configs:
Toss.head:
counters:
toss:
numeric: 1
Toss.tail:
counters:
toss:
numeric: 1
Now, run the performance model checker.
bazel-bin/performance/performance_bin \
--states samples/die/out/run_2024-05-08_22-34-14/ \
--source samples/die/Die.json \
--perf samples/die/perf_model.yaml
Metrics(mean={'toss': 3.666666666665151}, histogram=[(0.75, {'toss': 3.0}), (0.9375, {'toss': 5.0}), (0.984375, {'toss': 7.0}), (0.99609375, {'toss': 9.0}), (0.9990234375, {'toss': 11.0}), (0.999755859375, {'toss': 13.0}), (0.99993896484375, {'toss': 15.0}), (0.9999847412109375, {'toss': 17.0}), (0.9999961853027344, {'toss': 19.0}), (0.9999990463256836, {'toss': 21.0}), (0.9999997615814209, {'toss': 23.0}), (0.9999999403953552, {'toss': 25.0}), (0.9999999850988388, {'toss': 27.0}), (0.9999999962747097, {'toss': 29.0}), (0.9999999990686774, {'toss': 31.0}), (0.9999999997671694, {'toss': 33.0}), (0.9999999999417923, {'toss': 35.0}), (0.9999999999854481, {'toss': 37.0}), (0.999999999996362, {'toss': 39.0}), (0.9999999999990905, {'toss': 41.0})])
8: 0.16666667 state: {} / returns: {"Roll":"1"}
9: 0.16666667 state: {} / returns: {"Roll":"2"}
10: 0.16666667 state: {} / returns: {"Roll":"3"}
11: 0.16666667 state: {} / returns: {"Roll":"4"}
12: 0.16666667 state: {} / returns: {"Roll":"5"}
13: 0.16666667 state: {} / returns: {"Roll":"6"}
As before, we see the termination probabilities for each state - confirms the die is fair. But what is new here is, the distribution.
The mean toss is 3.67. That is, on average, you will need 3.67 coin tosses to simulate a 6-sided die. It also has the histogram. The minimum number of tosses required 3 that happens 75% of the time. Then, 5 tosses 93.75% of the time, and so on. It takes 11 tosses to respond to 99.9% of the time.
As we tried previously, let us make a tiny change. Instead of repeating the last 2 tosses when we 0 or 7, what if we repeated all three tosses.
@@ -5,8 +5,9 @@
atomic action Roll:
- toss0 = Toss()
+
while True:
+ toss0 = Toss()
toss1 = Toss()
toss2 = Toss()
Metrics(mean={'toss': 3.999999999998181}, histogram=[(0.75, {'toss': 3.0}), (0.9375, {'toss': 6.0}), (0.984375, {'toss': 9.0}), (0.99609375, {'toss': 12.0}), (0.9990234375, {'toss': 15.0}), (0.999755859375, {'toss': 18.0}), (0.99993896484375, {'toss': 21.0}), (0.9999847412109375, {'toss': 24.0}), (0.9999961853027344, {'toss': 27.0}), (0.9999990463256836, {'toss': 30.0}), (0.9999997615814209, {'toss': 33.0}), (0.9999999403953552, {'toss': 36.0}), (0.9999999850988388, {'toss': 39.0}), (0.9999999962747097, {'toss': 42.0}), (0.9999999990686774, {'toss': 45.0}), (0.9999999997671694, {'toss': 48.0}), (0.9999999999417923, {'toss': 51.0}), (0.9999999999854481, {'toss': 54.0}), (0.999999999996362, {'toss': 57.0}), (0.9999999999990905, {'toss': 60.0})])
8: 0.16666667 state: {} / returns: {"Roll":"1"}
9: 0.16666667 state: {} / returns: {"Roll":"2"}
10: 0.16666667 state: {} / returns: {"Roll":"3"}
11: 0.16666667 state: {} / returns: {"Roll":"4"}
12: 0.16666667 state: {} / returns: {"Roll":"5"}
13: 0.16666667 state: {} / returns: {"Roll":"6"}
The result will still produce 1-6 with equal probability. Although this change, results in the fair die, but the performance characteristics is slightly different.
Now, it takes a mean of 4 coin tosses to simulate a 6-sided die instead of just 3.66. On the histogram, you can see that, 75% of the time, it still takes only 3 tosses. but the tail is getting longer with 15 tosses to reach 99.9%.
Use the example from the probabilistic modeling,
Find the average number of tosses required to simulate a fair coin, and get the histogram
- With a fair die
- With a biased die (head: 0.9, tail: 0.1)
Try this as an exercise. The samples/fair-coin/FairCoin.fizz and fizz.yaml are the same.
You just need to define the counters in the perf_model_unbiased.yaml and perf_model_biased.yaml files.
Let us introduce a slightly more complexity. Performance model a request handler, that looks up a cache, if there is a cache hit, return immediately. Else, look up the database.
When the data is found in the db, it takes some time, but when the data is not present, the latency is lower. (For example: index lookup or bloom filters lookup is usually faster and return not found, but when it has to read the data, it would usually be slower)
What is the impact of the cache on the latency and how does it change with the cache hit ratio?
In the code below, notice that we are not using any ids or values or dictionaries to implement the cache etc. This is the crux of modeling, and why modeling is so simpler and faster than doing an actual implementation and then measuring the performance
At a high level, the way you will describe this sequence of steps in a white board is literally,
- Look up the cache
- If found in cache, return
- Else, look at the db
FizzBee you can describe and analyze the system at the same level of abstraction as you think instead of bogged down by unnecessary implementation details.
samples/cache/Cache.fizz:
atomic action Lookup:
cached = LookupCache()
if cached == "hit":
return cached
found = LookupDB()
return found
func LookupCache():
oneof:
`hit` return "hit"
`miss` return "miss"
func LookupDB():
oneof:
`found` return "found"
`notfound` return "notfound"
As before, set the maxActions: 1 in the fizz.yaml file.
Run the behavioral model checker fizz samples/cache/Cache.fizz.
Now, define the performance model.
samples/cache/perf_model.yaml:
configs:
LookupCache.call:
counters:
latency_ms:
numeric: 10
LookupCache.hit:
probability: 0.2
LookupCache.miss:
probability: 0.8
LookupDB.found:
probability: 0.9
counters:
latency_ms:
numeric: 100
LookupDB.notfound:
probability: 0.1
counters_ms:
latency:
numeric: 30
Run the performance model checker. You will see,
Metrics(mean={'latency_ms': 84.4}, histogram=[(0.2, {'latency_ms': 10.0}), (1.0000000000000002, {'latency_ms': 103.0})])
2: 0.20000000 state: {} / returns: {"Lookup":"\"hit\""}
4: 0.72000000 state: {} / returns: {"Lookup":"\"found\""}
5: 0.08000000 state: {} / returns: {"Lookup":"\"notfound\""}
That is, with 20% cache hit ratio, the mean latency is 84.4. 20% of the time, data from the cache will be returned with 10ms latency. 72% of the time, data is found in the db, and 8% of the time, data is not found in the db.
Now, instead of 0.2, if you change the cache hit ratio to 0.8, you will see the mean latency is 28.6.
Metrics(mean={'latency_ms': 28.6}, histogram=[(0.8, {'latency_ms': 10.0}), (1.0, {'latency_ms': 103.0})])
2: 0.80000000 state: {} / returns: {"Lookup":"\"hit\""}
4: 0.18000000 state: {} / returns: {"Lookup":"\"found\""}
5: 0.02000000 state: {} / returns: {"Lookup":"\"notfound\""}
In the previous example, we saw only a single counter. We can have multiple counters defined the same way.
For example, let us say, you are using a cache service and hosted db service that charges per API call, then you can get the estimated cost of the service.
samples/cache/perf_model.yaml:
configs:
LookupCache.call:
counters:
latency_ms:
numeric: 10
counters:
cost:
numeric: 0.00001
LookupCache.hit:
probability: 0.2
LookupCache.miss:
probability: 0.8
LookupDB.call:
counters:
cost:
numeric: 0.0001
LookupDB.found:
probability: 0.9
counters:
latency_ms:
numeric: 100
db_hits:
numeric: 1
LookupDB.notfound:
probability: 0.1
counters:
latency_ms:
numeric: 30
In the examples so far, we saw the counters defined using simple numeric value.
It is good enough in some cases, but in many real applications like latencies,
using mean latency as a simple numeric value isn’t good enough.
We are usually interested in the tail. In that case, even for the dependencies,
we have to use the latencies.
Instead of using numeric, we can use the distribution to define the latency distribution.
Note: To give the maximum power and ease of use, FizzBee maintains the same semantics as scipy distributions. So, you can use any distribution that is available in scipy.
If you only have some data points, you can create a histogram and use therv_histogramdistribution. https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.rv_histogram.html#scipy.stats.rv_histogram
configs:
LookupCache.call:
counters:
latency_ms:
distribution: lognorm(s=0.3, loc=10)
LookupCache.hit:
probability: 0.2
LookupCache.miss:
probability: 0.8
LookupDB.found:
probability: 0.9
counters:
latency_ms:
distribution: gamma(a=3, loc=100, scale=1)
LookupDB.notfound:
probability: 0.1
counters_ms:
latency:
distribution: lognorm(s=0.5, loc=30)
If you use common cloud components, you can simply specify the latency profile.
configs:
LookupCache.call:
counters:
latency_ms:
distribution: aws.elasticache.redis.read()
LookupCache.hit:
probability: 0.2
LookupCache.miss:
probability: 0.8
LookupDB.found:
probability: 0.9
counters:
latency_ms:
distribution: aws.dynamodb.query()
LookupDB.notfound:
probability: 0.1
counters_ms:
latency:
distribution: aws.dynamodb.query()
Now that we saw how to simulate a single die with a fair coin, let us see how to simulate two dice with a fair coin. Here, unlike before, the required probabilities are not uniform.
samples/two-dice/Die.fizz
atomic func Toss():
oneof:
return 0
return 1
atomic func RollDie():
toss0 = Toss()
while True:
toss1 = Toss()
toss2 = Toss()
if (toss0 != toss1 or toss0 != toss2):
return 4 * toss0 + 2 * toss1 + toss2
atomic action TwoDice:
die1 = RollDie()
die2 = RollDie()
return die1 + die2
samples/two-dice/perf_model.yaml
configs:
Toss.call:
counters:
toss:
numeric: 1
samples/two-dice/fizz.yaml
options:
maxActions: 1
Run both the behavioral and performance model checkers.
Metrics(mean={'toss': 7.333333333332462}, histogram=[(0.5625, {'toss': 6.4375}), (0.84375, {'toss': 7.794642857142858}), (0.94921875, {'toss': 9.119642857142859}), (0.984375, {'toss': 10.427335164835167}), (0.995361328125, {'toss': 11.724210164835167}), (0.9986572265625, {'toss': 13.013683849045693}), (0.9996185302734375, {'toss': 14.297774758136601}), (0.9998931884765625, {'toss': 15.5777747581366}), (0.9999704360961914, {'toss': 16.854560472422314}), (0.9999918937683105, {'toss': 18.12875402080941}), (0.9999977946281433, {'toss': 19.400812844338823}), (0.9999994039535522, {'toss': 20.671083114609093}), (0.9999998398125172, {'toss': 21.939833114609094}), (0.9999999571591616, {'toss': 23.20727497507421}), (0.9999999885912985, {'toss': 24.473579322900296}), (0.9999999969732016, {'toss': 25.738885445349275}), (0.9999999991996447, {'toss': 27.003308522272352}), (0.9999999997889972, {'toss': 28.266944885908718}), (0.9999999999445208, {'toss': 29.529875920391476}), (0.9999999999854481, {'toss': 30.79217100235869}), (0.9999999999961915, {'toss': 32.053889752358685}), (0.9999999999962482, {'toss': 33.053889752358685}), (0.999999999999062, {'toss': 33.315083782209435}), (0.9999999999990623, {'toss': 34.315083782209435})])
50: 0.02777778 state: {} / returns: {"TwoDice":"2"}
51: 0.05555556 state: {} / returns: {"TwoDice":"3"}
52: 0.08333333 state: {} / returns: {"TwoDice":"4"}
53: 0.11111111 state: {} / returns: {"TwoDice":"5"}
54: 0.13888889 state: {} / returns: {"TwoDice":"6"}
55: 0.16666667 state: {} / returns: {"TwoDice":"7"}
56: 0.13888889 state: {} / returns: {"TwoDice":"8"}
57: 0.11111111 state: {} / returns: {"TwoDice":"9"}
58: 0.08333333 state: {} / returns: {"TwoDice":"10"}
59: 0.05555556 state: {} / returns: {"TwoDice":"11"}
60: 0.02777778 state: {} / returns: {"TwoDice":"12"}
We will see more examples on how these can be used for performance modeling actual distributed systems in the next article.
In this tutorial, we saw how to model the performance of a system using FizzBee’s python’ish language. At present, the features are limited, but we will add much better query languages.