-
Notifications
You must be signed in to change notification settings - Fork 451
/
postings_list_cache_lru.go
221 lines (198 loc) · 6.9 KB
/
postings_list_cache_lru.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
// Copyright (c) 2019 Uber Technologies, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
package index
import (
"container/list"
"errors"
"github.com/m3db/m3/src/m3ninx/postings"
"github.com/pborman/uuid"
)
// PostingsListLRU implements a non-thread safe fixed size LRU cache of postings lists
// that were resolved by running a given query against a particular segment. Normally
// an key in the LRU would look like:
//
// type key struct {
// segmentUUID uuid.UUID
// pattern string
// patternType PatternType
// }
//
// However, some of the postings lists that we will store in the LRU have a fixed lifecycle
// because they reference mmap'd byte slices which will eventually be unmap'd. To prevent
// these postings lists that point to unmap'd regions from remaining in the LRU, we want to
// support the ability to efficiently purge the LRU of any postings list that belong to a
// given segment. This isn't technically required for correctness as once a segment has been
// closed, its old postings list in the LRU will never be accessed again (since they are only
// addressable by that segments UUID), but we purge them from the LRU before closing the segment
// anyways as an additional safety precaution.
//
// Instead of adding additional tracking on-top of an existing generic LRU, we've created a
// specialized LRU that instead of having a single top-level map pointing into the linked-list,
// has a two-level map where the top level map is keyed by segment UUID and the second level map
// is keyed by pattern and pattern type.
//
// As a result, when a segment is ready to be closed, they can call into the cache with their
// UUID and we can efficiently remove all the entries corresponding to that segment from the
// LRU. The specialization has the additional nice property that we don't need to allocate everytime
// we add an item to the LRU due to the interface{} conversion.
type postingsListLRU struct {
size int
evictList *list.List
items map[uuid.Array]map[patternAndPatternType]*list.Element
}
// entry is used to hold a value in the evictList.
type entry struct {
uuid uuid.UUID
pattern string
patternType PatternType
postingsList postings.List
}
type key struct {
uuid uuid.UUID
pattern string
patternType PatternType
}
type patternAndPatternType struct {
pattern string
patternType PatternType
}
// newPostingsListLRU constructs an LRU of the given size.
func newPostingsListLRU(size int) (*postingsListLRU, error) {
if size <= 0 {
return nil, errors.New("Must provide a positive size")
}
return &postingsListLRU{
size: size,
evictList: list.New(),
items: make(map[uuid.Array]map[patternAndPatternType]*list.Element),
}, nil
}
// Add adds a value to the cache. Returns true if an eviction occurred.
func (c *postingsListLRU) Add(
segmentUUID uuid.UUID,
pattern string,
patternType PatternType,
pl postings.List,
) (evicted bool) {
// Check for existing item.
uuidArray := segmentUUID.Array()
if uuidEntries, ok := c.items[uuidArray]; ok {
key := newPatternAndPatternType(pattern, patternType)
if ent, ok := uuidEntries[key]; ok {
// If it already exists, just move it to the front. This avoids storing
// the same item in the LRU twice which is important because the maps
// can only point to one entry at a time and we use them for purges. Also,
// it saves space by avoiding storing duplicate values.
c.evictList.MoveToFront(ent)
ent.Value.(*entry).postingsList = pl
return false
}
}
// Add new item.
var (
ent = &entry{
uuid: segmentUUID,
pattern: pattern,
patternType: patternType,
postingsList: pl,
}
entry = c.evictList.PushFront(ent)
key = newPatternAndPatternType(pattern, patternType)
)
if patterns, ok := c.items[uuidArray]; ok {
patterns[key] = entry
} else {
c.items[uuidArray] = map[patternAndPatternType]*list.Element{
key: entry,
}
}
evict := c.evictList.Len() > c.size
// Verify size not exceeded.
if evict {
c.removeOldest()
}
return evict
}
// Get looks up a key's value from the cache.
func (c *postingsListLRU) Get(
segmentUUID uuid.UUID,
pattern string,
patternType PatternType,
) (postings.List, bool) {
uuidArray := segmentUUID.Array()
if uuidEntries, ok := c.items[uuidArray]; ok {
key := newPatternAndPatternType(pattern, patternType)
if ent, ok := uuidEntries[key]; ok {
c.evictList.MoveToFront(ent)
return ent.Value.(*entry).postingsList, true
}
}
return nil, false
}
// Remove removes the provided key from the cache, returning if the
// key was contained.
func (c *postingsListLRU) Remove(
segmentUUID uuid.UUID,
pattern string,
patternType PatternType,
) bool {
uuidArray := segmentUUID.Array()
if uuidEntries, ok := c.items[uuidArray]; ok {
key := newPatternAndPatternType(pattern, patternType)
if ent, ok := uuidEntries[key]; ok {
c.removeElement(ent)
return true
}
}
return false
}
func (c *postingsListLRU) PurgeSegment(segmentUUID uuid.UUID) {
if uuidEntries, ok := c.items[segmentUUID.Array()]; ok {
for _, ent := range uuidEntries {
c.removeElement(ent)
}
}
}
// Len returns the number of items in the cache.
func (c *postingsListLRU) Len() int {
return c.evictList.Len()
}
// removeOldest removes the oldest item from the cache.
func (c *postingsListLRU) removeOldest() {
ent := c.evictList.Back()
if ent != nil {
c.removeElement(ent)
}
}
// removeElement is used to remove a given list element from the cache
func (c *postingsListLRU) removeElement(e *list.Element) {
c.evictList.Remove(e)
entry := e.Value.(*entry)
if patterns, ok := c.items[entry.uuid.Array()]; ok {
key := newPatternAndPatternType(entry.pattern, entry.patternType)
delete(patterns, key)
if len(patterns) == 0 {
delete(c.items, entry.uuid.Array())
}
}
}
func newPatternAndPatternType(pattern string, patternType PatternType) patternAndPatternType {
return patternAndPatternType{pattern: pattern, patternType: patternType}
}