Add a heap to client-go. Heap orders items with heap invariant ordering. #49752

bsalamat · 2017-07-27T22:02:53Z

What this PR does / why we need it:
Heap is useful in implementing priority queues. Some components may need such ordering to process their highest priority objects first. Scheduler is going to be the first user of the heap. It will store pending pods ordered by their priority, so that the highest priority pods are popped first to be scheduled.

Which issue this PR fixes (optional, in fixes #<issue number>(, fixes #<issue_number>, ...) format, will close that issue when PR gets merged): fixes #

Special notes for your reviewer:

Release note:

NONE

ref/ #47604
ref/ #48646

@kubernetes/api-reviewers @kubernetes/sig-scheduling-pr-reviews @davidopp
/assign @caesarxuchao

dixudx · 2017-07-28T02:41:40Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	_ = heap.Interface(&HeapData{}) // HeapData is a standard heap
+)
+
+// LessFunc compares two objects and returns true if they first one should go


s/LessFunc/Less

dixudx · 2017-07-28T02:48:38Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	return obj
+}
+
+// --------------------------------------------------------------------


No need to add this line ?

dixudx · 2017-07-28T03:17:25Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+
+// deleteItem removes the item from Heap.items and its key from Heap.queue.
+func (h *Heap) deleteItem(key string) {
+	item := h.data.items[key]


Better to change to

item, ok := h.data.items[key]

dixudx · 2017-07-28T03:21:36Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+}
+
+// Pop waits until an item is ready. If multiple items are
+// ready, they are returned in the order given by Heap.lessFunc.


s/Heap.lessFunc/Heap.data.lessFunc

bsalamat · 2017-07-28T17:42:46Z

Thanks, @dixudx for your review.

caesarxuchao

I haven't finished the review yet, so just some preliminary comments.

caesarxuchao · 2017-07-28T22:40:08Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+
+// addIfNotPresent assumes the lock is already held and adds the the provided
+// item to the queue if it does not already exist.
+func (h *Heap) addIfNotPresent(key string, obj interface{}) {


addIfNotPresentLocked

caesarxuchao · 2017-07-28T22:40:39Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+
+	// Indication the queue is closed.
+	// Used to indicate a queue is closed so a control loop can exit when a queue is empty.
+	// Currently, not used to gate any of CRED operations.


I guess! Was copied from fifo.go and was not carrying much info anyways. I deleted the line.

caesarxuchao · 2017-07-28T22:41:58Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	h.lock.Lock()
+	defer h.lock.Unlock()
+	if _, exists := h.data.items[key]; exists {
+		h.deleteItem(key)


Why not change the item and call Fix()? It's less expensive.

Agreed. Done.

bsalamat · 2017-08-01T18:19:34Z

@caesarxuchao Any more comments?

xiang90 · 2017-08-01T19:51:07Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	index int         // The index of the object's key in the Heap.queue.
+}
+
+// HeapData is an internal struct that implements the standard heap interface


why make internal struct public? heapData?

Makes sense. Done.

xiang90 · 2017-08-01T22:57:04Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+}
+
+// Push is supposed to be called by heap.Push only.
+func (h *heapData) Push(key interface{}) {


the implementation here confuses me at the first look. it does not take care of the item map. not sure why leave that out.

Heap is the type that manipulates heapData and is in charge of adding/removing elements to all the relevant arrays and maps. heapData implements the standard golang heap interface and the queue is the array that stores elements with the heap ordering. As a result, the heapData.Push and heapData.Pop only add and remove items from the queue. Removal of items from the items map is done by Heap.
In theory, Heap could implement standard golang heap, but it would require Heap to implement Push and Pop of the standard heap interface. In that case, those functions would be public. In order to hide those functions, I have added heapData.

and is in charge of adding/removing elements to all the relevant arrays and maps.

isnt the backing array is managed inside heapdata, and manipulated by the go's heap pkg? it is confusing to manage the "pointer" in heapdata, and store the actual item in heapdata, but manage the actual item outside heapdata.

Your point is valid. I made changes to Push and Pop of heapData to perform heapData.items manipulations.

xiang90 · 2017-08-01T22:57:24Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	closedLock sync.Mutex
+}
+
+// Close the Heap.


