The nsnotifyd daemon monitors a set of DNS zones and
runs a command when any of them change. It listens for DNS NOTIFY
messages so it can respond to changes promptly. It also uses each
zone’s SOA refresh and retry parameters to poll for updates if
nsnotifyd does not receive NOTIFY messages more frequently. It comes
with a client program nsnotify for sending notify messages.
The new -S option tells nsnotifyd to send all SOA queries to
a specific server.
Previously, in response to a NOTIFY message, it would send a SOA
query back to the source of the NOTIFY, as specified by RFC 1996.
(Typically, a NOTIFY will only be accepted from a known
authoritative server for the zone. The target of the NOTIFY
responds with a SOA refresh query and zone transfer. But it should
avoid trying to refresh from one of the other authoritative
servers which might not have received the latest version of the
zone.)
Mark Felder encountered a situation where it would have
been more convenient to fix the address that nsnotifyd sends SOA
queries to, because the source of the NOTIFY messages wasn’t
responding on that address.
Since nsnotifyd is intended to work as glue between disparate
parts of a system, it makes sense for it to work around awkward
interoperability problems.
The nsnotify client program was broken and unable to create
NOTIFY messages. D’oh!
I have adjusted the release process so that it works better with
git archive and web front-ends that offer tarball downloads.
I’m writing a simulation, or rather, I’m procrastinating, and this
blog post is the result of me going off on a side-track from the main
quest.
The simulation involves a bunch of tasks that go through a series of
steps with delays in between, and each step can affect some shared
state. I want it to run in fake virtual time so that the delays are
just administrative updates to variables without any real
sleep()ing, and I want to ensure that the mutations happen in the
right order.
I thought about doing this by representing each task as an enum State with a big match state to handle each step. But then I
thought, isn’t async supposed to be able to write the enum State and
match state for me? And then I wondered how much the simulation
would be overwhelmed by boilerplate if I wrote it using async.
Rather than digging around for a crate that solves my problem, I
thought I would use this as an opportunity to learn a little about
lower-level async Rust.
Turns out, if I strip away as much as possible, the boilerplate can
fit on one side of a sheet of paper if it is printed at a normal font
size. Not too bad!
There is an IETF draft that aims to standardize RateLimit header
fields for HTTP. A RateLimit header in a successful response
can inform a client when it might expect to be throttled, so it can
avoid 429 Too Many Requests errors. Servers can also
include RateLimit headers in a 429 response to make the error more
informative.
The draft is in reasonably good shape. However as written it seems to
require (or at least it assumes) that the server uses bad quota-reset
rate limit algorithms. Quota-reset algorithms encourage clients into
cyclic burst-pause behaviour; the draft has several paragraphs
discussing this problem.
However, if we consider that RateLimit headers are supposed to tell
the client what acceptable behaviour looks like, they can be used with
any rate limit algorithm. (And it isn’t too hard to rephrase the draft
so that it is written in terms of client behaviour instead of server
behaviour.)
When a client has more work to do than will fit in a single window’s
quota, linear rate limit algorithms such as GCRA encourage the client
to smooth out its requests nicely. In this article I’ll describe how a
server can use a linear rate limit algorithm with HTTP RateLimit
headers.
A while back I wrote about the linear rate limit algorithms leaky
bucket and GCRA. Since then I have been vexed by how common
it is to implement rate limiting using complicated and wasteful
algorithms (for example).
But linear (and exponential) rate limiters have a disadvantage:
they can be slow to throttle clients whose request rate is above the
limit but not super fast. And I just realised that this disadvantage
can be unacceptable in some situations, when it’s imperative that no
more than some quota of requests is accepted within a window of time.
In this article I’ll explore a way to enforce rate limit quotas more
precisely, without undue storage costs, and without encouraging
clients to oscillate between bursts and pauses. However I’m not sure
it’s a good idea.
There are four variants of the algorithm for shuffling an array,
arising from two independent choices:
whether to swap elements in the higher or lower parts of the array
whether the boundary between the parts moves upwards or downwards
The variants are perfectly symmetrical, but they work in two
fundamentally different ways: sampling or permutation.
The most common variant is Richard Durstenfeld’s shuffle
algorithm, which moves the boundary downwards and swaps
elements in the lower part of the array. Knuth describes it in TAOCP
vol. 2 sect. 3.4.2; TAOCP doesn’t discuss the other variants.
(Obeying Stigler’s law, it is often called a “Fisher-Yates”
shuffle, but their pre-computer algorithm is arguably different from
the modern algorithm.)
Concrete tetrapods are used to dissipate wave energy in
coastal defences.
There’s a bit of a craze for making tetrapod-shaped things: recently
I’ve seen people making a plush tetrapod and a tetrapod
lamp. So I thought it might be fun to model one.
I found a nice way to describe tetrapods that relies on very few
arbitrary aesthetic choices.
Recently, Chris “cks” Siebenmann has been working on
ratelimiting HTTP bots that are hammering his blog. His articles
prompted me to write some clarifications, plus a few practical
anecdotes about ratelimiting email.
Although it looks really good, I have not yet tried the Jujutsu (jj)
version control system, mainly
because it’s not yet clearly superior to Magit.
But I have been following jj discussions with great interest.
One of the things that jj has not yet tackled is how to do better than
git refs / branches / tags. As I underestand it, jj currently has
something like Mercurial bookmarks, which are more like raw git ref
plumbing than a high-level porcelain feature. In particular, jj lacks
signed or annotated tags, and it doesn’t have branch names that
always automatically refer to the tip.
This is clearly a temporary state of affairs because jj is still
incomplete and under development and these gaps are going to be
filled. But the discussions have led me to think about how git’s
branches are unsatisfactory, and what could be done to improve them.
What does it mean when someone writes that a programming language is
“strongly typed”?
I’ve known for many years that “strongly typed” is a poorly-defined
term. Recently I was prompted on Lobsters to
explain why it’s hard to understand what someone means when they use
the phrase.
Previously, I wrote some sketchy ideas for what I call a p-fast
trie, which is basically a wide fan-out variant of an x-fast
trie. It allows you to find the longest matching prefix or nearest
predecessor or successor of a query string in a set of names in
O(log k) cache misses, where k is the key length.
My initial sketch was more complicated and greedy for space than
necessary, so here’s a simplified revision.
Here’s a sketch of an idea that might or might not be a good idea.
Dunno if it’s similar to something already described in the literature
– if you know of something, please let me know via the links in the
footer!
The gist is to throw away the tree and interior pointers from a
qp-trie. Instead, the p-fast trie is stored using a hash map organized
into stratified levels, where each level corresponds to a prefix of
the key.
Exact-match lookups are normal O(1) hash map lookups. Predecessor /
successor searches use binary chop on the length of the key. Where a
qp-trie search is O(k), where k is the length of the key, a p-fast
trie search is O(log k).
This smaller O(log k) bound is why I call it a “p-fast trie” by
analogy with the x-fast trie, which has O(log log N) query time. (The
“p” is for popcount.) I’m not sure if this asymptotic improvement is
likely to be effective in practice; see my thoughts towards the end of
this note.
At the time I had previously been responsible for Cambridge
University’s email anti-spam system for about 10 years, and in 2014 I
had been given responsibility for Cambridge University’s DNS. So I
knew how Let’s Encrypt should validate mail domains.
Let’s Encrypt was about one year old. Unusually, the code
that runs their operations, Boulder, is free software and open to
external contributors.
Boulder is written in Golang, and I had not previously written any
code in Golang. But its reputation is to be easy to get to grips with.
So, in principle, the bug was straightforward for me to fix. How
difficult would it be as a Golang newbie? And what would Let’s
Encrypt’s contribution process be like?
I cloned the Boulder repository and had a look around the code.
As is pretty typical, there are a couple of stages to fixing a bug in
an unfamiliar codebase:
work out where the problem is
try to understand if the obvious fix could be better
In this case, I remember discovering a relatively substantial TODO
item that intersected with the bug. I can’t remember the details, but
I think there were wider issues with DNS lookups in Boulder. I decided
it made sense to fix the immediate problem without getting involved in
things that would require discussion with Let’s Encrypt staff.
I faffed around with the code and pushed something that looked like it
might work.
A fun thing about this hack is that I never got a working Boulder test
setup on my workstation (or even Golang, I think!) – I just relied on
the Let’s Encrypt cloud test setup. The feedback time was very slow,
but it was tolerable for a simple one-off change.
I thought Golang (at least as it was used in the Boulder codebase) was
as easy to get to grips with as promised. I did not touch it again
until several years later, because there was no need to, but it seemed
fine.
I was very impressed by the Let’s Encrypt continuous integration and
automated testing setup, and by their low-friction workflow for
external contributors. One of my fastest drive-by patches to get into
worldwide production.
My fix was always going to be temporary, and all trace of it was
overwritten years ago. It’s good when “temporary” turns out to be
true!
I was reminded of this story in the pub this evening, and I thought it
was worth writing down. It demonstrated to me that Let’s Encrypt
really were doing all the good stuff they said they were doing.
So thank you to Let’s Encrypt for providing an exemplary service and
for giving me a happy little anecdote.
A couple of years ago I wrote about random floating point
numbers. In that article I was mainly concerned about how
neat the code is, and I didn’t pay attention to its performance.
In hot weather I like to drink my coffee in an iced latte. To make it,
I have a very large Bialetti Moka Express. Recently when I
got it going again after a winter of disuse, it took me a couple of
attempts to get the technique right, so here are some notes as a
reminder to my future self next year.
About half a year ago I encountered a paper bombastically
titled “the ultimate conditional syntax”. It has the
attractive goal of unifying pattern match with boolean if tests,
and its solution is in some ways very nice. But it seems
over-complicated to me, especially for something that’s a basic
work-horse of programming.
I couldn’t immediately see how to cut it down to manageable
proportions, but after reading syntactic musings on match expressions
by Yoshua Wuyts a couple of weeks ago, I had an idea. I’ll
outline it under the “penultimate conditionals” heading below, after
reviewing the UCS and explaining my motivation.
Tony Finch – blog