Single-server queue simulation

This example demonstrates the use of Nextmv's discrete event simulator, Dash, for customers using Nextmv Enterprise.

In this example, we detail a single-server queue simulation.

Problem Definition

For a single-server queue problem, you have a line of customers waiting to be served and a single server to handle their requests. The server handles one request at a time in the order they arrive (e.g., a line at the bank or grocery store).

The key performance indicator is "wait time", defined as the time from entering the queue to the time entering service (or how long customers have to wait in line before being served).

Input Data

Assume you have historical information about customers, including their unique customer numbers, the number of minutes after opening our queue for business that they arrive, and the number of minutes it takes to service them.

Your input data can then be defined in JSON as a series of customers with the historical information detailed above as attributes.

[
  { "Number": 0, "Arrival":  0, "Service":  3 },
  { "Number": 1, "Arrival":  1, "Service": 10 },
  { "Number": 2, "Arrival":  1, "Service":  7 },
  { "Number": 3, "Arrival":  7, "Service":  2 },
  { "Number": 4, "Arrival":  9, "Service":  3 },
  { "Number": 5, "Arrival": 13, "Service":  4 },
  { "Number": 6, "Arrival": 14, "Service":  6 },
  { "Number": 7, "Arrival": 15, "Service":  8 },
  { "Number": 8, "Arrival": 15, "Service":  3 },
  { "Number": 9, "Arrival": 19, "Service":  2 }
]

Customer 0 arrives exactly at the start of the operating period and takes 3 minutes to service. Customers 1 and 2 arrive a minute after customer 0, and will therefore have to wait in line.

Customer 0's wait time should be 0, since they are serviced immediately upon entering the queue. Customer 1 has to wait 2 minutes, while customer 2 will have to wait 12. The simulation takes care of all the bookkeeping required to compute these values.

Customers

Dash operates directly on JSON data using Go structures. Next, define a customer.go file containing a customer type. It has the same fields as the input JSON. The customer type also has access to the event and measure ledgers of the simulation, which it uses to publish and subscribe to events, and to record measurements of wait time. Finally, the customer has pointer fields called arrivalTime and serviceTime for maintaining its internal state.

Customer Types

package main

import (
    "time"

    "github.com/nextmv-io/code/dash/sim/ledger"
)

type customer struct {
    Number  int
    Arrival int
    Service int

    events   ledger.Ledger
    measures ledger.Ledger

    arrivalTime *time.Time
    serviceTime *time.Time
}

Actors in Dash communicate through events. These events are published and subscribed to using an event ledger. An event can be anything that can be stored and converted to JSON.

There are two events that pertain to customers: times they arrive and enter the queue and times they start being served. We call these events arrival and service. For expediency the customer type is simply aliased, however these could be defined as custom types instead.

type arrival customer
type service customer

Next, we define a measure type for recording the amount of time a customer waits in the queue. Measures are published to a ledger and follow the same rules as events. waitSeconds is defined as a simple integer to track how long customers wait (not who has to wait).

type waitSeconds int

Customer Run Method

Dash works by maintaining a set of active actors in its simulation. When constructing a new simulation, actors are added to it with an initial time to "run" them. Dash adds them to its pool of actors, and calls their Run methods at the specified times.

All actors must implement Run. This method takes in the current time, updates the actor's state, and returns the next time to run them along with a boolean indicator of whether not there is anything left for them to do.

The example Run method is shown below. It has three sections. In the first, the customer tests to see if they have entered service. If so, they publish a measurement of their wait time in the queue, and tell Dash that they don't have anything left to do.

The second section contains logic for a customer arrival. If a customer hasn't recorded its arrival time yet, it does so and publishes an arrival event. Finally, in the third section the customer waits in the queue.

func (c *customer) Run(now time.Time) (time.Time, bool) {
    // 1. Customer has entered service.
    if c.serviceTime != nil {
        wait := c.serviceTime.Sub(*c.arrivalTime) / time.Second
        c.measures.Publish(waitSeconds(wait))
        return time.Time{}, false
    }

    // 2. Customer arrives.
    if c.arrivalTime == nil {
        c.arrivalTime = &now
        c.events.Publish(arrival(*c))
    }

    // 3. Customer waits in the queue.
    return now.Add(time.Minute), true
}

