Back to results
US 11,442,937 B2Granted
Optimal admission control for caches
AssigneeGoogle Inc.
InventorsArif Merchant, Tzu-Wei Yang, Mustafa Uysal
Life of this patent
Estimating the term…
Abstract
The technology is directed to cache admission control. One or more processors may categorize access requests for data items in a cache storage into a plurality of categories and collect information on the access requests over time. Based on the collected information, a utility value for caching data items in each category of the plurality of categories may be determined. Newly requested data items may be admitted into the cache storage in an order according to the corresponding utility values of their respective categories.
Claims17
A method, comprising:
- categorizing, by one or more processors, access requests for data items in a cache storage into a plurality of categories, wherein the plurality of categories include one or more of user accounts, jobs, tables, or portions of tables associated with processes that generated the access requests;
- collecting, by the one or more processors, information on the access requests over time;
- determining, by the one or more processors based on the collected information, a utility value for each category of the plurality of categories, wherein the utility value for each category is based on at least one of a number of disk accesses saved by the access requests or a measurement of bytes written to memory as a result of the access requests;
- identifying, by the one or more processors, a set of categories from the plurality of categories based on the determined utility values of each category;
- receiving, by the one or more processors, an access request for a new data item;
- determining, by the one or more processors, a category associated with the access request for the new data item;
- and
- admitting, by the one or more processors, the new data item into the cache storage when the category associated with the access request for the new data item matches at least one of the categories in the set of categories.
5 more elements
A system, comprising:
- one or more processors configured to:
- categorize access requests for data items in cache storage into a plurality of categories, wherein the plurality of categories include one or more of user accounts, jobs, tables, or portions of tables associated with processes that generated the access requests;
- collect information on the access requests over time;
- determine, based on the collected information, a utility value for each category of the plurality of categories, wherein the utility value for each category is based on at least one of a number of disk accesses saved by the access requests or a measurement of bytes written to memory as a result of the access requests;
- identify a set of categories from the plurality of categories based on the determined utility values of each category;
- receive an access request for a new data item;
- determine a category associated with the access request for the new data item;
- and
- admit the new data item into the cache storage when the category associated with the access request for the new data item matches at least one of the categories in the set of categories.
6 more elements
A non-transitory computer-readable storage medium storing instructions executable by one or more processors for performing a method, comprising:
- categorizing access requests for data items in a cache storage into a plurality of categories, wherein the plurality of categories include one or more of user accounts, jobs, tables, or portions of tables associated with processes that generated the access requests;
- collecting information on the access requests over time;
- determining, based on the collected information, a utility value for each category of the plurality of categories, wherein the utility value for each category is based on at least one of a number of disk accesses saved by the access requests or a measurement of bytes written to memory as a result of the access requests;
- identifying a set of categories from the plurality of categories based on the determined utility values of each category;
- receiving an access request for a new data item;
- determining a category associated with the access request for the new data item;
- and
- admitting the new data item into the cache storage when the category associated with the access request for the new data item matches at least one of the categories in the set of categories.
5 more elements
Dependencies are inferred from the claim text.