A design dilemma with new Streams XADD command

[Salvatore Sanfilippo]

Hello list!

It's a few weeks that I'm designing and implementing the new Stream data structure for Redis.

I'm very excited because this is the first general purpose data structure added to Redis after many years. Yes, in the past we added things like bit operations, hyperloglogs, lex ranges in sorted sets and with modules there are a multitude of other things possible. But Streams (which are actually "logs" conceptually), are the first new big data structure in Redis, like hashes, sets, lists and so forth.

While a few things changed during the implementation of Streams, you can read the proposal here: https://github.com/redis/redis-rcp/blob/master/RCP11.md

The implementation of the proposal is proceeding in a now public branch here:

https://github.com/antirez/redis/commits/streams

So far we have the following commands implemented:

XADD key field1 value1 ... fieldN valueN

XLEN key

XRANGE key <START id or time in milliseconds> <END id or time in milliseconds> [COUNT count]

XREAD key [BLOCK timeout] [COUNT count] STREAMS key1 start-ID1 key2 start-ID2 key3 start-ID3 ...

RDB storage is supported, AOF is still not supported.

So basically what we have is the data structure itself implemented, as an hybrid between a radix tree and the new "Listpack" serialization format. Range queries are fully implemented, and blocking on streams for new data is also supported.

However I reached a design dilemma with XADD, and I think that raising the issue publicly may improve the design, picking more brains to reach a better result.

This is how XADD now works:

127.0.0.1:6379> XADD mystream name Ada surname Lovelace

1505126157183.0

The entry ID is generated and returned.

The XADD command looks simple and natural like the other basic Redis commands to add things, like SADD or RPUSH or alike.

However there is a problem. In order to replicate the command to AOF and slaves, the ID must be passed as already generated, because it is not generated purely on what the stream already contained, there is also the local time of the server involved (not always, the IDs are guaranteed to be always increasing, so if the last ID in the stream has a timestamp part of the ID which is greater than the current time, it is used instead of the local milliseconds time, and just the sequence part is implemented, which is the part after the dot -- All the details are in the specification).

P.S. in case you wonder why unique IDs are generated with a timestamp part, this gives you, with XRANGE, not just IDs range queries, but also time range queries.

So, this problem could be easily bypassed just adding a different XADD form to use for AOF / replication. We do this with EXPIRE for example, which is translated to EXPIRE-AT.

So if we get from the client:

XADD mystream name Ada surname Lovelace => 1505126157183.0

We replicate something like:

XADD-WITH-ID mystream 1505126157183.0 name Ada surname Lovelace

And this is what will be sent to AOF / slaves. Consistency will be saved and everybody is happy.

However in most applications, streams should also be capped collections, since to append to an infinitely long stream is not what you always want indeed.

So you should be able to specify, when adding, how many maximum items, or the maximum age, entries can have: everything older, or after a certain number of elements will be evicted automatically. Something like:

XADD-AND-EVICT mystream BYLEN 10000 name Ada surname Lovelace

Or

XADD-AND-EVICT mystream BYAGE 5000 name Ada surname Lovelace

For now, I'll even ignore that to replicate this we need another variant where I can also specify the ID. Also note that BYAGE will be translated to an absolute fixed millisecond.

Now here is the dilemma. The above not just gets confusing soon, but also if you think at it, most of the people may never use the vanilla XADD in many applications, since to have a capped stream could be vital for *most* applications. Remember that Redis is in memory. Even if the memory efficiency of streams is amazing (thanks to the representation used) and is going to improve even more with IDs / fields compression, still you want to say "no more than 100 million entries" or alike I guess.

So, maybe it's worth to get out of the mentality of "vanilla XADD should be simple" and give directly a command which is capable of handling all the exceptions?

It would be like that:

XADD key <ID or *> [MAXLEN <len> | MAXAGE <ms-age> | MAXTIME <ms-unixtime> | NO CAP] filed1 value1 ... fieldN valueN

Note that the * ID means: generate it yourself, as the current XADD implementation does by default. Why NO CAP means not capped. This also means that the user has to explicitly write that it is using an unbound stream.

So the initial example in this email will turn into:

XADD mystream * NO CAP name Ada surname Lovelace => 1505126157183.0

Which is more complex, but with a single command we'll accomodate everything including replication. The command will be simply replicated as:

XADD mystream 1505126157183.0 NO CAP name Ada surname Lovelace

Note that the obvious solution of adding just optional specifiers for the ID or eviction policy is not simple because we don't know the field-value number of pairs, nor we want that certain field names are invalid.

So far, that's my reasoning, any hint? Thanks!

--

Salvatore 'antirez' Sanfilippo
open source developer - Redis Labs https://redislabs.com

"If a system is to have conceptual integrity, someone must control the concepts."
       — Fred Brooks, "The Mythical Man-Month", 1975.

[Timothy Downs]

Firstly, having a real-working-public-branch for this is terribly exciting (thanks very much for this!). I'm going to be playing with this every available night for next the next few weeks.

I really like the idea of having a maximally 'simple': XADD key k1 v1 k2 v2 command (if it can be made to work).

Would it be completely unreasonable to split XADD command from the eviction policy?

XEXPIRE MAXLEN key

XADD key k1 v1 (and perhaps XADD-AT could be the replicated command)

[Salvatore Sanfilippo]

