Rolling time window store
Store your data efficiently in rolling window buckets store. This technique is also named:
- Rolling ring
- Bucketing
- Bining
- Sliding window
Rolling windows module can be used by both browser and Node.js.
High perormance
All rolling windows were built with great concern of memory and CPU consumption. We don't use arrays under the hood.
Inside this module you will be able to find
- Super-high test coverage
- class WindowCore - A very simple & basic window, it only manages to additions and disposals of buckets.
- class TimeWindowCore - Window that adds and dispose buckets based on a configurable interval.
- class WindowSingleCounter - Window with counter in every bucket.
- class WindowSingleStackedCounter - Widnow with stacked counter (Based on previous bucket).
- class TimeBasedWindowCounter - Window with counter in every bucket it adds and dispose buckets based on a configurable interval.
- class WindowMultipleCounters - Window with multiple counters in every bucket.
- class TimeBasedWindowMultipleCounters - Window with multiple counters in every bucket it adds and dispose buckets based on a configurable interval.
- class GenericTimeBasedStore - Window with generic object in any bucket that you can store any info in the last bucket and query all at once.
Speed and quality are the greatest concerns, this module was built with proper data structures and with some V8 micro-optimizations for even better CPU and memory consumption.
What is a rolling window?
A rolling window is a technique to process and store a subset of an endless stream of data while perserving the order of processing/disposel of the data.
The window can be considerd as an actual window, while through the window you see at any given time data at a maximum size of the window. Similiar to a very long train passing and you can see only a few railroas cars at any given time.
It is used in mathemtics to analyze a subset of a bigger set of data points, usally over time.
For example if your planing to count all the requests your server is getting at any last 24 hours, you cannot use a simple stright forward single counter count++
because you will not know how to descrease the count.
- You cannot reset the count
count=0
you will lose all your data. - You can store a timestamp of every request however, this will consume a lot of memory and CPU because you will store every individual timestamp.
No worries you can just use a 'Rolling window'!
Simple to use
Using Javascript
//Require all `rolling time window` module const rollingTimeWindow = ; //Now you can use `rollingTimeWindow.TimeBasedWindowCounter` etc... //Directly load the desired class const WindowSingleCounter GenericTimeBasedStore = ;
Using TypeScript
;
Why not just array?
The most common and simple implementation of rolling window is sometimes handled by an array under the hood.
Arrays would have consumed more CPU in this use case
Array is an implementation of a stack data structure and is the best implementation when you need to push/pop something at the end of the stack. However, when it is also requeired to remove something at the beging of the stack the array will need to Move all elements and re-index the entire array with o(n) complexity (Imagine an array with millions of elements). While with linked list it's only o(1) complexity at any size of array.
Example of a bad practice:
var a = 12345;a // Will cause o(n) operations
Array would have have wasted more memory
Under the hood arrays are dynamic data strucure these change per the programtic demand in run time. Generally these are the recomendations of using arrays:
- Don't pre-allocate large arrays to their maximum size, instead grow as you go.
- Use contiguous keys starting at 0 for arrays
- Don't delete elements in arrays.
- Don't load uninitialized or deleted elements
Any deviation from these recomdations will cause the js engine (V8) to move the entire array from one implemnetation of array to the other, this will waste both memory & CPU.
Example of a bad practice:
var a = ;a0 = 20; // JS engine allocatesa1 = 100;a2 = 1005; // JS engine allocates, convertsa3 = true; // JS engine allocates, converts
Example of a better practice:
var a = 20 100 1005 true;
Example of a bad practice:
var a = 12345;a // Will cause o(n) operations
API
All rolling windows handles the basic concept rolling windows some in addition also handels a configurable internal time interval. A few concepts that will ease the API description:
- Window / Rolling window - The actual instance the implements the technique or the technique in general.
- Bucket - A window has multiple buckets/bins that store the data of that window fraction.
- Tick - The action of addind a bucket at the end of the window and when maximum window size passed it will also remove the bucket at the beginning of the window.
- Bucket value - The value the bucket points on, it can be a single numeric value, an object , array, etc...
The follwing is not a complete module decleration, I sugesst to require the module with TypeScript, it will give you a full view on the entire module.
The following will assist you to gasp what the module can do for you before you install it. If you are not famillier with TypeScript you can go a head and jump to the exampels.
; ; ; ;
Examples
Simple use of multiple counters
const TimeBasedWindowMultipleCounters = ; const rollingTimeCounters = timeWindow : 1000*60 //I want to have information up to 1 minute bucketsFrequancy : 1000*10//I want to have bucket every 10 seconds;//Start the internalrollingTimeCountersstart; //You can count any eventrollingTimeCounters; //You can iterate over your bucketrollingTimeCounters
Simple use of single counter
const WindowSingleCounter = ; const counter = timeWindow : 1000*60*60 //I want to have information up tp an hour bucketsFrequancy : 1000*20//I want to have bucket per 20 seconds;//increasecounter; //I can iterate over your bucket and calculate totallet total = 0;counter;console; counterstart;
Some cool examples of what you can do with these rolling windows.
Count the status code of your http server
const TimeBasedWindowMultipleCounters = ; const rollingTimeCounters = timeWindow : 1000*20 //I want to have information up to 20 seconds bucketsFrequancy : 1000*2//I want to have bucket per 2 seconds;rollingTimeCountersstart; const server = ;
Rate limit your client http requests per client account
In the following example I want to:
- Limit account to 1K requests an hour.
- Notify the client on the quata left at any given request.
const REQUEST_LIMIT_PER_HOUR = 1000;const TimeBasedWindowMultipleCounters = ;const querystring = ; const rollingTimeCounters = timeWindow : 1000*60*60 //I want to have information up to 1 hour bucketsFrequancy : 1000*2//I want to have bucket every 1 minute;//Start the internal intervalrollingTimeCountersstart; { let shouldBlock = false; //If the account already passed the limit we need to block it let requestsThisHour = 0; //Find requests count of the last hour - the full window rollingTimeCounters; if shouldBlock return false; else //Request passed - count it rollingTimeCounters; //Sending rate limits information to the client res; res; res; return true; //Find if this account passed one of the limits};