1// Copyright 2016 The etcd Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package recipe 16 17import ( 18 "fmt" 19 20 v3 "github.com/coreos/etcd/clientv3" 21 "github.com/coreos/etcd/mvcc/mvccpb" 22 "golang.org/x/net/context" 23) 24 25// PriorityQueue implements a multi-reader, multi-writer distributed queue. 26type PriorityQueue struct { 27 client *v3.Client 28 ctx context.Context 29 key string 30} 31 32// NewPriorityQueue creates an etcd priority queue. 33func NewPriorityQueue(client *v3.Client, key string) *PriorityQueue { 34 return &PriorityQueue{client, context.TODO(), key + "/"} 35} 36 37// Enqueue puts a value into a queue with a given priority. 38func (q *PriorityQueue) Enqueue(val string, pr uint16) error { 39 prefix := fmt.Sprintf("%s%05d", q.key, pr) 40 _, err := newSequentialKV(q.client, prefix, val) 41 return err 42} 43 44// Dequeue returns Enqueue()'d items in FIFO order. If the 45// queue is empty, Dequeue blocks until items are available. 46func (q *PriorityQueue) Dequeue() (string, error) { 47 // TODO: fewer round trips by fetching more than one key 48 resp, err := q.client.Get(q.ctx, q.key, v3.WithFirstKey()...) 49 if err != nil { 50 return "", err 51 } 52 53 kv, err := claimFirstKey(q.client, resp.Kvs) 54 if err != nil { 55 return "", err 56 } else if kv != nil { 57 return string(kv.Value), nil 58 } else if resp.More { 59 // missed some items, retry to read in more 60 return q.Dequeue() 61 } 62 63 // nothing to dequeue; wait on items 64 ev, err := WaitPrefixEvents( 65 q.client, 66 q.key, 67 resp.Header.Revision, 68 []mvccpb.Event_EventType{mvccpb.PUT}) 69 if err != nil { 70 return "", err 71 } 72 73 ok, err := deleteRevKey(q.client, string(ev.Kv.Key), ev.Kv.ModRevision) 74 if err != nil { 75 return "", err 76 } else if !ok { 77 return q.Dequeue() 78 } 79 return string(ev.Kv.Value), err 80} 81