Customer Events & Measures

Since the example customer type publishes measurements of its wait time, it must implement Dash's Measure interface. This means defining a method named MeasureTo so Dash can tell it where to publish measurements.

func (c *customer) MeasureTo(measures ledger.Ledger) {
    c.measures = measures
}

Similarly, the customer communicates its arrivals to other actors through events. To do so, it must implement the Publisher interface. This requires a PublishTo method.

func (c *customer) PublishTo(events ledger.Ledger) {
    c.events = events
}

The example customer publishes arrival events and responds to service events. In order to update its state based on events published by other actors in the simulation, the customer implements the Subscriber interface through SubscribeTo. Note that SubscribeTo receives a ledger.Subscriber type, which lets us associate a handler with an event type.

func (c *customer) SubscribeTo(subscriber ledger.Subscriber) {
    subscriber.Subscribe(c.service)
}

func (c *customer) service(now time.Time, event service) {
    if event.Number == c.Number {
        c.serviceTime = &now
    }
}

Any number of handlers can be created for a subscriber. These handlers are updated before each call to the actor's Run method. This means that when Dash selects a customer actor to run, it first processes all events published to the event ledger since the last time it ran. Thus our customer's state is kept up to date.

Server

The example server implementation has many of the same components as the customer. The server does not have any data in the input JSON, so define the server type in server.go as a queue of arrival events to process and an event ledger to publish to.

package main

import (
    "time"

    "github.com/nextmv-io/code/dash/sim/ledger"
)

type server struct {
    queue  []arrival
    events ledger.Ledger
}

The server's Run method is simple. If the server has a nonempty queue of customer arrivals to serve, it starts the first one and publishes their service time. The server is then busy until they are done servicing that customer. Otherwise, the server waits for something to do.

func (s *server) Run(now time.Time) (time.Time, bool) {
    if len(s.queue) > 0 {
        c := s.queue[0]
        s.queue = s.queue[1:]
        s.events.Publish(service(c))
        return now.Add(time.Duration(c.Service) * time.Minute), true
    }

    return now.Add(time.Minute), true
}

A server publishes service events just like a customer publishes arrival events.

func (s *server) PublishTo(events ledger.Ledger) {
    s.events = events
}

Finally, a server subscribes to arrival events. Whenever it encounters one, it adds that arrival to its queue.

func (s *server) SubscribeTo(subscriber ledger.Subscriber) {
    subscriber.Subscribe(s.enqueue)
}

func (s *server) enqueue(now time.Time, event arrival) {
    s.queue = append(s.queue, event)
}

Runner

A Dash runner is needed to read input data into the queue simulation, run that simulation, and aggregate its output. The CLI runner takes a handler with a variable to unmarshal the input into and options parsed from the environment and command line flags, and returns a simulator.

package main

import (
    "time"

    "github.com/nextmv-io/code/dash/run/cli"
    "github.com/nextmv-io/code/dash/sim"
)

func main() {
    cli.Run(
        func(customers []*customer, opt sim.Options) (sim.Simulator, error) {
            simulator := sim.New(opt)

            now := time.Now()
            for _, c := range customers {
                arrival := now.Add(time.Duration(c.Arrival) * time.Minute)
                simulator.Add(arrival, c)
            }

            simulator.Add(now, &server{})

            return simulator, nil
        },
    )
}

Next, build the simulation into an atomic binary and run it on the example input.

Note that the time is the amount of simulated time to run for and limits is the actual run time limits. Use time to set how much simulated time to run for and limits to set time limits. For example, setting a time of 10 hours will run 10 hours of simulated time, but pairing that with limits of 1 minute will ensure that the simulation stops after 1 real minute of time, regardless of whether those 10 simulated hours have completed. In our model, there is always a server actor lurking about, so we have to tell Dash when to quit.

go build
./queue -dash.simulator.time.duration 2h < input.json | jq

or, with command-line file input/output flags

go build
./queue -dash.simulator.time.duration 2h \
        -dash.runner.input.path input.json \
        -dash.runner.output.path output.json

