Kasino

A construction that elastically relaxes a given collection.

Kasino aims to improve performance of concurrent datastructures by sharding operations into multiple subqueues. This process introduces a relaxation of the wrapped datastructure, the specifics depending on the used strategy.

Strategies optimize for performance and relaxation bounds, but can be implemented to optimize for other properties.

Multiple strategies, amenable to different kinds of datastructures and requirements are provided.

Additionally an interface for defining custom strategies is available.

Usage

use kasino::{InlineBandit, strategy::DCBO};

let bandit = InlineBandit::<MyQueue<i32>, DCBO, 8>::new();

let mut handle = bandit.buy_in();
let mut handle2 = handle.fork();

assert!(handle.offer(42).is_ok());
assert!(handle2.offer(10).is_ok());
assert!(handle.poll(()).is_ok());

Property preservation

Progress Guarantees:

• Lock Freedom: if the wrapped collection is lock-free, Bandits are also lock-free.
• Obstruction Freedom: if the wrapped collection exposes obstruction-free methods, all corresponding operations on Bandits are also obstruction-free.

Ordering and Consistency Guarantees:

• Relaxed Specification: if the wrapped collection has some specification, Bandits relax that specification based on the chosen strategy.
• Linearizability: if the wrapped collection is linearizable, all operations on Bandits are also linearizable with respect to their relaxed specification.

Relaxation

The rank error and delay are in general unbounded. However, the rank error and delay of some strategies are bounded with high probability. The exact bounds here are differing across different strategies.

For more information refer to the strategies documentation and the reference papers.

For an empirical analysis of the rank errors, refer to relaxed-queue-simulations.

Performance

Sharding operations to multiple sub-collections incurs both memory cost, as well as additional overhead. Under low contention Kasino is slower than the raw collection.

However, scheduling thread access across multiple sub-collections allows to reduce cache-line invalidation at high contention, improving performance as thread count increases.

Limitations

• Currently an instantiated Bandit cannot be resized. Its capacity is fixed at construction time.
• The capacity of each sub-collection is fixed statically. The total capacity of a Bandit is constrained to a multiple of this.

Advanced Usage

The interfaces for Collection, strategy::Strategy and Bandit are general enough to support the implementation of a large set of datastructures. For examples of this consult examples/.

Platform Support

All platforms supporting native atomic operations are supported.

The feature atomic-fallback may be used, if no native atomic operations are available.

Feature Flags

• std: Enables std support.
• instrumented: Adds telemetry collection to strategies
• atomic-fallback: Uses the portable-atomic fallback feature if native atomics are missing. It is discouraged to use this feature, as fallback atomics internally rely on locks.
• default: None

Testing

Currently testing is based on:

• Miri - to validate pointer arithmetic and catch undefined behavior.
• Loom and Shuttle - to test for race conditions and non-blocking invariants.
• ASan - to check for memory corruption.

References

• Performance, Scalability, and Semantics of Concurrent FIFO Queues, Kirsch et al.
• Balanced Allocations over Efficient Queues: A Fast Relaxed FIFO Queue, Geijer et al.