nextmv Docs

Using Dash

Using Dash

Let's do something a little more practical to clarify some of these abstract concepts. Most introductions to discrete event simulation begin with an example of a single-server queue, so we start there as well.

Problem Definition

In this system, we 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. Think of it like a line at the bank or grocery store.

Simulation is a way of investigating and understanding the properties of complex systems that are otherwise hard to model. Before we build our simulation, we should consider what it is we want to learn about this queuing system. That is, why are we simulating it?

Chances are, if we operate such a system, we are interested in knowing how long our customers have to wait in line before being served. This is defined as the time from entering the queue to the time entering service. We can think of this "wait time" as our key performance indicator for the queue.

Input Data

Now let's create some input data for our simulation. Imagine we have some historical information about our 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.

In our system, all these attributes can be defined as part of a customer record, so we can define our input as nothing more than a series of customers.

[
{ "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 }
]

We see that customer 0 arrives exactly at the start of our 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 for us.

Customers

Just like Hop, Dash operates directly on JSON data using Go structures. We define a customer.go file containing a customer type. It has the same fields shown in our 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 a couple pointer fields called arrivalTime and serviceTime for maintaining its internal state.

Customer Types

package main
import (
"time"
"github.com/nextmv-io/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, so long as it 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. If we wanted, we could define them as custom types with exactly the fields pertaining to them, but for expediency we simply alias our customer type instead.

type arrival customer
type service customer

We also define a measure type for recording the amount of time a customer waits in the queue. Measures are published to a ledger just like events, and follow the same rules. For our purposes we only care about how long customers wait, not who has to wait, so we define a waitSeconds as a simple integer.

type waitSeconds int

Customer Run Method

Dash works by maintaining a set of active actors in its simulation. When we construct a new simulation, we add actors 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.

Our customer's 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 our customer type publishes measurements of its wait time, it must implement Dash's Measurer 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
}

Our 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
}
}

We can create as many handlers as we want 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

Our 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 merely a queue of arrival events to process and an event ledger to publish to.

package main
import (
"time"
"github.com/nextmv-io/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

Just like in Hop, we create a Dash runner to read input data into our queue simulation, run that simulation, and aggregate its output. Dash runners look a lot like Hop runners. 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/dash/run/cli"
"github.com/nextmv-io/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
},
)
}

We build the simulation into an atomic binary and run it on our 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 ensure that doesn't consume too much real life time. 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.