Zero cache misses is a lower bound but is usually impossible. The key is to compare how well our algorithm performs with how well our algorithm could possibly perform. So our worst-case performance corresponds to our worst-case user: one who maximally breaks our cache at every step.īut a pure adversarial analysis won’t work, since a user can always make our cache perform badly by just requesting lots of files –eventually, some of them won’t be cached. How do we measure the worst case number of cache misses? Unlike a normal algorithm, our runtime is driven by the user’s actions. Maximizing cache hits is the goal of the first part of this post quickly implementing the cache will be the topic of the second part. Second, the overhead of using a cache should be small: testing membership and deciding when to replace a file should be as fast as possible. First, The cache should ensure that as many of the requests for files go to it (cache hit), not over the network (cache miss). The cache needs to be fast, along two metrics. Note also that we’re stuck with an on-line algorithm: we can’t predict what files a user will want in the future. If the cache has a file, it will give us its copy if not, the cache has to fetch the new file, and it might also want to remove a file from its cache to make room for the new file. To determine which files to keep, every time we want to use a file, we tell the cache to fetch it for us. In fact, Dropbox stores files in 4MB blocks, so this simplification isn’t too far off (we’ll see later how to avoid it). We’re assuming all files have the same size. We have a large set of files, and we’d like an algorithm to determine which (k) files to keep at any point.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |