[go: up one dir, main page]

WO2018145725A1 - Systèmes et procédés destinés au remplacement de mémoire cache - Google Patents

Systèmes et procédés destinés au remplacement de mémoire cache Download PDF

Info

Publication number
WO2018145725A1
WO2018145725A1 PCT/EP2017/052607 EP2017052607W WO2018145725A1 WO 2018145725 A1 WO2018145725 A1 WO 2018145725A1 EP 2017052607 W EP2017052607 W EP 2017052607W WO 2018145725 A1 WO2018145725 A1 WO 2018145725A1
Authority
WO
WIPO (PCT)
Prior art keywords
score
cached
cache
entries
entry
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/EP2017/052607
Other languages
English (en)
Inventor
Aviv GRUBER
Dror MIZRACHI
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Huawei Technologies Co Ltd
Original Assignee
Huawei Technologies Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Co Ltd filed Critical Huawei Technologies Co Ltd
Priority to CN201780085816.0A priority Critical patent/CN110249318A/zh
Priority to PCT/EP2017/052607 priority patent/WO2018145725A1/fr
Publication of WO2018145725A1 publication Critical patent/WO2018145725A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/95—Retrieval from the web
    • G06F16/957—Browsing optimisation, e.g. caching or content distillation
    • G06F16/9574—Browsing optimisation, e.g. caching or content distillation of access to content, e.g. by caching
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/50—Network services
    • H04L67/56—Provisioning of proxy services
    • H04L67/568—Storing data temporarily at an intermediate stage, e.g. caching
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/50—Network services
    • H04L67/56—Provisioning of proxy services
    • H04L67/568—Storing data temporarily at an intermediate stage, e.g. caching
    • H04L67/5682—Policies or rules for updating, deleting or replacing the stored data
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1016—Performance improvement
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/16—General purpose computing application
    • G06F2212/163—Server or database system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/50—Control mechanisms for virtual memory, cache or TLB
    • G06F2212/502—Control mechanisms for virtual memory, cache or TLB using adaptive policy

Definitions

  • the present invention in some embodiments thereof, relates to cache management and, more specifically, but not exclusively, to cache replacement policies.
  • Hardware and software applications may use a cache to improve performance.
  • Page caching for example, is a cache of disk pages kept by the operating system, stored in unused main memory.
  • web caching is a temporary storage of web documents to increase performance.
  • OVS open virtual switch
  • cloud networking uses a caching mechanism in the OS kernel level (the data path) to process incoming traffic faster compared to the user level.
  • OVS open virtual switch
  • cloud networking where compute nodes are deployed massively, inefficient local caching might cause bottlenecks in the network.
  • the implemented caching policy therefore becomes crucial. Every cache has a limited capacity and therefore requires replacement of entries when the capacity of the cache is exceeded, otherwise the processing performance benefit provided by the cache is degraded.
  • the caching policy performance is measured by the miss rate, which is defined as the number of times a referenced entry is not found in the cache.
  • the goal of a cache replacement policy is to improve performance by minimizing the miss rate.
  • LRU least recently used
  • LRU Least-Recently Used
  • MRU Most-Recently Used
  • PLRU Pseudo-LRU
  • LRU Low Inter-reference Recency Set
  • RR Random Replacement
  • SLRU Segmented LRU
  • LFU Least-Frequently Used
  • LFU with Dynamic Aging LFU with Dynamic Aging
  • NFU Not Frequently Used
  • ARC Adaptive Replacement Cache
  • CAR Clock with Adaptive Replacement
  • an apparatus for managing a cache storing cached entries comprises: a processor configured to: receive snapshots of the cached entries, compute for each cached entry of the cached entries based on the snapshot of the respective cached entry, the following values: a usage score indicative of the average number of references of the respective cached entry per unit of time, and a span score indicative of the effective lifetime of the respective cached entry, and designate a subset of the cached entries for replacement according to the computed values of the usage score and span score.
  • a method for managing a cache storing cached entries comprises: receiving snapshots of the cached entries, computing for each cached entry of the cached entries based on the snapshot of the respective cached entry, the following values: a usage score indicative of the average number of references of the respective cached entry per unit of time, and a span score indicative of the effective lifetime of the respective cached entry, and designating a subset of the cached entries for replacement according to the computed values of the usage score and span score.
  • the apparatus and/or method provide an improvement in performance of a cache replacement policy in comparison to existing cache replacement policies (e.g., least recently used (LRU)), by reducing the cache miss rate and/or increasing the cache hit rate.
  • LRU-based replacement e.g., implemented by OVS
  • the usage score is used to replace cache entries with low usage while expecting new arbitrary cache entries, which increases the probability that higher usage entries will be stored in the cache.
  • the span score is used to replace cache entries that have already been hit, but are unlikely to be further hit. Long-lived cache entries are prioritized for remaining in the cache entries.
  • the evaluation of the cache entries over a period of time using multiple aggregated snapshots, and the designation of the cache entries for replacement, occurs in parallel and/or independently of cache activity (i.e., reading and writing the cache entries), which improves performance of the cache by reducing or preventing interference with the cache activity.
  • the parallel and/or simultaneous evaluation of the cache entries is in contrast to other existing cache replacement policies that perform cache replacement together (i.e., directly dependent on) with evaluation of the cache entries.
  • the cache entries are designated for replacement according to a combination based on time (i.e., span score) and on usage (i.e., usage score), which improves performance over replacement according to only time based factors or only usage based factors.
  • the apparatus and/or method are agnostic to the caching domain, and may be applied to different utilities, applications, and use cases that are implemented using a cache.
  • the processor is further configured to or the method further comprises: computing for each cached entry of the cached entries based on the snapshot of the respective cached entry, a dirtiness score indicative of whether the respective cached entry is being processed, and wherein the designation of the subset is further performed according to the computed value of the dirtiness score.
  • the dirtiness score handles prescaling. Latency is reduced by postponing replacement of cache entries currently being processed to a future time when the cache entry is not being processed.
  • the processor is further configured to or the method further comprises sorting the cached entries according to at least the computed values of the usage score, and the span score, and designate the subset of the cached entries according to the sorting based on a replacement score requirement.
  • the scoring is designed for flexibility, and is not based on a specific underlying use, application, case, or scenario.
  • the sorting of the scores may be performed by increasing value or decreasing value, depending on the implementation.
  • the snapshots of the cached entries are obtained at a first predefined rate, and aggregation is performed using the snapshots obtained during a predefined sliding window.
  • the snapshots may be taken at a predefined rate that is independent of other events (e.g., reads/writes to the cache), which improves computation of the scores in real time.
  • the size of the subset of the cached items designated for replacement is according to a predefined score intensity that denotes a maximum percentage of cache entries designated for replacement.
  • the replacements are performed according to the maximum percentage of cache entries that may be replaced, which improves performance of the cache in comparison to other methods that decide whether to replace each cache entry independently of other entries.
  • the subset of the cached items designated for replacement are evicted from the cache at a second predefined rate.
  • the evictions may be performed at a predefined rate that is independent of other events (e.g., reads/writes to the cache), which improves the real time eviction of cache entries.
  • the processor is further configured to or the method further comprises computing a score vector based on at least the computed values of the usage score, and span score, and wherein the subset of the cached entries is designated for replacement according to the computed score vector.
  • the score vector which is based on the usage score and the span score, may improve computations, for example, in comparison to independently considering each of the usage score and span score.
  • each cache entry stores an indication of an item with references.
  • the apparatus improves the performance of a network using the cache entries to store flows of packets and/or (other items).
  • At least some of the items with references include mice items of high rate and high entropy.
  • the apparatus improves performance of the cache for caching mice flows, in comparison to existing cache replacement policies that create bottlenecks, resulting in performance degradation. For example, incoming packets (and/or other items) may not be processed in adequate time, increasing the latency and/or the loss rate of the packets (and/or other items).
  • the values of the usage score is computed as the average number of references per item associated with each cache entry, and the values of the span score is computed as the effective lifetime of the item associated with each cache entry.
  • mice flows which include short lived flows with a small number of items (e.g., packets), lead to inefficiency of the cache, and are therefore designated for replacement.
  • items e.g., packets
  • each cache entry stores an indication of a switching flow item of an open virtual switch (OVS) implemented in at least one of a computing cloud and a cloud networking environment.
  • OVS open virtual switch
  • the apparatus improves performance of a cache used by an OVS deployed in cloud network computing hosts (e.g., in a cloud computing and/or cloud networking environment).
  • the performance of each OVS in the network is critical to ensure the quality of service (QoS) of the network.
  • QoS quality of service
  • the improvement in performance of the OVS cache by the apparatus is in comparison to existing OVS cache replacement policies that become bottlenecks, resulting in performance degradation.
  • the OVS cache management is not necessarily sufficient to treat all the incoming packets in adequate time, increasing the latency and/or the loss rate of the packets.
  • the performance of the OVS is improved by improving the performance of the cache, for example, in comparison to other attempts to improve the performance of the OVS by other approaches.
  • data plane development kit DPDK
  • code optimizations code optimizations
  • mega- flows priority sorting
  • staged lookup staged lookup
  • longest prefix match are examples of existing methods that were implemented in order to improve the OVS performance along different versions.
  • the apparatus further comprising a cache monitoring device that captures snapshots of each of the cached entries, or the apparatus further comprises capturing snapshots of each of the cached entries, and wherein the processor is further configured to or the method further comprises performing aggregation of the snapshots.
  • the cache monitoring device obtains snapshots of the cached entries and performs the aggregation without significantly affecting performance of the cache.
  • all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention pertains.
  • methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the invention, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control.
  • the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.
  • FIG. 1 is a flowchart of a method that designates cache entries for eviction based on a usage score and a span score, in accordance with some embodiments of the present invention
  • FIG. 2 is a block diagram of components of a system that includes a computing device that manages cache entries stored in a cache used by a computing system, by designating cache entries for eviction based on a usage score and a span score, in accordance with some embodiments of the present invention
  • FIG. 3 is a graph depicting computation of the usage score, in accordance with some embodiments of the present invention.
  • FIG. 4 is a graph depicting computation of the span score, in accordance with some embodiments of the present invention.
  • FIG. 5 is a block diagram depicting components of a system based on the method described with reference to FIG. 1, and/or implemented by the system described with reference to FIG. 2, in accordance with some embodiments of the present invention
  • FIG. 6 is a dataflow diagram depicting dataflow within a system based on the method described with reference to FIG. 1, and/or implemented by the system described with reference to FIG. 2, in accordance with some embodiments of the present invention
  • FIG. 7 is a dataflow diagram depicting the process of designating cached entries for eviction according to the usage score and the span score, in accordance with some
  • FIG. 8 is a schematic of a set-up of a test environment used to experimentally measure performance of a cache using the apparatus and/or systems and/or methods described herein, in accordance with some embodiments of the present invention
  • FIG. 9 is a table summarizing the experimental results for the experiment performed using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention.
  • FIG. 10 is a graph depicting miss rate as a function of the number of targets per virtual machine for the experiment performed using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention.
  • FIG. 11 is a graph depicting latency as a function of the number of targets per virtual machine for the experiment performed using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention.
  • the present invention in some embodiments thereof, relates to cache management and, more specifically, but not exclusively, to cache replacement policies.
  • An aspect of some embodiments of the present invention relates to an apparatus and/or a method (e.g., code instructions stored in a data storage device executed by one or more processors) that designate a subset of cached entries stored in a cache for replacement according to values of a usage score and a span score computed for each cached entry.
  • the usage score is indicative of the average number of references of the respective cached entry per unit of time.
  • the span score is indicative of the effective lifetime of the respective cached entry.
  • the designation of the subset of cached entries for replacement is performed according to a dirtiness score indicative of whether the respective cached entry is being processed.
  • the apparatus and/or method provide an improvement in performance of a cache replacement policy in comparison to existing cache replacement policies (e.g., least recently used (LRU)), by reducing the cache miss rate and/or increasing the cache hit rate.
  • LRU-based replacement e.g., implemented by OVS
  • the usage score is used to replace cache entries with low usage while expecting new arbitrary cache entries, which increases the probability that higher usage entries will be stored in the cache.
  • the span score is used to replace cache entries that have already been hit, but are unlikely to be further hit. Long-lived cache entries are prioritized for remaining in the cache entries.
  • the evaluation of the cache entries over a period of time using multiple aggregated snapshots, and the designation of the cache entries for replacement, occurs in parallel and/or independently of cache activity (i.e., reading and writing the cache entries), which improves performance of the cache by reducing or preventing interference with the cache activity.
  • the parallel and/or simultaneous evaluation of the cache entries is in contrast to other existing cache replacement policies that perform cache replacement together (i.e., directly dependent on) with evaluation of the cache entries.
  • the cache entries are designated for replacement according to a combination based on time (i.e., span score) and on usage (i.e., usage score), which improves performance over replacement according to only time based factors or only usage based factors.
  • the apparatus and/or method is agnostic to the caching domain, and may be applied to different utilities, applications, and use cases that are implemented using a cache.
  • the present invention may be a system, a method, and/or a computer program product.
  • the computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.
  • the computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device.
  • the computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing.
  • Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network.
  • a network for example, the Internet, a local area network, a wide area network and/or a wireless network.
  • the computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server.
  • the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).
  • LAN local area network
  • WAN wide area network
  • Internet Service Provider for example, AT&T, MCI, Sprint, EarthLink, MSN, GTE, etc.
  • electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention.
  • FPGA field-programmable gate arrays
  • PLA programmable logic arrays
  • each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s).
  • the functions noted in the block may occur out of the order noted in the figures.
  • two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved.
  • eviction, replacement, and deletion are used interchangeably with reference to cache entries that are deleted, evicted, and/or replaced with new cache entries.
  • FIG. 1 is a flowchart of a method that designates cache entries for eviction based on a usage score and a span score, in accordance with some embodiments of the present invention.
  • Blocks 102-108 refer to the process of computing the usage score and span score.
  • Blocks 110-114 refer to the process of designating cache entries for eviction based on the computed usage score and span score.
  • FIG. 2 is a block diagram of components of a system 200 that includes a computing device 202 that manages cache entries stored in a cache 204 used by a computing system 206, by designating cache entries for eviction based on a usage score and a span score, in accordance with some embodiments of the present invention.
  • Computing system 206 may be implemented as, for example, one of more of: a computing cloud, a cloud network, a computer network, a virtual machine(s) (e.g., hypervisor, virtual server), a switch, an OVS, a virtual network, a router, a virtual router, a single computing device (e.g., client terminal), a group of computing devices arranged in parallel, a network server, a web server, a storage server, a local server, a remote server, a client terminal, a mobile device, a stationary device, a kiosk, a smartphone, a laptop, a tablet computer, a wearable computing device, a glasses computing device, a watch computing device, and a desktop computer.
  • a computing cloud e.g., hypervisor, virtual server
  • a switch e.g., an OVS
  • a virtual network e.g., a virtual network
  • a router e.g., a virtual router
  • a single computing device e.g.
  • Cache 204 is used by computing system 206 to improve performance by storing cache entries.
  • Cache 204 may be integrated within computing system 206, and/or may be implemented as an external storage device.
  • Cache 204 may be implemented as, for example, a random access memory (RAM), read-only memory (ROM), and/or a storage device, for example, non- volatile memory, magnetic media, semiconductor memory devices, hard drive, removable storage, and optical media (e.g., DVD, CD-ROM).
  • RAM random access memory
  • ROM read-only memory
  • storage device for example, non- volatile memory, magnetic media, semiconductor memory devices, hard drive, removable storage, and optical media (e.g., DVD, CD-ROM).
  • Cache 204 may be implemented as, for example, a single level cache, a multi-level cache, and/or one or more levels of a multi-level cache (e.g., a last level cache).
  • Computing device 202 may be implemented as, for example, integrated within cache 204 (e.g., as hardware and/or software installed within cache 204), integrated within computing system 206 (e.g., as hardware and/or software installed within computing system 206), and/or as an external component (e.g., implemented as hardware and/or software) in communication with cache 204.
  • cache 204 e.g., as hardware and/or software installed within cache 204
  • computing system 206 e.g., as hardware and/or software installed within computing system 206
  • an external component e.g., implemented as hardware and/or software
  • Computing device 202 includes one or more processor(s) 208, implemented as for example, central processing unit(s) (CPU), graphics processing unit(s) (GPU), field programmable gate array(s) (FPGA), digital signal processor(s) (DSP), application specific integrated circuit(s) (ASIC), customized circuit(s), processors for interfacing with other units, and/or specialized hardware accelerators.
  • processor(s) 208 may be implemented as a single processor, a multi-core processor, and/or a cluster of processors arranged for parallel processing (which may include homogenous and/or heterogeneous processor architectures). It is noted that processor(s) 208 may be designed to implement in hardware one or more features stored as code instructions (e.g., described herein as stored in memory 210 and/or data storage 212).
  • Memory 210 stores code instructions implementable by processor(s) 208, for example, a random access memory (RAM), read-only memory (ROM), and/or a storage device, for example, non- volatile memory, magnetic media, semiconductor memory devices, hard drive, removable storage, and optical media (e.g., DVD, CD-ROM).
  • Memory 206 may store code instructions that when executed by processor(s) 208, implement one or more acts of the method described with reference to FIG. 1.
  • Computing device 202 may include a data storage device 212 for storing data.
  • Data storage device 212 may be implemented as, for example, a memory, a local hard-drive, a removable storage unit, an optical disk, a storage device, and/or as a remote server and/or computing cloud (e.g., accessed using a network connection). It is noted that code instructions executable by processor(s) 208 may be stored in data storage device 212, for example, with executing portions loaded into memory 210 for execution by processor(s) 208.
  • Data storage device 212 may include one or more data repositories, for example, snapshots of cache entries obtained from cache 204.
  • a cache monitoring device 214 monitors cache entries stored in cache 204.
  • Cache monitoring device 214 acquires snapshots of the cache entries, for example, as memory dumps, and provides the snapshots to computing device 202.
  • Cache monitoring device 214 may perform aggregation of the snapshots (as described herein), and/or provide the snapshots for aggregation by a different component (e.g., computing device 202).
  • Cache monitoring device 214 may be implemented as software instructions, and/or as a hardware component, which may be an independent component, integrated within cache 204, and/or integrated within computing device 202, and/or integrated within computing system 206.
  • a cache interface 216 designates cache entries stored in cache 204 for eviction (selected by computing device 202 as described herein), for example, by marking the designated cache entries, such as by setting one or more bits of the cache indicative that the cache entry may be overwritten. Alternatively or additionally, cache interface 216 actively deletes the designated cache entries from cache 204. Cache interface 216 may be
  • Computing device 202 may be in communication with a user interface 218 that presents data to a user and/or includes a mechanism for entry of data, for example, one or more of: a touch-screen, a display, a keyboard, a mouse, voice activated software, and a microphone.
  • User interfaces 218 may be used to manually or automatically configure, for example, the association between the computed span score and usage score, and the cache entries designated for eviction.
  • the term automatically configure means an external optimizer and/or machine learning program that recommends configuration based on historical data, either dynamically or each setup, subject to the specific environment in which the code executes.
  • snapshots of the cached entries stored in cache 204 are received by computing device 202 for processing by processor(s) 208.
  • the snapshots of the cached entries may be captured by cache monitoring device 214.
  • the cache monitoring device obtains snapshots of the cached entries and performs the aggregation without significantly affecting performance of the cache.
  • the snapshots of the cached entries are obtained at a predefined rate.
  • the snapshots may be taken at a predefined rate that is independent of other events (e.g., reads/writes to the cache), which improves computation of the scores in real time.
  • the snapshots are aggregated.
  • the aggregations of the snapshots of the cached entries may be performed by processor(s) 208, by cache monitoring device 214, and/or by another computing device.
  • the aggregation is performed using the snapshots obtained during a predefined sliding window.
  • the aggregation may include processing of cache related data, grouped by flow id (ufid) into a data structure used to compute the usage score and/or span score and/or dirtiness score, each by its corresponding definition, together with the common flow's attributes. For example, obtaining the src/dst IP, src/dst MAC, src/dst port, action, packets, bytes, usage score, span score, dirtiness score during the predefined sliding window.
  • Each cache entry stores an indication of an item with references.
  • Exemplary items with references include a flow of packets through a network.
  • the apparatus and/or method improve the performance of the network using the cache entries to store flows of packets.
  • At least some of the items with references may include mice items of high rate and high entropy, for example, flow of packets defined as mice flows of high rate and high entropy traffic.
  • the apparatus and/or method improve performance of the cache for caching mice flows, in comparison to existing cache replacement policies that create bottlenecks, resulting in performance degradation. For example, incoming packets (and/or other items) may not be processed in adequate time, increasing the latency and/or the loss rate of the packets (and/or other items).
  • each cache entry stores an indication of a switching flow item of an open virtual switch (OVS) 206 implemented in a computing cloud and/or a cloud networking environment.
  • OVS open virtual switch
  • the apparatus and/or method improve performance of a cache used by an OVS deployed in cloud network computing hosts (e.g., in a cloud computing and/or cloud networking environment).
  • the performance of each OVS in the network is critical to ensure the quality of service (QoS) of the network.
  • QoS quality of service
  • the improvement in performance of the OVS cache by the apparatus is in comparison to existing OVS cache replacement policies that become bottlenecks, resulting in performance degradation. For example, in cases of port scans, P2P rendezvous servers, and/or network monitoring applications, the OVS cache management is not necessarily sufficient to treat all the incoming packets in adequate time, increasing the latency and/or the loss rate of the packets.
  • the performance of the OVS is improved by improving the performance of the cache, for example, in comparison to other attempts to improve the performance of the OVS by other approaches.
  • data plane development kit DPDK
  • code optimizations code optimizations
  • mega- flows priority sorting
  • staged lookup staged lookup
  • longest prefix match are examples of existing methods that were implemented in order to improve the OVS performance along different versions.
  • a usage score indicative of the average number of references of the respective cached entry per unit of time is computed.
  • Each reference denotes a read access to the cached entry.
  • the unit of time may correspond to the caching duration of the flow within the sliding window used to perform the aggregation of the snapshots.
  • the value of the usage score may be computed as the average number of references per item associated with each cache entry, for example, the average number of packets per flow.
  • the value of the span score may be computed as the effective lifetime of the item associated with each cache entry, for example, the effective lifetime of the flow.
  • the average number of references (e.g., packets) per flow and/or the lifetime of the flow are used to differentiate between mice flows and elephant flows. Mice flows which include short lived flows with a small number of references (e.g., packets), lead to inefficiency of the cache, and are therefore designated for replacement.
  • the scoring described herein is designed for flexibility, and is not necessarily based on a specific underlying use, application, case, or scenario.
  • the usage score is mathematically represented by the following equation: ⁇
  • T denotes time in which the item was observed in the cache
  • Ri(t) denotes reference to an item at time t (e.g., number of packets observed in a snapshot).
  • FIG. 3 is a graph depicting computation of the usage score based on the above mathematical equation, in accordance with some embodiments of the present invention.
  • X-axis 302 denotes time t.
  • Y-axis 304 denotes a number of references.
  • Curve 306 denotes current references as a function of time, Ri(t).
  • Curve 308 denotes the accumulated number of references.
  • T denotes the time range for which the usage score is computed.
  • a span score indicative of the effective lifetime of the respective cached entry is computed.
  • the lifetime of the cached entry may be defined as the time from which new item (e.g., flow) is cached to the time during which the item is replaced.
  • the effective lifetime may be computed over multiple snapshots within the sliding window. The effective lifetime may be computed during the sliding window, for example, to identify cached entries that have a lifetime shorter than time T.
  • FIG. 4 is a graph depicting computation of the span score based on the above mathematical relationship, in accordance with some embodiments of the present invention.
  • X-axis 402 denotes time T.
  • Y-axis 404 denotes a number of references.
  • Curve 406 denotes current references as a function of time.
  • the effective lifetime of the cached entry is represented by portion 408.
  • S spn 410 is defined as the time during which curve 406 reaches X-axis 402, where it remains zero up to time T.
  • Curve 412 denotes the accumulated number of references.
  • S spn is the smallest time for which the usage equals S usg (stops increasing).
  • a score vector is computed based on at least the computed values of the usage score, and span score.
  • the score vector may include the computed dirtiness score, as described with reference to 108.
  • the score vector may include weights assigned to each of the usage score and/or span score and/or dirtiness score.
  • the score vector may be processed in two dimensions (when including the usage score and span score), or three dimensions (when further including the dirtiness score).
  • the score vector may be evaluated to arrive at a single dimension, for example, a numerical value computed based on a function applied to the usage score and span score.
  • the subset of the cached entries is designated for replacement according to the computed score vector, as described with reference to 112.
  • the score vector which is based on the usage score and the span score, may improve computations, for example, in comparison to independently considering each of the usage score and span score.
  • a dirtiness score indicative of whether the respective cached entry is being processed is computed for the cached entries based on the snapshot of the respective cached entry.
  • the dirtiness score handles prescaling. Latency is reduced by postponing replacement of cache entries currently being processed to a future time when the cache entry is not being processed.
  • the dirtiness score may be computed as follows: if the cached entry is being processed, then the dirtiness score is based on (e.g., equal to) the average time it takes to process the respective cached entry minus the time since processing started, otherwise the value of the dirtiness score is zero.
  • the cached entries may in turn be sorted according to each score S x of the score vector S and a subset determined by the score intensity I x will be designated. Dirtiness score may be included in the score vector.
  • the sorting may be performed per computed score, of the score vector.
  • the sorting of the scores may be performed by increasing value or decreasing value, depending on the implementation. For example, relatively higher scores may be indicative of cache entries that are actively used and have long life spans, and therefore should not be replaced. Lower scores may be indicative of cache entries that are rarely used and have short life spans, and therefore should be replaced.
  • a union of the cached designated entries may be replaced according to the computed values of the usage score and span score, and optionally the dirtiness score.
  • the designation may be performed according to the vector score.
  • the designation of the subset of the cached entries is performed according to the sorted cached entries based on a replacement score requirement.
  • the replacement score requirement may define a threshold, where cached entries having score values above (or below) the replacement score requirement are replaced, and cached entries having score values below (or above) the replacement score requirement are retained.
  • the replacement score requirement may include a predefined number or percentage of cached entries that are to be replaced, for example, 10000 entries, or 10% of all entries.
  • the size of the subset of the cached items designated for replacement may be defined according to a predefined score intensity that denotes a maximum percentage of cache entries designated for replacement, for example, no more than 10% of all cached entries.
  • the predefined score intensity may include a predefined maximum number of cached entries designated for replacement, for example, no more than 10000 cached entries may be replaced. For example, the top 10000 or the top 10% of cached entries (based on the sorting) having the highest (or lowest) scores are designated.
  • Designating cached entries for replacement according to the maximum percentage (or predefined number) of cache entries that may be replaced improves performance of the cache in comparison to other methods that decide whether to replace each cache entry independently of other entries.
  • the union of the cached items designated for replacement are evicted from the cache.
  • the eviction may be performed at a predefined rate that is independent of other events (e.g., reads/writes to the cache), which improves the real time eviction of cache entries.
  • blocks 102-108 are iterated, dynamically updating the score vector of each entry according to the scores definition described herein.
  • blocks 110-114 are iterated, dynamically replacing cached entries according to the scores described herein, which improves performance of the cache as described herein.
  • the acts of the method described with reference to FIG. 1 may be mathematically represented as follows:
  • Cw denotes the number of instances from which aggregation is performed to obtain the scores.
  • ⁇ denotes the time to replacement
  • Score computation phase (occurs every B seconds) includes aggregating snapshots of cached entries over C w events, and computing S for each cached entry.
  • FIG. 5 is a block diagram depicting components of a system 500 based on the method described with reference to FIG. 1, and/or implemented by system 200 described with reference to FIG. 2, in accordance with some embodiments of the present invention.
  • a cache monitoring device 514 (corresponding to cache monitoring device 214 described with reference to FIG. 2) transmits CacheStatst 550 (i.e., snapshots of cached entries) obtained from a cache (e.g., cache 204 described with reference to FIG. 2).
  • CacheStatst 550 are provided to computing device 502 (corresponding to computing device 202 described with reference to FIG. 2) for computation of the usage score and span score used for designation of the cache entries for eviction, as described herein.
  • Computing device 502 includes the following modules, which may be implemented as code instructions stored in a memory executed by a processor(s) of computing device 502, and/or implemented as hardware:
  • Scoring 554 calculates the scores of each cache entry (i.e., usage, span, and/or dirtiness), as described herein.
  • * Prioritizing 556 sorts the cache entries according to the computed scores, as described herein.
  • Selection 558 designates (e.g., marks) cache entries, up to the predetermined score intensity as candidates for replacement according to the sorting.
  • FIG. 6 is a dataflow diagram depicting dataflow within a system 600 based on the method described with reference to FIG. 1, and/or implemented by system 200 described with reference to FIG. 2, in accordance with some embodiments of the present invention.
  • a cache monitoring system 614 (corresponding to cache monitoring device 214 described with reference to FIG. 2) transmits CacheStatst 650 (i.e., snapshots) obtained from a cache (e.g., cache 204 described with reference to FIG. 2).
  • CacheStatst 650 are provided to computing device 602 (corresponding to computing device 202 described with reference to FIG. 2) for designation of the cache entries for eviction, as described herein.
  • a collection of flow dump results (denoted as ⁇ f tl , ft 2 > — > ft m ⁇ ) obtained at times ⁇ t-L, t 2 , ... , t m ⁇ is received from monitoring system 614, where f t is the flow dump result at time t. Snapshots of the cache entries are taken from the cache at a constant rate.
  • an aggregation of the monitored flow dump results is performed every ⁇ seconds.
  • the aggregated flow (denoted F) is provided. Each aggregated item F is characterized by the computed scores.
  • monitoring system 614 obtains a snapshot of the cache.
  • the cached entries are selected.
  • the cache entries undergo block 664 and block 666 as described next.
  • the cached entries are sorted according to the current score (ascending or descending, depending on the score sentiment).
  • cached entries are marked (i.e., designated) for replacement according to a ratio of Ix denoting the score intensity of the maximum percentage (or number of) cached entries that may be designated for replacement.
  • the marked cache entries are evicted from the cache.
  • the cache entries may be removed from the cache by deleting the union of the marked flows.
  • FIG. 7 is a dataflow diagram depicting cached entries designated for eviction according to the usage score and the span score, based on the method described with reference to FIG. 1 , and/or implemented by system 200 described with reference to FIG. 2, in accordance with some embodiments of the present invention.
  • the score intensity denoting the maximum percentage of cached entries designated for replacement is defined for the usage score and for the span score. For example, when cached entries store indications of multiple flows of packets, the intensity denoting the maximum percentage of cached entries designated for replacement is defined for the usage score and for the span score.
  • Block 702 denotes designation of cached entries for replacement according to the score intensity defined for the usage score.
  • Block 704 denotes sorting of the cached entries according to the span score, and block 706 denotes designation of the cached entries for replacement according to the score intensity defined for the span score. It is noted that sorting may be performed based on one of the elements in the score vector, including the dirtiness score, where the score intensity is according to the intensity vector including the dirtiness intensity.
  • FIG. 8 is a schematic of a set-up of a test environment used to experimentally measure performance of a cache using the apparatus and/or systems and/or methods described herein, in accordance with some embodiments of the present invention.
  • the testing was performed on a DevStack (DragonFlow, a distributed software defined networking (SDN) controller supporting distributed switching and routing) - single host.
  • the cache being evaluated was used by OVS 2.5.
  • the cache flow size limit was set to 1000 (the default is 200K).
  • the network topology included a total of 50 virtual machines (VMs) in 3 networks.
  • VMs virtual machines
  • NetPerf TCP CRR open multiple TCP connections
  • NetPerf is a benchmark that is used to measure the performance of different types of networks.
  • FIG. 9 is a table summarizing the experimental results for 30 targets per virtual machine, for the experiment performed using the systems and/or methods described herein, using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention.
  • the experimental results show that the miss rate of incoming packets into the data path looking for matching cache flows when the cache is flooded due to high rate and high entropy traffic, where the cache is used by an OVS, is reduced relative to the existing LRU cache replacement policy.
  • FIG. 10 is a graph depicting miss rate as a function of the number of targets per virtual machine for the experiment performed using the systems and/or methods described herein, using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention.
  • the input parameters for the algorithm are encoded to a string as follows: Three graphs are shown in FIG 10, "baseline”, “algo 0.5_60_60_0_10000_2_” and “algo minima”.
  • baseline refers to a run without eviction; that is, 0%> intensity to each of the scores.
  • the legend "algo minima” refers to a collection of all setups that yielded the minimum miss rate each, given the number of target per VM. Each point in the "algo minima” curve is a result of a single setup of the input parameters for the algorithm, and thus is shown along the curve as “Params". In addition to the "Params" notation, the "Distance” specify the distance of the curve that would be drawn from that setup along the x- axis for variable number of targets per VM.
  • FIG. 11 is a graph depicting latency as a function of the number of targets per virtual machine for the experiment performed using the systems and/or methods described herein, using the set-up depicted in FIG. 8, in accordance with some embodiments of the present invention. Based on the graph, the following conclusions may be reached: for 25-35 VMs per host use a usage score intensity of 40%, for over 35 VMs per host use a LRU score intensity of 40%.
  • composition or method may include additional ingredients and/or steps, but only if the additional ingredients and/or steps do not materially alter the basic and novel characteristics of the claimed composition or method.
  • the singular form “a”, “an” and “the” include plural references unless the context clearly dictates otherwise.
  • the term “a compound” or “at least one compound” may include a plurality of compounds, including mixtures thereof.
  • the word “exemplary” is used herein to mean “serving as an example, instance or illustration”. Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments.
  • the word “optionally” is used herein to mean “is provided in some embodiments and not provided in other embodiments”. Any particular embodiment of the invention may include a plurality of “optional” features unless such features conflict.
  • range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the invention. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1, 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

L'invention concerne un appareil destiné à gérer une mémoire cache mémorisant des entrées mises en mémoire cache, l'appareil consistant : en un processeur configuré pour : recevoir des instantanés des entrées mises en mémoire cache ; calculer pour chaque entrée mise en mémoire cache des entrées mises en mémoire cache en fonction de l'instantané de l'entrée mise en mémoire cache respective, en les valeurs suivantes : un score d'utilisation indiquant le nombre moyen de références de l'entrée mise en mémoire cache respective par unité de temps et un score d'étendue indiquant la durée de vie effective de l'entrée mise en mémoire cache respective ; et désigner un sous-ensemble des entrées mises en mémoire cache destinées au remplacement selon les valeurs calculées du score d'utilisation et du score d'étendue.
PCT/EP2017/052607 2017-02-07 2017-02-07 Systèmes et procédés destinés au remplacement de mémoire cache Ceased WO2018145725A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CN201780085816.0A CN110249318A (zh) 2017-02-07 2017-02-07 高速缓存替换系统和方法
PCT/EP2017/052607 WO2018145725A1 (fr) 2017-02-07 2017-02-07 Systèmes et procédés destinés au remplacement de mémoire cache

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/EP2017/052607 WO2018145725A1 (fr) 2017-02-07 2017-02-07 Systèmes et procédés destinés au remplacement de mémoire cache

Publications (1)

Publication Number Publication Date
WO2018145725A1 true WO2018145725A1 (fr) 2018-08-16

Family

ID=58009807

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2017/052607 Ceased WO2018145725A1 (fr) 2017-02-07 2017-02-07 Systèmes et procédés destinés au remplacement de mémoire cache

Country Status (2)

Country Link
CN (1) CN110249318A (fr)
WO (1) WO2018145725A1 (fr)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11797379B2 (en) 2022-02-04 2023-10-24 Western Digital Technologies, Inc. Error detection and data recovery for distributed cache
US11899585B2 (en) 2021-12-24 2024-02-13 Western Digital Technologies, Inc. In-kernel caching for distributed cache
US11934663B2 (en) 2022-01-10 2024-03-19 Western Digital Technologies, Inc. Computational acceleration for distributed cache
US12182022B2 (en) 2022-05-10 2024-12-31 Western Digital Tehcnologies, Inc. In-kernel cache request queuing for distributed cache
US12379951B2 (en) 2022-06-27 2025-08-05 Western Digital Technologies, Inc. Memory coherence in virtualized environments
US12386648B2 (en) 2022-06-09 2025-08-12 Western Digital Technologies, Inc. Resource allocation in virtualized environments
US12452189B2 (en) 2022-06-01 2025-10-21 Western Digital Technologies, Inc. Context-aware NVMe processing in virtualized environments

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6523102B1 (en) * 2000-04-14 2003-02-18 Interactive Silicon, Inc. Parallel compression/decompression system and method for implementation of in-memory compressed cache improving storage density and access speed for industry standard memory subsystems and in-line memory modules
US20060136673A1 (en) * 2004-12-20 2006-06-22 Microsoft Corporation Unused item management
US20140019677A1 (en) * 2012-07-16 2014-01-16 Jichuan Chang Storing data in presistent hybrid memory
US20140089595A1 (en) * 2011-12-23 2014-03-27 Nevin Hyuseinova Utility and lifetime based cache replacement policy
US20140136792A1 (en) * 2012-11-12 2014-05-15 Eitan Frachtenberg Predictive cache replacement

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101236530B (zh) * 2008-01-30 2010-09-01 清华大学 高速缓存替换策略的动态选择方法
CN101534204B (zh) * 2008-03-10 2011-08-31 中国网通集团宽带业务应用国家工程实验室有限公司 流媒体信息分发系统和方法及客户端
CN101945129A (zh) * 2010-09-10 2011-01-12 北京易视腾科技有限公司 P2p流媒体直播的低延时传输方法及系统
US9177072B2 (en) * 2013-03-14 2015-11-03 Facebook, Inc. Social cache
CN104090852B (zh) * 2014-07-03 2017-04-05 华为技术有限公司 管理混合缓存的方法及设备
CN104794064B (zh) * 2015-04-21 2017-09-29 华中科技大学 一种基于区域热度的缓存管理方法

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6523102B1 (en) * 2000-04-14 2003-02-18 Interactive Silicon, Inc. Parallel compression/decompression system and method for implementation of in-memory compressed cache improving storage density and access speed for industry standard memory subsystems and in-line memory modules
US20060136673A1 (en) * 2004-12-20 2006-06-22 Microsoft Corporation Unused item management
US20140089595A1 (en) * 2011-12-23 2014-03-27 Nevin Hyuseinova Utility and lifetime based cache replacement policy
US20140019677A1 (en) * 2012-07-16 2014-01-16 Jichuan Chang Storing data in presistent hybrid memory
US20140136792A1 (en) * 2012-11-12 2014-05-15 Eitan Frachtenberg Predictive cache replacement

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
ANILKUMAR VISHNOI ET AL: "Effective switch memory management in OpenFlow networks", DISTRIBUTED EVENT-BASED SYSTEMS, ACM, 2 PENN PLAZA, SUITE 701 NEW YORK NY 10121-0701 USA, 26 May 2014 (2014-05-26), pages 177 - 188, XP058050056, ISBN: 978-1-4503-2737-4, DOI: 10.1145/2611286.2611301 *

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11899585B2 (en) 2021-12-24 2024-02-13 Western Digital Technologies, Inc. In-kernel caching for distributed cache
US11934663B2 (en) 2022-01-10 2024-03-19 Western Digital Technologies, Inc. Computational acceleration for distributed cache
US11797379B2 (en) 2022-02-04 2023-10-24 Western Digital Technologies, Inc. Error detection and data recovery for distributed cache
US12182022B2 (en) 2022-05-10 2024-12-31 Western Digital Tehcnologies, Inc. In-kernel cache request queuing for distributed cache
US12452189B2 (en) 2022-06-01 2025-10-21 Western Digital Technologies, Inc. Context-aware NVMe processing in virtualized environments
US12386648B2 (en) 2022-06-09 2025-08-12 Western Digital Technologies, Inc. Resource allocation in virtualized environments
US12379951B2 (en) 2022-06-27 2025-08-05 Western Digital Technologies, Inc. Memory coherence in virtualized environments

