US20180173638A1 - Method and apparatus for data access - Google Patents

Abstract

Embodiments of the present disclosure relates to a method and device of data access. The method comprises determining whether target data stored in a non-volatile storage device is cached in a memory. The target data is organized in a first level of a multi-way tree in the storage device. The method further comprises, in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory. Besides, the method comprises, in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.

Description

RELATED APPLICATIONS
• This application claim priority from Chinese Patent Application Number CN201611194069.8, filed on Dec. 21, 2016 at the State Intellectual Property Office, China, titled “METHOD AND APPARATUS FOR DATA ACCESS” the contents of which is herein incorporated by reference in its entirety.
FIELD
• Embodiments of the present disclosure generally relate to the field of data storage, and more specifically, to method and apparatus for data access.
BACKGROUND
• A multi-way tree (e.g. B-tree and its variations) is widely used in a file system or a database to organize data on a storage device (e.g. disk). A typical multi-way tree may consist of a root node, intermediate nodes and leaf nodes. Generally, an upper-level node may be used to store an address of a lower-level node (e.g., disk block number), and the leaf nodes may be used to store data for an actual application. To access a leaf node, an address of a next-level node can be searched sequentially from the root node, until the address of the leaf node to be accessed is found. Besides, to access a node in a storage device, the node needs to be read from the storage device to a memory firstly, and then accessed from the memory.
• In order to access a node in the multi-way tree more quickly with considering a limited memory size, some of the nodes in the multi-way tree may be cached in the memory. Typically, least recently used (LRU) algorithm can be used to swap in/out a node to/from the memory. For example, an LRU linked list may be used to link the nodes in the memory, where a head of the linked list is the most recently accessed node and a tail of the linked list is the least recently used node. If usage of the memory exceeds a predetermined threshold, one or more cached nodes starting from the tail of the linked list may be swapped out of the memory to release the pressure on the memory.
SUMMARY
• Embodiments of the present disclosure provide a method and an apparatus for data access.
• In a first aspect of the present disclosure, a method of data access is provided. The method comprises determining whether target data stored in a non-volatile storage device is cached in a memory. The target data is organized in a first level of a multi-way tree in the storage device. The method further comprises, in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory. Besides, the method comprises, in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.
• In a second aspect of the present disclosure, an electronic device is provided. The device comprises at least one processing unit and at least one memory. The at least one memory is coupled to the at least one processing unit and stores instructions for execution by the at least one processing unit. The instructions, when executed by the at least one processing unit, cause the device to: determine whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device; in response to determining that the target data is missing in the memory, move the target data from the storage device into the memory; and in response to the target data being accessed from the memory, add a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.
• In a third aspect of the present disclosure, a computer program product is provided. The computer program product is tangibly stored in a non-transient computer readable medium and comprises machine-executable instructions. The machine-executable instructions, when executed by a machine, cause the machine to perform any step of the method according to the first aspect of the present disclosure.
• This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.
BRIEF DESCRIPTION OF THE DRAWINGS
• The above and other objectives, features, and advantages of example embodiments of the present disclosure will become more apparent from the following detailed description with reference to the accompanying drawings, in which the same reference symbols refer to the same elements.
• FIG. 1 illustrates an example structure of a typicalmulti-way tree100 for organizing data on a storage device;
• FIG. 2 illustrates a flowchart of amethod200 of data access according to embodiments of the present disclosure;
• FIG. 3 illustrates a diagram of an example harsh table300 for organizing nodes cached in a memory according to embodiments of the present disclosure;
• FIG. 4 illustrates a diagram of a plurality of lists associated with levels of the multi-way tree and provided for recording an access sequence of the nodes in the multi-way tree;
• FIG. 5 illustrates a flowchart of amethod500 of moving a node of the multi-way tree out of the memory according to embodiments of the present disclosure;
• FIG. 6 illustrates a flowchart of amethod600 of data access according to embodiments of the present disclosure;
• FIG. 7 illustrates a block diagram of an apparatus700 for data access according to embodiments of the present disclosure; and
• FIG. 8 illustrates a block diagram of acomputer system800 adapted to implement example embodiments of the present disclosure.
• Throughout the drawings, the same or corresponding reference symbols are used to indicate the same or corresponding parts.
DETAILED DESCRIPTION OF EMBODIMENTS
• Preferred embodiments of the present disclosure will now be described in more detail with reference to the drawings; however, it should be appreciated that the present disclosure may be implemented in various manners but cannot be limited by the embodiments as described herein. On the contrary, these embodiments are provided to disclose the present disclosure more thoroughly and completely, and to convey the scope of the present disclosure exactly to those skilled in the art.
• As used herein, the term “includes” and its variants are to be read as open-ended terms that mean “includes, but is not limited to.” The term “or” is to be read as “and/or” unless the context clearly indicates otherwise. The term “based on” is to be read as “based at least in part on.” The term “an example embodiment” and “an embodiment” are to be read as “at least one example embodiment.” The term “another embodiment” is to be read as “at least another one embodiment”. The terms “first”, “second”, etc., may represent different or identical objects. Other explicit and implicit definitions may be included below.
• As described above, in traditional solutions, a single LRU linked list is typically used to swap in/out a node to/from a memory. However, such LRU linked list does not take characteristics of the tree structure into consideration. For example, the leaf nodes are often placed in front of the LRU linked list as they are last access. Therefore, as compared with the leaf nodes, the root node and intermediate nodes which are more important for subsequent accesses will be swapped out of the memory earlier. In addition, each access to a node will cause a position change of the node in the LRU linked list. When the number of nodes is great or frequent accesses occur, operations on the single LRU linked list tend to become a bottle-neck of the system.
• In order to solve one or more of the above problems and other potential problems, example embodiments of the present disclosure provide a solution for data access. With considering characteristics of the tree structure, this solution divides each LRU linked list into a plurality of linked lists of different priorities, each of which corresponds to a respective level of the tree structure. As such, nodes which are more important for subsequent accesses can be swapped out of the memory later. Besides, frequent operations on the LRU linked list can be avoided by deleting, from the LRU linked list, the node being accessed, thereby improving the system performance.
• Principles and several example embodiments of the present disclosure will be described as below with reference toFIGS. 1 to 7.FIG. 1 illustrates an example structure of a typicalmulti-way tree100 for organizing data on a storage device. It should be appreciated that the structure of themulti-way tree100, as shown inFIG. 1, is only for the purpose of illustration, without suggesting any limitations to functionalities and scope of embodiments of the present disclosure.
• For sake of description, a disk is taken as an example of a storage device in the following. However, this is only for the purpose of illustration. Any storage medium currently known or to be developed in the future based on other mechanisms may act as the storage device.
• As shown inFIG. 1, the multi-way tree100 (e.g., B+ tree) includes nodes101-113. These nodes are organized inlevels120,121 and122 (i.e., a depth of themulti-way tree100 is 3). Specifically, thelevel120 includes aroot node101, thelevel121 includes intermediate nodes102-104, and thelevel122 includes leaf nodes105-113. Each of the nodes101-113 may be used to store one or more key-value (KV for short) pairs. Typically, a value stored in a non-leaf node (i.e., any of theroot node101 and intermediate nodes102-104), may be typically an address (e.g. disk block number) of a lower-level node. The values stored in the leaf nodes105-113 may depend on an actual application.
• For example, to access theleaf node105, theroot node101 may be first accessed. That is, an address of a lower-level node (i.e., the intermediate node102) may be searched based on an input key (e.g. an index of the leaf node105) in theroot node101. Next, theintermediate node102 may be accessed. That is, the address of theleaf node105 is searched in theintermediate node102. Finally, theleaf node105 may be accessed based on the found address of theleaf node105. Moreover, to access a node in thetree100, the node needs to be read from the disk to a memory firstly, and then accessed from the memory.
• It should be understood that the data stored in the nodes of the multi-way tree are not limited to the example forms as mentioned above. Embodiments of the present disclosure can be applied to any data organized in a tree structure. The scope of the present disclosure is not limited in this regard.
• In order to access a node in themulti-way tree100 more quickly with considering a limited memory size, some of the nodes in themulti-way tree100 may be cached in the memory. If usage of the memory exceeds a predetermined threshold, some of the cached nodes may be swapped out of the memory to release the pressure on the memory. Embodiments of the present disclosure provide such a solution for data access.
• FIG. 2 illustrates a flowchart of amethod200 of data access according to embodiments of the present disclosure. Acts involved in the method20 will be detailed described with reference toFIG. 1. It is to be understood that themethod200 may include additional acts not shown and/or may omit some acts as shown, and the scope of the present disclosure is not limited in this regard.
• At block201, it is determined whether target data stored in a non-volatile storage device is cached in a memory. For example, the target data may be organized in thenode102 of thelevel121 of themulti-way tree100. In some embodiments, whether thenode102 has been cached in the memory can be determined by searching a hash table. As an example,FIG. 3 illustrates a diagram of an example harsh table300 for organizing nodes cached in a memory according to embodiments of the present disclosure.
• As shown inFIG. 3, the hash table300 is implemented in form of hash buckets where an sequential list may be employed to store head nodes (hereinafter also called “heads”) of linked lists (hereinafter also called “buckets” or “hash links”) comprised of data entries of identical hash values. As used herein, a data entry may indicate caching of a corresponding multi-way tree node in the memory. For example, the data entry may include a disk block number of the corresponding node, a pointer pointing to the cache of the corresponding node in the memory, a pointer pointing to a preceding data entry in the hash link, a pointer pointing to a subsequent data entry in the hash link, and so on. Detailed descriptions will be further provided with reference toFIG. 2.
• For example, assuming that the disk block number of theroot node101 is 32, the hash length is 8, and the hash algorithm is a remainder method. Since 32% 8=4 (% represents a remainder operation), the search may be performed in the 4th hash link (i.e., the hash link314). For example, if thedata entry310 in thehash link314 can be found and the disk block number recorded by thedata entry301 is 32, it can be determined that theroot node101 has been cached in the memory. Assuming that the disk block number of thenode102 is 41, since 41% 8=1, the search may be performed in thehash link311. Since thehash link311 is empty, there is no any data entry therein, it thus can be determined that thenode102 is not cached in the memory.
• It is to be understood that thehash bucket300 as shown inFIG. 3 is only an example of an implementation of the hash table. Embodiments of the present disclosure may be applied to any hash table in another form currently known or to be developed in the future. The scope of the present disclosure is not limited in this regard.
• Returning toFIG. 2, if it is determined at block201 that the target data is missing in the memory, atblock202, the target data may be moved from the storage device into the memory. In some embodiments, a data entry (e.g. the data entry as described above with reference toFIG. 3) indicating that thenode102 is cached in the memory may be created. An address of a buffer for caching thenode102 and the disk block number of thenode102 may be saved in the data entry, and the data entry may be added to the hash table300 as shown inFIG. 3.
• Atblock203, in response to the target data being accessed from the memory, a reference to the target data may be added to the list. In some embodiments, the list may be implemented as a linked list associated with one or more levels in themulti-way tree100. For sake of description, an LRU linked list is taken as an example of the list in the following, and the LRU linked list may be only associated with one level of themulti-way tree100. It is to be understood that this is for the purpose of illustration without suggesting any limitations to the scope of the present disclosure. The reference to thenode102 may be added to the LRU linked list which records an order for accessing the nodes in thelevel121. For example, the reference to thenode102 can be inserted into the head of the LRU linked list. In some embodiments, the LRU linked list may be created (i.e., initialized) in response to creation of thelevel121, and accordingly destroyed when all of the nodes in thelevel121 are deleted (for example, from the storage device).
• In addition, the data entry corresponding to thenode102, as described with reference toFIG. 3, may further include a first pointer pointing to a preceding data entry in the LRU linked list and a second pointer pointing to a subsequent data entry in the LRU linked list, in addition to the disk block number of thenode102, the pointer pointing to the cache of thenode102 in the memory, the pointer pointing to a preceding data entry in the hash link and the pointer pointing to a subsequent data entry in the hash link. The data entry corresponding to thenode102 can be added to the LRU linked list by modifying the first and second points.
• If it is determined at block201 that the target data have been cached in the memory, themethod200 proceeds to block204. Atblock204, in response to the target data being accessed from the memory and the reference to the target data being added to the list, the position of the reference in the list may be updated. In some embodiments, for example, the first pointer pointing to the preceding data entry in the LRU linked list and the second pointer pointing the subsequent data entry in the LRU linked list, in the data entry corresponding to thenode102 may be modified to move the data entry to the head of the LRU linked list, so as to indicate that thenode102 has been accessed recently.
• In this manner, an access sequence of respective nodes cached in the memory may be recorded in a plurality of lists associated with respective levels of the multi-way tree.FIG. 4 illustrates a diagram of the plurality of lists associated with respective levels of the multi-way tree and provided for recording an access sequence of the nodes in the multi-way tree. As shown inFIG. 4, the access sequence of the nodes in thelevel120 is recorded in thelist401, the access sequence of the nodes in thelevel121 is recorded in thelist402, and the access sequence of the nodes in thelevel122 is recorded in thelist403. It is to be understood that the list as shown inFIG. 4 is only for the purpose of illustration without suggesting any limitations to the scope of the present disclosure.
• If usage of the memory exceeds a predetermined threshold, some nodes may be swapped out of the memory based on the list to reduce the pressure on the memory.FIG. 5 illustrates a flowchart of amethod500 of moving a node of the multi-way tree out of the memory according to embodiments of the present disclosure. Acts involved in themethod500 will be detailed described with reference toFIG. 1. Themethod500 may be performed in parallel with themethod200 or in succession with the method200 (e.g. before or after the method200). It should be appreciated that themethod500 may include additional acts not shown and/or may omit some acts as shown, and the scope of the present disclosure is not limited in this regard.
• Atblock501, in response to determining that the usage of the memory exceeds the predetermined threshold, a recent access condition of data in a level associated with a list is determined based on the list. For example, the recent access condition of the nodes in thelevel121 may be determined based on thelist402.
• Atblock502, a part of the data in the level may be moved out of the memory based on the recent access condition. For example, when thelist402 is an LRU linked list, one or more nodes starting from the tail of the LRU linked list can be sequentially moved out of the memory until the usage of the memory drops below the predetermined threshold. That is, several least recently accessed nodes in thelevel121 may be moved out of the memory.
• In some embodiments, themethod500 may be performed sequentially for the linked lists associated with respective levels. For example, themethod500 may be performed firstly for the list403 (i.e., leaf nodes), then for the list402 (i.e., intermediate nodes), and finally for the list401 (i.e., a root node). As such, a nodes which are more important for subsequent accesses will be moved out of the memory later. Particularly, the root node can be always cached in the memory (i.e., themethod500 are performed only for thelists402 and403), so as to improve the access efficiency.
• In some embodiments, themethod500 may be performed in parallel for the linked lists associated with respective levels. For example, a first recent access condition of the data in thelevel121 may be determined based on thelist402. Then, a first amount of data in thelevel121 may be moved out of the memory based on the first recent access condition. Furthermore, a second recent access condition of data in thelevel122 may be determined based on thelist403. Then, a second amount of data in thelevel122 may be moved out of the memory based on the second access condition. Alternatively or in addition, different priorities can be set for thelevels121 and122, respectively. For example, the priority of thelevel121 can be set higher than that of thelevel122, since the depth of thelevel121 is less than that of thelevel122. Accordingly, the data in thelevel122 may be moved out of the memory in a greater proportion as compared with thelevel121, i.e., the first amount may be less than the second amount. In some embodiments, an amount of data moved out of the memory in a higher level may be set to be 1/d of another amount of data moved out of the memory in a lower level, where d is an order of the multi-way tree (i.e., the maximum number of child nodes owned by a node in the tree). For example, assuming that the order of themulti-way tree100 is 1024 and totally 2050 nodes needs to be moved out of the memory. In this event, 2 nodes can be moved out of thelevel121, while 2048 nodes can be moved out of thelevel122.
• In some embodiments, if the usage of the memory exceeds a first threshold (e.g., a lower water line) but is lower than a second threshold (e.g., a high water line), themethod500 may be performed equentially (e.g. from the lower level to the higher level) for the linked lists associated with respective levels. When the usage of the memory exceeds the second threshold, themethod500 may be performed in parallel for the linked lists associated with respective levels.
• It is to be understood that, some of the nodes may be moved out of the memory based on the lists according to another strategy instead of the above one. The scope of the present disclosure is not limited in this regard. In this manner, nodes which are more important for subsequent accesses can be moved out of the memory later, thereby improving the access efficiency.
• As described above, each access to a node may cause a position change of the node in the corresponding LRU linked list. When the number of nodes of the multi-way tree is great or frequent accesses occur (e.g. a plurality of processes accesse the multi-way tree in parallel), this may lead to frequent operations on the LRU linked list, thereby reducing the system performance. In this regard, embodiments of the present disclosure may avoid frequent operations on the LRU linked lists by deleting, from the LRU linked list, the nodes being accessed.
• FIG. 6 illustrates a flowchart of amethod600 for data access according to embodiments of the present disclosure. In some embodiments, themethod600 may be performed as an additional act betweenblocks202 and203, and/or betweenblocks201 and204 in themethod200. It is to be understood that themethod600 may include additional acts not shown and/or may omit some acts as shown, and the scope of the present disclosure is not limited in this regard.
• At block601, a reference count associated with the target data (e.g. the node102) may be incremented by one. The reference count may be used to indicate whether the target data is being accessed.
• Atblock602, in response to the reference count associated with the target data being greater than one and the reference to the target data having been added to the list (e.g. the list402), the reference is deleted from the list. That is, when the target data are being accessed, it will be deleted from the list to avoid frequent operations on the list. It is to be understood that, if themethod600 is performed as an additional act betweenblocks202 and203 of themethod200, theblock602 may be omitted.
• Atblock603, in response to the target data being accessed from the memory, the reference count may be decremented by one.
• In this manner, when a plurality of processes accesses the multi-way tree in parallel, frequent operations on the list can be avoided, thereby improving the access performance.
• FIG. 7 illustrates a block diagram of an apparatus700 for data access according to embodiments of the present disclosure. As shown inFIG. 7, the device700 may comprise adetermination module710 configured to determine whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device. The device700 may further comprise an access control module701 configured to, in response to determining that the target data is missing in the memory, move the target data from the storage device into the memory; and in response to the target data being accessed from the memory, add a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.
• For the sake of clarity,FIG. 7 does not show some optional modules of the apparatus700. However, it should be understood that respective features described above with reference toFIGS. 1-6 are also suitable for the apparatus700. Moreover, respective modules in the apparatus700 may be hardware modules or software modules. For example, in some embodiments, the apparatus700 may be implemented partially or fully with software and/or firmware, e.g., implemented as a computer program product embodied on a computer readable medium. Alternatively or additionally, the apparatus700 may be implemented partially or fully based on hardware, e.g., implemented as an integrated circuit (IC), an application-specific integrated circuit (ASIC), a system on chip (SOC), a field programmable gate array (FPGA), etc. The scope of the present disclosure is not limited in this aspect.
• FIG. 8 illustrates a block diagram of anexample apparatus800 adapted to implement embodiments of the present disclosure. As shown inFIG. 8, theapparatus800 comprises a central processing unit (CPU)801 that may perform various appropriate acts and processing based on computer program instructions stored in a read-only memory (ROM)802 or computer program instructions loaded from astorage section808 to a random access memory (RAM)803. In theRAM803, there further store various programs and data needed for operations of theapparatus800. TheCPU801,ROM802 andRAM803 are connected to each other via abus804. An input/output (I/O)interface805 is also connected to thebus804.
• Multiple components in theapparatus800 are connected to the I/O interface805: aninput unit806 such as a keyboard, a mouse and the like; anoutput unit807 including various kinds of displays and a loudspeaker, etc.; astorage unit808 including a magnetic disk, an optical disk, and etc.; acommunication unit809 including a network card, a modem, and a wireless communication transceiver, etc. Thecommunication unit809 allows theapparatus800 to exchange information/data with other apparatuses through a computer network such as the Internet and/or various kinds of telecommunications networks.
• Various processes and processing described above, e.g., themethod200,500 and/or600, may be executed by theprocessing unit801. For example, in some embodiments, themethod200,500 and/or600 may be implemented as a computer software program that is tangibly embodied on a machine readable medium, e.g., thestorage unit808. In some embodiments, part or all of the computer programs may be loaded and/or mounted onto theapparatus800 viaROM802 and/orcommunication unit809. When the computer program is loaded to theRAM803 and executed by theCPU801, one or more steps of themethod200,500 and/or600 as described above may be executed.
• The present disclosure may be a system, an apparatus, a device, 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 disclosure.
• 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. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire.
• 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 region network, a wide region network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device.
• Computer readable program instructions for carrying out operations of the present disclosure may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++ or the like, and conventional procedural programming languages, such as the “C” programming language or similar programming languages. 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. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local region network (LAN) or a wide region network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, 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 disclosure.
• Aspects of the present disclosure are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present disclosure. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.
• These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.
• The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed on the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks.
• The flowchart and block diagrams illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, snippet, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, 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. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.
• The descriptions of the various embodiments of the present disclosure have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

