# US 12,216,576 B2 · Method and apparatus to reduce cache stampeding > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,216,576 B2 - Document ID: US12216576B2 - Status: Granted - Kind: B2 - Application number: 17/880,481 - Filed: 2022-08-03 - Published: 2023-02-16 - Granted: 2025-02-04 - Earliest claimed: 2021-08-04 - Assignees: Walmart Apollo, LLC - Applicants: Walmart Apollo, LLC - Inventors: Raikirat Sohi; Mayur Saxena; Sandeep Singh - Web page: https://patentgrep.com/patent/US12216576B2 ## CPC - G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches - G06F 12/0871: Allocation or management of cache space - G06F 12/121: using replacement algorithms - G06F 16/24552: {Database cache management} - H04L 67/5682: Policies or rules for updating, deleting or replacing the stored data - G06F 11/004: {Error avoidance (G06F11/07 and subgroups take precedence)} - G06F 2212/1008: Correctness of operation, e.g. memory ordering - G06F 2212/1021: Hit rate improvement - G06F 2212/1024: Latency reduction - G06F 2212/1048: Scalability - G06F 2212/154: Networked environment - G06F 2212/173: Vehicle or other transportation - G06F 2212/283: Plural cache memories - G06F 2212/285: Redundant cache memory - G06F 2212/60: Details of cache memory - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract An apparatus comprises a memory having a data cache stored therein and a control circuit operably coupled thereto. The control circuit is configured to update that data cache in accordance with a scheduled update time. In the latter regards, by one approach, the control circuit computes selected entries for the data cache prior to the scheduled update time pursuant to a prioritization scheme to provide a substitute data cache. At the scheduled update time, the control circuit switches the substitute data cache for the data cache such that data queries made subsequent to the scheduled update time access the substitute data cache and not the data cache. ## Claims ### Claim 1 An apparatus configured to at least reduce cache stampeding, the apparatus comprising: a memory having a data cache stored therein; and a control circuit operably coupled to the memory and configured as a probabilistic data structure to update the data cache in accordance with a scheduled update time, by: prior to the scheduled update time, computing selected entries of the data cache pursuant to a prioritization scheme that uses hash functions to map events to frequencies using sub-linear space, the prioritization scheme creating a score for entries of the data cache that comprises a normalized function of a use frequency of the entry added with a random value generated using a jitter function; generating a substitute data cache using the computed selected entries; and at the scheduled update time, switching the substitute data cache for the data cache such that data queries made subsequent to the scheduled update time access the substitute data cache and not the data cache. ### Claim 2 (depends on 1) The apparatus of claim 1 wherein the data cache contains entries corresponding to hundreds of thousands of discrete items. ### Claim 3 (depends on 1) The apparatus of claim 1 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache. ### Claim 4 (depends on 1) The apparatus of claim 1 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache during a predetermined window of time. ### Claim 5 (depends on 1) The apparatus of claim 1 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache such that at least some of the computed selected entries are computed based upon those entries having been accessed more frequently than other items in the data cache. ### Claim 6 (depends on 1) The apparatus of claim 1 further comprises, subsequent to the scheduled update time, computing additional selected entries for the substitute data cache. ### Claim 7 (depends on 6) The apparatus of claim 6 wherein the additional selected entries have a lower prioritization per the prioritization scheme. ### Claim 8 (depends on 1) The apparatus of claim 1 wherein computing the selected entries pursuant to the prioritization scheme further determines an estimate of frequently-requested data items. ### Claim 9 A method to at least reduce cache stampeding, the method comprising: computing, by a control circuit operably coupled to a memory having a data cache stored therein, selected entries for the data cache prior to a scheduled update time pursuant to a prioritization scheme, the prioritization scheme creating a score for entries of the data cache that comprises a normalized function of a use frequency of the entry added with a random value generated using a jitter function; generating a substitute data cache using the computed selected entries; and at the scheduled update time, switching the substitute data cache for the data cache such that data queries made subsequent to the scheduled update time access the substitute data cache and not the data cache. ### Claim 10 (depends on 9) The method of claim 9 wherein computing the selected entries pursuant to the prioritization scheme further comprises: generating a two-dimensional sketch of an array of a counter and a set of hash functions, wherein the array is a sequence of rows; mapping each request for data into a hash function of a row in the sequence of rows; incrementing the counter at each occurrence of the request; and aggregating counter values for predetermined time intervals to introduce a time aggregate. ### Claim 11 (depends on 9) The method of claim 9 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache. ### Claim 12 (depends on 9) The method of claim 9 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache during a predetermined window of time. ### Claim 13 (depends on 9) The method of claim 9 wherein the prioritization scheme comprises, at least in part, identifying which items in the data cache are being accessed more frequently than other items in the data cache such that at least some of the computed selected entries are computed based upon those entries having been accessed more frequently than other items in the data cache. ### Claim 14 (depends on 9) The method of claim 9 further comprises, subsequent to the scheduled update time, computing additional selected entries for the substitute data cache. ### Claim 15 (depends on 14) The method of claim 14 wherein the additional selected entries have a lower prioritization per the prioritization scheme. ### Claim 16 (depends on 9) The method of claim 9 wherein the control circuit is configured, at least in part, as a probabilistic data structure that effects the prioritization scheme.