Also Published As

Publication number Publication date
CN110249318A (zh) 2019-09-17

Similar Documents

Publication Publication Date Title
WO2018145725A1 (fr) Systèmes et procédés destinés au remplacement de mémoire cache
US11113192B2 (en) Method and apparatus for dynamically adapting cache size based on estimated cache performance
US11194725B2 (en) Method and apparatus for adjusting cache prefetch policies based on predicted cache pollution from dynamically evolving workloads
US8688915B2 (en) Weighted history allocation predictor algorithm in a hybrid cache
US8788757B2 (en) Dynamic inclusive policy in a hybrid cache hierarchy using hit rate
US10466964B2 (en) Engine architecture for processing finite automata
Basat et al. Optimal elephant flow detection
US8843707B2 (en) Dynamic inclusive policy in a hybrid cache hierarchy using bandwidth
US8965819B2 (en) System and method for effective caching using neural networks
US8271729B2 (en) Read and write aware cache storing cache lines in a read-often portion and a write-often portion
US8250306B2 (en) Method for improving frequency-based caching algorithms by maintaining a stable history of evicted items
US9477601B2 (en) Apparatus and method for determining a sector division ratio of a shared cache memory
US20160255169A1 (en) Method and system for smart object eviction for proxy cache
US9779031B2 (en) Caching policies for selection and replacement of objects
CN109032964A (zh) 缓存替换方法及其装置、异构多核系统
KR102860320B1 (ko) 스토리지 리소스의 파티션 관리를 위한 시스템, 방법, 및 장치
US20160335177A1 (en) Cache Management Method and Apparatus
US9940060B1 (en) Memory use and eviction in a deduplication storage system
WO2017117734A1 (fr) Procédé de gestion d'antémémoire, contrôleur d'antémémoire et système informatique
US9372810B2 (en) Collaborative caching
US10904353B2 (en) Trending topic driven cache eviction management
WO2017069907A1 (fr) Système et procédé associés à une mémoire cache partagée à partitionnement adaptatif
US20140215156A1 (en) Prioritized dual caching method and apparatus
US20170168944A1 (en) Block cache eviction
US10185666B2 (en) Item-wise simulation in a block cache where data eviction places data into comparable score in comparable section in the block cache

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 17704213

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 17704213

Country of ref document: EP

Kind code of ref document: A1