0
$\begingroup$

I have a server. It has e.g. one million documents. My website has a spreadsheet. Each page has space enough for e.g. 50 rows. As I scroll down, I will want to request the rows from the server, and I will cache the range I asked for in memory.

However, if I scroll up again (or place the scrollbar arbitrarily), I only want to ask for the subset of documents that I have not yet cached. Thus, I will possibly ask the server several times for different smaller ranges until I have been able to complete my target range.

This must be a well-known fragmentation problem, but I don't know.

Which data structures and algorithms is the best to use in this case?

$\endgroup$
1
  • $\begingroup$ I don't understand what the problem is. You already described what sounds like a complete solution. I'm not sure what more there is to say or what kind of answer you are hoping for. We generally discourage asking what is "best" because that is vague and a matter of opinion. We would ask that you identify your requirements or criteria by which you will evaluate answers. "best" by what metric? $\endgroup$
    – D.W.
    Dec 22, 2021 at 1:35

1 Answer 1

0
$\begingroup$

There are things unclear in your question, but lets assume some things first.

If you want to deploy a caching mechanism you need consider the size of the cache and in what size chunks you want to cache the data.

Secondly, you need to understand the temporal and spatial locality of your data. For example, if you have a database which has a primary key and the results are sorted by the same in your website, you could prefetch some extra data along with the request to minimize the calls to your server. However if it is non-indexed data, something like hashes, then it would depend on the request, if the user scrolls down /up you may have cache hits and if its a random request you may not.

Thirdly, based on what you asked it seems like a case of the optimal page replacement algorithm(feel free to correct me), which is non implementable. You can never predict what data is going to be requested, which is why we have the locality of reference to help reach near optimality in most cases. You will have to decide cache eviction/cache replacement policy(Why is this needed? If we assume what you want is possible then eventually your whole database is going to be stored on the cache, then why would you store it on the server in the first place?). Stack based algorithms are generally used like LRU, LFU and its variations. At some point your cache will fill up and you will need to decide which existing cached data to remove.

You only need to worry about all these if you yourself are going to implement a caching mechanism. For data structures you can use anything from a simple array to a self balancing tree to a hashtable. Since caching is all about reducing the retrieval time, you need to understand that only the complexity of operations on data structures don't matter. Sometimes an operation might have a higher growth rate but may be faster at runtime.

Look up how in memory databases work, for example Redis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.