By default, this doesn't give us much information beyond input options and time statistics.

{
  "dash":{
    "version":"v0.2.1"
  },
  "events":null,
  "measures":null,
  "options":{
    "time":{
      "duration":"2h0m0s"
    }
  },
  "statistics":{
    "time":{
      "elapsed":"281.891µs",
      "simulated":"2h1m0s",
      "start":"2020-09-03T08:38:38.090664-07:00"
    }
  }
}

We can tell Dash to include its event log in the output. This adds an events field to the JSON.

./queue -dash.runner.output.events \
        -dash.simulator.time.duration 1m < input.json | jq

or

./queue -dash.runner.input.path input.json \
        -dash.runner.output.path output.json \
        -dash.runner.output.events \
        -dash.simulator.time.duration 1m

{
  "dash":{
    "version":"v0.2.1"
    },
    "events":[
      {
        "event":{
          "Number":0,
          "Arrival":0,
          "Service":3
        },
        "type":"arrival",
        "when":"2020-09-03T08:43:10.916384-07:00"
      },
      {
        "event":{
          "Number":0,
          "Arrival":0,
          "Service":3
        },
        "type":"service",
        "when":"2020-09-03T08:43:10.916384-07:00"
      },
      {
        "event":{
          "Number":1,
          "Arrival":1,
          "Service":10
        },
        "type":"arrival",
        "when":"2020-09-03T08:44:10.916384-07:00"
      },
      {
        "event":{
          "Number":2,
          "Arrival":1,
          "Service":7}
        ,
        "type":"arrival",
        "when":"2020-09-03T08:44:10.916384-07:00"
      }
    ],
    "measures":null,
    "options":{
      "time":{
        "duration":"1m0s"
        }
      },
      "statistics":{
        "time":{
          "elapsed":"84.777µs",
          "simulated":"2m0s",
          "start":"2020-09-03T08:43:10.91637-07:00"
        }
      }
    }

In this example, customers publish arrival events, which the server subscribes to. The server publishes service events, which the customers subscribe to. The customers measure their time spent in the queue and publish those measurements to the measure ledger. This requires that the customers implement MeasureTo.

Requesting measurements from Dash is similar to requesting events.

./queue -dash.runner.output.measures \
        -dash.simulator.time.duration 30m < input.json | jq

or alternatively

./queue -dash.runner.input.path input.json \
        -dash.runner.output.path output.json \
        -dash.runner.output.measures \
        -dash.simulator.time.duration 30m

{
  "dash":{
    "version":"v0.2.1"
    },
    "events":null,
    "measures":[
      {
        "measure":0,
        "type":"waitSeconds",
        "when":"2020-09-03T08:53:03.882231-07:00"
      },
      {
        "measure":120,
        "type":"waitSeconds",
        "when":"2020-09-03T08:56:03.882231-07:00"
      },
      {
        "measure":720,
        "type":"waitSeconds",
        "when":"2020-09-03T09:06:03.882231-07:00"
      },
      {
        "measure":780,
        "type":"waitSeconds",
        "when":"2020-09-03T09:13:03.882231-07:00"
      },
      {
        "measure":780,
        "type":"waitSeconds",
        "when":"2020-09-03T09:15:03.882231-07:00"
      },
      {
        "measure":720,
        "type":"waitSeconds",
        "when":"2020-09-03T09:18:03.882231-07:00"
      },
      {
        "measure":900,
        "type":"waitSeconds",
        "when":"2020-09-03T09:22:03.882231-07:00"
      }
    ],
    "options":{
      "time":{
        "duration":"30m0s"
      }
    },
    "statistics":{
      "time":{
        "elapsed":"183.519µs",
        "simulated":"31m0s",
        "start":"2020-09-03T08:52:03.882219-07:00"
      }
    }
  }

In this example, the waitSeconds measurement type is simply an int. If we want more information we can make it a struct or provide a MarshalJSON method, and Dash will automatically incorporate those details into its output.

Randomness

Dash also has the ability to sample randomly from a distribution to represent behaviors. Check out the Random Queue example for more details.