Patent Publication Number: US-10324809-B2

Title: Cache recovery for failed database instances

Description:
FIELD OF THE DISCLOSURE 
     Embodiments relate to database systems and more specifically, to cache recovery for failed database instances. 
     BACKGROUND 
     The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section. 
     A clustered database system that runs on multiple computing nodes offers several advantages, such as fault tolerance and/or load balancing, over a database system running on a single computing node. In some example embodiments, a clustered database system includes a plurality of database servers or “instances” that share resources, including a database.  FIG. 1  depicts an example clustered database system comprising database instance  100  and database instance  126  that share primary persistent storage  138 . Although the example of  FIG. 1  depicts two database instances, in some example embodiments, a clustered database system may include more than two database instances. 
     Database instance  100 ,  126  may be a collection of memory and processes that interact with data stored on primary persistent storage  138 . Database instance  100  and database instance  126  may collectively implement server-side functions of a database management system. To ensure data consistency, each database instance of a clustered database system may acquire mastership of one or more resources. Referring to  FIG. 1 , set of data  140  and set of data  142  are stored on primary persistent storage  138 . Thus, database instance  100  may be a master database instance for set of data  140 , and database instance  126  may be a master database instance for set of data  142 . Modifying particular data involves obtaining permission from the master database instance of the particular data. Thus, modifying set of data  140  involves obtaining permission from database instance  100 , and modifying set of data  142  involves obtaining permission from database instance  126 . 
     Primary persistent storage  138  may be one or more systems that store data structures in files, such as data blocks. For example, primary persistent storage  138  may include a virtual disk and/or one or more physical disks. Data stored on primary persistent storage  138  survives system failure. However, retrieving the data is typically a relatively slow and computationally expensive process. 
     For efficient data access, a database system typically maintains one or more caches of data in volatile memory, such as main memory or random-access memory. In the example of  FIG. 1 , database instance  100  includes volatile memory  102 , and database instance  126  includes volatile memory  128 . Volatile memory  102  and volatile memory  128  may be the same volatile memory of a single computing device or separate volatile memories of separate computing devices. 
     Referring to  FIG. 1 , volatile memory  102  includes primary cache  104 , and volatile memory  128  includes primary cache  130 . Database instance  100  stores set of data  108  in primary cache  104 , and database instance  126  stores set of data  134  in primary cache  130 . In some example embodiments, each database instance may maintain a respective primary cache of data for which the database instance has become a master database instance. Thus, set of data  140  may be stored as set of data  108  in primary cache  104 , and set of data  142  may be stored as set of data  134  in primary cache  130 . 
     Increased efficiency of data access may be achieved based on increasing the amount of data that can be cached. However, adding volatile memory to a database system may be cost-prohibitive. Thus, a cost-effective alternative is to supplement volatile memory with relatively inexpensive forms of low-latency non-volatile memory, such as flash memory or any other solid-state drive (SSD). 
     In  FIG. 1 , secondary persistent storage  112  is an example of non-volatile memory that is used to supplement volatile memories  102 ,  128 . Like primary persistent storage  138 , secondary persistent storage  112  is shared by database instances  100  and  126 . Secondary persistent storage  112  may be partitioned into a plurality of secondary caches, such as secondary cache  114  and secondary cache  120 . Each database instance may maintain a respective secondary cache of data for which the database instance has become a master database instance. Thus, set of data  108  may be stored as set of data  116  in secondary cache  114 , and set of data  134  may be stored as set of data  122  in secondary cache  120 . 
     In some example embodiments, a secondary cache may serve as an extension of a primary cache. Typically, lower priority data is moved from a primary cache to a secondary cache. Examples of lower priority data include data that is accessed with a relatively lower frequency, data that is relatively older, and data that is stored at a higher compression level. To track data that has been cached to the secondary cache, header information is stored in volatile memory. The header information is read and consulted to retrieve the data stored in the secondary cache.  FIG. 1  depicts set of header data  106  and set of header data  132  as being stored in primary cache  104  and primary cache  130 , respectively. However, in some example embodiments, header data may be stored outside of a primary cache in volatile memory. 
     When a database instance fails, data stored in volatile memory may be lost. This data includes header data. In contrast, data stored in non-volatile memory typically survives any failure. However, the data stored in non-volatile memory is inaccessible without access to corresponding header data. 
     During instance recovery, the secondary cache is completely repopulated, even though valid data there had survived. This is because the header data that may be used to determine what valid data is in the secondary cache is not available. Unfortunately, repopulating a cache involves a significant amount of time, and in the interim, data access may exhibit decreased throughput and increased response times, for example, due to data retrieval from primary persistent storage  138 . 
     Thus, an approach for quickly recovering data stored in a non-volatile memory cache is beneficial and desirable. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the drawings: 
         FIG. 1  depicts an example computer architecture on which embodiments may be implemented. 
         FIG. 2  depicts a detailed view of metadata, in an example embodiment. 
         FIG. 3  depicts an example approach for accessing data stored in a secondary cache. 
         FIG. 4  depicts an example approach for modifying data stored in a secondary cache. 
         FIG. 5  depicts an example approach for storing data in a secondary cache. 
         FIG. 6  is a flow diagram that depicts an approach for recovering data cached by a failed database instance. 
         FIG. 7  is a flow diagram that depicts an approach for acquiring mastership of data cached by a failed database instance. 
         FIG. 8  depicts a computer system upon which an embodiment may be implemented. 
     
    
    
     While each of the drawing figures depicts a particular embodiment for purposes of depicting a clear example, other embodiments may omit, add to, reorder, and/or modify any of the elements shown in the drawing figures. For purposes of depicting clear examples, one or more figures may be described with reference to one or more other figures, but using the particular arrangement depicted in the one or more other figures is not required in other embodiments. 
     DETAILED DESCRIPTION 
     In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure. It will be apparent, however, that the present disclosure may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present disclosure. Modifiers such as “first” and “second” may be used to differentiate elements, but the modifiers do not necessarily indicate any particular order. 
     General Overview 
     A clustered database system may include multiple database instances that share a database maintained on persistent storage, such as a magnetic disk. The multiple database instances also share low-latency form of non-volatile memory used for caching, such as a SSD. Data stored in the shared low-latency form of non-volatile memory can be accessed more quickly than other forms of non-volatile memory, such as magnetic disk. Each database instance may be a master of a respective subset of the database. Each master database instance may use the shared low-latency non-volatile memory to cache the respective subset of the database of the master. 
     Each master database instance stores header data in volatile memory. Each set of header data includes memory addresses associated with cached data stored in the shared non-volatile memory and whether that cached data is a valid or invalid cache copy. 
     The low-latency form of non-volatile memory stores a respective set of persistent metadata for each master database instance. Each set of persistent metadata includes one or more memory addresses of data stored in the low-latency form of non-volatile memory. Unlike data stored in volatile memory, persistent metadata stored in the low-latency form of non-volatile memory may survive an instance failure and can be used to recreate a corresponding set of header data in volatile memory. 
     For example, when a first database instance fails, a second database instance may recover a portion (“recoverable data”) of the surviving cached data that the first database instance stored in the low-latency form of non-volatile memory. To do so, the second database instance may acquire mastership of the data. Acquiring mastership may involve retrieving, from the low-latency form of non-volatile memory, persistent metadata corresponding to the cached data. Based on the persistent metadata, the second database instance may generate, in volatile memory, the header data corresponding to the usable recoverable data. Furthermore, based on the header data, the second database instance may access the recoverable data stored in the low-latency form of non-volatile memory. 
     Cache Recovery for Instance Failure 
     When a database instance fails, data stored in non-volatile memory may be recovered based on persistent metadata that corresponds to the data. Referring to  FIG. 1 , secondary persistent storage  112  stores set of persistent metadata  118  and set of persistent metadata  124 . Although  FIG. 1  depicts secondary caches that store metadata, in some example embodiments, persistent metadata may be stored in non-volatile memory outside of any cache. 
     In some example embodiments, persistent metadata stored in non-volatile memory is a copy of metadata stored in volatile memory. For example, database instance  100  may modify set of metadata  110  in volatile memory  102 . Thereafter, modifications to set of metadata  110  may be batched together and stored on secondary persistent storage  112  as set of persistent metadata  118 . Set of metadata  110  and/or set of persistent metadata  118  may include one or more memory addresses, such as one or more data block addresses, corresponding to set of data  140  on primary persistent storage  138 . 
     Persistent metadata stored in non-volatile memory includes information from which header data may be reconstructed in volatile memory. For example, set of persistent metadata  118  may be used to reconstruct set of header data  106  for set of data  116 . Set of header data  106  may include one or more memory addresses, such as one or more block addresses, corresponding to set of data  116  on secondary persistent storage  112 . The one or more memory addresses stored in set of header data  106  may be derived from index data for set of data  140 . 
     Referring to  FIG. 1 , set of header data  106  may be a subset of a larger set of header data (not shown) that also includes data that is stored in primary cache  104  but is absent from secondary cache  114 . 
     An operative instance may reconstruct header data directly or indirectly from persistent metadata of an inoperative instance. For example, when database instance  100  fails, database instance  126  may generate set of header data  106  in volatile memory  128  based on set of persistent metadata  118 . Alternatively, when database instance  100  fails, database instance  126  may store set of persistent metadata  118  in volatile memory  128  as set of metadata  110 . Thereafter, database instance  126  may generate set of header data  106  in volatile memory  128  based on set of metadata  110 . 
     Prior to reconstructing header data of an inoperative instance, an operative instance becomes a master database instance for data corresponding to the header data. However, when the inoperative instance becomes operative again (hereinafter “recovered instance”), mastership of the data may be restored to the recovered instance. For example, if database instance  100  fails, database instance  126  may have mastership of set of data  116  in addition to set of data  122 . However, when database instance  100  recovers, database instance  126  may transfer mastership of set of data  116  back to database instance  100 . Database instance  100  may reacquire mastership of set of data  116  and reconstruct set of header data  106  in volatile memory  102 . Database instance  100  may reconstruct set of header data  106  using any of the aforementioned approaches for reconstructing header data of an inoperative instance. Additionally or alternatively, when database instance  100  reacquires mastership of set of data  116 , database instance  126  may send, via an interconnect, header data or metadata corresponding to set of data  116 , thereby enabling database instance  100  to avoid retrieving set of persistent metadata  118  from secondary persistent storage  112 . 
     As mentioned above, an operative instance may become an interim master instance on behalf of an inoperative instance. Any instance performing database recovery, such as by applying redo records or undo records, may be a candidate for interim mastership. However, determining which operative instance is to become the interim master instance may be based on one or more of a variety of considerations. For example, operative instances may compete for interim mastership based on vying for a global lock. Additionally or alternatively, interim mastership may be determined based on a proximity of an operative instance&#39;s secondary cache to the inoperative instance&#39;s secondary cache. 
     Database Recovery of Cached Data in Secondary Cache 
     Modifying cached data typically incurs less overhead than modifying data stored on primary persistent storage  138 . Thus, database changes are made to cached data that is stored in primary cache  104  or  130 . These database changes may be stored in shared volatile memory as one or more redo records. Thereafter, the cached data in its modified form (hereinafter “modified data”) may be moved to primary persistent storage  138 . A copy of the modified data may be cached in secondary cache  114  in conjunction with moving the modified data to primary persistent storage  138 . 
     According to an embodiment, secondary cache  114  and set of persistent metadata  118  are maintained such that set of persistent metadata  118  indicates whether data in secondary cache  114  is valid or invalid. Both validation and invalidation may be written lazily to persistent metadata and may be batched. However, persistent metadata is invalidated before modified data is written to primary persistent storage  138 . For example, when a copy of data in secondary cache  114  is modified in primary cache  130  to generate modified data, set of persistent metadata  118  may be modified to indicate that the data in secondary cache  114  is invalid. The modified data may be written to primary persistent storage  138 , and a copy of the modified data may be written to secondary cache  114 . When the copy of the modified data is written to secondary cache  114 , set of persistent metadata  118  may be modified to indicate that the copy of the modified data is a valid copy of the modified data stored in primary persistent storage  138 . 
     Database changes may be implemented as transactions that are executed on a database. A transaction effects one or more changes to a database based on one or more instructions that are processed as a single logical operation. For example, the Structured Query Language (SQL) commands “INSERT”, “UPDATE”, and “DELETE” may be processed as a single transaction. Any changes implemented by a particular transaction are persisted when the particular transaction commits. However, when a transaction fails to commit, data affected by the transaction may undergo a “rollback” operation that restores the data to a previous state. For example, a previous version of the data may be stored as an undo record in shared volatile memory. Thus, a “rollback” operation may involve replacing modified data with data from an undo record. 
     Modified data may be moved to primary persistent storage  138  for a number of different reasons. For example, modified data may be moved to primary persistent storage  138  when a transaction resulting in the modified data commits. When the transaction commits, the one or more redo records corresponding to the modified data is also moved to primary persistent storage  138 . Additionally or alternatively, modified data may be moved to primary persistent storage  138  as part of cache management of primary cache  130 , regardless of whether a transaction resulting in the modified data commits. 
     A database instance may fail at any time. However, a surviving database instance may enable a database recovery based on database state information available from redo records or undo records. In other words, a surviving database instance may enable picking up where a failed database instance left off. For example, a surviving database instance may determine that particular data in primary persistent storage  138  was modified by an uncommitted transaction. Thus, the surviving database instance may enable a database recovery process to apply undo records to the particular data. As another example, a surviving database instance may determine that particular data in volatile memory was modified by a committed transaction but the particular data was not written to primary persistent storage  138 . Thus, the surviving database instance may enable a database recovery process to apply redo records to corresponding data stored in primary persistent storage  138 . 
     As mentioned above, set of persistent metadata  118 ,  124  indicates whether or not data in secondary persistent storage  112  is a valid copy of the data in primary persistent storage  138 . Thus, when a database recovery process applies redo records and/or undo records to data in primary persistent storage  138 , the database recovery process may cause corresponding data cached on secondary persistent storage  112  to become invalid. In such scenarios, a surviving database instance may avoid generating header data corresponding to invalid data cached on secondary persistent storage  112 . This may be achieved based on invalidating persistent metadata that corresponds to invalid data. Thus, the surviving database instance enables selective retention of data cached on secondary persistent storage  112 . 
     In some example embodiments, data cached on secondary persistent storage  112  may be used during database recovery instead of data stored on primary persistent storage  138 . Advantageously, this can significantly reduce database recovery time. 
     Cache Recovery for System Failure 
     When all database instances in a cluster fail, any database state information stored in shared volatile memory may be lost. As a result, it may be impractical to selectively repopulate data cached on secondary persistent storage  112 . Instead, an entire cache of data stored on secondary persistent storage  112  may be repopulated if there is any inconsistency with corresponding data stored on primary persistent storage  138 . For example, if data stored in secondary cache  114  differs from corresponding data stored on primary persistent storage  138 , then the data stored in secondary cache  114 , as well as any metadata corresponding to it, may be ignored. 
     Any differences between data stored on primary persistent storage  138  and corresponding data stored in a particular secondary cache may be detected based on comparing version identifiers. If a version identifier for data stored on primary persistent storage  138  matches a version identifier for corresponding data stored in a particular secondary cache, the corresponding data may be treated as valid. Header data may be generated for valid data. However, if the version identifiers fail to match, the corresponding data may be ignored as invalid. Generating header data may be avoided for invalid data. 
     Among other information, a database control file may include a version identifier for data stored on persistent storage. Referring to  FIG. 1 , primary persistent storage  138  stores database control file  144 . Database control file  144  may be a binary record of a database&#39;s status and/or physical structure. The version identifier may be updated whenever a corresponding database is mounted. In other words, a version identifier may indicate a version of a database. 
     Among other information, metadata may include a version identifier for data stored in a particular secondary cache. Referring to  FIG. 2 , metadata  200  includes memory address(es)  202  and version identifier  204 . For example, metadata  200  may correspond to set of persistent metadata  118 , and memory address(es)  202  may correspond to one or more locations in secondary persistent storage  112  where set of data  116  is stored. Version identifier  204  may be updated whenever data is stored on primary persistent storage  138 . In other words, a version identifier may indicate a version of primary persistent storage  138 . In some example embodiments, version identifier  204  may be stored in a header portion of set of persistent metadata  118 . 
     After a cluster outage, instances may come back up concurrently. In such a scenario, each instance may reconstruct its own header data. For example, database instance  100  and database instance  126  may retrieve set of persistent metadata  118  and set of persistent metadata  124 , respectively. Database instance  100  may compare version identifiers in set of persistent metadata  118  and database control file  144 . Similarly, database instance  126  may compare version identifiers in set of persistent metadata  124  and database control file  144 . If the version identifiers match, database instance  100  and database instance  126  recreate set of header data  106  and set of header data  132 , respectively. However, if any of the version identifiers fail to match, a corresponding secondary cache may be ignored in its entirety. For example, if a version identifier in database control file  144  matches a version identifier for secondary cache  114  but fails to match a version identifier for secondary cache  120 , set of header data  106  may be recreated, but set of header data  132  may avoid being recreated. 
     Alternatively, instances may come back up at significantly different times after a cluster outage. In such a scenario, the first instance(s) to come back up may compare version identifiers and transfer mastership back to any failed instances that come back up afterward. For example, database instance  126  may retrieve set of persistent metadata  118  and set of persistent metadata  124  from secondary persistent storage  112 . Database instance  126  may compare a version identifier in database control file  144  to a respective version identifier in each of set of persistent metadata  118  and set of persistent metadata  124 . Depending on whether the version identifier in database control file  144  matches any other version identifier, database instance  126  may generate set of header data  106  and/or set of header data  132  in volatile memory  128 . If database instance  100  comes back up, database instance  126  may transfer mastership of secondary cache  114  back to database  100 . 
     Lazy Data Write 
     Further efficiency may be achieved based on reducing computational overhead involved in writing to non-volatile memory. This may be achieved based on writing to non-volatile memory in a lazy manner. In other words, writing to non-volatile memory may occur on an “as-needed” basis. According to some embodiments, such “lazy” writes may include multiple updates to different metadata in a single write. 
     Referring to  FIG. 3 , primary cache  130  includes data  320 - 328 , and secondary cache  114  includes data  300 - 308  and metadata  310 - 318  corresponding to data  300 - 308 . As mentioned above secondary cache  114  may serve as an extension of primary cache  130 . Thus, primary cache  130  and secondary cache  114  generally avoid storing duplicative data. For example, if secondary cache  114  stores data  302 , then primary cache  130  avoids storing data  302 , and if primary cache  130  stores data  320 , then secondary cache  114  avoids storing data  320 . 
     In some example embodiments, however, primary cache  130  and secondary cache  114  may store duplicative data when data stored in secondary cache  114  is being read. In the example of  FIG. 3 , database instance  126  retrieves data  300  from secondary cache  114  and stores a copy of data  300  in primary cache  130 . As mentioned above, data is typically read from volatile memory, so reading data stored in non-volatile memory may involve copying the data to volatile memory. 
     Advantageously, copying data from non-volatile memory to volatile memory without deleting the data from non-volatile memory avoids computational overhead involved in writing to non-volatile memory. For example, moving data  300  from secondary cache  114  to primary cache  130  would have involved invalidating metadata  310  and/or deleting data  300  from secondary cache  114 . During a read, however, data  300  remains unmodified. Thus, data  300  in secondary cache  114  remains consistent with data  300  in primary cache  130 . Hence, secondary cache  114  may continue to store data  300  so that it remains accessible to any other database instance. Furthermore, if data  300  remains unmodified after being read in primary cache  130 , data  300  may be moved back to secondary cache  114 . Such a scenario would involve undoing the invalidating metadata  310  and/or the deleting data  300  from secondary cache  114 , thereby involving multiple sets of writes that could have been avoided. 
     To avoid unnecessarily modifying data and/or metadata stored in non-volatile memory, a database instance may avoid writing to non-volatile memory except when modifying or replacing data stored in non-volatile memory.  FIG. 4  depicts an approach for modifying data stored in non-volatile memory, and  FIG. 5  depicts an approach for replacing data in non-volatile memory. 
     Referring to  FIG. 4 , data  300  is retrieved from secondary cache  114  and copied into primary cache  130  as in  FIG. 3 . However,  FIG. 4  depicts modifying data  300  based on applying change(s)  400  to data  300  in primary cache  130 . In such a scenario, data  300  in secondary cache  114  becomes stale data. Thus, it may be necessary to write to non-volatile memory at least to store indication of invalidity  402 . Referring to  FIG. 4 , data  300  in secondary cache  114  awaits being overwritten. However, indication of invalidity  402 , which corresponds to metadata  310 , may be queued for lazy write to secondary cache  114 . Thus, indication of invalidity  402  is written to secondary cache  114  before a modified version of data  300  is written to primary persistent storage  138 . In case of instance failure, a database recovery process will notice indication of invalidity  402  and avoid recreation of header data or invalidate header data corresponding to data  300 , depending on whether the database recovery process noticed indication of invalidity  402  first or whether a cache recovery process scanned metadata  310  first. 
     In some example embodiments, indication of invalidity  402  may be stored in a header portion of set of persistent metadata  118 . In some example embodiments, metadata  310  may include indication of invalidity  402 . For example, indication of invalidity  402  may be a bit flag or an invalid memory address. Indication of invalidity  402  may prevent database instance  126  from generating header data based on metadata  310 . Additionally or alternatively, indication of invalidity  402  may prevent any other database instances from relying on data  300  in secondary cache  114 . 
     In some example embodiments, modifying data  300  may involve storing modified data on primary persistent storage  138  and/or secondary persistent storage  112 . Storing data on secondary persistent storage  112  may further involve storing, in secondary persistent storage  112 , metadata corresponding to the data. For example, indication of invalidity  402  may be stored in non-volatile memory when a modified version of data  300  is stored in secondary cache  114 . In some example embodiments, the modified version of data  300  may be stored, in non-volatile memory, separately from data  300  and indication of invalidity  402 . For example, the modified version of data  300  may be stored as data  330  (not shown) along with metadata  332  (not shown), which indicates that data  330  is valid. In some example embodiments, data  330  (not shown) may replace data  300 , and metadata  332  (not shown) may serve as indication of invalidity  402  by replacing metadata  310 . 
       FIG. 5  depicts the latter embodiment when new data  500  and metadata  502  replace data  300  and metadata  310 , respectively. For example, data  300  may be, in effect, evicted from secondary cache  114  due to infrequency of access. Note that when new data  500  is moved from primary cache  130  to secondary cache  114 , any copy of new data  500  is deleted from primary cache  130 . Furthermore, replacing metadata  310  with metadata  502  may involve replace indication of invalidity  402  with an indication of validity. 
     Process Overview 
       FIG. 6  is a flow diagram that depicts an approach for recovering data cached by a failed database instance. At block  600 , a first database instance acquires mastership of data stored on a persistent storage that is shared with a second database instance. Thus, the first database instance may determine whether to permit any other database instance to access the data. Accessing data may involve reading, modifying, and/or replacing the data. 
     At block  602 , the first database instance stores the data in a primary cache in a first volatile memory. The first database instance also stores, in the first volatile memory, header data that includes one or more memory addresses of the data. 
     At block  604 , the first database instance moves the data from the first primary cache to a secondary cache in non-volatile memory that is shared with the second database instance. The first database instance may modify the header data to include one or more memory addresses in the secondary cache. 
     At block  606 , the first database instance stores, in the non-volatile memory, metadata that corresponds to the data. The metadata includes one or more memory addresses of the data in the secondary cache. 
     At block  608 , when the first database instance becomes inoperative, the second database instance acquires the mastership of the data that is stored in the secondary cache.  FIG. 7  is a flow diagram that provides further details of block  608 . 
     At block  700 , the second database instance retrieves the metadata from the non-volatile memory. For example, the second database instance may store a copy of the metadata in a second volatile memory that corresponds to the second database instance. 
     At block  702 , based on the metadata, the second database instance recreates the header data in the second volatile memory. The second database instance may avoid recreating any of the header data that corresponds to any of the data that is modified by a database recovery process. 
     At block  704 , based on the header data, the second database instance accesses the data stored in the secondary cache. Unless accessing the data involves modifying or replacing the data, the second database instance may avoid updating the metadata corresponding to the data in the non-volatile memory. 
     Hardware Overview 
     According to one embodiment, the techniques described herein are implemented by one or more special-purpose computing devices. The special-purpose computing devices may be hard-wired to perform the techniques, or may include digital electronic devices such as one or more application-specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs) that are persistently programmed to perform the techniques, or may include one or more general purpose hardware processors programmed to perform the techniques pursuant to program instructions in firmware, memory, other storage, or a combination. Such special-purpose computing devices may also combine custom hard-wired logic, ASICs, or FPGAs with custom programming to accomplish the techniques. The special-purpose computing devices may be desktop computer systems, portable computer systems, handheld devices, networking devices or any other device that incorporates hard-wired and/or program logic to implement the techniques. 
     For example,  FIG. 8  is a block diagram that illustrates a computer system  800  upon which an embodiment of the disclosure may be implemented. Computer system  800  includes a bus  802  or other communication mechanism for communicating information, and a hardware processor  804  coupled with bus  802  for processing information. Hardware processor  804  may be, for example, a general purpose microprocessor. 
     Computer system  800  also includes a main memory  806 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus  802  for storing information and instructions to be executed by processor  804 . Main memory  806  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  804 . Such instructions, when stored in non-transitory storage media accessible to processor  804 , render computer system  800  into a special-purpose machine that is customized to perform the operations specified in the instructions. 
     Computer system  800  further includes a read only memory (ROM)  808  or other static storage device coupled to bus  802  for storing static information and instructions for processor  804 . A storage device  810 , such as a magnetic disk, optical disk, or solid-state drive is provided and coupled to bus  802  for storing information and instructions. 
     Computer system  800  may be coupled via bus  802  to a display  812 , such as a cathode ray tube (CRT), for displaying information to a computer user. An input device  814 , including alphanumeric and other keys, is coupled to bus  802  for communicating information and command selections to processor  804 . Another type of user input device is cursor control  816 , such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor  804  and for controlling cursor movement on display  812 . This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane. 
     Computer system  800  may implement the techniques described herein using customized hard-wired logic, one or more ASICs or FPGAs, firmware and/or program logic which in combination with the computer system causes or programs computer system  800  to be a special-purpose machine. According to one embodiment, the techniques herein are performed by computer system  800  in response to processor  804  executing one or more sequences of one or more instructions contained in main memory  806 . Such instructions may be read into main memory  806  from another storage medium, such as storage device  810 . Execution of the sequences of instructions contained in main memory  806  causes processor  804  to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions. 
     The term “storage media” as used herein refers to any non-transitory media that store data and/or instructions that cause a machine to operate in a specific fashion. Such storage media may comprise non-volatile media and/or volatile media. Non-volatile media includes, for example, optical disks, magnetic disks, or solid-state drives, such as storage device  810 . Volatile media includes dynamic memory, such as main memory  806 . Common forms of storage media include, for example, a floppy disk, a flexible disk, hard disk, solid-state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, NVRAM, any other memory chip or cartridge. 
     Storage media is distinct from but may be used in conjunction with transmission media. Transmission media participates in transferring information between storage media. For example, transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus  802 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infra-red data communications. 
     Various forms of media may be involved in carrying one or more sequences of one or more instructions to processor  804  for execution. For example, the instructions may initially be carried on a magnetic disk or solid-state drive of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system  800  can receive the data on the telephone line and use an infra-red transmitter to convert the data to an infra-red signal. An infra-red detector can receive the data carried in the infra-red signal and appropriate circuitry can place the data on bus  802 . Bus  802  carries the data to main memory  806 , from which processor  804  retrieves and executes the instructions. The instructions received by main memory  806  may optionally be stored on storage device  810  either before or after execution by processor  804 . 
     Computer system  800  also includes a communication interface  818  coupled to bus  802 . Communication interface  818  provides a two-way data communication coupling to a network link  820  that is connected to a local network  822 . For example, communication interface  818  may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface  818  may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface  818  sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information. 
     Network link  820  typically provides data communication through one or more networks to other data devices. For example, network link  820  may provide a connection through local network  822  to a host computer  824  or to data equipment operated by an Internet Service Provider (ISP)  826 . ISP  826  in turn provides data communication services through the world wide packet data communication network now commonly referred to as the “Internet”  828 . Local network  822  and Internet  828  both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link  820  and through communication interface  818 , which carry the digital data to and from computer system  800 , are example forms of transmission media. 
     Computer system  800  can send messages and receive data, including program code, through the network(s), network link  820  and communication interface  818 . In the Internet example, a server  830  might transmit a requested code for an application program through Internet  828 , ISP  826 , local network  822  and communication interface  818 . 
     The received code may be executed by processor  804  as it is received, and/or stored in storage device  810 , or other non-volatile storage for later execution. 
     In the foregoing specification, embodiments of the disclosure have been described with reference to numerous specific details that may vary from implementation to implementation. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense. The sole and exclusive indicator of the scope of the disclosure, and what is intended by the applicants to be the scope of the disclosure, is the literal and equivalent scope of the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction.