News for hackers. Stuff that matters.
Re:What If We Could Rebuild Kafka from Scratch? by bjornsing on Friday April 25, 2025 @11:22AM (#43794533)
I think the problem is that if you want quick access to all messages with a particular key then you have to maintain some kind of index over all persisted messages. So n would be total number of persisted messages as I read it, which can be quite large. But even storing them in the first place is O(n), so O(n log n) might not be so bad.
Re:What If We Could Rebuild Kafka from Scratch? by galeaspablo on Friday April 25, 2025 @12:33PM (#43795611)
That's correct. And keep in mind that you might have new consumers starting from the beginning come into play, so you have to permanently retain the indexes.

And yes, O(n log n ) is not bad at all. Sorted database indexes (whether SQL, NoSQL, or AcmeVendorSQL, etc.) already take O(n log n) to insert n elements into data storage or to read n elements from data storage.