Patent Publication Number: US-9842061-B2

Title: Implementing advanced caching

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS 
     This application is a continuation of commonly assigned U.S. patent application Ser. No. 14/316,395, filed on Jun. 26, 2014, and entitled “IMPLEMENTING ADVANCED CACHING,” the disclosure of which is hereby incorporated herein in its entirety by reference. 
    
    
     BACKGROUND 
     Some web sites store many documents and a subset of these documents is accessed frequently. For example, social network web sites can store billions of photographs, and a subset of these photographs can be very frequently accessed for an initial period of time (e.g., soon after the photograph is first “shared” with friends) and then rarely accessed thereafter. Web site operators, e.g., social network web sites, can employ caching techniques to reduce the overhead associated with accessing these documents, but must manage a tradeoff between having very many web site servers to enable quick access to these documents and large caches to reduce load on the servers. These tradeoffs can affect speed and cost. For example, caching can be done using relatively more expensive hardware, e.g., solid state drives (SSDs) instead of disk drives to provide faster speeds. 
     An example of a caching algorithm is a “least recently used” (LRU) cache. An LRU cache discards the least recently used items first. For example, a photograph that is popularly accessed may remain in a cache for an extended period, whereas a photograph that is accessed rarely may be discarded from the cache. Other advanced caching algorithms also exist. The LRU algorithm can keep an initially posted photograph in the cache and then eventually discard the cache as the photograph becomes less frequently accessed. 
     Priority queues can be used to implement various advanced caching algorithms. A priority queue is a data type that is like a regular queue or stack data structure, but where additionally each element has a priority associated with it. To implement an LRU algorithm using a priority queue, priorities of items in the queue can be updated when the items are accessed. Thus, an item that is accessed infrequently would eventually have a low priority and so may be discarded from the queue. On the other hand, an item that is accessed frequently will eventually have a high priority and so may remain in the queue longer than other items. 
     When using SSDs to store data, it is generally desirable to minimize the number of write operations to reduce an undesirable operation referred to as “write amplification.” Write amplification occurs because, unlike with magnetic disks, data in memory must be erased before it is rewritten. This writing and rewriting can cause data to be moved in the SSD, which results in many more writes than the initial write operation. Thus, when an application changes the priority of an item in a priority queue, the SSD may perform multiple writes. It is desirable to reduce the number of writes because SSDs (and memory generally) can have a limited write lifetime. Moreover, it can be advantageous to avoid operations that prevent efficient use SSDs. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments disclosed herein may be better understood by referring to the following Detailed Description in conjunction with the accompanying drawings, in which like reference numerals indicate identical or functionally similar elements: 
         FIG. 1  is a block diagram illustrating an environment in which the technology may operate in various embodiments. 
         FIG. 2  is a block diagram illustrating items that may be stored in a memory or a solid state drives in various embodiments. 
         FIG. 3A  is a table diagram illustrating data that may be stored in an index, consistent with various embodiments. 
         FIG. 3B  is another table diagram illustrating data that may be stored in an index, consistent with various embodiments. 
         FIG. 4  is a flow diagram illustrating a routine for implementing a priority queue in a storage device, consistent with various embodiments. 
         FIGS. 5A-D  are portions of the flow diagrams illustrating various aspects for implementing a priority queue, consistent with various embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments are disclosed for implementing advanced caching, e.g., using priority queues, in conjunction with one or more storage devices. Examples of storage devices are solid state drives (SSDs) of various capacities, pluggable cards with flash memory, etc. In various embodiments, one or more storage devices are divided into multiple logical “blocks.” The logical blocks can be large enough to store items that are to be tracked in a priority queue or cache, but much smaller than the overall size of the storage device. A small subset of the logical blocks may be identified as “active” blocks. Each active block can have a corresponding block that is stored in a memory region of a computing device that implements the cache. A caching system can provide an application program interface that applications can use to cache items, e.g., photographs, text, etc. As an example, when a social networking web site stores or retrieves a photograph, it may invoke the caching system to perform the storing or retrieving. 
     Each active block can have associated therewith a priority value. In some embodiments, the active blocks are distributed so that the number of items in adjacent active blocks is roughly equal. In an absolute-priority example, if there are 10 items with priorities between 1 and 5, 20 items with priorities 6 between and 10, and 10 items with priorities between 11 and 15, and the caching system makes four blocks active, it may select as priorities 3, 7, 9, and 13 so that there are approximately 10 items in each of the four active blocks. In a relative-priority example, the priority numbers can be real numbers in the range from 0 to 1. For example, the priority number 0.1 can represent a lower priority than the priority number 0.8. The caching system can process these relative-priorities similarly to the absolute-priorities as discussed above. 
     When an application adds an item to the cache, the application can invoke the application program interface provided by the caching system. The caching system can store the item in an in-memory block corresponding to an active block in the storage device. The caching system can also add an entry into an in-memory index to indicate in which active block the item was stored. The caching system adds the item to the active block that has a priority that is closest to the added item. In case of a tie (e.g., the priority is exactly between two priorities of active blocks), the caching system can add the item to either block, e.g., a block having fewer items than the other block. When an item having the lowest priority is deleted, the caching system marks the item in the in-memory index as having been deleted, but does not delete the item in the storage device. When an item is read, the caching system looks up its location (e.g., block identifier) in the in-memory index and then reads the item from the storage device. 
     The index can store information about items stored in all blocks, whether the blocks are active or not. In some embodiments, the index stores information only about items stored in non-active blocks. The information can include, for each item, its name, location (e.g., logical block), priority, etc. When an in-memory block becomes full (e.g., can accommodate no more items), the caching system can commit the now full block to the storage device and erase an older block in the storage device. In some embodiments, the active block with the lowest priority is erased. Before erasing the block in the storage device, the caching system first reads that block into memory. The caching system then discards all items in that block that are marked in the in-memory index as having been deleted and removes entries in the index for those items. The caching system then begins populating a new block in memory and assigns a new active block in the storage device. In some embodiments, the new active block is assigned a priority that minimizes the maximum difference between priority values for all active blocks. As an example, if there are four blocks with priorities 3, 7, 9, and 15, the caching system may assign a priority of 12 to the new block to minimize the maximum difference between 9 and 15. The remaining items in the erased block that are not indicated in the index as having been deleted are then inserted into the active blocks closest to the priorities of those items. In relative-priority embodiments, the caching system can assign a priority to a block so as to minimize the maximum number of items between priorities. For example, if there are four blocks with priorities 0.1, 0.3, 0.5 and 0.9, the caching system may assign a priority of 0.8 to a new block to minimize the maximum number of items between priorities (e.g., there are three groups in a first relative-priority range of 0 to 0.5, but there is only one group in a second relative-priority range of 0.51 to 1). Similarly, the remaining items in the erased block that are not indicated in the index as having been deleted are then inserted into the active blocks closest to the priorities of those items. 
     When an item&#39;s priority is increased, e.g., because it is read, the caching system updates the priority value in the in-memory index, but does not modify its value in the storage device. By postponing writing to the storage device, write-related issues (e.g., bandwidth and write amplification) are reduced. Moreover, because blocks are larger than items, the buffered writes improve the efficiency of using storage devices (e.g., SSDs) for priority queues. 
     In the foregoing and following descriptions, although SSDs may be used for convenience of description, it is to be understood that other solid state memory-based storage devices can also be employed. 
     Several embodiments of the described technology are described in more detail in reference to the Figures. The computing devices on which the described technology may be implemented may include one or more central processing units, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), storage devices (e.g., disk drives), and network devices (e.g., network interfaces). The memory and storage devices are computer-readable storage media that may store instructions that implement at least portions of the described technology. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links may be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection. Thus, computer-readable media can comprise computer-readable storage media (e.g., “non-transitory” media) and computer-readable transmission media. 
       FIG. 1  is a block diagram illustrating an environment  100  in which the technology may operate in various embodiments. The environment  100  can be a portion of a computing device, e.g., a general-purpose computing device or a special purpose computing device. The environment  100  can include a processor  102 , e.g., a central processing unit, a memory  104 , and one or more solid state drives (SSDs)  106   a ,  106   b , and  106   n . In various embodiments, multiple such environments  100  may be deployed, e.g., as web server computing devices, caching system computing devices, etc. 
       FIG. 2  is a block diagram illustrating items that may be stored in a memory  104  or a solid state drive  106   a  in various embodiments. The memory  104  can have a blocks region  202  and an index region  203 . The blocks region  202  can store one or more in-memory blocks, e.g.,  202   a ,  202   b ,  202   c , and  202   m . The index region  203  can store an index of stored items, as further described below. 
     The illustrated SSD  106   a  can have an active blocks region  204  and an inactive blocks region  206 . The active blocks region  204  can store one or more blocks that are also cached in memory  104 . For example, block  204   a  stored in the SSD  106   a  can correspond to block  202  that is stored in memory  104 . In various embodiments, some or all blocks in the active blocks region  204  can be cached in the blocks region  202  of memory  104 . Each block in active blocks region  204  can have associated therewith a priority. For example, block  204   a  has priority 0.1, block  204   b  has priority 0.2, block  204   c  has priority 0.3, block  204   d  has priority 0.4, and block  204   m  has priority 1.0. The inactive blocks region  206  can store blocks that are not presently cached in memory  104 . 
     In various embodiments, each block is larger than items to be stored in the priority queue (e.g., in a cache), but much smaller than the total space available in the SSD. For example, there may be hundreds of blocks in an SSD. In some embodiments, the number of active blocks may be between 10 and 30. 
       FIG. 3A  is a table diagram illustrating data that may be stored in an index, consistent with various embodiments. The index can indicate a name  302  for each item, a priority  304  associated with the item, an indication  306  of whether the item is deleted, and a block number  308  (e.g., logical or physical block numbers) of the items stored. Row  310  indicates that an item with name “name 1” has a priority of 0.05, is not deleted, and is stored at block  204   a ; row  312  indicates that an item with name “name 2” has a priority of 0.35, is not deleted, and is stored at block  204   c ; row  314  indicate that an item with name “name 3” has a priority of 0.12, has been deleted, and is stored at block  204   a ; and row  316  indicates that an item with name “name 5” has a priority of 0.99, is not deleted, and is stored at block  204   m . In various embodiments, items can be stored in blocks having nearest priorities. For example, item  310  can be stored in block  204   a  because block  204   a  has a priority of 0.1 whereas block  204   b  has a priority of 0.2, and the priority for item  310  is 0.05, which is closer mathematically to 0.1 than to 0.2. 
       FIG. 3B  is another table diagram illustrating data that may be stored in an index, consistent with various embodiments. In the illustrated embodiment, the index can indicate a name  302  for each item, an indication  306  of whether the item is deleted, and a virtual block number  318  (e.g., a logical block number) of the items stored. Comparing to the embodiments described in  FIG. 3A , the index described here does not include a priority column and only includes virtual block numbers (i.e., no physical block number). By doing so, the index described in  FIG. 3B  can have a smaller size than the embodiments described in  FIG. 3A . In various embodiments, system administrators can determine which information should be included in the index table, depending on various factors, such as availability of computing resources and/or system efficiency. 
     While  FIGS. 3A and 3B  and each of the table diagrams discussed below show a table whose contents and organization are designed to make them more comprehensible by a human reader, those skilled in the art will appreciate that actual data structures used by the facility to store this information may differ from the table shown, in that they, for example, may be organized in a different manner; may contain more or less information than shown; may be compressed and/or encrypted; etc. 
       FIG. 4  is a flow diagram illustrating a routine  400  for implementing a priority queue in a storage device, consistent with various embodiments. The routine  400  begins at block  402 . At block  404 , the routine  400  selects a specified number (M) of blocks. The selected blocks are indicated to be active blocks. At block  406 , the routine  400  assigns priorities to the selected blocks. In various embodiments, the priorities may be distributed evenly, distributed to approximately balance the number of items stored in each block, etc. At block  408 , the routine  400  receives a command (also referred to as an “operation”) relating to the priority queue, e.g., to write an item, read an item, delete an item, or change the priority of an item. At decision block  410 , the routine  400  determines the type of the received command. If the type of the received command is “read,” the routine  400  continues at block  412 . If the type of the received command is “write,” the routine  400  continues at block  414 . If the type of the received command is “delete,” the routine  400  continues at block  416 . If the type of the received command is “change priority,” the routine  400  continues at block  418 . The illustrated flow of these commands continues in  FIGS. 5A-D . 
     Those skilled in the art will appreciate that the logic illustrated in  FIG. 4  and described above, and in each of the flow diagrams discussed below, may be altered in various ways. For example, the order of the logic may be rearranged, substeps may be performed in parallel, illustrated logic may be omitted, other logic may be included, etc. 
       FIG. 5A  illustrates a routine  500  to implement the “read” command. At block  501 , the routine  500  looks up the item in the index to identify the block at which the item is stored. As an example, the routine  500  may look up the name of the item and identify a block at which the item is stored. At block  502 , the routine  500  reads the identified block from the SSD and returns the item at block  503 . In alternate embodiments, the routine  500  may simply read the item from the in-memory block. 
       FIG. 5B  illustrates a routine  550  to implement the “write” command. At block  504 , the routine  550  selects an active block with the closest priority. As an example, if the item to be written has priority 31, the routine  550  may select block  204   c  illustrated in  FIG. 2 , because block  204   c  has a priority of 30, which is mathematically closer to 30 than priorities of the other blocks. At block  505 , the routine  550  inserts the item into the selected block in memory but not the SSD. At block  506 , the routine  550  adds to the index the name of the item, the indicated priority, and the SSD block identifier corresponding to the cached block in memory. At decision block  508 , the routine  550  determines whether the block is full. If the block is full, the routine  550  continues at block  510 . Otherwise, the routine  550  returns at block  524 . The routine  550  then commits the cached block to the SSD and deletes the block with the lowest priority from the SSD. The logic for this deletion will now be explained in further detail. At block  510 , the routine writes the now full block to the SSD. At block  512 , the routine  550  reads the block with the lowest priority to memory. At block  514 , the routine  550  deletes the block that was read from the SSD. At block  516 , the routine creates a new active block. At block  518 , the routine  550  assigns a priority to the new active block. In various embodiments, the priority may be assigned to minimize the maximum difference between the priority values for all active blocks. At block  519 , the routine  550  implicitly deletes all items in the block having a priority lower than a threshold X (which can be determined by a system administrator; e.g., relative-priority 0.9). “Implicit deletion” can be defined as removing items from the SSD at eviction time without updating these items&#39; priorities after they are inserted into corresponding blocks. For example, in an LRU cache, all items that have not been accessed after they are inserted into blocks can be implicitly deleted at eviction time. In some embodiments, the implicit deletion process can be done by not reinserting items to the block with the lowest priority (e.g., lowest 10%). At block  520 , the routine  550  removes from the index all corresponding entries marked as deleted. At block  522 , the routine  550  inserts the remaining items into active blocks that have the closest priority to the remaining items. The routine  550  then returns at block  524 . 
       FIG. 5C  illustrates a routine  600  to implement the “delete” command (please refer back to  FIG. 4  and corresponding descriptions above). At block  602 , the routine  600  marks, in the index, the item as deleted, but does not indicate any change in the SSD. The routine  600  then returns at block  604 . 
       FIG. 5D  illustrates a routine  700  to implement the “update priority” command (please refer back to  FIG. 4  and corresponding descriptions above). At block  702 , the routine  700  updates the priority for the item in the index. The routine  700  then returns at block  704 . 
     Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims. Accordingly, the invention is not limited except as by the appended claims.