scheduling

README

scheduling

Scheduling algorithms in Go language. The following algorithms are implemented:

• Round Robin - Schedules each request sequentially around the pool of backends. Using this algorithm, all the backends are treated as equals.
• Least Connections - Schedules more requests to backends with fewer active connections.
• Weighted Least Connections - Schedules each request sequentially around the pool of backends but gives more requests to backends with greater weights (capacity).
• Rate Limiting - Schedules a request to a backend based on a set limit of requests per duration (e.g., requests/second), using the Token bucket algorithm.

Requirements

• Go 1.1 or higher

Documentation

Godoc documentation is available at http://godoc.org/github.com/brandscreen/scheduling.

Installation

$ go get github.com/brandscreen/scheduling

Usage

Import Scheduling

Ensure you have imported the scheduling package at the top of your source file.

import "github.com/brandscreen/scheduling"

Scheduling

Setup the Backends

Setup a slice of Backends. Each Backend has a Value which provides context to the application for selecting the real server.

var server1, server2, server3 interface{} // These are your actual servers...

backends := make([]*scheduling.Backend, 3)
backends[0] = scheduling.NewBackend(server1)
backends[1] = scheduling.NewWeightedBackend(server2, 50)
backends[2] = scheduling.NewBackend(server3)

Create a Scheduler

Next, create an instance of the scheduling algorithm.

Round Robin

scheduler := scheduling.NewRoundRobinScheduler(backends)

Least Connections

scheduler := scheduling.NewLeastConnectionsScheduler(backends)

Weighted Least Connections

scheduler := scheduling.NewWeightedLeastConnectionsScheduler(backends)

Schedule an activity using the Scheduler

Call the Schedule function on the scheduler to obtain the selected Backend. Note you should call Close() in order to release the backend otherwise the connection count will continue to increase.

backend := scheduler.Schedule()
defer backend.Close()

Rate Limiting

Not strictly a scheduling algorithm, you can rate limit requests to a backend using the RateLimiter object.

Create a RateLimiter

This example creates a RateLimiter that is limited to 500 requests per second. Ensure to import time package.

limiter := scheduling.NewRateLimiter(500, time.Second)

Check if the request fits within the limit

Call the Schedule() function to determine if the request can be sent to the backend.

if limiter.Schedule() {
    // Send the request to the backend
} else {
    // Drop the request
}

Contributing

Please see CONTRIBUTING.md. If you have a bugfix or new feature that you would like to contribute, please find or open an issue about it first.

License

Licensed under the MIT License.

Documentation

Overview

Package scheduling provides a variety of scheduling and rate limiting algorithms.

Index

• type Backend
  • func NewBackend(value interface{}) *Backend
  • func NewWeightedBackend(value interface{}, weight uint32) *Backend
  • func (b *Backend) Close() error
• type LeastConnectionsScheduler
  • func (s *LeastConnectionsScheduler) GetBackends() []*Backend
  • func (s *LeastConnectionsScheduler) Schedule() *Backend
• type RateLimiter
  • func NewRateLimiter(limit uint64, d time.Duration) *RateLimiter
  • func (r *RateLimiter) Close() error
  • func (r *RateLimiter) Schedule() bool
• type RoundRobinScheduler
  • func (s *RoundRobinScheduler) GetBackends() []*Backend
  • func (s *RoundRobinScheduler) Schedule() *Backend
• type Scheduler
  • func NewLeastConnectionsScheduler(backends []*Backend) Scheduler
  • func NewRoundRobinScheduler(backends []*Backend) Scheduler
  • func NewWeightedLeastConnectionsScheduler(backends []*Backend) Scheduler
• type WeightedLeastConnectionsScheduler
  • func (s *WeightedLeastConnectionsScheduler) GetBackends() []*Backend
  • func (s *WeightedLeastConnectionsScheduler) Schedule() *Backend

Types

type Backend

type Backend struct {
	Connections uint32
	Weight      uint32
	Value       interface{}
}

Backend represents some abstract backend that has connections and optionsllay a weight. The Value gives the actual backend value used by the application. Backend implements the io.Closer interface so callers should use defer backend.Close()

