Hi Charles, There is a FLIP-220[1] and discussions[2] about introducing a sorted map state in binary order. But it seems like there is no further progress and conclusion. It would be nice if anyone could drive this.
I would +1 for introducing this. As the RocksDB stores key-value in binary order, we should also keep that order. And the API design requires more discussion. [1] https://cwiki.apache.org/confluence/x/Xo_FD [2] https://lists.apache.org/thread/lbdpr1cjt9ddrotowmzzk4lv787b3t5z Best, Zakelly On Sat, Apr 12, 2025 at 6:35 PM Charles COLELLA <charles...@hotmail.fr> wrote: > Hi all, > > I'm building a Flink application that processes real-time order book data > (~70k events/sec), partitioned by instrument. > > > For each key, I need to maintain an order book where levels are kept > ordered by price. Since Flink's state API doesn't support ordered > structures like a NavigableMap or TreeMap, I currently have to: > > - Store all levels in a MapState<Double, OrderLevel> for persistence, > > - Maintain a parallel TreeMap<Double, OrderLevel> in memory to preserve > ordering, > > - Keep both in sync on every update, > > - And rebuild the memory structure from MapState during recovery. > > > This adds significant overhead: > > - Extra memory (duplicate data structures), > > - Extra logic (synchronization and consistency), > > - Extra CPU cost (sorting, filtering, top-K extraction). > > The use case (maintaining sorted state per key) is common in financial > applications, ranking systems, and any stream logic requiring efficient > ordered access. > > > I’ve tried to search the Jira, dev mailing list, and flips, but couldn’t > find a discussion on 'TreeMapState', 'SortedMapState`, or abstraction that > would support this. > > > Has this been discussed before, or would it make sense to open a proposal? > > > Thanks, > > Charles >