Hello Timothy, and thanks for your reply. The maxlen/age as an attribute of the stream (XEXPIRE or alike) would be possible, but would depart a bit from what we do know (no meta-data inside data structures, so that there is no creation + set-parameters stage), with exception of expires where it is literally the only option (the TTL is intrinsically part of the object). So basically the alternative would be more something like "XTRIM" acting similar yo LTRIM, so that the XADD + XTRIM combo would serve the goal, like [RL]PUSH + LTRIM does now. However I've the feeling this will be a so common use case, that is a shame not having it part of XADD itself.

--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+unsubscribe@googlegroups.com.
To post to this group, send email to redi...@googlegroups.com.
Visit this group at https://groups.google.com/group/redis-db.
For more options, visit https://groups.google.com/d/optout.

[Salvatore Sanfilippo]

I think I found a good solution eventually, that is to make only the ID (usually "*") mandatory:

XADD mystream * name Ada surname Lovelace 

Since the ID is either * or a well-formed <ms>.<seq> ID, it can never collide with an option name, so it is possible to add options before like that:

XADD mystream MAXLEN 100 * name Ada surname Lovelace

And so forth. This way the basic command form remains very simple, just the "*" is spurious. At the same time however the command will be future-proof, allowing options before the * that we cannot easily anticipate now. I think I'm modifying the current implementation to use this system, however please if you have a better idea, keep me posted!

Cheers,
Salvatore

[Nathan Scott]

Hi Salvatore,

On Mon, Sep 11, 2017 at 8:53 PM, Salvatore Sanfilippo <ant...@gmail.com> wrote:

Hello list!

It's a few weeks that I'm designing and implementing the new Stream data structure for Redis.

I'm very excited because this is the first general purpose data structure added to Redis after many years. Yes, in the past we added things like bit operations, hyperloglogs, lex ranges in sorted sets and with modules there are a multitude of other things possible. But Streams (which are actually "logs" conceptually), are the first new big data structure in Redis, like hashes, sets, lists and so forth.

This is a fascinating new development, thanks, I'm hoping to use

it for performance data querying.

 

While a few things changed during the implementation of Streams, you can read the proposal here: https://github.com/redis/redis-rcp/blob/master/RCP11.md

The implementation of the proposal is proceeding in a now public branch here:

https://github.com/antirez/redis/commits/streams

Some early feedback (not directly related to your question, sorry) -

any possibility of supporting a finer granularity of timestamps too?

It looks like milliseconds is being baked into streams at quite a low

level (in the struct stream_offset_t) currently.

So far we have the following commands implemented:

[...] Range queries are fully implemented, and blocking on streams for new data is also supported.

In a timeseries system I'm currently involved with users have wanted

the finest timestamp precision available from the platform.  On Linux

some were dissatisfied with the microseconds from gettimeofday(3),

which we had been using exclusively, and we ended up with disk and

wire-protocol changes for clock_gettime(3)'s nanosecond resolution.

These were people in two camps that I came across (from real world

users) - firstly, the people doing real time trading of stocks, and then

there were people doing hardware and software performance analysis

with event trace time series (e.g. http://lttng.org style trace data).

Anyway, just something for consideration in the new code - if the time

resolution could be increased, or perhaps configured? that'll be helpful

for these groups of users.

 

However I reached a design dilemma with XADD, and I think that raising the issue publicly may improve the design, picking more brains to reach a better result.

And apologies again for taking this thread a little OT.

cheers.

--

Nathan

[Joshua Scott]

Following the form of the other options, could you do something like

XADD mystream name Ada surname Lovelace
=> 1505126157183.0

and replicate by adding an "ID" option:

XADD ID 1505126157183.0 name Ada surname Lovelace

Which eliminates the mandatory * in every XADD but still allows replication to take place with consistent IDs

Thoughts?

[Salvatore Sanfilippo]

Update: I just published a video with what we have currently -> https://www.youtube.com/watch?v=ELDzy9lCFHQ&feature=youtu.be

This includes the recent change to XADD.

On Mon, Sep 11, 2017 at 12:53 PM, Salvatore Sanfilippo <ant...@gmail.com> wrote:

[Salvatore Sanfilippo]

Btw... I wanted to ask Timothy, given that he was the initial trigger for this data structure, if the final result is kinda what he had in mind originally and matches the use cases that he was trying to solve. Thanks!

On Mon, Sep 11, 2017 at 3:36 PM, Timothy Downs <timoth...@gmail.com> wrote:

--

You received this message because you are subscribed to the Google Groups "Redis DB" group.
To unsubscribe from this group and stop receiving emails from it, send an email to redis-db+unsubscribe@googlegroups.com.
To post to this group, send email to redi...@googlegroups.com.
Visit this group at https://groups.google.com/group/redis-db.
For more options, visit https://groups.google.com/d/optout.

[Timothy Downs]

My original concept was much simpler and far less flexible. I'm really liking what you've come up with however! It is a much more flexible solution than what I was originally thinking.

I've started to experiment with two uses of streams:

* Log file processing

* A memory-safe under load store for HTTP intercepting requests/responses from Nginx for assisting with micro-service debugging/playback

For both of these, I'm surprised by how well the new data structure is working out - in particular I was worried about excessive memory use, but I'm finding only a very small amount of additional memory usage above the underlying data.

Super impressed by what I've seen so far, and really keen to see where it ends up (in particular with groups).

Regards,

Tim