queues.slide

Queueing with Go
FIFO, Round-Robin and Beyond
24 Jan 2016

Loh Siu Yin
Technology Consultant, Beyond Broadcast LLP
siuyin@beyondbroadcast.com

* Queue Types / Ordering / Discipline

* First-In First-Out (FIFO)

Also known as First come, first served.

Useful in many day-to-day scenarios.
Eg. Buying food at a hawker stall.

* Last-In First-Out (LIFO)

Also known as a Stack.

Useful in picking the freshest item.
Eg. When buying fruit at the supermarket.

* Priority Queue

Like FIFO but has the ability to jump queue.
Eg. Everybody has to queue up.

But those who are in danger of missing their
flight will be served first.


* But first some operations

- Enqueue -- join the queue
- Dequeue -- remove from the queue so that the job can be served
- Head -- inspect (not remove) head of the queue
- Len -- number of items currently in the queue

* Let's define a Queue interface

.code q/queue.go /^package/,/^}/

* Let's also define a FIFO queue type

.code q/fifo.go /01 OMIT/,/02 OMIT/

Our FIFO queue internally (notice lower-cased s) has a slice of interface{}.

i.e. any data type -- because all data types satisfy the
empty interface.

* Provide methods for FIFO to statisfy the Queue interface

.code q/fifo.go /02 OMIT/,/03 OMIT/ HL01 

* Let's do some testing

.code q/fifo_test.go /01 OMIT/,/02 OMIT/ HL01

Switch over to a terminal window and

  go test -v -run Len 
  
* Testing FIFO Enqueue and Dequeue (1)

.code q/fifo_test.go /04 OMIT/,/05 OMIT/ HL02

Note we can enqueue any data type Eg. 2 is an integer.
When we dequeue, we need a type assertion o.(int) 

* Testing FIFO Enqueue and Dequeue (2)

.code q/fifo_test.go /05 OMIT/,/06 OMIT/ HL03

This tests the First-In First-Out behaviour
and also acceptance of interface{} .

* Handle some error conditions for our FIFO Queue

Any type with an Error() method returning a string
satisfies the go error interface.

.code q/fifo.go /03 OMIT/,/07 OMIT/ HL02

In our FIFO implementation:

.code q/fifo.go /05 OMIT/,/05a OMIT/ HL02

* You could just use errors.New

  import "errors"
  
  err := errors.New("something went wrong with the queue")

A matter of preference between using errors directly or
defining your own Errors type.

* A priority queue implementation

The go standard library package

  container/heap

provides an implementation of a priority queue.

I leave this as an exercise for you.

* Multiple Queues

* Multiple Queue Servicing

Consider the situation where we have multiple queues
feeding into one server or a set of servers.

We often encounter this situation in *load*balancers*.

We can service multiple queues using:

- Round Robin
- Earliest Deadline First
- Shortest/Easiest Jobs First
- Fair Queueing


* Round Robin

Server(s) draws from each queue one at a time.
If a queue is empty it is skipped.

Similar to First-Come First-Served philosophy.

All queues get an equal chance of being serviced.
Thus it is fair in terms of the _number_ of jobs serviced.

_Long_ jobs have the same priority as _short_ jobs...
Imagine your job is to "ta-pau" one packet of chicken rice
while the two beside you are to "ta-pau" 10 and 20
packets of chicken rice respectively.

* Earliest Deadline First

The head element of all queues are scanned for their
individual deadlines.

The queue with the earliest deadline is serviced,
then the queues are scanned again.

Advantage: Last-minute jobs get done
Conversely jobs with long-term deadlines have to
wait a very long time to run.

* Shortest / Easiest Jobs first

The head element of all queues are scanned for their
estimated job length / difficulty.

The queue having the shortest job length / easiest complexity
is serviced,
then the queues are scanned again.

Advantage: Short / easy jobs get run often
Conversely Long / hard jobs may never get to run.

"ta-pau" one packet fast,
"ta-pau" 10 packets slow...

How can we ensure "fairness"?

* Fair Queueing

Principle is each queue will get a fair-share of resources.

Eg. If we have two queues:
(A) having 5 jobs of 2 minutes each
(B) having 2 jobs of 5 minutes each

Then both queues should empty / clear at about the same time.

Concepts: 

- each job or queue item has a time cost and thus an estimated finish time
- each queue has a finish time = finish time of last job in the queue

* Psuedo-code on Wikipedia
.image fair_queue_wikipedia.png

* First try at an implementation

.code q/fair_q.go /01 OMIT/,/02 OMIT/

This implementation has N queues -- think Immigration Clearance at Airports.

Each queue is a FIFO.

And we keep a list of the last virtual finish time of a job in each of the queues. 
i.e. the predicted / estimated time the latest job in a particular queue would complete

* Receiving a Job into the system
.image receive_wik.png

.code q/fair_q.go /02 OMIT/,/03 OMIT/  HL01

packet == Job

Notice I'm using the Queue interface's Enqueue method to enqueue job _j_.

Customize *chooseQueue* to your needs to maps incoming jobs to your
set of *N* queues.

* chooseQueue is a mapping from Job to queue number
In practice it could be based on customer name or id
or passport nationality 
or some specific property of the Job

In my test implementation I choose to always map to queue number 1.

.code q/fair_q.go /03 OMIT/,/04 OMIT/ 

A real implementation would use a hashing function like

 hash/fnv

available from the standard library.



* Updating estimated (virtual) finish time

.image update_time_wik.png

.code q/fair_q.go /04 OMIT/,/05 OMIT/ HL01

Finish time is greater of ( now and last job's finish time)
plus current job's time cost.
 
* Select and send a job to be processed

.image send_wik.png

.code q/fair_q.go /05 OMIT/,/06 OMIT/ HL01

The heart of the send function is selectQueue,
that is were the fair queueing comes in.

The rest of *send* is just a FIFO Dequeue.

* Fairly selectQueue

.image select_queue_wik.png

The main ideas:

- skip empty queues
- select the queue with earliest estimated finish time

This effectively is First-Come, First-Served weighted by the Job cost.

* selectQueue Go implementation

.code q/fair_q.go /06 OMIT/,/07 OMIT/ HL01

* Testing the Fair Queue - Update Time 

.code q/fair_q_test.go /ut1 OMIT/,/ut2 OMIT/ 

FakeClock Now() is always 2000-01-01 00:00:00 UTC

* Testing Fair Queue send() 

.code q/fair_q_test.go /01 OMIT/,/02 OMIT/

We have j1 and j2 in the queue and they should be
FIFO dequeued

* Testing the Fair Queue send() underflow 

.code q/fair_q_test.go /02 OMIT/,/03 OMIT/

We have only j1 in the queue.

The second send() attempt should result in an 
idle job.

* Running the tests

Switch to a terminal:

  go test

* Presentation and code
.link http://github.com/siuyin/queue_present

Get the go present tool:

 go get golang.org/x/tools/cmd/present