seq

README

seq

A fast implementation of sequence buffers described in this blog post by Glenn Fiedler in Go with 100% unit test coverage.

This was built for the purpose of creating reliable UDP networking protocols, where sequence buffers may be used as an efficient, resilient, fixed-sized rolling buffer for:

1. tracking metadata over sent/received packets,
2. ordering packets received from an unreliable stream, or
3. tracking acknowledgement over the recipient of sent packets from peers.

The sequence numbers used to buffer entries are fixed to be unsigned 16-bit integers, as larger amounts of entries are redundant and would provide a negligible improvement to your packet acknowledgement system.

Notes

The size of the buffer must be divisible by the max value of an unsigned 16-bit integer (65536), otherwise data buffered by sequence numbers would not wrap around the entire buffer. This was encountered while writing tests for this library.

The method RemoveRange was benchmarked and optimized over the sequence buffer implementation in the reference C codebase reliable.io to use a few memcpy calls over for loops.

The actual sequences and buffered data are stored in two separate, contiguous slices so that entries that have popped from the rolling buffer will remain as stale memory that may optionally be garbage-collected later.

Setup

go get github.com/lithdew/seq

Benchmarks

$ go test -bench=. -benchtime=10s
goos: linux
goarch: amd64
pkg: github.com/lithdew/seq
BenchmarkTestBufferInsert-8                     327525945               35.6 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferRemoveRange-8                243091503               51.3 ns/op             0 B/op          0 allocs/op
BenchmarkTestBufferGenerateBitset32-8           84982886               137 ns/op               0 B/op          0 allocs/op

Documentation

Overview

Package seq is a fast implementation of sequence buffers described in Go with 100% unit test coverage.

Index

• Constants
• func GT(a, b uint16) bool
• func GTE(a, b uint16) bool
• func LT(a, b uint16) bool
• func LTE(a, b uint16) bool
• type Buffer
  • func NewBuffer(size uint16) *Buffer
  • func (b *Buffer) At(seq uint16) interface{}
  • func (b *Buffer) Exists(seq uint16) bool
  • func (b *Buffer) Find(seq uint16) interface{}
  • func (b *Buffer) GenerateBitset32(ack uint16) (ackBits uint32)
  • func (b *Buffer) GenerateLatestBitset32() (ack uint16, ackBits uint32)
  • func (b *Buffer) Insert(seq uint16, item interface{}) bool
  • func (b *Buffer) Latest() uint16
  • func (b *Buffer) Len() uint16
  • func (b *Buffer) Next() uint16
  • func (b *Buffer) Outdated(seq uint16, size uint16) bool
  • func (b *Buffer) Remove(seq uint16)
  • func (b *Buffer) RemoveRange(start, end uint16)
  • func (b *Buffer) Reset()

Constants

const HalfMaxUint16 = uint16(math.MaxUint16/2) + 1

Half the max value of an unsigned 16-bit integer.

Functions

func GT

func GT(a, b uint16) bool

GT returns whether or not the sequence number a is greater than b. This is done by returning whether or not a and b are apart by more than 32767 (half the max value of an unsigned 16-bit integer).

func GTE

func GTE(a, b uint16) bool

GTE returns whether or not the sequence number a is greater than or equal to b. See GT for how this is determined.

func LT

func LT(a, b uint16) bool

LT returns whether or not the sequence number a is less than b. See GT for how this is determined.

func LTE

func LTE(a, b uint16) bool

LTE returns whether or not the sequence number a is less than or equal to b. See GT for how this is determined.

Types

type Buffer

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

Buffer is a fast, fixed-sized rolling buffer that buffers entries based on an unsigned 16-bit integer.

func NewBuffer

func NewBuffer(size uint16) *Buffer

NewBuffer instantiates a new sequence buffer of size.

func (*Buffer) At

func (b *Buffer) At(seq uint16) interface{}

At returns the entry at seq, even if it might be stale.

func (*Buffer) Exists

func (b *Buffer) Exists(seq uint16) bool

Exists returns whether or not seq is stored in the buffer.

func (*Buffer) Find

func (b *Buffer) Find(seq uint16) interface{}

Find returns the entry at seq, should seq not be outdated.

func (*Buffer) GenerateBitset32

func (b *Buffer) GenerateBitset32(ack uint16) (ackBits uint32)

GenerateBitset32 generates a 32-bit integer representative of a bitset where entries at index i are 1 if there exists an entry in the buffer whose sequence number is equal to the largest sequence number inserted/acknowledged so far minus i. It returns both the largest sequence number known thus far alongside the bitset as an unsigned 16-bit integer and an unsigned 32-bit integer respectively.

func (*Buffer) GenerateLatestBitset32

func (b *Buffer) GenerateLatestBitset32() (ack uint16, ackBits uint32)

GenerateLatestBitset32 calls GenerateBitset32 on the latest known sequence number.

func (*Buffer) Insert

func (b *Buffer) Insert(seq uint16, item interface{}) bool

Insert inserts a new item into this buffer indexed by seq, should seq not be outdated. It returns true if the insertion is successful.

func (*Buffer) Latest

func (b *Buffer) Latest() uint16

Latest returns the latest sequence number inserted/acknowledged by this buffer.

func (*Buffer) Len

func (b *Buffer) Len() uint16

Len returns the size of this buffer.

func (*Buffer) Next

func (b *Buffer) Next() uint16

Next returns the next expected sequence number to be inserted/acknowledged by this buffer.

func (*Buffer) Outdated

func (b *Buffer) Outdated(seq uint16, size uint16) bool

Outdated returns true if seq is capable of being stored in this buffer based on the largest sequence number that has been inserted/acknowledged so far.

func (*Buffer) Remove

func (b *Buffer) Remove(seq uint16)

Remove invalidates items and entries stored by the sequence number seq.

func (*Buffer) RemoveRange

func (b *Buffer) RemoveRange(start, end uint16)

RemoveRange invalidates all items and entries with sequence numbers in the range [start, end].

func (*Buffer) Reset

func (b *Buffer) Reset()

Reset resets the buffer.