signature.go 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144
  1. // Copyright 2014 The Prometheus Authors
  2. // Licensed under the Apache License, Version 2.0 (the "License");
  3. // you may not use this file except in compliance with the License.
  4. // You may obtain a copy of the License at
  5. //
  6. // http://www.apache.org/licenses/LICENSE-2.0
  7. //
  8. // Unless required by applicable law or agreed to in writing, software
  9. // distributed under the License is distributed on an "AS IS" BASIS,
  10. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  11. // See the License for the specific language governing permissions and
  12. // limitations under the License.
  13. package model
  14. import (
  15. "sort"
  16. )
  17. // SeparatorByte is a byte that cannot occur in valid UTF-8 sequences and is
  18. // used to separate label names, label values, and other strings from each other
  19. // when calculating their combined hash value (aka signature aka fingerprint).
  20. const SeparatorByte byte = 255
  21. var (
  22. // cache the signature of an empty label set.
  23. emptyLabelSignature = hashNew()
  24. )
  25. // LabelsToSignature returns a quasi-unique signature (i.e., fingerprint) for a
  26. // given label set. (Collisions are possible but unlikely if the number of label
  27. // sets the function is applied to is small.)
  28. func LabelsToSignature(labels map[string]string) uint64 {
  29. if len(labels) == 0 {
  30. return emptyLabelSignature
  31. }
  32. labelNames := make([]string, 0, len(labels))
  33. for labelName := range labels {
  34. labelNames = append(labelNames, labelName)
  35. }
  36. sort.Strings(labelNames)
  37. sum := hashNew()
  38. for _, labelName := range labelNames {
  39. sum = hashAdd(sum, labelName)
  40. sum = hashAddByte(sum, SeparatorByte)
  41. sum = hashAdd(sum, labels[labelName])
  42. sum = hashAddByte(sum, SeparatorByte)
  43. }
  44. return sum
  45. }
  46. // labelSetToFingerprint works exactly as LabelsToSignature but takes a LabelSet as
  47. // parameter (rather than a label map) and returns a Fingerprint.
  48. func labelSetToFingerprint(ls LabelSet) Fingerprint {
  49. if len(ls) == 0 {
  50. return Fingerprint(emptyLabelSignature)
  51. }
  52. labelNames := make(LabelNames, 0, len(ls))
  53. for labelName := range ls {
  54. labelNames = append(labelNames, labelName)
  55. }
  56. sort.Sort(labelNames)
  57. sum := hashNew()
  58. for _, labelName := range labelNames {
  59. sum = hashAdd(sum, string(labelName))
  60. sum = hashAddByte(sum, SeparatorByte)
  61. sum = hashAdd(sum, string(ls[labelName]))
  62. sum = hashAddByte(sum, SeparatorByte)
  63. }
  64. return Fingerprint(sum)
  65. }
  66. // labelSetToFastFingerprint works similar to labelSetToFingerprint but uses a
  67. // faster and less allocation-heavy hash function, which is more susceptible to
  68. // create hash collisions. Therefore, collision detection should be applied.
  69. func labelSetToFastFingerprint(ls LabelSet) Fingerprint {
  70. if len(ls) == 0 {
  71. return Fingerprint(emptyLabelSignature)
  72. }
  73. var result uint64
  74. for labelName, labelValue := range ls {
  75. sum := hashNew()
  76. sum = hashAdd(sum, string(labelName))
  77. sum = hashAddByte(sum, SeparatorByte)
  78. sum = hashAdd(sum, string(labelValue))
  79. result ^= sum
  80. }
  81. return Fingerprint(result)
  82. }
  83. // SignatureForLabels works like LabelsToSignature but takes a Metric as
  84. // parameter (rather than a label map) and only includes the labels with the
  85. // specified LabelNames into the signature calculation. The labels passed in
  86. // will be sorted by this function.
  87. func SignatureForLabels(m Metric, labels ...LabelName) uint64 {
  88. if len(labels) == 0 {
  89. return emptyLabelSignature
  90. }
  91. sort.Sort(LabelNames(labels))
  92. sum := hashNew()
  93. for _, label := range labels {
  94. sum = hashAdd(sum, string(label))
  95. sum = hashAddByte(sum, SeparatorByte)
  96. sum = hashAdd(sum, string(m[label]))
  97. sum = hashAddByte(sum, SeparatorByte)
  98. }
  99. return sum
  100. }
  101. // SignatureWithoutLabels works like LabelsToSignature but takes a Metric as
  102. // parameter (rather than a label map) and excludes the labels with any of the
  103. // specified LabelNames from the signature calculation.
  104. func SignatureWithoutLabels(m Metric, labels map[LabelName]struct{}) uint64 {
  105. if len(m) == 0 {
  106. return emptyLabelSignature
  107. }
  108. labelNames := make(LabelNames, 0, len(m))
  109. for labelName := range m {
  110. if _, exclude := labels[labelName]; !exclude {
  111. labelNames = append(labelNames, labelName)
  112. }
  113. }
  114. if len(labelNames) == 0 {
  115. return emptyLabelSignature
  116. }
  117. sort.Sort(labelNames)
  118. sum := hashNew()
  119. for _, labelName := range labelNames {
  120. sum = hashAdd(sum, string(labelName))
  121. sum = hashAddByte(sum, SeparatorByte)
  122. sum = hashAdd(sum, string(m[labelName]))
  123. sum = hashAddByte(sum, SeparatorByte)
  124. }
  125. return sum
  126. }