STREAMS API in Garnet

[ramananeesh]

trafficstars

Adds support for STREAMS in Garnet.

Index Structure

Uses an in-memory B+tree (B-tree) index that has the following features:

1. Fast insertions through the tail leaf node of the index, taking advantage of sorted data input.
2. Maximizes leaf occupancy, taking advantage of sorted data input.
3. Uses tombstones for deletes.
4. Supports forward and reverse range scans.

Supported Operations in API

The following operations are currently supported:

1. XADD - add using auto-generated id and user-defined id. Does not currently support [NOMKSTREAM], [MAXLEN], [MINID] and [threshold]
2. XLEN
3. XRANGE
4. XDEL

STREAMID

Stream ID is a 128-bit ID for an entry in the Stream that is of a format ts-seq where ts is generally the timestamp and seq is the sequence number.

STREAM

The Stream Object that consists of an instance to its B-tree index and a Tsavorite log instance for persistence. Every entry added to a Stream is first inserted into the Tsavorite log that returns the added address. This address is added as the value to the index using the STREAMID as key.

StreamManager

A container/wrapper that holds all Streams in the server in a dictionary.

SessionStreamCache

A local cache of Streams added by the client for faster access. Currently capped at capacity and uses a simple FIFO policy for the initial version. Can be extended to support other eviction strategies (preferably LRU).

[prvyk]

Two nits:

1. FLUSHDB/FLUSHALL should clear the sequence number.
2. Return value is bulk string, not simple string.

[badrishc]

Run dotnet format at the command line to get rid of formatting errors.

[ramananeesh]

@microsoft-github-policy-service agree company="Microsoft"

[prvyk]

Is closing this intentional? A tracking PR could be useful for this...

[davidglassborow]

I'm also interested in it's status, streams allows us to use KEDA scaling in K8