Redis Dynamic Memory Analzyer

 

In previous posts, I've displayed examples for Trie implementation in GO, and for how to analyze Redis memory usage. In this post we will combine both to a dynamic analyzer of redis memory usage.

First we will change the Trie to keep some Redis related information within each of the Trie node:

package trie

import "sort"

type NodeData struct {
 Count           int
 Size            int64
 NotPrintedSize  int64
 NotPrintedCount int
 TotalSize       int64
}

type Scanner func(path []rune, node *Node)

type Node struct {
 value    rune
 Data     *NodeData
 Children map[rune]*Node
}

func ProduceTrie() *Node {
 return &Node{
  Children: make(map[rune]*Node),
  Data:     &NodeData{},
 }
}

func (n *Node) AddNode(values []rune, size int64) {
 if len(values) == 0 {
  n.Data.Count++
  n.Data.Size = size
  return
 }

 childName := values[0]
 child, exists := n.Children[childName]
 if !exists {
  child = ProduceTrie()
  child.value = childName
  n.Children[childName] = child
 }

 child.AddNode(values[1:], size)
}

func (n *Node) TraverseDepthFirst(scanner Scanner) {
 n.traverseDepthFirst(scanner, nil)
}

func (n *Node) traverseDepthFirst(scanner Scanner, path []rune) {
 var newPath []rune
 if path == nil {
  newPath = make([]rune, 0)
 } else {
  newPath = make([]rune, len(path)+1)
  for i, value := range path {
   newPath[i] = value
  }
  newPath[len(path)] = n.value
 }

 sorted := n.sortedNodes()
 for _, name := range sorted {
  child := n.Children[name]
  child.traverseDepthFirst(scanner, newPath)
 }

 scanner(newPath, n)
}

func (n *Node) sortedNodes() []rune {
 sorted := make([]rune, 0)

 for name := range n.Children {
  sorted = append(sorted, name)
 }
 sort.Slice(sorted, func(i, j int) bool {
  return sorted[i] < sorted[j]
 })
 return sorted
}

Notice that each trie node represents one letter, so the redis key "abc" is represented by 3 nodes.

Each of the trie node holds information about how many keys are ending in this node, which is equal to 0 in case it is only in the middle of a key (for example "a", and "b" nodes for key "abc"), and equals to 1 in case it is the end of the key (for example "c" node for key "abc"). 

In addition, each node holds information about the TotalSize of all it children recursively. 

Now we we build the trie by scanning the redis keys.

type Analyzer struct {
 redisApi      redisapi.RedisApi
 root          *trie.Node
 printFraction float32
 report        []string
}

func ProduceAnalyzer(
 redisApi redisapi.RedisApi,
 printFraction float32,
) *Analyzer {
 return &Analyzer{
  redisApi:      redisApi,
  printFraction: printFraction,
  root:          trie.ProduceTrie(),
 }
}

func (a *Analyzer) AnalyzeMemory(
 keysPrefix string,
) string {
 keys := a.redisApi.Keys(keysPrefix)
 progressLog := progress.ProduceProgress(len(keys), "scan keys")

 totalMemory := int64(0)
 for _, key := range keys {
  keyMemory, _ := a.memoryUsageSafe(key)
  totalMemory += keyMemory
  a.root.AddNode([]rune(key), keyMemory)
  progressLog.Increment()
 }

 a.buildDataBottomUp()
 return a.getSummary()
}

func (a *Analyzer) memoryUsageSafe(key string) (size int64, wrappedError error) {
 defer errsimple.WrapWithError(&wrappedError)
 size = a.redisApi.MemoryUsage(key)
 return size, wrappedError
}

func (a *Analyzer) buildDataBottomUp() {
 a.root.TraverseDepthFirst(a.buildDataScanner)
}

func (a *Analyzer) buildDataScanner(_ []rune, node *trie.Node) {
 node.Data.TotalSize = node.Data.Size

 for _, child := range node.Children {
  node.Data.TotalSize += child.Data.TotalSize
 }
}

func (a *Analyzer) getSummary() string {
 a.root.TraverseDepthFirst(a.printScanner)
 return strings.Join(a.report, "\n")
}

func (a *Analyzer) printScanner(path []rune, node *trie.Node) {
 totalSizeAll := float32(a.root.Data.TotalSize)
 printThreshold := int64(totalSizeAll * a.printFraction)

 anyChildPrinted := false
 node.Data.NotPrintedSize = node.Data.Size
 node.Data.NotPrintedCount = node.Data.Count
 for _, child := range node.Children {
  node.Data.NotPrintedSize += child.Data.NotPrintedSize
  node.Data.NotPrintedCount += child.Data.NotPrintedCount
  if child.Data.NotPrintedSize == 0 {
   anyChildPrinted = true
  }
 }

 if node.Data.NotPrintedSize == 0 {
  return
 }

 if !anyChildPrinted && node.Data.NotPrintedSize < printThreshold {
  return
 }

 nodePercentNotPrinted := 100 * float32(node.Data.NotPrintedSize) / totalSizeAll
 nodePercentAll := 100 * float32(node.Data.TotalSize) / totalSizeAll
 line := fmt.Sprintf(
  "%9v keys, size excluding %6.3f%%, size including %6.3f%%   %s",
  node.Data.NotPrintedCount,
  nodePercentNotPrinted,
  nodePercentAll,
  string(path),
 )
 a.report = append(a.report, line)

 node.Data.NotPrintedSize = 0
 node.Data.NotPrintedCount = 0
}

The real power of this analyzer is in its dynamic representation of the memory. The analyzer builds a Trie representation of all the keys in redis with a specified prefix, but prints the Trie by a fraction value. The fraction value indicates which nodes should be printed, for example if the fraction value is 0.01, the summary includes only keys whose cumulative memory is over 1% of the redis memory. This allows a dynamic view of the redis memory, and enables a gradual analysis of the keys, while aiming to find the problematic keys.

Example of output is:

11 keys, size excluding  4.343%, size including  4.343%   aaak1
11 keys, size excluding  4.343%, size including  4.343%   aaak2
11 keys, size excluding  4.343%, size including  4.343%   aaak3
11 keys, size excluding  4.343%, size including  4.343%   aaak4
11 keys, size excluding  2.997%, size including  2.997%   aaak501
11 keys, size excluding  3.670%, size including  3.670%   aaak50201
11 keys, size excluding  3.670%, size including  3.670%   aaak50202
11 keys, size excluding  3.670%, size including  3.670%   aaak50203
11 keys, size excluding  3.670%, size including  3.670%   aaak50204
11 keys, size excluding  3.670%, size including  3.670%   aaak50205
11 keys, size excluding  3.670%, size including  3.670%   aaak50206
11 keys, size excluding  3.670%, size including  3.670%   aaak50207
11 keys, size excluding  3.670%, size including  3.670%   aaak50208
11 keys, size excluding  3.670%, size including  3.670%   aaak50209
 2 keys, size excluding  0.581%, size including 33.609%   aaak5020
10 keys, size excluding  2.722%, size including 36.330%   aaak502
11 keys, size excluding  2.997%, size including  2.997%   aaak503
11 keys, size excluding  2.997%, size including  2.997%   aaak504
11 keys, size excluding  2.997%, size including  2.997%   aaak505
11 keys, size excluding  2.997%, size including  2.997%   aaak506
11 keys, size excluding  2.997%, size including  2.997%   aaak507
11 keys, size excluding  2.997%, size including  2.997%   aaak508
11 keys, size excluding  2.997%, size including  2.997%   aaak509
 2 keys, size excluding  0.642%, size including 60.948%   aaak50
10 keys, size excluding  3.945%, size including 64.893%   aaak5
11 keys, size excluding  4.343%, size including  4.343%   aaak6
11 keys, size excluding  4.343%, size including  4.343%   aaak7
11 keys, size excluding  4.343%, size including  4.343%   aaak8
11 keys, size excluding  4.343%, size including  4.343%   aaak9
 1 keys, size excluding  0.367%, size including 100.000%   aaak