LRU Query Cache

Question: A cache is a data store housed in memory (RAM) that is used for quick data retrieval. Real-time data in kdb+ is usually cached, allowing for quick queries. Historical data, however, is always stored on disk which results in retrieval times that are magnitudes slower. Due to the cost of RAM and sheer volume of data, it is not practical to store historical data in its entirety in RAM. We can, however, cache bits of it based on usage. The cache we will build is a Least Recently Used (LRU) cache, whose eviction policy is to discard the least recently used item. The cache will be used to store a whole day's worth of data for a single date and sym. The cache size is the maximum number of items allowed in the cache. If the cache fills up past the cache size, then the eviction policy will need to be enforced.

Given the below definitions, override the function '.z.pg' to use and update the cache whenever a query is received. Each entry in the cache is a whole day's worth of data for a single sym (ex. all AAPL data for one date). The query can come in as a qSQL string or parse tree. For simplicity's sake, no more than one date and sym are allowed in the query. Date and sym should also be supplied as the first two filters in the where clause. If these conditions are not met, '.z.pg' should error with 'BadQuery'. We are only sticking to one date and sym to simplify the logic needed for this question, however it is easy to extend the cache for supporting multiple syms in each entry.

More Information:

https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

Example

                                
                                cache:([]date:();sym:();data:());
CACHE_SIZE:2;

// After .z.pg defined, date partitioned and parted sym column

q)\t t1:.z.pg "select from quote where date=2018.01.03, sym=`AABA"
984
q)\t t2:.z.pg "select from quote where date=2018.01.03, sym=`AABA"
0
q)t1~t2
1b
q)cache
date       sym  data                                                         ..
-----------------------------------------------------------------------------..
2018.01.03 AABA +`date`sym`time`exchange`bid_price`bid_size`offer_price`offer..
q)\t t1:.z.pg "select max bid_price, min offer_price by `minute$time from quote where date = 2018.01.03, sym=`AAPL"
2158
q)\t t2:.z.pg "select max bid_price, min offer_price by `minute$time from quote where date = 2018.01.03, sym=`AAPL"
51
q)t1~t2
1b
q)\t .z.pg parse "select max bid_price, min offer_price by `minute$time from quote where date = 2018.01.03, sym=`AAPL"
52
q)cache
date       sym  data                                                         ..
-----------------------------------------------------------------------------..
2018.01.03 AAPL +`date`sym`time`exchange`bid_price`bid_size`offer_price`offer..
2018.01.03 AABA +`date`sym`time`exchange`bid_price`bid_size`offer_price`offer..
q)\t t1:.z.pg "select from quote where date=2018.01.03, sym=`A"
424
q)\t t2:.z.pg "select from quote where date=2018.01.03, sym=`A"
0
q)t1~t2
1b
q)cache
date       sym  data                                                         ..
-----------------------------------------------------------------------------..
2018.01.03 A    +`date`sym`time`exchange`bid_price`bid_size`offer_price`offer..
2018.01.03 AAPL +`date`sym`time`exchange`bid_price`bid_size`offer_price`offer..

Solution

                                
                                ######## solution.q ########

cache:([]date:();sym:();data:());
CACHE_SIZE:2;
.z.pg:{
    if[10h=type x;x:parse x];                                       /convert str to parse tree
    wc:raze x[2];                                                   /where clause
    dt:wc[0;2];                                                     /date value
    s:wc[1;2];                                                      /sym value
    if[not `date`sym~2#wc[;1];'BadQuery];                           /expect date,sym
    if[not (1=count s) & 1=count dt;'BadQuery];                     /expect 1 date, 1 sym
    data:exec data from cache where date=dt, sym=first s;
    data:reval $[count data; data; (?;x[1];enlist 2#wc;0b;())];     /initial select for date+sym data
    delete from `cache where date=dt, sym=first s;
    `cache insert (dt;first s;data);
    cache::-1 rotate cache;                                         /place data at head of cache
    if[CACHE_SIZE<count cache; cache::-1_cache];                    /drop least recent
    reval (?;data;enlist 2_wc;x[3];x[4])
 };

Explanation: Check whether the incoming query is a string, if so convert it to a parse tree using 'parse'. Next, check if date and sym are the first two columns in the where clause, and that only one date and sym exists, otherwise return an error. Check the cache for an existing entry for the given date and sym. If an entry exists, then select from the cached data, otherwise select from disk. Delete the cache entry if it exists, insert the selected data, and rotate the cache table to the right to have the new entry at the top of the cache. Check if your cache size is exceeded, if so then drop the last entry. Finally, select from the data using the remaining where clause filters, group by expression, and column selection.

Code:

https://bitbucket.org/alvikabir/dailyq/src/master/Advanced/lru-query-cache

Tags:

architecture ipc optimizations sql tables

Searchable Tags

algorithms api architecture asynchronous c csv data structures dictionaries disk feedhandler finance functions ingestion ipc iterators machine learning math multithreading optimizations realtime shared library sql statistics streaming strings tables temporal utility websockets

daily q

LRU Query Cache

Example

Solution

Tags:

Searchable Tags