Cache bypass utilizing a binary tree

Patent metadata

Field	Value
Publication number	US-9779026-B2
Application number	US-201614995740-A
Country	US
Kind code	B2
Filing date	Jan 14, 2016
Priority date	Jan 14, 2016
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

A storage command is received at a block level interface from a file system. The storage command is associated with a window of a virtual drive. One of a plurality of binary trees is selected based on the window being associated with the storage command, each of the binary trees being associated with a plurality of windows. If a data storage size of the storage command exceeds a threshold, a window identifier of the window is added to the selected binary tree to indicate the command will bypass a cache and send data of the storage command directly to main data storage.

First claim

What is claimed is:

1. A method comprising:
receiving, at a block level interface, a storage command from a file system, the storage command associated with a window of a virtual drive;
selecting one of a plurality of binary trees based on the window, each of the binary trees associated with a plurality of windows;
if a data storage size of the storage command exceeds a threshold, adding a window identifier of the window to the selected binary tree to indicate the command will bypass a cache and send data of the storage command directly to a main data storage; and
if the data storage size does not exceed the threshold, searching for the window identifier in the selected binary tree and putting the storage command in a wait queue before sending the storage command to a caching library if the window identifier is found.

2. The method of claim 1 , wherein each of the binary trees is associated with respective one of a plurality of spin locks, and wherein adding to the binary tree or searching in the binary tree comprises holding the associated spin lock when the tree is searched and releasing the associated spin lock when the adding or the search is complete.

3. The method of claim 1 , further comprising maintaining a caching bitmap having a bit associated with each of the windows, wherein each bit is set to a predetermined value if a small storage command associated with the window is currently cached, the small storage command having a size below the threshold.

4. The method of claim 1 , wherein the adding of the window identifier to the selected binary tree comprises adding a node to the tree associated with the window if the node does not already exist.

5. The method of claim 4 , wherein if the data storage size of the command exceeds the threshold, performing a callback function upon completion of the command that deletes the node from the tree.

6. The method of claim 1 , wherein the adding of the window identifier to the selected binary tree comprises incrementing a counter to a node of the tree associated with the window if a node already exists.

7. The method of claim 6 , wherein if the data storage size of the command exceeds the threshold, performing a callback function upon completion of the command that decrements the counter.

8. The method of claim 1 , wherein the filesystem comprises a distributed filesystem having a plurality of virtual drives, each of the binary trees associated with windows from two or more of the virtual drives.

9. An apparatus comprising:
an input/output bus configured to communicate with a faster storage tier configured as a cache and slower storage tier configured as a main storage; and
a processor coupled to the input/output bus and configured to:
receive, at a block level interface, a storage command from a file system, the storage command associated with a window of a virtual drive;
select one of a plurality of binary trees based on the window, each of the binary trees associated with a plurality of windows;
if a data storage size of the storage command exceeds a threshold, add a window identifier of the window to the selected binary tree to indicate the command will bypass the cache and send data of the storage command directly to the main data storage; and
if the data storage size does not exceed the threshold, search for the window identifier in the selected binary tree and put the storage command in a wait queue before sending the storage command to a caching library if the window identifier is found.

10. The apparatus of claim 9 , wherein each of the binary trees is associated with respective one of a plurality of spin locks, and wherein adding to the binary tree or searching in the binary tree comprises holding the associated spin lock when the tree is searched and releasing the associated spin lock when the adding or the search is complete.

11. The apparatus of claim 9 , wherein the processor is further configured to maintain a caching bitmap having a bit associated with each of the windows, wherein each bit is set to a predetermined value if a small storage command associated with the window is currently cached, the small storage command having a size below the threshold.

12. The apparatus of claim 9 , wherein the adding of the window identifier to the selected binary tree comprises adding a node to the tree associated with the window if the node does not already exist.

13. The apparatus of claim 12 , wherein if the data storage size of the command exceeds the threshold, performing a callback function upon completion of the command that deletes the node from the tree.

14. The apparatus of claim 9 , wherein the adding of the window identifier to the selected binary tree comprises incrementing a counter to a node of the tree associated with the window if a node already exists.

15. The apparatus of claim 14 , wherein if the data storage size of the command exceeds the threshold, performing a callback function upon completion of the command that decrements the counter.

16. The apparatus of claim 9 , wherein the filesystem comprises a distributed filesystem having a plurality of virtual drives, each of the binary trees associated with windows from two or more of the virtual drives.

17. A distributed file system server, comprising:
a faster storage tier configured as a cache;
a slower storage tier configured as a main storage; and
a processor coupled to the faster and slower tiers of storage, configured to:
receive, at a block level interface, a storage command from a file system, the storage command associated with a window of a virtual drive;
select one of a plurality of binary trees based on the window, each of the binary trees associated with a plurality of windows;
if a data storage size of the storage command exceeds a threshold, add a window identifier of the window to the selected binary tree to indicate the command will bypass the cache and send data of the storage command directly to the main data storage; and
if the data storage size does not exceed the threshold; search for the window identifier in the selected binary tree and put the storage command in a wait queue before sending the storage command to a caching library if the window identifier is found.

18. The server of claim 17 , wherein each of the binary trees is associated with respective one of a plurality of spin locks, and wherein adding to the binary tree or searching in the binary tree comprises holding the associated spin lock when the tree is searched and releasing the associated spin lock when the adding or the search is complete.

19. The server of claim 17 , wherein the filesystem comprises a Ceph filesystem.

20. The server of claim 17 , wherein the filesystem comprises a Lustre filesystem.

Assignees

• Seagate Technology Llc

Inventors

• Kumar Amit
• Radhakrishna Venkatesha Pradeep
• Venkatesh Shashikiran

Classifications

• G06F2212/222

  Non-volatile memory · CPC title

• G06F16/1827

  Management specifically adapted to NAS (management of storage area networks [SAN] G06F3/067) · CPC title

• G06F12/0888 Primary

  using selective caching, e.g. bypass · CPC title

• G06F2212/6046

  Using a specific cache allocation policy other than replacement policy · CPC title

• G06F16/1774

  Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files · CPC title