Sliding Window Data Store in Erlang(stratus3d.com)
stratus3d.com
Sliding Window Data Store in Erlang
http://stratus3d.com/blog/2015/05/19/sliding-window-data-store-in-erlang/
3 comments
Queue based implementation is obviously the cheapest but author does not mention that queue.erl time complexity is O(1) amortized. It does introduce latency spike when "in" list needs to get reversed because "out" list is empty.
Your right. There will be a huge latency spike when the out list needs to be refilled.
My throughput benchmark does take this into account though. It attempts to add 100,000 events to a window that only keeps events for 10 seconds. Adding 100,000 events takes much longer than 10 seconds, so the out list will be repopulated a couple times before the test is complete. The throughput benchmark is only an average though... And a longer running throughput test would yield a more accurate average.
I will update the post with this information.
My throughput benchmark does take this into account though. It attempts to add 100,000 events to a window that only keeps events for 10 seconds. Adding 100,000 events takes much longer than 10 seconds, so the out list will be repopulated a couple times before the test is complete. The throughput benchmark is only an average though... And a longer running throughput test would yield a more accurate average.
I will update the post with this information.
Is there some possible optimization to be made here by bucketing seconds and dropping buckets wholesale rather than having to peel off items until you find the start of the window?
You'd end up quantizing the window, but.. dunno, just spitballing here.
You'd end up quantizing the window, but.. dunno, just spitballing here.
I had thought about that but never got around to building a sliding window that worked that way. The challenge is that then the `events/0` call might return events outside the window of time. But there is a potential performance improvement if we don't have to always be removing old events one by one.
I'll have to try improving the list implementation with "buckets"... I wonder if buckets could be represented as lists stored inside a tuple or another list...
I'll have to try improving the list implementation with "buckets"... I wonder if buckets could be represented as lists stored inside a tuple or another list...
Right, you'd end up returning one bucket too little, or one bucket too much, of your full time window, depending on what tradeoff you decided was OK to have.
And yeah, I was thinking of buckets as append-only lists that got dropped in their entirety when out of range.
And yeah, I was thinking of buckets as append-only lists that got dropped in their entirety when out of range.
Looking at this code I really can't help but think the biggest opportunity out there for PL designers is Pythonic BeamVM language.
Elixir is great, but I think a language like this would pull away so many Python guys from their migration to Go and Python3 and take Erlang to a new level.
Elixir is great, but I think a language like this would pull away so many Python guys from their migration to Go and Python3 and take Erlang to a new level.