CloudFlare knows how to do public postmortems on outages
Posted by jpluimers on 2021/07/16
Everyone can learn from an outage. CloudFlare shows how to do it right, for instance on the RegEx-going-wild downtime 2 years ago.
So it’s time to link to that one again: [WayBack] Details of the Cloudflare outage on July 2, 2019
More like these at [WayBack] Post Mortem – The Cloudflare Blog.
More on evaluating regular expressions in linear time:
- [WayBack] Regular Expression Search Algorithm KEN THOMPSON Bell Telephone Laboratories, Inc., Murray Hill, New Jersey
- [WayBack] Programming Techniques: Regular expression search algorithm / [WayBack] Programming Techniques: Regular expression search algorithm
A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts a regular expression as source language and produces an IBM 7094 program as object language. The object program then accepts the text to be searched as input and produces a signal every time an embedded string in the text matches the given regular expression. Examples, problems, and solutions are also presented.
Programming Techniques: Regular expression search algorithm
Full Text: 
PDFAuthor: Ken Thompson Bell Telphone Labs, Inc., Murray Hill Published in:
· Magazine Communications of the ACM CACM Homepage archive Volume 11 Issue 6, June 1968
Pages 419-422
ACM New York, NY, USA
table of contents doi>10.1145/363347.363387 - Thompson’s construction – Wikipedia
is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA)
The algorithm works recursively by splitting an expression into its constituent subexpressions, from which the NFA will be constructed using a set of rules.[3] More precisely, from a regular expression E, the obtained automaton A with the transition function δ respects the following properties:
- A has exactly one initial state q0, which is not accessible from any other state. That is, for any state q and any letter a, {\displaystyle \delta (q,a)} does not contain q0.
- A has exactly one final state qf, which is not co-accessible from any other state. That is, for any letter a, {\displaystyle \delta (q_{f},a)=\emptyset }.
- Let c be the number of concatenation of the regular expression E and let s be the number of symbols apart from parentheses — that is, |, *, a and ε. Then, the number of states of A is 2s − c (linear in the size of E).
- The number of transitions leaving any state is at most two.
- Since an NFA of m states and at most e transitions from each state can match a string of length n in time O(emn), a Thompson NFA can do pattern matching in linear time, assuming a fixed-size alphabet.
- [WayBack] A Regular Expression Matcher Code by Rob Pike Exegesis by Brian Kernighan
Via [WayBack] Details of the Cloudflare outage on July 2, 2019 | Hacker News
–jeroen
The Wiert Corner - irregular stream of stuff 
Leave a Reply