Claims (20)

I/We claim:

1. A method for data access, comprising:

determining whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device;

in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory; and

in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.

2. The method according toclaim 1, wherein the determining whether target data stored in a non-volatile storage device is cached in a memory comprises:

determining, by searching a hash table, whether the target data is cached in the memory; and

wherein the moving the target data from the storage device into the memory comprises:

adding, to the hash table, a data entry indicating that the target data is cached in the memory.

3. The method according toclaim 1, further comprising:

in response to determining that the target data has been cached in the memory, causing the target data to be accessed from the memory; and

in response to the target data being accessed from the memory and the reference being added to the first list, updating a position of the reference in the first list.

4. The method according toclaim 1, further comprising:

in response to determining that usage of the memory exceeds a predetermined threshold, determining, based on the first list, a recent access condition of data in the first level; and

moving, based on the recent access condition, a part of the data in the first level out of the memory.

5. The method according toclaim 1, further comprising:

in response to determining usage of the memory exceeds a predetermined threshold,

determining, based on the first list, a first recent access condition of data in the first level;

moving, based on the first recent access condition, a first amount of data in the first level out of the memory;

determining, based on a second list, a second recent access condition of data in a second level of the multi-way tree, a priority of the second level being lower than that of the first level, and the second list recording a sequence for accessing the data in the second level; and

