Are there any best practice recommendations for maintaining a sorted list in keyed state?

FYI, some of us are working on FLIP-220 (https://cwiki.apache.org/confluence/display/FLINK/FLIP-220%3A+Binary+Sorted+State), which is aimed directly at handling this use case in a more efficient way. For now, the best way to handle this depends a bit on the specifics of your job. (In some cases it might be better to use MapState, using the timestamps as the keys in the map.) You might also consider using Flink SQL to do the sorting for you. It has a reasonable implementation of sorting by timestamp, and I expect that eventually that implementation will be reworked to take advantage of FLIP-220.

When iterating over map state, does that come out sorted? Timestamp as the key does make sense in my scenario as I do not expect to have multiple events with the same timestamp

If you are using rocksdb, then the map iterator will, in fact, iterate in sorted order if the keys are timestamps. But this is an accident of the implementation, and isn’t guaranteed by the API. Part of the goal of FLIP-220 is to expose this in a principled way, and support it across all state backends.

Hmm very interesting. I think that might make the most sense for me despite the accidental behavior of it and then stay as a watcher for the more dedicated feature.

I think that could be a reasonable choice.

What’s the timeline for that feature? That proposal looks quite thorough

We have a few final tweaks to make to the API, and then we’ll put it up for a vote. We’d like to get it into 1.17, but with the feature freeze coming in 2 weeks, dunno if we’ll make it. The implementation is nearly complete, but there are a few tasks remaining.