fsm

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

• func TestIfNeedBacktracking(mappings []string, orderingDisabled bool) bool
• type FSM
  • func NewFSM(metricTypes []string, maxPossibleTransitions int, orderingDisabled bool) *FSM
  • func (f *FSM) AddState(match string, matchMetricType string, maxPossibleTransitions int, ...) int
  • func (f *FSM) DumpFSM(w io.Writer)
  • func (f *FSM) GetMapping(statsdMetric string, statsdMetricType string) (*mappingState, []string)
• type TemplateFormatter
  • func NewTemplateFormatter(template string, captureCount int) *TemplateFormatter
  • func (formatter *TemplateFormatter) Format(captures []string) string

Functions

func TestIfNeedBacktracking

func TestIfNeedBacktracking(mappings []string, orderingDisabled bool) bool

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 NewFSM

func NewFSM(metricTypes []string, maxPossibleTransitions int, orderingDisabled bool) *FSM

NewFSM creates a new FSM instance

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) DumpFSM

func (f *FSM) DumpFSM(w io.Writer)

DumpFSM accepts a io.writer and write the current FSM into dot file format.

func (*FSM) GetMapping

func (f *FSM) GetMapping(statsdMetric string, statsdMetricType string) (*mappingState, []string)

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.