共计 5917 个字符,预计需要花费 15 分钟才能阅读完成。
QuerySeries 办法实现
本篇就讲 QuerySeries 办法的实现,这儿会用到一些额定常识~
- Roaring Bitmap
- 来自 Prometheus 优化的正则匹配器
tsdb.go
func (db *TSDB) QuerySeries(matcherList LabelMatcherList, start, end int64) ([]map[string]string, error) {labelList := make([]LabelList, 0)
// 从 内存的有序 List 中获取 segment
for _, segment := range db.segments.Get(start, end) {
// 将其加载成为 segment(磁盘或者内存)segment = segment.Load()
// 依据传入的正则匹配器查问 Series,匹配器能够为 nil
data, err := segment.QuerySeries(matcherList)
if err != nil {return nil, err}
labelList = append(labelList, data...)
}
// 合并 series 的所有 label 返回
return db.mergeQuerySeries(labelList...), nil
}
从内存中查问一个 segment 之前咱们曾经实现过,就不过多介绍了,Load()
函数也上一篇写过,也不去叙述细节,间接看外围办法QuerySeries()
同样,QuerySeries()
分为从内存查问和从磁盘查问,具体从哪儿查问,次要看之前的 Load()
办法获取的 segment 是磁盘的还是内存的
memtable 内存
memtable.go
func (m *memtable) QuerySeries(matcherList LabelMatcherList) ([]LabelList, error) {matchSeriesIds := m.indexMap.MatchSids(m.labelVs, matcherList)
ret := make([]LabelList, 0)
for _, seriesID := range matchSeriesIds {s, _ := m.segment.Load(seriesID)
series := s.(*memSeries)
ret = append(ret, series.labels)
}
return ret, nil
}
indexMap
保留的就是 key=labelName,value = seriesList
的数据,所以上述代码,外围就是 MatchSids,查问出以后 segment 中所有我须要的 labelName 对应的 series。
index.go
func (mim *memtableIndexMap) MatchSids(valueList *labelValueList, matcherList LabelMatcherList) []string {mim.mutex.Lock()
defer mim.mutex.Unlock()
seriesIdList := newMemtableSidList()
var got bool
for i := len(matcherList) - 1; i >= 0; i-- {temp := newMemtableSidList()
vs := valueList.Match(matcherList[i])
for _, value := range vs {mimIndex := mim.index[joinSeprator(matcherList[i].Name, value)]
if mimIndex == nil || mimIndex.Size() <= 0 {continue}
temp.Union(mimIndex.Copy())
}
if temp == nil || temp.Size() <= 0 {return nil}
if !got {
seriesIdList = temp
got = true
continue
}
seriesIdList.DeleteSids(temp.Copy())
}
return seriesIdList.List()}
这儿两个点
-
通过优化的正则优化器去查问符合条件的 label
这儿差一点,Prometheus 算是 tsdb 的 鼻祖了,举荐浏览一下它的论文,很优良
- 对于雷同的 labelName,求并集获取所有的 sid,对于不同的 labelName,求交加去获取符合条件的 sid,这样就能够获取咱们所须要的 series 了
正则优化器实现
label.go
的fastMatcher
留神,咱们传入的是 labelMatcher,而去进行正则优化的是 fastMatcher,所以须要定义两个构造体
// LabelMatcher 标签匹配器
type LabelMatcher struct {
Name string
Value string
IsRegular bool
}
type fastMatcher struct {
regular *regexp.Regexp
prefix string
suffix string
contains string
}
查找过程 Match()
办法
func (lvl *labelValueList) Match(matcher LabelMatcher) []string {ret := make([]string, 0)
if matcher.IsRegular {pattern, err := newFastRegularMatcher(matcher.Value)
if err != nil {return []string{matcher.Value}
}
for _, value := range lvl.Get(matcher.Name) {if pattern.MatchStr(value) {ret = append(ret, value)
}
}
return ret
}
return []string{matcher.Value}
}
外围步骤
-
结构 fastMatcher
func newFastRegularMatcher(value string) (*fastMatcher, error) {ret, err := regexp.Compile("^(?:" + value + ")$") if err != nil {return nil, err} parse, err := syntax.Parse(value, syntax.Perl) if err != nil {return nil, err} frm := &fastMatcher{regular: ret,} if parse.Op == syntax.OpConcat {frm.prefix, frm.suffix, frm.contains = optimizeRegular(parse) } return frm, nil } func optimizeRegular(regular *syntax.Regexp) (prefix, sufiix, contains string) { sub := regular.Sub if len(sub) > 0 && sub[0].Op == syntax.OpBeginText {sub = sub[1:] } if len(sub) > 0 && sub[len(sub)-1].Op == syntax.OpEndText {sub = sub[:len(sub)-1] } if len(sub) <= 0 {return} if sub[0].Op == syntax.OpLiteral && (sub[0].Flags&syntax.FoldCase) == 0 {prefix = string(sub[0].Rune) } if last := len(sub) - 1; sub[last].Op == syntax.OpLiteral && (sub[last].Flags&syntax.FoldCase) == 0 {sufiix = string(sub[last].Rune) } for i := 1; i < len(sub)-1; i++ {if sub[i].Op == syntax.OpLiteral && (sub[i].Flags&syntax.FoldCase) == 0 {contains = string(sub[i].Rune) break } } return }
-
获取以后的 lableList 的所有 labelName 去通过 fastMatcher 匹配值
func (fm *fastMatcher) MatchStr(s string) bool {if !strings.EqualFold(fm.prefix, "") && !strings.HasPrefix(s, fm.prefix) {return false} if !strings.EqualFold(fm.suffix, "") && !strings.HasSuffix(s, fm.suffix) {return false} if !strings.EqualFold(fm.contains, "") && !strings.Contains(s, fm.contains) {return false} return fm.regular.MatchString(s) }
这样就能够拿到以后的 segment 中的所有的 labelName 标签,而后就能够通过 index 索引获取所有的 seriesID,而后将其全副保存起来,就是求并集的过程
func (msl *memtableSidList) Union(other *memtableSidList) {msl.mutex.Lock()
defer msl.mutex.Unlock()
for key := range msl.container {msl.container[key] = struct{}{}
}
}
而后对于不同的 labelName 的 seriesID,求交加
func (msl *memtableSidList) DeleteSids(other *memtableSidList) {msl.mutex.Lock()
defer msl.mutex.Unlock()
for key := range msl.container {_, ok := other.container[key]
if !ok {delete(msl.container, key)
}
}
}
留神,container 中保留的 key=sid, value = struct{}
至此,咱们就把内存的 MatchSids
办法实现了,接下来实现磁盘的
disk 磁盘
disk.go
func (ds *diskSegment) QuerySeries(matcherList LabelMatcherList) ([]LabelList, error) {seriesIDList := ds.indexMap.MatchSids(ds.labelVs, matcherList)
ret := make([]LabelList, 0)
for _, seriesID := range seriesIDList {ret = append(ret, ds.indexMap.MatchLabels(ds.series[seriesID].Labels...))
}
return ret, nil
}
MatchSids()
func (dim *diskIndexMap) MatchSids(lvl *labelValueList, matcherList LabelMatcherList) []uint32 {dim.mutex.Lock()
defer dim.mutex.Unlock()
bitmapList := make([]*roaring.Bitmap, 0)
for i := len(matcherList) - 1; i >= 0; i-- {bitmapTemp := make([]*roaring.Bitmap, 0)
values := lvl.Match(matcherList[i])
for _, value := range values {didIndex := dim.label2sids[joinSeprator(matcherList[i].Name, value)]
if didIndex == nil || didIndex.list.IsEmpty() {continue}
bitmapTemp = append(bitmapTemp, didIndex.list)
}
union := roaring.ParOr(4, bitmapTemp...)
if union.IsEmpty() {return nil}
bitmapList = append(bitmapList, union)
}
return roaring.ParAnd(4, bitmapList...).ToArray()}
逻辑和下面 memtable.go
的一样,然而这儿通过 roaing.bitmap 进行存储,通过 union := roaring.ParOr(4, bitmapTemp...)
执行并集,通过roaring.ParAnd(4, bitmapList...).ToArray()
求交加
这样获取所有的 sids 后,memtable 就是基于 sids 找到所有的 series 而后返回memtable.go
func (m *memtable) QuerySeries(matcherList LabelMatcherList) ([]LabelList, error) {matchSeriesIds := m.indexMap.MatchSids(m.labelVs, matcherList)
ret := make([]LabelList, 0)
for _, seriesID := range matchSeriesIds {s, _ := m.segment.Load(seriesID)
series := s.(*memSeries)
ret = append(ret, series.labels)
}
return ret, nil
}
磁盘则是通过 seriesID 拿到 labels 索引,而后通过索引获取 label 的值,将其拼接成为 Label 返回,可能磁盘这儿说着有点点难懂,看下数据的流转流程就清晰了。
当咱们在执行 Load()
办法将数据从磁盘中解码进去时,能够拿到 meta.Labels, 而后让 label2sids
保留 labelName 和 sids,labelOrdered
保留索引和 labelName
所以下面咱们是通过 seriesID 获取 labelOrdered 的索引,而后通过 labelOrdered 获取 labelName,其实这个 labelName 之前存储时就是 labelName+Value 存储的,所以就能够获取 label 的值了
github:https://github.com/azhsmesos/…
本文由 mdnice 多平台公布