A quick intro on queues.

queues.md

What is a queue?

Anytime you go out for a meal and the hostess informs you that there is a wait and you agree to be added to a waitlist, you are being put into a queue. A queue is at it's core nothing more than a line. In fact, in the UK they call waiting in line queueing.

Our queue when you arrive -

[
  {"name": "Bob"},
  {"name": "Karen"}
]

Our queue once you're added -

[
  {"name": "Bob"},
  {"name": "Karen"},
  {"name": "You"}
]

Let's imagine that each time a table is available, it magically has the exact number of seats requested by the next party in the queue. Therefore, the restaurant can simply use a first in, first out approach. Simply put, it's first come, first served.

After a table is ready and a name is called, our queue looks like -

[
  {"name": "Karen"},
  {"name": "Liz"}
]

What if we don't have enough seats?

Fair question and a more likely scenario.

This is where Redis comes in. It's important to remember that Redis is primarily a String store. So, in order to have the ability to order our incoming patrons properly, we need to take advantage of both a score and Redis' inherent lexicographical ordering of elements with the same score.

What we want is a queue like so -

[
  "Bob",
  "Karen"
]

We want the records to be sorted by both the number of seats requested and when the party arrived. Since, we're working with strings in Redis, we can't just set some arbitrary key:value pairs as a hash and search them. Instead, we'll insert an element into waitlist with a score equal to the seats requested and a value equal to the current timestamp and the person's name. We're creating this string so that Redis will sub-sort them by time arrived for us.

# redis.zadd key score value
redis.zadd("waitlist", @customer.seats_requested, "#{Time.now.to_i} #{@customer.name}")

We now have a queue that looks like this - note: scores not shown

[
  "1452266753 Bob",
  "1452267102 Karen",
  "1452267136 You"
]

Now a table becomes available, it seats two people. Here's how we find the first party in that requested two seats.

# redis.zrangebyscore key, min, max *defaults to inclusive, use ( to exclude
customer_name = redis.zrangebyscore("waitlist", "(1", "(3", :limit => [0, 1])&.first
# => "1452267102 Karen"

# remove the key so it isn't called again, if it exists
redis.zrem("waitlist", customer_name) if customer_name.present?