1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
---
title: "Trillian log sequencing: demystified?"
date: 2021-02-09
---
# Trillian log sequencing: demystified?
_Rasmus Dahlberg, 2021-02-09._
One way to view
[Trillian](https://transparency.dev/)
is as
[a database with an append-only Merkle tree](https://www.rgdd.se/post/observations-from-a-trillian-play-date/).
That Merkle tree is managed by a separate component called a log signer. It runs
in a dedicated process that basically merges pending leaves that have yet to be
incorporated into the Merkle tree. This part of the log signer is structured as
a sequencing job that runs periodically. I spent a few hours learning more about
the details and thought shared knowledge is better.
## Problem definition and overview
Trillian’s
[log signer](https://github.com/google/trillian/blob/3ae67195ffd778d37275c6972445f4e7f9e21410/cmd/trillian_log_signer/main.go)
comes with a whole bunch of configuration options that are spread across several
different files. Some of these options are more difficult to grasp than others,
such as `num_sequencers`, `sequencer_interval`, and `batch_size`. I don't mean
difficult as in understanding that there may be several sequencers that run
periodically, but rather what that actually means in terms of concurrency and
how much can be sequenced per time unit.
The short answer is as follows:
1. Regardless of how many sequencers you configure there will be no concurrent
sequencing of a particular Merkle tree. The number of sequencers is only
relevant if there are multiple Merkle trees.
2. The sequencer interval tells you how often the log signer wakes up to do a
sequencing job. It sequences no more than the configured batch size before going
back to sleep. If the interval elapsed already there will be no sleep.
In other words, to avoid building up a large backlog you need to consider how
often the sequencer runs and how much work it is willing to do every time. The
longer answer is detailed below, and it includes a little bit of additional
context regarding what you may (not) do with these three parameters. For
example, the sequencer job is most reliable if it runs often over small batches.
## Log signer
The most central part of the log signer is probably its forever loop. For
reference it is implemented by Trillian’s
[operation manager](https://github.com/google/trillian/blob/3ae67195ffd778d37275c6972445f4e7f9e21410/log/operation_manager.go#L110),
see the `OperationLoop` function. In a nutshell, the log signer wakes up,
performs some jobs, and goes back to sleep. Pretty much a busy working day!
### Coordination
Before proceeding you need to know that a log signer may manage multiple
different Merkle trees. It might sound odd at first, but hopefully less so if
you think about the existence of transparency applications that use
[temporal sharding](https://www.digicert.com/dc/blog/scaling-certificate-transparency-logs-temporal-sharding/):
the split of one transparency log into multiple smaller ones so that the leaves
are grouped by, say, yearly relevance like 2020 and 2021. This allows parts of
the log to be retired as soon as they are no longer needed. You can also run
multiple different log signers to avoid single points of failure. At most one
log signer is responsible for a particular Merkle tree at a time though. This
requires coordination, which is one part of the forever loop.
### Sequencing
The other part is log sequencing. After waking up once per interval as defined
by the configured `sequencer_interval`, the log signer takes a pass over all
Merkle trees that it manages. A sequencing job is scheduled for each Merkle tree
that the log signer is currently the master for. It is determined by an election
protocol which is used for coordination in the case of multiple log signers,
otherwise master is assumed as there is nothing to coordinate. Next, these jobs
are distributed to a number of concurrent sequencers that work on _different
Merkle trees_. This means that there is no concurrency whatsoever when _a
particular Merkle tree_ is being sequenced. Moreover,
[what is selected for sequencing](https://github.com/google/trillian/blob/3ae67195ffd778d37275c6972445f4e7f9e21410/storage/mysql/queue.go#L33)
is deterministic based on Trillian’s internal timestamp order and the number of
leaves that the sequencer is willing to process per job.
In other words, there is no point setting `num_sequencers` higher than the
number of Merkle trees that you manage. You may set it lower, in which case at
least one sequencer will move on to a different sequencing job (and thus a
different Merkle tree) once it is done. Now it is also evident that the
configured `sequencer_interval` and `batch_size` determines an upper bound for
the number of writes per time unit. It is an upper bound because your hardware
might not be capable of handling, say, 10k writes per second.
## Concluding remarks
When I noticed the `sequencer_interval` parameter I wondered if it could be used
to configure a tree head frequency, such that the Trillian front-end personality
would only see a fixed number of updates per time interval. For example, you
might want that because the
[second version of Certificate Transparency requires control over it](https://datatracker.ietf.org/doc/html/draft-ietf-trans-rfc6962-bis-34#section-4.1)
and some gossip-audit models
[assume it](https://tools.ietf.org/html/draft-ietf-trans-gossip-05).
If not supported by the Trillian back-end, the front-end personality has to take
on the role. While it is trivial in the case of a single personality instance
(e.g., pick a tree head every hour), it might require some additional
coordination if there are multiple concurrent instances running. So, it would be
convenient if the _already coordinated_ log signer could enforce a tree head
frequency.
In theory it is of course possible to set the sequencer interval and batch size
to accommodate both a frequency and an upper bound for writes per second. In
practice it is apparently recommended to use short intervals and batch sizes of
up to 1000 leaves. This recommendation involves quite a bit of nuance, and
relates to things like
[which back-end is used for the underlying database](https://github.com/google/trillian/issues/1845).
If tree head frequencies are generally useful it might land as a back-end
feature at some point. For now, it is better enforced by the front-end
personality.
## Acknowledgments
This story is sponsored by my
[System Transparency](https://system-transparency.org/)
employment at Mullvad VPN. Martin Hutchinson and Pavel Kalinnikov provided
valuable insights as part of a conversation in the
[Trillian slack](https://gtrillian.slack.com).
Mistakes, if any, are my own.
|