moving, based on the second access condition, a second amount of data in the second level out of the memory, the first amount being less than the second amount.

6. The method according toclaim 5, wherein a depth of the second level in the multi-way tree is greater than that of the first level in the multi-way tree.

7. The method according toclaim 1, further comprising:

in response to determining that the target data is being accessed and the reference has been added to the first list, removing the reference from the first list.

8. An electronic device, comprising:

at least one processing unit;

at least one memory coupled to the at least one processing unit and storing instructions for execution by the at least one processing unit, the instructions, when executed by the at least one processing unit, causing the device to:

determine whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device;

in response to determining that the target data is missing in the memory, move the target data from the storage device into the memory; and

in response to the target data being accessed from the memory, add a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.

9. The device according toclaim 8, wherein the determining whether target data stored in a non-volatile storage device is cached in a memory comprises:

determining, by searching a hash table, whether the target data is cached in the memory; and

wherein the moving the target data from the storage device into the memory comprises:

adding, to the hash table, a data entry indicating that the target data is cached in the memory.

10. The device according toclaim 8, wherein the instructions, when executed by the at least one processing unit, further cause the device to:

in response to determining that the target data has been cached in the memory, cause the target data to be accessed from the memory; and

in response to the target data being accessed from the memory and the reference being added to the first list, update a position of the reference in the first list.