what does close a heap mean?

Pop blocks until there is an element in the queue or the heap is closed. Closing the heap signals the condition variable.

probably add that to the comment. it was not clear why a heap needs to be closed.

xiang90 · 2017-08-01T22:59:25Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+			// When Close() is called, the h.closed is set and the condition is broadcast.
+			// Which causes this loop to continue and return from the Pop().
+			if h.IsClosed() {
+				return nil, fmt.Errorf("Heap is closed")


heap is closed.

xiang90 · 2017-08-01T23:00:24Z

staging/src/k8s.io/client-go/tools/cache/heap_test.go

@@ -0,0 +1,325 @@
+/*
+Copyright 2014 The Kubernetes Authors.


xiang90 · 2017-08-02T21:03:29Z

@bsalamat

LGTM. Thanks! You need to ping the owners to review it again and get approved though :P

bsalamat · 2017-08-02T21:31:42Z

Thanks, @xiang90! I have already spoken with Chao. He is very busy, but he will take a look soon.

caesarxuchao

I have a few comments on the implementation. I'll review the tests later.

caesarxuchao · 2017-08-04T20:55:27Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+// AddIfNotPresent inserts an item, and puts it in the queue. If an item with
+// the key is present in the map, no changes is made to the item.
+//
+// This is useful in a single producer/consumer scenario so that the consumer can


Do you mean the consumer's requeue function should call AddIfNotPresent? Why it only useful in a single producer/consumer scenario? Isn't it useful in general?

This is a comment copied from fifo.go. The comment doesn't say it is only useful in a single producer/consumer scenario, but if there are multiple consumers, the main benefit of it, which is not contending with the producer, goes away. Consider this scenario:

Producer adds item: key: test, value: 1

Consumer 1 takes the item with value 1 and processes it.

Producer adds item: key: test, value: 2

Consumer 2 takes the item with value 2 and processes it.

Consumer 1 faces an error, requeues the stale item with value 1.

Thanks for the explanation.

caesarxuchao · 2017-08-04T20:59:36Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+func (h *Heap) deleteItem(key string) {
+	item, ok := h.data.items[key]
+	if ok {
+		heap.Remove(h.data, item.index)


Why not inline deleteItem in Delete and save one existence check?

Good point. Done

caesarxuchao · 2017-08-04T21:03:25Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+			if h.IsClosed() {
+				return nil, fmt.Errorf("heap is closed")
+			}
+			h.cond.Wait()


Close() needs to be protected by h.lock. Otherwise if Close() is called between line 248 and 249, Wait() will sleep forever.

And if Close() has to be proteced by h.lock anyway, then we can remove the h.closeLock.

That's a very good point. Looks like fifo.go has the same problem. I used fifo.go as a template to implement heap.go.
I think Close() should hold both closedLock and lock. IsClosed() holds closedLock() only. It cannot hold the same lock as it is called inside Pop and after locking lock.

caesarxuchao · 2017-08-04T21:59:15Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+)
+
+type LessFunc func(interface{}, interface{}) bool
+type HeapItem struct {


Make it private?

caesarxuchao · 2017-08-04T22:11:55Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	old := h.queue
+	n := len(old)
+	key := old[n-1]
+	h.queue = old[0 : n-1]


Why not

key := h.queue(len(h.queue)-1) h.queue = h.queue[:len(h.queue)-1]

caesarxuchao · 2017-08-04T22:15:05Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+		// This is an error
+		return nil
+	}
+	obj := item.obj


Why is this extra copy needed? Can we just return item.obj?

caesarxuchao · 2017-08-04T22:30:32Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+func (h *Heap) Pop() (interface{}, error) {
+	h.lock.Lock()
+	defer h.lock.Unlock()
+	for {


Remove this loop?

caesarxuchao · 2017-08-04T22:33:56Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	h.lock.RLock()
+	defer h.lock.RUnlock()
+	item, exists := h.data.items[key]
+	var obj interface{}


Why not

if !exists { return nil, false, nil } return item.obj, true, nil

caesarxuchao

I left a few more comments. Thanks @bsalamat.

caesarxuchao · 2017-08-04T22:57:10Z

staging/src/k8s.io/client-go/tools/cache/heap_test.go

+}
+
+// TestHeap_Delete tests Heap.Delete and ensures that heap invariant is
+// preserved after adding items.


nit:s/adding/deleting

caesarxuchao · 2017-08-04T23:08:00Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+
+	// Indication the queue is closed.
+	// Used to indicate a queue is closed so a control loop can exit when a queue is empty.
+	closed     bool


Shall we prevent adding more elements to the heap after it's closed? If you agree that's the expected behavior, then consider adding some tests.

Makes sense. This is another example of following whatever fifo.go did. FIFO does not prevent addition and I didn't either, but I just added the checks and a test.

The only downside of this check is that IsClosed holds a lock to check whether the heap is closed. Doing so before every addition to the heap hurts performance. That may be the reason fifo.go doesn't check it.

I changed the code to directly check closed instead of calling IsClosed in order to avoid the extra lock/unlock.

caesarxuchao · 2017-08-04T23:08:53Z

staging/src/k8s.io/client-go/tools/cache/heap_test.go

+			t.Errorf("unexpected item in the list: %v", key)
+		}
+	}
+}


Could you add a test Pop() of an empty heap properly returns after Close() is called?

bsalamat

Thanks, @caesarxuchao! PTAL.

bsalamat · 2017-08-05T01:06:07Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+)
+
+type LessFunc func(interface{}, interface{}) bool
+type HeapItem struct {


bsalamat · 2017-08-05T01:06:20Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	old := h.queue
+	n := len(old)
+	key := old[n-1]
+	h.queue = old[0 : n-1]


bsalamat · 2017-08-05T01:06:26Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+		// This is an error
+		return nil
+	}
+	obj := item.obj


bsalamat · 2017-08-05T01:07:21Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+
+	// Indication the queue is closed.
+	// Used to indicate a queue is closed so a control loop can exit when a queue is empty.
+	closed     bool


Makes sense. This is another example of following whatever fifo.go did. FIFO does not prevent addition and I didn't either, but I just added the checks and a test.

bsalamat · 2017-08-05T01:18:18Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+// AddIfNotPresent inserts an item, and puts it in the queue. If an item with
+// the key is present in the map, no changes is made to the item.
+//
+// This is useful in a single producer/consumer scenario so that the consumer can


This is a comment copied from fifo.go. The comment doesn't say it is only useful in a single producer/consumer scenario, but if there are multiple consumers, the main benefit of it, which is not contending with the producer, goes away. Consider this scenario:

Producer adds item: key: test, value: 1

Consumer 1 takes the item with value 1 and processes it.

Producer adds item: key: test, value: 2

Consumer 2 takes the item with value 2 and processes it.

Consumer 1 faces an error, requeues the stale item with value 1.

bsalamat · 2017-08-05T01:18:51Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+func (h *Heap) deleteItem(key string) {
+	item, ok := h.data.items[key]
+	if ok {
+		heap.Remove(h.data, item.index)


Good point. Done

bsalamat · 2017-08-05T01:18:56Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+func (h *Heap) Pop() (interface{}, error) {
+	h.lock.Lock()
+	defer h.lock.Unlock()
+	for {


bsalamat · 2017-08-05T01:19:09Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+	h.lock.RLock()
+	defer h.lock.RUnlock()
+	item, exists := h.data.items[key]
+	var obj interface{}


bsalamat · 2017-08-05T01:19:18Z

staging/src/k8s.io/client-go/tools/cache/heap_test.go

+}
+
+// TestHeap_Delete tests Heap.Delete and ensures that heap invariant is
+// preserved after adding items.


bsalamat · 2017-08-05T01:19:30Z

staging/src/k8s.io/client-go/tools/cache/heap_test.go

+			t.Errorf("unexpected item in the list: %v", key)
+		}
+	}
+}


bsalamat · 2017-08-09T18:16:52Z

ping @caesarxuchao

caesarxuchao · 2017-08-10T16:50:09Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+// AddIfNotPresent inserts an item, and puts it in the queue. If an item with
+// the key is present in the map, no changes is made to the item.
+//
+// This is useful in a single producer/consumer scenario so that the consumer can


Thanks for the explanation.

caesarxuchao · 2017-08-10T16:57:12Z

staging/src/k8s.io/client-go/tools/cache/heap.go

+		// When the queue is empty, invocation of Pop() is blocked until new item is enqueued.
+		// When Close() is called, the h.closed is set and the condition is broadcast.
+		// Which causes this loop to continue and return from the Pop().
+		if h.IsClosed() {


Can you directly check h.closed here? Then IsClosed() can hold the lock, and closedLock can be removed.

Otherwise lgtm. Thanks @bsalamat.

Done. Thanks! PTAL.

caesarxuchao · 2017-08-10T17:45:36Z

/lgtm

k8s-github-robot · 2017-08-10T17:45:43Z

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: bsalamat, caesarxuchao

Associated issue: 47604

The full list of commands accepted by this bot can be found here.

Needs approval from an approver in each of these OWNERS Files:

~~staging/src/k8s.io/client-go/OWNERS~~ [caesarxuchao]

You can indicate your approval by writing /approve in a comment
You can cancel your approval by writing /approve cancel in a comment

caesarxuchao · 2017-08-10T17:46:10Z

@bsalamat please squash as you see proper.

bsalamat · 2017-08-10T18:18:51Z

Thanks, @caesarxuchao! Done.

bsalamat · 2017-08-10T20:40:47Z

/retest

k8s-github-robot · 2017-08-11T14:35:10Z

/test all [submit-queue is verifying that this PR is safe to merge]

k8s-github-robot · 2017-08-11T15:27:21Z

Automatic merge from submit-queue

k8s-ci-robot assigned caesarxuchao Jul 27, 2017

k8s-ci-robot added sig/scheduling Categorizes an issue or PR as relevant to SIG Scheduling. cncf-cla: yes Indicates the PR's author has signed the CNCF CLA. labels Jul 27, 2017

k8s-github-robot added size/XL Denotes a PR that changes 500-999 lines, ignoring generated files. release-note-none Denotes a PR that doesn't merit a release note. labels Jul 27, 2017

dixudx reviewed Jul 28, 2017

View reviewed changes

caesarxuchao reviewed Jul 28, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch 3 times, most recently from f3f9d2d to 5042dfe Compare July 28, 2017 23:43

xiang90 reviewed Aug 1, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch from 5042dfe to b9051aa Compare August 1, 2017 20:11

xiang90 reviewed Aug 1, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch 4 times, most recently from e75545b to 2d22d91 Compare August 2, 2017 19:56

caesarxuchao reviewed Aug 4, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch from 2d22d91 to bed1e5f Compare August 5, 2017 01:05

bsalamat commented Aug 5, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch 2 times, most recently from a21b514 to 2c3b39e Compare August 9, 2017 06:52

caesarxuchao reviewed Aug 10, 2017

View reviewed changes

bsalamat force-pushed the priority_scheduler branch from 2c3b39e to 897f5b4 Compare August 10, 2017 17:40

k8s-ci-robot added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 10, 2017

k8s-github-robot added the approved Indicates a PR has been approved by an approver from all required OWNERS files. label Aug 10, 2017

bsalamat added 2 commits August 10, 2017 11:14

Add a heap data store to client-go

6cad5bb

autogenerated files

68926a2

bsalamat force-pushed the priority_scheduler branch from 897f5b4 to 68926a2 Compare August 10, 2017 18:15

k8s-github-robot removed the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 10, 2017

caesarxuchao added the lgtm "Looks good to me", indicates that a PR is ready to be merged. label Aug 10, 2017

k8s-github-robot merged commit 868fef1 into kubernetes:master Aug 11, 2017

bsalamat deleted the priority_scheduler branch August 11, 2017 17:36

Add a heap to client-go. Heap orders items with heap invariant ordering. #49752

Add a heap to client-go. Heap orders items with heap invariant ordering. #49752

Conversation

bsalamat commented Jul 27, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat commented Jul 28, 2017

caesarxuchao left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat commented Aug 1, 2017

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

xiang90 commented Aug 2, 2017

bsalamat commented Aug 2, 2017

caesarxuchao left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

caesarxuchao left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat Aug 5, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat Aug 5, 2017 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

bsalamat Aug 5, 2017 •

edited

Loading

bsalamat Aug 5, 2017 •

edited

Loading