func NewBackend

func NewBackend(value interface{}) *Backend

NewBackend returns a new backend using the given value and 100% weighting.

func NewWeightedBackend

func NewWeightedBackend(value interface{}, weight uint32) *Backend

NewWeightedBackend returns a new backend using the given value and weithing.

func (*Backend) Close

func (b *Backend) Close() error

Close closes the backend, releasing its connections.

type LeastConnectionsScheduler

type LeastConnectionsScheduler struct {
	// contains filtered or unexported fields
}

LeastConnectionsScheduler is a scheduler that uses connections to determine the next backend to use. It does not take into account any weighting applied to the backends.

func (*LeastConnectionsScheduler) GetBackends

func (s *LeastConnectionsScheduler) GetBackends() []*Backend

Returns the backends in use

func (*LeastConnectionsScheduler) Schedule

func (s *LeastConnectionsScheduler) Schedule() *Backend

Schedule returns the next backend according to the algorithm.

type RateLimiter

type RateLimiter struct {
	Limit     uint64
	Remaining int64
}

RateLimiter provides the capability of limiting some activity using a given rate.

This could be a requests per second to a backend web service or a number of emails per day.

func NewRateLimiter

func NewRateLimiter(limit uint64, d time.Duration) *RateLimiter

NewRateLimiter returns a new RateLimiter using the given rate (limit/duration)

func (*RateLimiter) Close

func (r *RateLimiter) Close() error

Close closes the rate limiter and cleans up

func (*RateLimiter) Schedule

func (r *RateLimiter) Schedule() bool

Schedule returns true if the given activity may be scheduled according to the specified rate limits.

type RoundRobinScheduler

type RoundRobinScheduler struct {
	// contains filtered or unexported fields
}

RoundRobinScheduler is a scheduler that simply loops through the backends returning the next one, without regard to number of connections or weighting.

func (*RoundRobinScheduler) GetBackends

func (s *RoundRobinScheduler) GetBackends() []*Backend

Returns the backends in use

func (*RoundRobinScheduler) Schedule

func (s *RoundRobinScheduler) Schedule() *Backend

Schedule returns the next backend according to the algorithm.

type Scheduler

type Scheduler interface {
	// Schedule returns the next backend according to the algorithm.
	Schedule() *Backend

	// Returns the backends in use
	GetBackends() []*Backend
}

Scheduler is an interface implemented by all schedulers.

func NewLeastConnectionsScheduler

func NewLeastConnectionsScheduler(backends []*Backend) Scheduler

NewLeastConnectionsScheduler returns a new LeastConnectionsScheduler with the given backends.

func NewRoundRobinScheduler

func NewRoundRobinScheduler(backends []*Backend) Scheduler

NewRoundRobinScheduler return a new RoundRobinScheduler

func NewWeightedLeastConnectionsScheduler

func NewWeightedLeastConnectionsScheduler(backends []*Backend) Scheduler

NewWeightedLeastConnectionsScheduler returns a new WeightedLeastConnectionsScheduler

type WeightedLeastConnectionsScheduler

type WeightedLeastConnectionsScheduler struct {
	// contains filtered or unexported fields
}

WeightedLeastConnectionsScheduler is a Scheduler that uses a weighted least connections algorithm to schedule backends.

Supposing there is a server set S = {S0, S1, ..., Sn-1}, W(Si) is the weight of server Si; C(Si) is the current connection number of server Si; CSUM = ΣC(Si) (i=0, 1, .. , n-1) is the sum of current connection numbers;

The new connection is assigned to the server j, in which

(C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1),
where W(Si) isn't zero

Since the CSUM is a constant in this lookup, there is no need to divide by CSUM, the condition can be optimized as

C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1), where W(Si) isn't zero

func (*WeightedLeastConnectionsScheduler) GetBackends

func (s *WeightedLeastConnectionsScheduler) GetBackends() []*Backend

Returns the backends in use

func (*WeightedLeastConnectionsScheduler) Schedule

func (s *WeightedLeastConnectionsScheduler) Schedule() *Backend

Schedule returns the next backend according to the algorithm.