11. The device according toclaim 8, wherein the instructions, when executed by the at least one processing unit, further cause the device to:

in response to determining that usage of the memory exceeds a predetermined threshold, determine, based on the first list, a recent access condition of data in the first level; and

move, based on the recent access condition, a part of the data in the first level out of the memory.

12. The device according toclaim 8, wherein the instructions, when executed by the at least one processing unit, further cause the device to:

in response to determining usage of the memory exceeds a predetermined threshold,

determine, based on the first list, a first recent access condition of data in the first level;

move, based on the first recent access condition, a first amount of data in the first level out of the memory;

determine, based on a second list, a second recent access condition of data in a second level of the multi-way tree, a priority of the second level being lower than that of the first level, and the second list recording a sequence for accessing the data in the second level; and

move, based on the second access condition, a second amount of data in the second level out of the memory, the first amount being less than the second amount.

13. The device according toclaim 12, wherein a depth of the second level in the multi-way tree is greater than that of the first level in the multi-way tree.

14. The device according toclaim 8, wherein the instructions, when executed by the at least one processing unit, further cause the device to:

in response to determining that the target data is being accessed and the reference has been added to the first list, remove the reference from the first list.

15. A computer program product for data access, the computer program product comprising:

a non-transitory computer readable medium encoded with computer-executable program code, the code configured to enable the execution of:

