README
¶
FSM Mapping
Overview
This package implements a fast and efficient algorithm for generic glob style string matching using a finite state machine (FSM).
Source Hierachy
'-- fsm
'-- dump.go // functionality to dump the FSM to Dot file
'-- formatter.go // format glob templates using captured * groups
'-- fsm.go // manipulating and searching of FSM
'-- minmax.go // min() max() function for interger
FSM Explained
Per Wikipedia:
A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition.
In our use case, each state is a substring after the input StatsD metric name is splitted by ..
Add state to FSM
func (f *FSM) AddState(match string, matchMetricType string, maxPossibleTransitions int, result interface{}) int
At first, the FSM only contains three states, representing three possible metric types:
____ [gauge]
/
(start)---- [counter]
\
'--- [ timer ]
Adding a rule client.*.request.count with type counter will make the FSM to be:
____ [gauge]
/
(start)---- [counter] -- [client] -- [*] -- [request] -- [count] -- {R1}
\
'--- [timer]
{R1} is short for result 1, which is the match result for client.*.request.count.
Adding a rule client.*.*.size with type counter will make the FSM to be:
____ [gauge] __ [request] -- [count] -- {R1}
/ /
(start)---- [counter] -- [client] -- [*]
\ \__ [*] -- [size] -- {R2}
'--- [timer]
Finding a result state in FSM
func (f *FSM) GetMapping(statsdMetric string, statsdMetricType string) (*mappingState, []string)
For example, when mapping client.aaa.request.count with counter type in the
FSM, the ^1 to ^7 symbols indicate how FSM will traversal in its tree:
____ [gauge] __ [request] -- [count] -- {R1}
/ / ^5 ^6 ^7
(start)---- [counter] -- [client] -- [*]
^1 \ ^2 ^3 \__ [*] -- [size] -- {R2}
'--- [timer] ^4
To map client.bbb.request.size, FSM will do a backtracking:
____ [gauge] __ [request] -- [count] -- {R1}
/ / ^5 ^6
(start)---- [counter] -- [client] -- [*]
^1 \ ^2 ^3 \__ [*] -- [size] -- {R2}
'--- [timer] ^4
^7 ^8 ^9
Debugging
To see all the states of the current FSM, use func (f *FSM) DumpFSM(w io.Writer)
to dump into a Dot file. The Dot file can be further renderer into image using:
$ dot -Tpng dump.dot > dump.png
In StatsD exporter, one could use the following:
$ statsd_exporter --statsd.mapping-config=statsd.rules --debug.dump-fsm=dump.dot
$ dot -Tpng dump.dot > dump.png
For example, the following rules:
mappings:
- match: client.*.request.count
name: request_count
match_metric_type: counter
labels:
client: $1
- match: client.*.*.size
name: sizes
match_metric_type: counter
labels:
client: $1
direction: $2
will be rendered as:
The dot program is part of Graphviz and is
available in most of popular operating systems.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func TestIfNeedBacktracking ¶
TestIfNeedBacktracking tests if backtrack is needed for given list of mappings and whether ordering is disabled.
Types ¶
type FSM ¶
type FSM struct {
BacktrackingNeeded bool
OrderingDisabled bool
// contains filtered or unexported fields
}
func (*FSM) AddState ¶
func (f *FSM) AddState(match string, matchMetricType string, maxPossibleTransitions int, result interface{}) int
AddState adds a mapping rule into the existing FSM. The maxPossibleTransitions parameter sets the expected count of transitions left. The result parameter sets the generic type to be returned when fsm found a match in GetMapping.
func (*FSM) GetMapping ¶
GetMapping using the fsm to find matching rules according to given statsdMetric and statsdMetricType. If it finds a match, the final state and the captured strings are returned; if there's no match found, nil and a empty list will be returned.
type TemplateFormatter ¶
type TemplateFormatter struct {
// contains filtered or unexported fields
}
func NewTemplateFormatter ¶
func NewTemplateFormatter(template string, captureCount int) *TemplateFormatter
NewTemplateFormatter instantiates a TemplateFormatter from given template string and the maximum amount of captures.
func (*TemplateFormatter) Format ¶
func (formatter *TemplateFormatter) Format(captures []string) string
Format accepts a list containing captured strings and returns the formatted string using the template stored in current TemplateFormatter.
Source Files