# US 11,442,937 B2 · Optimal admission control for caches > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,442,937 B2 - Document ID: US11442937B2 - Status: Granted - Kind: B2 - Application number: 16/899,180 - Filed: 2020-06-11 - Published: 2021-12-16 - Granted: 2022-09-13 - Earliest claimed: 2020-06-11 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Arif Merchant; Tzu-Wei Yang; Mustafa Uysal - Web page: https://patentgrep.com/patent/US11442937B2 ## CPC - G06F 16/24552: {Database cache management} - G06F 9/30047: {Prefetch instructions; cache control instructions} - G06F 12/0246: {in block erasable memory, e.g. flash memory} - G06F 12/0813: with a network or matrix configuration - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/24539: {using cached or materialised query results} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the information is collected over a historical time period. ### Claim 3 (depends on 1) The method of claim 1, wherein the information is collected in real-time over a predetermined moving window. ### Claim 4 (depends on 1) The method of claim 1, wherein the information collected may include at least one of: whether access requests have been received for data items in each category before eviction or a number of times data items from each category has been accessed before eviction. ### Claim 5 (depends on 1) The method of claim 1, wherein data items are stored as blocks in the cache storage and the information on access requests are collected for each block. ### Claim 6 (depends on 5) The method of claim 5, wherein data items in each category is stored in multiple blocks, and the utility value for each category is determined by summing respective utility values of the multiple blocks. ### Claim 7 (depends on 1) The method of claim 1, wherein the utility value is determined by one or more of: disk access time savings, written bytes to flash, and cache byte-time used. ### Claim 8 (depends on 1) The method of claim 1, wherein the utility value is determined over a plurality of cache retention times. ### Claim 9 (depends on 1) The method of claim 1, wherein newly requested data items are admitted into the cache storage in a descending order according to their respective utility value until the cache storage is full or when a next category provides a negative utility value. ### Claim 10 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. ### Claim 11 (depends on 10) The system of claim 10, wherein the one or more processors are on the storage devices. ### Claim 12 (depends on 10) The system of claim 10, further comprising: one or more client devices configured to access the data items in the cache storage. ### Claim 13 (depends on 12) The system of claim 12, wherein the one or more processors are on the client devices. ### Claim 14 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. ### Claim 15 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the information is collected over a historical time period. ### Claim 16 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the information is collected in real-time over a predetermined moving window. ### Claim 17 (depends on 14) The non-transitory computer-readable storage medium of claim 14, wherein the information collected may include at least one of: whether access requests have been received for data items in each category before eviction or a number of times data items from each category has been accessed before eviction.