Request Cache for Super Node

[SteamShon]

I want to ask about feasibility of following idea.

Problem

let me first start with one example usage, realtime collaborative filtering.

for example, in below picture, user-content activity is represented by top layer and content-content similarity is represented by bottom layer, so it is basically two step query such as V("user") -> interactedContents -> similarContents

current problem is that there are too much request amplification on content-content similarity layer(second step).

Many times, content interaction is very skewed and only few of them(few most popular contents) consist of most of user`s interaction which means many user will ask what are similar content of these few most popular contents.(watch red arc on picture).

This problem is not limited to realtime collaborative filtering example. In general, It is inevitable to amplify request on next step if there is super node(few of most popular content in example) on previous step (super node also could be very famous people in social media domain).

super node eat up all resource on HBase side even though we use bloomfilter.

here is example table that has very small amount of data(2~3 MB) per each region, but requests on this table reached over 400K per second.

Approach

I have been experimenting with following two approach.

Simple Result Cache

current implementation already use local cache on meta data from RDBMS. so why not use local cache for result?

well, it turns out local cache is only useful when data is very small and can be fitted into memory. so tried with Redis cluster as cache. I used Rediscala client since it support asynchronous client.

summary is following.

1. we can reduce requests into HBase if we use redis. but how we going to reduce requests into redis then?
2. simply not performant enough. the response time drops because we spend all our cpu for sending rpcs into redis. have used pipelined but not helped much.

So basically, we need to reduce number of rpc calls to what ever storage is(HBase or redis or whatever cache layer) rather than optimize single rpc performance.

Future Cache

I researched and find out spray cache idea can be nice solution for our problem.

Basic idea is storing Future for expensive operation, not result of expensive operation.

By storing Future instead result, we can save lots of resource thanks to future`s callback property.

spray cache it self is very nice library but to understanding mechanism, I tried to implemented it by hand.

current implementation expire future on two criteria.

1. number of concurrent request on same key while single future is running.
2. expire time for future after accessed.

This criteria means "squash maximum concurrent request to storage into one future, or squash at least expire time.

experiment shows that there is throuhput gain and reduce on reponse time with much smaller requests sent to HBase.

will try more experiment on this.

Discussion

Is this right? What others think? How we are going to our problem? give me a direction and I am on my way to experiment more. any feedback would be appreciated and correct me if I am on wrong direction.

[HeartSaVioR]

Second approach looks promising. One thing to consider is when we want to invalidate cache element. Do you want to remove future from cache table as soon as future gets the result? Or do you want to store result for some moment? If you want to do latter, do you want to tolerate showing previous data for some moment, or invalidate cache immediately when result becomes invalid (removed, updated)? If operation is async, it seems that invalidating cache still have a chance to show previous data.

[SteamShon]

@HeartSaVioR

good point. so problem is when to invalidate future cache table. right.

if we use second approach on every request, then there is chance to show previous data since.

I was thinking about giving user option to specify, "ok I am ok with this much of time old data" then run second approach only when user specify this option. This option can be turn on by providing cacheTTL on query. if user specify this value, then we can expire future from cache after this time. but if first request put future on table, then there is no more request on that key, then we need to expiration. so I was thinking about max idle time too.

The basic expiration policy is when future finished, then remove it from future table(like you said).

I want to give option to user to control this by # of concurrent request on same key while first future finished(1 is same as you described).

so in brief, followings are what I have come up with.

1. of concurrent request on future table.

2. time to live
3. time to idle

I am testing with these 3 and let me know if you come up with better way.

[HeartSaVioR]

@SteamShon 2, 3 are clear and make sense to me. Regarding 1, I'm curious about use cases of this approach. Basic expiration policy could be also implemented via setting TTL to 0, so we may want to get another use cases.

[SteamShon]

This is what I have found sofar.

I tested with following data + query.

test graph data

for quick test I used following synthetic data.

matrix: 1000000 x 1 rowId: 0 ~ 1000000 colId: one of randInt(0, 1000000)

query

ids array size 100. each test set represent probability of future cache hit.

{
    "srcVertices": [
        {
            "serviceName": "s2graph-test",
            "columnName": "item_id_test",
            "ids": [
                %s
            ]
        }
    ],
    "steps": [
        {
            "step": [
                {
                    "cacheTTL": -1,
                    "label": "insert_test",
                    "direction": "out",
                    "offset": 0,
                    "limit": 1
                }
            ]
        }
    ]
}

test

I was curious about how much future cache can reduce requests to hbase, when the probability to hit future cache decrease.

so start from 100% hit to almost 0% hit, I created following test sets. for each case, I compared # of requests to hbase with respose time and throughput on s2graph server to see how much penalty we get on client side.

test set 1: 100 from randInt(0, 100) per each query request

this is 100% hit case.

HBase

turns out by increasing cacheTTL, we can reduce significant requests to hbase as expected.

no cache

cacheTTL 1000

cacheTTL 10000

App server

turns out when future cache hit with high probability, client response and throughput increase also as expected.

no cache

cacheTTL 1000

cacheTTL 10000

test set 2: 100 from randInt(0, 1000) per each query request

less hit than set 1 but still very high probability of hit.

HBase

no cache

cacheTTL 1000

cacheTTL 10000

App server

no cache

cacheTTL 1000

cacheTTL 10000

test set 3: 100 from randInt(0, 10000) per each query request

less hit than set 1 but still high probability of hit.

HBase

no cache

cacheTTL 1000

App server

no cache

cacheTTL 1000

test set 4: 100 from randInt(0, 100000) per each query request

small probability of hit.

HBase

no cache

cacheTTL 1000

cacheTTL 10000

App server

no cache

cacheTTL 1000

cacheTTL 10000

test set 5: 100 from randInt(0, 1000000) per each query request

very small hit. I tested with long cacheTTL this case to see if rlu eviction is working correctly(not blowing up memory)

HBase

no cache

cacheTTL 1000

cacheTTL 10000

cacheTTL 100000

App server

no cache

cacheTTL 1000

cacheTTL 10000

cacheTTL 100000

Result

If there are high probability of future cache hit, then great, we can reduce number of requests to storage as we expected and actually getting performance gain. if there is no chance to hit on future cache, then simply don`t use this feature by specifying cacheTTL -1 to avoid wasting cpu cycle to look for cache table.

[SteamShon]

@HeartSaVioR

I agree that there is no real use cases for # of cuncurrent requests on same future. I was curious how performance affected if we cache more requests into future cache so 1 was just for test purpose.

So finally I was testing above result with following setup.

cache is simple LRU without expiration on it and each query hint cacheTTL specifying how much old data user can accept so each future can have different expiration time.

if request on cached future keep comming, then expire if current time > cachedAt + query`s cacheTTL. otherwise let LRU evit this not accessed future.

Thanks for pointing out and let me know what you think.

[Ephemera]

:+1:

[HeartSaVioR]

@SteamShon :+1: Since issue points out about super node, which represents that we expect cache hit would be high when circumstance is normal. Actually test 5's TPS is much lower than test 1 without cache, so we could think it is worst case and tolerate result of test 5.

[elric-k]

:+1:

[djfwan]

:+1: