Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

VALUE-BASED EVICTION SCHEDULING IN CACHE

IP.com Disclosure Number: IPCOM000246413D
Publication Date: 2016-Jun-06
Document File: 4 page(s) / 211K

Publishing Venue

The IP.com Prior Art Database

Abstract

This application discloses a system and method of value-based eviction scheduling in cache. The system may be a network server enabling access to resources through the web. The method involves calculating an expected value of a page as a function of time, based on variables including page-hitrate, computational cost of creating an object, size of an object, the time of the last page reference, the type of access read/write, etc. The cache eviction method here could function as an alternative to the LRU algorithm that will handle variable-sized objects.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 4

VALUE-BASED EVICTION SCHEDULING IN CACHE

ABSTRACT

    This application discloses a system and method of value-based eviction scheduling in cache. The system may be a network server enabling access to resources through the web. The method involves calculating an expected value of a page as a function of time, based on variables including page-hitrate, computational cost of creating an object, size of an object, the time of the last page reference, the type of access read/write, etc. The cache eviction method here could function as an alternative to the LRU algorithm that will handle variable-sized objects.

BACKGROUND

    In computing, the performance of data storage is enhanced by cache. Some caches, like memcached store a large number of variable sized objects in a context where the scanning of memories is expensive during eviction phases. The goal of this system is to store objects in memory so that commonly accessed objects could be served from relatively fast memory as opposed to fetching the data from a solid-state drive (SSD) or hard disk drive (HDD) based backing store, fetching the object over network, or recreating the object.

    Systems such as memcached have a few constraints. First, the metadata tables could be large enough that the metadata has to live on the same medium as the cached data. This becomes a problem when a demon wakes up and needs to evict some objects to create free memory. If the metadata is stored in a linked list, the demon will need to query the data once for every object. The round trip times for interacting with the main memory could cause time delays. There is additionally the overhead of maintaining pointers for the linked list. Another relevant constraint


Page 02 of 4

is that since these caches could deal with objects of varying sizes, holding a large object means that fewer small objects could be cached.

    The last constraint that is relevant here is that caches of this size could not have expensive eviction policy algorithms. In general, the eviction decision needs run in constant time O(1) with respect to the object churn rate in the cache and the size of the cache. A more efficient method for cache eviction that still runs in constant time is proposed here.

DESCRIPTION

    Disclosed here is a system and method of value-based eviction scheduling in cache. The system may be a network server enabling access to resources through the web. The method involves implementing an algorithm with core features in the syste...