Dynamic Block-Level Indexing for Cache with Overflow

Patent metadata

Field	Value
Publication number	US-2017308473-A1
Application number	US-201615136253-A
Country	US
Kind code	A1
Filing date	Apr 22, 2016
Priority date	Apr 22, 2016
Publication date	Oct 26, 2017
Grant date	—

Abstract

Methods, systems, computer-readable media, and apparatuses may provide management of virtual memory. For instance, aspects described herein relate to dynamic generation of nodes in a binary search tree in response to a write command, with each of its nodes being representative of different memory ranges in the virtual system disk. Each node may be associated with a different record in a global linked list, ordered by offset that includes pointers to locations where blocks are stored in a virtual cache and offsets of locations where blocks are stored in the virtual overflow disk. Aspects described herein relate to reading blocks from a virtual system memory to service a read command without storing the blocks in the virtual cache.

First claim

We claim:

1 . An apparatus comprising:
a processor; and a non-transitory computer-readable medium storing one or more instructions that, when executed by the processor, causes the apparatus to:
generate a virtual session comprising a virtual driver, a virtual cache, a virtual overflow disk, and a virtual system disk;
receive, by the virtual driver from an input/output request issuer, a write command comprising an offset and a length, the offset being relative to the virtual system disk;
calculate, by the virtual driver, a requested range based on the offset and the length;
in response to determining that an overflow condition for the virtual cache has been satisfied,
transfer one or more blocks from the virtual cache to the virtual overflow disk;
determine whether any of a plurality of nodes of a tree have a range that at least partially overlaps the requested range; and
in response to determining that none of the plurality of nodes have a range that at least partially overlaps the requested range, generate a new node for the tree having a range that at least overlaps a portion of the requested range.

2 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
write, to the virtual cache, a block associated with the portion of the requested range; and generate a record in a global linked list for the new node, the record comprising a pointer to a location of the block in the virtual cache.

3 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
in response to determining that a node of the tree overlaps the requested range,
retrieve a record corresponding to the node from the global linked list;
obtain a pointer to a location in the virtual cache from the record;
write, to the location in the virtual cache, a block associated with a portion of the requested range that is overlapped by the range of the node.

4 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
update an offset index associated with the virtual overflow disk for the transferred one or more blocks, the offset index comprising one or more offsets at which the transferred one or more blocks are stored in the virtual overflow disk, respectively.

5 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
select the one or more blocks for transfer from the virtual cache to the virtual overflow disk based on the one or more blocks being least recently used with respect to blocks stored in the virtual cache.

6 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
receive, by the virtual driver from the input/output request issuer, a read command comprising an offset and a length; calculate, by the virtual driver, a different requested range based on the offset and the length included in the read command; and determine whether any of the plurality of nodes of the tree have a range that at least partially overlaps the different requested range.

7 . The apparatus of claim 6 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
in response to determining that none of the plurality of nodes of the tree have a range that at least partially overlaps the different requested range, retrieve blocks associated with the different requested range from the virtual system disk and place the retrieved blocks in an input/output buffer different from the virtual cache and the virtual overflow disk.

8 . The apparatus of claim 6 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
in response to determining that one or more of the plurality of nodes of the tree have a range that entirely overlaps the different requested range, retrieve blocks associated with the different requested range from the virtual cache or the virtual overflow disk.

9 . The apparatus of claim 6 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
in response to determining that the plurality of nodes of the tree have a collective range that only partially overlaps the different requested range, retrieve a first set of blocks associated with the different requested range from the virtual cache or the virtual overflow disk and a retrieve a second set of blocks associated with the different requested range from the virtual system disk.

10 . The apparatus of claim 1 , wherein the non-transitory computer-readable medium stores one or more additional instructions that, when executed by the processor, causes the apparatus to:
receive a trim message comprising an offset and a range; calculate an identified range based on the offset and the range included in the trim message; determine whether any of the plurality of nodes have a range that at least partially overlaps the identified range; in response to determining that a node of the plurality of nodes has a range that overlaps the identified range,
determine a location of a block associated with the node in the virtual cache or the virtual overflow disk using the global linked list;
delete the block from the virtual cache or the virtual overflow disk; and
delete the node from the tree and a record corresponding to the node from the global linked list.

11 . A system comprising:
a computing device providing a virtual session for another computing device, the virtual session comprising:
a virtual cache;
a virtual overflow disk;
a virtual system disk;
a tree comprising a plurality of nodes, each node having a different range and being associated with a different record in a global linked list, wherein each record comprises a pointer to a location of a block stored in the virtual cache or an offset to a location of a block stored in the virtual overflow disk; and
a virtual driver configured to:
in response to receiving a write command,
determine whether at least one node of the tree has a range that at least partially overlaps a first requested range associated with the write command; and
in response to determining that none of the plurality of nodes of the tree have a range that at least partially overlaps the first requested range, generate a node for the tree that has at least a portion of the first requested range, and a corresponding record in the global linked list, wherein the record comprises a pointer to a location of a block associated with the node in the virtual cache; and

in response to receiving a read command, determine whether one or more nodes of the tree have a range that at least partially overlaps a second requested range associated with the read command.

12 . The system of claim 11 , wherein the virtual session further comprises an input/output buffer different from the virtual cache and the virtual overflow disk, wherein the virtual driver is further configured to:
in response to determining that none of the plurality of nodes of the tree have a range that

Assignees

• Citrix Systems Inc

Inventors

• Bassi Ajai Kumar

Classifications

• G06F3/0665 Primary

  at area level, e.g. provisioning of virtual or logical volumes · CPC title

• G06F12/0824 Primary

  Distributed directories, e.g. linked lists of caches · CPC title

• G06F3/0689

  Disk arrays, e.g. RAID, JBOD · CPC title

• G06F2212/314

  In storage network, e.g. network attached cache · CPC title

• G06F2212/224

  Disk storage · CPC title