Pre-fetching data based on memory usage patterns

{
  "publication_number": "US10228864B1",
  "country": "US",
  "kind": "B1",
  "title": "Pre-fetching data based on memory usage patterns",
  "abstract": "Systems and methods for pre-fetching data based on memory usage patterns. An example method comprises: receiving a first memory access request identifying a first memory block; receiving a second memory access request identifying a second memory block; update a memory access tracking data structure by incrementing a sequence counter corresponding to a memory access sequence that references the first memory block and the second memory block; receive a third memory access request identifying a third memory block; identifying, based on the memory access tracking data structure, a sequence counter having a maximal value among sequence counters associated with memory access sequences that reference the third memory block; and pre-fetching a fourth memory block corresponding to the identified sequence counter.",
  "claims": [
    "1. A method, comprising: receiving, by a processing device, a first memory access request identifying a first memory block by a first memory block identifier; receiving a second memory access request identifying a second memory block by a second memory block identifier; determining a first index by applying a pre-defined transformation to the first memory block identifier; determining a second index by applying the pre-defined transformation to the second memory block identifier; updating a memory access tracking data structure by incrementing a first sequence counter corresponding to a memory access sequence identified by the first index and the second index, wherein the memory access tracking data structure is provided by a rectangular matrix comprising a plurality of sequence counters, wherein a position of the first sequence counter is identified by an intersection of a row of the matrix and a column of the matrix, wherein the row is identified by the first index and the column is identified by the second index; receiving a third memory access request identifying a third memory block; identifying, based on the memory access tracking data structure, a second sequence counter having a maximal value among sequence counters associated with memory access sequences that reference the third memory block; and pre-fetching a fourth memory block corresponding to the second sequence counter.",
    "2. The method of claim 1, wherein the memory access sequence references the second memory block as immediately following the first memory block.",
    "3. The method of claim 1, wherein the memory block is provided by one of: a block of a volatile memory or a block of a non-volatile memory.",
    "4. The method of claim 1, further comprising: responsive to evaluating a triggering condition, updating the memory access tracking data structure by resetting the first sequence counter.",
    "5. The method of claim 1, wherein the first memory block is provided by one of: a memory page, a disk block, or a disk file.",
    "6. The method of claim 1, wherein the first memory block identifier comprises one of: a memory page number, a disk block identifier, or a file name hash.",
    "7. The method of claim 1, further comprising: detecting an operational issue associated with a memory accessing agent by evaluating, using the memory access tracking data structure, a memory usage pattern by the memory accessing agent.",
    "8. A computer system, comprising: a memory; and a processing device coupled to the memory, the processing device configured to: receive a first memory access request identifying a first memory block by a first memory block identifier; receive a second memory access request identifying a second memory block by a second memory block identifier; determine a first index by applying a pre-defined transformation to the first memory block identifier; determine a second index by applying the pre-defined transformation to the second memory block identifier; update a memory access tracking data structure by incrementing a first sequence counter corresponding to a memory access sequence identified by the first index and the second index, wherein the memory access tracking data structure is provided by a rectangular matrix comprising a plurality of sequence counters, wherein a position of the first sequence counter is identified by an intersection of a row of the matrix and a column of the matrix, wherein the row is identified by the first index and the column is identified by the second index; receive a third memory access request identifying a third memory block; identify, based on the memory access tracking data structure, a second sequence counter having a maximal value among sequence counters associated with memory access sequences that reference the third memory block; and pre-fetch a fourth memory block corresponding to the second sequence counter.",
    "9. The computer system of claim 8, wherein the memory block is provided by one of: a block of a volatile memory or a block of a non-volatile memory.",
    "10. The computer system of claim 8, wherein the processing device is further configured to: responsive to evaluating a triggering condition, update the memory access tracking data structure by resetting the first sequence counter.",
    "11. The computer system of claim 8, wherein the first memory block is provided by one of: a memory page, a disk block, or a disk file.",
    "12. The computer system of claim 8, wherein the processing device is further configured to: detect an operational issue associated with a memory accessing agent by evaluating, using the memory access tracking data structure, a memory usage pattern by the memory accessing agent.",
    "13. A non-transitory computer-readable storage medium comprising executable instructions that, when executed by a processing device, cause the processing device to: receive a first memory access request identifying a first memory block by a first memory block identifier; receive a second memory access request identifying a second memory block by a second memory block identifier; determine a first index by applying a pre-defined transformation to the first memory block identifier; determine a second index by applying the pre-defined transformation to the second memory block identifier; update a memory access tracking data structure by incrementing a first sequence counter corresponding to a memory access sequence identified by the first index and the second memory block index, wherein the memory access tracking data structure is provided by a rectangular matrix comprising a plurality of sequence counters, wherein a position of the first sequence counter is identified by an intersection of a row of the matrix and a column of the matrix, wherein the row is identified by the first index and the column is identified by the second index; receive a third memory access request identifying a third memory block; identify, based on the memory access tracking data structure, a second sequence counter having a maximal value among sequence counters associated with memory access sequences that reference the third memory block; and pre-fetch a fourth memory block corresponding to the second sequence counter.",
    "14. The non-transitory computer-readable storage medium of claim 13, further comprising executable instructions causing the processing device to: responsive to evaluating a triggering condition, update the memory access tracking data structure by resetting the first sequence counter."
  ],
  "description_excerpt": "The present disclosure is generally related to computer systems, and is specifically related to systems and methods for pre-fetching data based on memory usage patterns.\n\nVirtualization may be viewed as abstraction of hardware components into logical objects in order to allow a computer system to execute various software modules, for example, multiple operating systems, concurrently and in isolation from other software modules. Virtualization may be achieved by running a software layer, often referred to as a “virtual machine monitor,” above the hardware and below the virtual machines. The virtual machine monitor may abstract the physical layer and present this abstraction to virtual machines to use, by providing interfaces between the underlying hardware and virtual devices of virtual machines. For example, processor virtualization may be implemented by the virtual machine manager scheduling time slots on one or more physical processors for a virtual machine, rather than a virtual machine actually having a dedicated physical processor.\n\nThe present disclosure is illustrated by way of examples, and not by way of limitation, and may be more fully understood with references to the following detailed description when considered in connection with the figures, in which:\n\nFIG. 1 depicts a high-level diagram of an example computer system 100 in which the example methods of pre-fetching data based on memory usage patterns may be implemented, in accordance with one or more aspects of the present disclosure;",
  "cpc": [
    "G06F 12/0862",
    "G06F 2212/1016",
    "G06F 2212/152",
    "G06F 2212/6024",
    "G06F 3/0611",
    "G06F 3/064",
    "G06F 3/0659",
    "G06F 3/0664",
    "G06F 3/0685"
  ],
  "ipc": [
    "G06F 12/00",
    "G06F 13/00",
    "G06F 3/06"
  ],
  "assignees": [
    "Parallels International GmbH"
  ],
  "inventors": [
    "Anton Zelenov",
    "Nikolay Dobrovolskiy",
    "Serguei M. Beloussov"
  ],
  "filing_date": "2016-12-30",
  "publication_date": "2019-03-12",
  "grant_date": "2019-03-12",
  "priority_date": "2016-12-30",
  "application_number": "US-201615395916-A",
  "family_id": "65633143",
  "cited_by_count": 14,
  "citations": [
    "US20030093312A1",
    "US20040064668A1",
    "US20070070764A1",
    "US20100268661A1",
    "US20110219169A1",
    "US20110219222A1",
    "US20160092133A1"
  ]
}