determining whether target data stored in a non-volatile storage device is cached in a memory, the target data being organized in a first level of a multi-way tree in the storage device;

in response to determining that the target data is missing in the memory, moving the target data from the storage device into the memory; and

in response to the target data being accessed from the memory, adding a reference to the target data to a first list, the first list recording a sequence for accessing data in the first level.

16. The computer program product ofclaim 15, wherein the determining whether target data stored in a non-volatile storage device is cached in a memory comprises:

determining, by searching a hash table, whether the target data is cached in the memory; and

wherein the moving the target data from the storage device into the memory comprises:

adding, to the hash table, a data entry indicating that the target data is cached in the memory.

17. The computer program product ofclaim 15, wherein the code is further configured to enable the execution of:

in response to determining that the target data has been cached in the memory, causing the target data to be accessed from the memory; and

in response to the target data being accessed from the memory and the reference being added to the first list, updating a position of the reference in the first list.

18. The computer program product ofclaim 15, wherein the code is further configured to enable the execution of:

in response to determining that usage of the memory exceeds a predetermined threshold, determining, based on the first list, a recent access condition of data in the first level; and

moving, based on the recent access condition, a part of the data in the first level out of the memory.

19. The computer program product ofclaim 15, wherein the code is further configured to enable the execution of:

in response to determining usage of the memory exceeds a predetermined threshold,

determining, based on the first list, a first recent access condition of data in the first level;

moving, based on the first recent access condition, a first amount of data in the first level out of the memory;

determining, based on a second list, a second recent access condition of data in a second level of the multi-way tree, a priority of the second level being lower than that of the first level, and the second list recording a sequence for accessing the data in the second level; and

moving, based on the second access condition, a second amount of data in the second level out of the memory, the first amount being less than the second amount.

20. The computer program product ofclaim 19, wherein a depth of the second level in the multi-way tree is greater than that of the first level in the multi-way tree.

Images