ptravers / spq Goto Github PK

Sorting Priority Queue

Rust 87.08% Dockerfile 2.31% Makefile 2.52% Shell 0.31% Python 7.78%

spq's Introduction

spq

Sorting Priority Queue

SPQ provides a Priority Queue that ensures an even distribution of dequeued elements over a herirarchical feature space. The queue is a grpc service that can be run with docker. The project is a WIP and doesn't currently support full durability. But it shouldn't be too long before it does.

But Why?

At previous place of work we had a problem of fair resource sharing for a pool of worker nodes. We wanted a queue that provided exactly once delivery and would be CP or PC+EC in the event of a network partition or the choice of latency over consistency. But most importantly we wanted the queue to provide the ability to re-sort on which features had most recently been removed from the queue. The system we wanted didn't exist so we built a much less generic solution than this one that only supported two features and leveraged postgres as a data store.

Toy Example

If you imagine the queue as a line of children waiting for lunch and the features are Class and Age. Where each child belongs to a class at School and is a number of years old.

SPQ will guarantee that the sweets are given to the children in a round robin based on age and class. Class 1 = [Child_A, Child_B] Class 2 = [Child_C, Child_D]

Age 9 = [Child_D, Child_A] Age 10 = [Child_B, Child_C]

The children having arrived in order in alphabetic order e.g. A, B, C and D.

The queue will return Child_A, Child_C, Child_B and Child_D

API

The queue leverages gRPC for all communication and thus requires support for HTTP 2.0

Create queue

Creates a queue with a set of features that all items inserted must have

e.g. Create queue named "school" with features Age and Class

Enqueue

Adds an item to the queue. Request must contain:

Name of the Queue
The list of Features with a value for each feature
The item to be stored. Which is an arbitrary set of bytes

e.g. Enqueue item request:

queue named "school"
features [(Age, 9), (Class, 2)]

Dequeue

Remove next item from the queue. Request must contain:

Name of the Queue

e.g. Dequeue item request:

queue named "school"

Peek

View the next item in the queue without removing it from the queue. Request must contain:

Name of the Queue

e.g. Peek item request:

queue named "school"

Get Size

Get the current size of the queue

Name of the Queue

e.g. Get Size request:

queue named "school"

Get Epoch

Get the current "epoch" of the queue. See documentation for details of semantics of epoch

Name of the Queue

e.g. Get Epoch request:

queue named "school"

Glossary

Epoch = A Lamport Clock that increases for each mutation of the queue
Feature = A category of values i.e. Age in Years
Feature Value = A value in the feature category i.e. 8 years old

Implementation

The system is structured into two packages a grpc server and the queue itself

The queue is built atop RocksDB as it's persistence layer.

This README is underconstruction

spq's People

Contributors

Stargazers

spq's Issues

Discovery

Given Multiple SPQ nodes
When The nodes attempt to replicate
Then They can discover all the other nodes

Flatten node and node value

WTH is a node or node value (long story short it's a mess)

Each node in SPQ has a set of associated values. A node represents a feature in a path of features. For a feature space with 2 features there are at minimum two nodes.

Currently the following are tracked per node per value in the feature hierarchy:
value - the value in the feature space this node value represents
items at index - the number of items in paths through the tree below this node
child index - the index of the node that contains the children of this value
hash - the index in the storage layer at which the epoch of the value is being stored

Each node contains
A list of node values
The name of the feature the node represents
If the node has leaf nodes beneath it

We want to flatten this structure ideally into one rocksdb table

Refactor to be resilient in the case of partial failure

Currently the queue if killed part way through dequeuing or enqueuing an item will create invalid partial state:

During enqueue the number of items available on the path will have been decremented without an item having been removed. If the enqueue fails after any node value in the path has had the number if items available decremented.
The epoch can have been incremented without having been used during dequeue. Which does not have a pathological effect on the system but is definitely not clean.
We would in the case of partial failure on enqueue. Add an item to the items table and never add it's features to the feature space. Thereby accruing junk data in the items table. The item would eventually be dequeued, if another item with the same features was added successfully later. The possibility of failure during enqueue resulting in a successful dequeue is pathological.

At minimum we need the process of removing an item to be atomic. As we can otherwise arrive in a state where we are not returning the fairest item.

Make memory usage in storage layer configurable
Make SPQ itself detect memory limits and configure storage layer appropriately