-
Notifications
You must be signed in to change notification settings - Fork 4.7k
/
eventqueue.go
257 lines (231 loc) · 8.47 KB
/
eventqueue.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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
package plugin
import (
"fmt"
"reflect"
utilruntime "k8s.io/apimachinery/pkg/util/runtime"
"k8s.io/client-go/tools/cache"
)
// EventQueue is an enhanced DeltaFIFO that provides reliable Deleted deltas
// even if no knownObjects store is given, and compresses multiple deltas
// to reduce duplicate events.
//
// Without a store, DeltaFIFO will drop Deleted deltas when its queue is empty
// because the deleted object is not present in the queue and DeltaFIFO tries
// to protect against duplicate Deleted deltas resulting from Replace().
//
// To get reliable deletion, a store must be provided, and EventQueue provides
// one if the caller does not.
type EventQueue struct {
*cache.DeltaFIFO
// Private store if not intitialized with one to ensure deletion
// events are always recognized.
knownObjects cache.Store
}
func DeletionHandlingMetaNamespaceKeyFunc(obj interface{}) (string, error) {
if d, ok := obj.(cache.DeletedFinalStateUnknown); ok {
return d.Key, nil
}
return cache.MetaNamespaceKeyFunc(obj)
}
func NewEventQueue(keyFunc cache.KeyFunc) *EventQueue {
knownObjects := cache.NewStore(keyFunc)
return &EventQueue{
DeltaFIFO: cache.NewDeltaFIFO(
keyFunc,
cache.DeltaCompressorFunc(func(d cache.Deltas) cache.Deltas {
return deltaCompressor(d, keyFunc)
}),
knownObjects),
knownObjects: knownObjects,
}
}
func NewEventQueueForStore(keyFunc cache.KeyFunc, knownObjects cache.KeyListerGetter) *EventQueue {
return &EventQueue{
DeltaFIFO: cache.NewDeltaFIFO(
keyFunc,
cache.DeltaCompressorFunc(func(d cache.Deltas) cache.Deltas {
return deltaCompressor(d, keyFunc)
}),
knownObjects),
}
}
func (queue *EventQueue) updateKnownObjects(delta cache.Delta) {
switch delta.Type {
case cache.Added:
queue.knownObjects.Add(delta.Object)
case cache.Updated:
queue.knownObjects.Update(delta.Object)
case cache.Sync:
if _, ok, _ := queue.knownObjects.Get(delta.Object); ok {
queue.knownObjects.Update(delta.Object)
} else {
queue.knownObjects.Add(delta.Object)
}
case cache.Deleted:
queue.knownObjects.Delete(delta.Object)
}
}
// Function should process one object delta, which represents a change notification
// for a single object. Function is passed the delta, which contains the
// changed object or the deleted final object state. The deleted final object
// state is extracted from the DeletedFinalStateUnknown passed by DeltaFIFO.
type ProcessEventFunc func(delta cache.Delta) error
// Process queued changes for an object. The 'process' function is called
// repeatedly with each available cache.Delta that describes state changes
// for that object. If the process function returns an error queued changes
// for that object are dropped but processing continues with the next available
// object's cache.Deltas. The error is logged with call stack information.
func (queue *EventQueue) Pop(process ProcessEventFunc, expectedType interface{}) (interface{}, error) {
return queue.DeltaFIFO.Pop(func(obj interface{}) error {
// Oldest to newest delta lists
for _, delta := range obj.(cache.Deltas) {
// Update private store to track object deletion
if queue.knownObjects != nil {
queue.updateKnownObjects(delta)
}
// Handle DeletedFinalStateUnknown delta objects
var err error
if expectedType != nil {
delta.Object, err = extractDeltaObject(delta, expectedType)
if err != nil {
utilruntime.HandleError(err)
return nil
}
}
// Process one delta for the object
if err = process(delta); err != nil {
utilruntime.HandleError(fmt.Errorf("event processing failed: %v", err))
return nil
}
}
return nil
})
}
// Helper function to extract the object from a Delta (including special handling
// of DeletedFinalStateUnknown delta objects) and check its type against
// an expected type. The contained object is only returned if it matches the
// expected type, otherwise an error is returned.
func extractDeltaObject(delta cache.Delta, expectedType interface{}) (interface{}, error) {
deltaObject := delta.Object
if deleted, ok := deltaObject.(cache.DeletedFinalStateUnknown); ok {
deltaObject = deleted.Obj
}
if reflect.TypeOf(deltaObject) != reflect.TypeOf(expectedType) {
return nil, fmt.Errorf("event processing failed: got delta object type %T but wanted type %T", deltaObject, expectedType)
}
return deltaObject, nil
}
// Describes the action to take for a given combination of deltas
type actionType string
const (
// The delta combination should result in the delta being added to the compressor cache
actionAdd actionType = "ADD"
// The delta combination should should be compressed into a single delta
actionCompress actionType = "COMPRESS"
// The delta combination should result in the object being deleted from the compressor cache
actionDelete actionType = "DELETE"
)
type deltaAction struct {
// The action to take for the delta combination
action actionType
// The type for the new compressed delta
deltaType cache.DeltaType
}
// The delta combination action matrix defines the valid delta sequences and
// how to compress specific combinations of deltas.
//
// A delta combination that produces an invalid sequence results in a panic.
var deltaActionMatrix = map[cache.DeltaType]map[cache.DeltaType]deltaAction{
cache.Added: {
cache.Sync: {actionCompress, cache.Added},
cache.Updated: {actionCompress, cache.Added},
cache.Deleted: {actionDelete, cache.Deleted},
},
cache.Sync: {
cache.Sync: {actionCompress, cache.Sync},
cache.Updated: {actionCompress, cache.Sync},
cache.Deleted: {actionCompress, cache.Deleted},
},
cache.Updated: {
cache.Updated: {actionCompress, cache.Updated},
cache.Deleted: {actionCompress, cache.Deleted},
},
cache.Deleted: {
cache.Added: {actionCompress, cache.Updated},
cache.Sync: {actionCompress, cache.Sync},
},
}
func removeDeltasWithKey(deltas cache.Deltas, removeKey string, keyFunc cache.KeyFunc) cache.Deltas {
newDeltas := cache.Deltas{}
for _, d := range deltas {
key, err := keyFunc(d.Object)
if err == nil && key != removeKey {
newDeltas = append(newDeltas, d)
}
}
return newDeltas
}
// This DeltaFIFO compressor combines deltas for the same object, the exact
// compression semantics of which are as follows:
//
// 1. If a cache.Added/cache.Sync is enqueued with state X and a cache.Updated with state Y
// is received, these are compressed into (Added/Sync, Y)
//
// 2. If a cache.Added is enqueued with state X and a cache.Deleted is received with state Y,
// these are dropped and consumers will not see either event
//
// 3. If a cache.Sync/cache.Updated is enqueued with state X and a cache.Deleted
// is received with state Y, these are compressed into (Deleted, Y)
//
// 4. If a cache.Updated is enqueued with state X and a cache.Updated with state Y is received,
// these two events are compressed into (Updated, Y)
//
// 5. If a cache.Added is enqueued with state X and a cache.Sync with state Y is received,
// these are compressed into (Added, Y)
//
// 6. If a cache.Sync is enqueued with state X and a cache.Sync with state Y is received,
// these are compressed into (Sync, Y)
//
// 7. Invalid combinations (eg, Sync + Added or Updated + Added) result in a panic.
//
// This function will compress all events for the same object into a single delta.
func deltaCompressor(deltas cache.Deltas, keyFunc cache.KeyFunc) cache.Deltas {
// Final compressed deltas list
newDeltas := cache.Deltas{}
// Cache of object's current state including previous deltas
objects := make(map[string]cache.DeltaType)
// Deltas range from oldest (index 0) to newest (last index)
for _, d := range deltas {
key, err := keyFunc(d.Object)
if err != nil {
panic(fmt.Sprintf("unkeyable object: %v, %v", d.Object, err))
}
var compressAction deltaAction
if oldType, ok := objects[key]; !ok {
compressAction = deltaAction{actionAdd, d.Type}
} else {
// Older event exists; combine them
compressAction, ok = deltaActionMatrix[oldType][d.Type]
if !ok {
panic(fmt.Sprintf("invalid state transition: %v -> %v", oldType, d.Type))
}
}
switch compressAction.action {
case actionAdd:
newDeltas = append(newDeltas, d)
objects[key] = d.Type
case actionCompress:
newDelta := cache.Delta{
Type: compressAction.deltaType,
Object: d.Object,
}
objects[key] = newDelta.Type
newDeltas = removeDeltasWithKey(newDeltas, key, keyFunc)
newDeltas = append(newDeltas, newDelta)
case actionDelete:
delete(objects, key)
newDeltas = removeDeltasWithKey(newDeltas, key, keyFunc)
}
}
return newDeltas
}