Patent ID: 12229053

DETAILED DESCRIPTION

Embodiments of the improved technique will now be described. One should appreciate that such embodiments are provided by way of example to illustrate certain features and principles but are not intended to be limiting.

An improved technique of managing locks in a transaction cache includes opening, in the transactional cache, a first transaction identifying a first plurality of pages to be accessed and a second transaction identifying a second plurality of pages to be accessed, where the first plurality of pages has at least one page in common with the second plurality of pages. The technique further includes, after opening the first transaction and the second transaction, selecting a target page that is highest in the predefined page ordering out of the at least one page in common, where second plurality of pages includes a lower-ordered page that is lower in the predefined page ordering than the target page. The technique further includes, while the first transaction is open, inserting a first lock request of the second transaction into a queue of the target page and preventing insertion of a second lock request of the second transaction into a queue of the lower-ordered page.

In some arrangements, the improved technique is applied to a transactional cache that stores pages of data which may be accessed in transactions. A transaction is a grouping of operations that are committed or aborted atomically. Before accessing a page as part of a transaction, the transaction obtains ownership of a lock on the page to block or otherwise limit access to the page by other transactions. This process helps to maintain data consistency by preventing the other transactions from changing the page while access operations are ongoing. A transaction typically retains ownership of a lock until the transaction completes, upon which the transaction releases the lock.

The improved technique is amenable to a variety of implementations. In some arrangements, a single storage processing node is configured to open multiple transactions in a transactional cache. In these arrangements, the node provides lock queues of respective pages in the transaction cache, into which the node may insert lock requests. The node is configured to prevent deadlock by managing which lock requests will be inserted into the queues and when.

In other arrangements, multiple storage processing nodes have shared access to a transactional cache distributed across the nodes. Each of the nodes may open its own transactions and communicate with other nodes to obtain permission to grant ownership over locks to transactions. Each node in a “multi-node” implementation may apply methodologies as described herein to avoid deadlock both between multiple nodes and internally within a single node.

FIG.1shows an example environment100in which embodiments of the improved technique can be practiced. Here, multiple hosts110are configured to access a data storage system116over a network114. The data storage system116includes one or more nodes120(e.g., node120-1and node120-2), and storage190, such as magnetic disk drives, electronic flash drives, and/or the like. Nodes120may be provided as circuit board assemblies or blades, which plug into a chassis (not shown) that encloses and cools the nodes. The chassis has a backplane or midplane for interconnecting the nodes120, and additional connections may be made among nodes120using cables. In some examples, the nodes120are part of a storage cluster, such as one which contains any number of storage appliances, where each appliance includes a pair of nodes120connected to shared storage. In some arrangements, a host application runs directly on the nodes120, such that separate host machines110need not be present. No particular hardware configuration is required, however, as any number of nodes120may be provided, including a single node, in any arrangement, and the node or nodes120can be any type or types of computing device capable of running software and processing host I/O's.

The network114may be any type of network or combination of networks, such as a storage area network (SAN), a local area network (LAN), a wide area network (WAN), the Internet, and/or some other type of network or combination of networks, for example. In cases where hosts110are provided, such hosts110may connect to the node120using various technologies, such as Fibre Channel, iSCSI (Internet small computer system interface), NVMeOF (Nonvolatile Memory Express (NVMe) over Fabrics), NFS (network file system), and CIFS (common Internet file system), for example. As is known, Fibre Channel, iSCSI, and NVMeOF are block-based protocols, whereas NFS and CIFS are file-based protocols. The node120is configured to receive I/O requests112according to block-based and/or file-based protocols and to respond to such I/O requests112by reading or writing the storage190.

The depiction of node120-1is intended to be representative of all nodes120. As shown, node120-1includes one or more communication interfaces122, a set of processing units124, and memory130. The communication interfaces122include, for example, SCSI target adapters and/or network interface adapters for converting electronic and/or optical signals received over the network114to electronic form for use by the node120-1. The set of processing units124includes one or more processing chips and/or assemblies, such as numerous multi-core CPUs (central processing units). The memory130includes both volatile memory, e.g., RAM (Random Access Memory), and non-volatile memory, such as one or more ROMs (Read-Only Memories), disk drives, solid state drives, and the like. The set of processing units124and the memory130together form control circuitry, which is constructed and arranged to carry out various methods and functions as described herein. Also, the memory130includes a variety of software constructs realized in the form of executable instructions. When the executable instructions are run by the set of processing units124, the set of processing units124is made to carry out the operations of the software constructs. Although certain software constructs are specifically shown and described, it is understood that the memory130typically includes many other software components, which are not shown, such as an operating system, various applications, processes, and daemons.

As further shown inFIG.1, the memory130“includes,” i.e., realizes by execution of software instructions, a transactional cache140, a cache manager150, and a data path160.

Transactional cache140may be a metadata cache configured to manage metadata of data path160in pages142(e.g., pages142athrough142n). Pages142may provide in-memory versions of blocks, where a “block” is a unit of allocatable storage space.

Cache manager150is configured to manage the transactional cache140. For example, cache manager150is configured to receive access requests identifying certain pages142stored in transactional cache140to access as part of a transaction. The cache manager150is further configured to issue lock requests to limit access to certain pages142by other transactions. For example, the cache manager150may receive an access request from a cache client that identifies pages142to be accessed. In response, the cache manager150may insert lock requests into queues of some or all of the identified pages142. The cache manager150is further configured to prevent insertion of lock requests under certain circumstances, as discussed in more detail below.

The cache client may be any client in electronic communication with the transactional cache140. In some arrangements, the cache client is configured to send access requests to the transactional cache140. For example, cache client may be a mapper in data path160that identifies metadata to be stored in the transactional cache140.

Data path160is configured to manage metadata for accessing data of data objects, e.g., by mapping logical data to physical data. As described in more detail below, the data path160may include various logical blocks, mapping pointers, and block virtualization structures, for example, and may track various attributes of blocks. In an example, the data path160provides a predefined page ordering of pages in the transactional cache. For example, the data path160may include different levels of pointers, and such levels may be used at least in part in establishing the predefined page ordering. However, it should be understood that that establishing the predefined page ordering in this manner is merely an example, and the predefined page ordering may be established in other ways.

In an example operation, the hosts110issue I/O requests112to the data storage system116. The node120receives the I/O requests112at the communication interfaces122and initiates further processing. Such processing may involve managing metadata that maps the location of data objects in the data storage system116. Managing such metadata may involve storing the metadata within pages142in the transactional cache140and accessing the pages142in transactions managed by the cache manager150. In some examples, prior to accessing the pages142, the cache manager150issues lock requests to assign ownership of locks on the pages142to transactions.

Managing Locks in an Individual Storage Processing Node

FIG.2shows an example method200that may be performed and/or directed by the cache manager150. Method200provides a high-level summary of various embodiments, including embodiments that have only a single storage processing node and embodiments that have multiple nodes. In multi-node embodiments, each node is configured to manage lock requests of multiple transactions.

At202, the cache manager150opens a first transaction and a second transaction. The transactions may be opened in any order or at the same time. In an example, the first transaction identifies a first plurality of pages to be accessed and the second transaction identifies a second plurality of pages to be accessed.

At204, the cache manager150enqueues a set of lock requests of the first transaction. For example, the cache manager150may insert lock requests of the first transaction into queues of some or all of the pages in the first plurality of pages. In some examples, the cache manager150maintains separate queues for individual pages in the transactional cache. Enqueuing lock requests of the first transaction may occur before enqueuing lock requests of the second transaction.

At206, the cache manager150determines whether the first plurality of pages and the second plurality of pages contain any pages in common. The pages in common are pages to be accessed in both the first transaction and the second transaction.

If act206determines that there are no pages in common, then the operation proceeds to208, whereupon the cache manager150enqueues the lock requests for pages of the second transaction. For example, the cache manager150may insert a lock request of the second transaction into a respective queue of each of the second plurality of pages. It should be understood that if there are no pages in common between the transactions, then the second transaction can proceed without waiting for locks currently owned by the first transaction. In some examples, the lock requests of the second transaction are hard locks, rather than try locks.

If act206determines that there is at least one page in common, then operation proceeds to210, whereupon the cache manager150selects a currently highest-ordered page from the at least one page in common according to a predefined page ordering. The selected page is also referred to herein as a “target” page.

The predefined page ordering is an ordered arrangement of pages and provides a common reference between transactions when selecting lock requests to issue. For example, the first transaction and the second transaction may identify multiple pages in common including a first page and a second page. By referencing the predefined page ordering, the cache manager150may determine that the first page is higher ordered than the second page, and as a result, the cache manager150selects the first page as the target page to lock.

In some arrangements, the predefined page ordering is based on page addressing provided by a cache client, e.g., a mapper. However, using page addressing to determine the predefined page ordering is merely an example, and other arrangements are possible. For example, pages may be ordered randomly, ordered according to page access rates, or ordered in some other manner. In some arrangements, pages in the transactional cache are assigned respective indicators of the predefined page ordering.

The term “highest-ordered” refers to placement of a page relative to other pages in a predefined page ordering. It should be understood that the placement of a page may differ based on how the predefined page ordering is defined. For example, when performing the above-described act210, a first page with a lower page address may be selected over a second page with a higher page address. In this example, the first page is in fact the highest-ordered page out of the first and second pages, even though the first page has a lower page address. Similar variations may be made without departing from the scope of the invention.

At212, the cache manager150enqueues lock requests of the second transaction for the target page and any pages higher in the predefined page ordering than the target page. In some arrangements, these lock requests are hard locks, rather than try locks.

In some arrangements, the second transaction involves accessing one or more lower-ordered pages that are lower in the predefined page ordering than the target page. In such cases, while the first transaction is open, the cache manager150prevents insertion of lock requests of the second transaction into queues of the lower-ordered pages. For example, cache manager150may place a hold on issuing lock requests of the second transaction for the lower-ordered pages. While the hold is in place, the cache manager150will refrain from issuing lock requests of the second transaction for the lower-ordered pages. The lower-ordered pages may include pages in common between the first transaction and the second transaction, as well as pages other than the pages in common.

Advantageously, because the cache manager150prevents lock requests of the second transaction for the lower-ordered pages from being enqueued, the second transaction will not provide an opportunity for deadlock to occur on those pages. As a result, lock requests of the first transaction may be enqueued without needing to calculate potential deadlock conflicts with the second transaction. For example, after placing a hold, the cache manager150may receive a new access request that identifies the lower-ordered pages as pages to be accessed in the first transaction. The cache manager150may immediately issue lock requests of first transaction for these pages without first needing to calculate potential deadlock conflicts with the second transaction. In this manner, these features enable an improvement to the utilization of processor resources and an improvement to response time when servicing access requests. Further, these lock requests may be hard locks, rather than try locks.

At214, the cache manager150monitors a completion status of the first transaction. In some arrangements, the cache manager150waits for the first transaction to complete. Once act214detects that the first transaction has completed, the operation proceeds to216, whereupon the cache manager150enqueues lock requests of the second transaction for the lower-ordered pages. In some examples, these lock requests are hard locks, rather than try locks.

Advantageously, method200enables a reduction in the use of try locks over conventional approaches that allow only one hard lock per transaction. As described above, a try lock is one that is granted if a target page is immediately available but otherwise fails. Although failed try locks can be retried, repetitive use of try locks may result in wasted processor resources. Using method200, cache manager150may enqueue multiple hard locks in each transaction without increasing the risk of deadlock. As a result, method200enables fewer try locks to be issued, increasing utilization of processor resources.

FIG.3shows an example method300that may be performed and/or directed by the cache manager150. Method300is directed to servicing access requests received after a lock request has already been enqueued for a transaction. Method300may be performed in conjunction with method200, described above.

At302, the cache manager150enqueues a set of lock requests of a transaction. Act302may be any of acts204,208,212,216, and the like. For example, the cache manager150may receive a first access request that identifies pages to access in a transaction. In response to receiving the first access request, the cache manager150may insert lock requests of the transaction into respective queues of the identified pages.

At304, after enqueuing the lock requests, the cache manager150receives a new access request in the same transaction. The new access request identifies a set of new pages to be accessed in the transaction.

At306, the cache manager150selects a page identified in the new access request. The selected page may be, for example, the highest-ordered page out of the set of new pages according to a predefined page ordering. In some arrangements, the predefined page ordering is the same page ordering as the one described in connection with method200.

At308, the cache manager150determines whether the selected page is higher in the predefined page ordering than the highest-ordered page identified by the transaction prior to receiving the new access request. For example, the cache manager150may compare the pages identified in a prior access request with pages identified in the new access request.

If act308determines that the selected page is higher in the predefined page ordering than the currently highest-ordered page, then the operation proceeds to310, whereupon the cache manager150issues a try lock for the selected page in the transaction.

If act308determines that the selected page is not higher in the predefined page ordering than the currently highest-ordered page, then the operation proceeds to312, whereupon the cache manager150determines whether it is prevented from inserting lock requests of the transaction into a queue of the selected page. In some arrangements, the cache manager150identifies a hold that prevents insertion of such a lock request, e.g., a hold described above in connection with act212of method200.

If act312determines that the cache manager150is not prevented from inserting a lock request of the transaction into a queue of the selected page, then the operation proceeds to314, whereupon the cache manager150enqueues a hard lock for the selected page in the transaction.

At316, the cache manager150determines whether the new access request identifies any additional pages, and if so, the operation proceeds back to306, whereupon the cache manager150selects another page identified in the new access request. Method300may proceed until each of the pages in the new access request are enqueued.

Advantageously, in conjunction with method200, method300enables improved utilization of processor resources while avoiding deadlock. In some arrangements, both methods200and300utilize the same predefined page ordering to select the types of lock requests to issue. In accordance with method200, the cache manager150may use the predefined page ordering to prevent insertion of lock requests of an earlier transaction into queues of certain pages, denying an opportunity for the earlier transaction to cause deadlock to occur on those pages. Subsequently, in accordance with method300, the cache manager150may receive an access request in a later transaction identifying the certain pages. As described, the cache manager150may issue lock requests of the later transaction for the certain pages without first needing to calculate potential deadlock conflicts with the earlier transaction. In this manner, these features enable an improvement to the utilization of processor resources and an improvement to response time when servicing access requests. Further, these lock requests may be hard locks, enabling fewer try locks to be issued.

FIG.4athroughFIG.4e(collectively referred to asFIG.4) show an example arrangement for managing locks in a transactional cache utilizing methods200and300.FIG.4includes transactional cache140that stores pages142athrough142d. In an example, each of pages142athrough142dhas respective queues444athrough444din which lock requests may be inserted. When a transaction completes, locks owned by the transaction are released.

InFIG.4a, the cache manager150receives a first access request410athat identifies pages142band142cto be accessed in a first transaction (as shown as “TX1”). The cache manager150issues command420ato insert lock requests into respective queues444band444c. As there are currently no enqueued locks for pages142band142c, the cache manager150may immediately assign ownership of the lock on pages142band142cto the first transaction.

InFIG.4b, the cache manager150receives a second access request410bthat identifies pages142athrough142dto be accessed in a second transaction (as shown as “TX2”). However, because both the first transaction and the second transaction identify pages142band142cto be accessed, pages142band142care pages in common between the transactions. As a result, the cache manager150selects the highest-ordered page from among the pages in common according to a predefined page ordering. In this example, suppose that the predefined page ordering places page142ahigher than page142b, page142bhigher than page142c, and page142chigher than page142d. The cache manager150thus selects page142bas the highest-ordered page out of the pages in common (pages142band142c).

The cache manager150then enqueues a lock request of the second transaction for the selected page (page142b) behind the lock request of the first transaction. The cache manager150further places a hold430on pages142cand142d, as they are lower in the predefined page ordering than the selected page.

Note that the second access request410balso identifies page142athat (1) is not one of the pages in common and (2) is higher in the predefined page ordering than the pages in common. As explained in further detail below in connection withFIG.4c, a lock request for page142amay be inserted without causing deadlock. As a result, the cache manager150issues command420bto insert lock requests into respective queues444aand444b. Both lock requests are hard locks that are enqueued regardless of whether another transaction has ownership of locks on the respective pages.

InFIG.4c, the cache manager150receives a third access request410cthat identifies page142ato be accessed in the first transaction. In this example, page142ais higher in the predefined page ordering than the pages for which locks have been enqueued in the first transaction (pages142band142c). As a result, the cache manager150issues a command420cto insert a try lock for page142a. As a conflicting lock request is already enqueued, the try lock fails.

Advantageously, use of the predefined page ordering enables deadlock to be avoided. Note that denying the try lock means that the first transaction does not wait behind the second transaction for page142awhile the second transaction waits behind the first transaction for page142b. In this manner, deadlock does not occur because the second transaction does not block the first transaction from completing and vice versa.

InFIG.4d, the cache manager150receives a fourth access request410dthat identifies page142dto be accessed in the first transaction. In this example, page142dis lower in the predefined page ordering than the pages for which locks have been enqueued in the first transaction (pages142band142c). As a result, the cache manager150issues a command420cto insert a hard lock for page142d.

InFIG.4e, the first transaction has completed and the locks owned by the first transaction have been removed from the queues of the respective pages (queues444b,444c, and444d). Afterwards, the cache manager150lifts the hold430on pages142cand142dand issues command420eto insert lock requests into respective queues444cand444d. The second transaction thus obtain ownership of the locks on pages142cand142d.

Managing Locks in Multiple Storage Processing Nodes

FIG.5aandFIG.5b(collectively referred to asFIG.5) show an example arrangement in which multiple storage processing nodes manage locks in a transactional cache. In the example arrangement, nodes have shared access to a transactional cache. Further, each node maintains its own queues of pages in the transactional cache and may insert lock requests into its queues independently from other nodes. For example, a first node may open a first transaction and insert a lock request into a queue managed by the first node for a page in the transactional cache. Simultaneously, a second node may open a second transaction and insert a conflicting lock request into a queue managed by the second node for the same page. However, although conflicting lock requests may be enqueued in different nodes at the same time, a transaction cannot own a lock that conflicts with a lock owned by another transaction. As addressed at least in part herein, there is a need to resolve such conflicts prior to granting ownership of a lock to a transaction.

The example arrangement uses a concept called “staging” to resolve conflicts. A lock request is considered “staged” when the lock request reaches the head of a queue of a target page while the target page is unlocked. In some examples, after a node stages a lock request, the node then sends a peer permission request to other nodes (also referred to as “peer nodes”) that are capable of accessing the target page. The peer permission request identifies a transaction and pages to be accessed in the transaction and enables the nodes to identify and resolve any potential conflicts. As a result, the nodes may resolve conflicts prior to locking the pages while the lock requests are staged, rather than immediately granting the lock requests and potentially causing deadlock to occur.

InFIG.5, nodes520-1and520-2collectively manage access to pages142athrough142din transactional cache540(as shown as transactional cache540-1and transactional cache540-2). Node520-1manages queues544athrough544dcorresponding to respective pages142athrough142d. Similarly, node520-2manages queues546athrough546dcorresponding to the same respective pages.

InFIG.5a, node520-1inserts lock requests of a first transaction (as shown as “TX1”) into respective queues544band544c. As the lock requests are at the heads of their respective queues while the pages are unlocked, the lock requests are considered staged. Likewise, node520-2inserts lock requests of a second transaction (as shown as “TX2”) into respective queues546athrough546d, and these lock requests are considered staged.

After staging the lock requests, each node sends a peer permission request to the other node (e.g., using communication interfaces122). In an example, node520-1sends peer permission request570-1to node520-2, which identifies staged pages142band142cto be locked in the first transaction. Similarly, node520-2sends peer permission request570-2to node520-1, which identifies staged pages142athrough142dto be locked in the second transaction. It should be understood thatFIG.5is an example arrangement and any number of additional nodes (not shown) may access to the same set of pages142athrough142d. In such circumstances, the peer permission requests520-1and520-2may also be sent to each of the additional nodes.

Upon receiving the peer permission requests, the nodes520-1and520-2resolve potential deadlock conflicts based on a “primary wins” scheme. Under this scheme, one node is designated as the “primary” node and the other node is designated as the “secondary” or “non-primary” node. Staged lock requests identified by the primary node have priority over staged lock requests identified by the secondary node. Primary and non-primary designations may be assigned at a variety of different times, e.g., at startup, after a predetermined time interval, upon discovering a potential deadlock conflict, and so forth. Further, the nodes may assign designations in a variety of different manners, e.g., randomly, according to node characteristics, and so forth.

InFIG.5b, node520-1has been designated as the primary node while node520-2has been designated as the secondary node. As a result, the staged lock requests of the first transaction opened by node520-1have priority over the staged lock requests of the second transaction opened by node520-2.

Note that methodologies used to manage deadlock in an individual node may still apply in a multi-node setting. For example, node520-1receives peer permission request570-2identifying pages142athrough142dto be locked in the second transaction. However, node520-1has already enqueued lock requests of the first transaction for pages142band142c, meaning pages142band142care pages in common between the first transaction and the second transaction. As a result, node520-1performs a process similar to the one described above in connection withFIG.4b. Along these lines, node520-1selects page142bas a target page that is highest in the predefined page ordering out of the pages in common. Node520-1further identifies pages142aas a page higher in the predefined page ordering than the target page. As a result, node520-1enqueues lock requests of the second transaction for pages142aand142band prevents insertion of lock requests of the second transaction for pages lower in the predefined page ordering than the target page (pages142cand142d). Node520-1then sends response580-1to node520-2indicating queue changes.

Likewise, in node520-2, lock requests from the primary node are enqueued before lock requests from the secondary node (lock requests of the first transaction are staged in queues546band546c). Following methodologies used to manage deadlock in a single node, node520-2removes lock requests of the second transaction from queues546cand546d. Node520-2then sends response580-2to node520-1indicating queue changes.

FIG.6aandFIG.6b(collectively referred to asFIG.6) show an example arrangement of an exception to the “primary wins” scheme described above in connection withFIG.5. This exception arises when a particular transaction already owns a lock on a first page and then the nodes stage conflicting lock requests for a second page. In such circumstances, deadlock may be avoided by giving priority to the particular transaction to obtain a lock on the second page, regardless of whether the particular transaction was opened by the primary node.

InFIG.6, nodes620-1and620-2collectively manage access to pages142athrough142din transactional cache640(as shown as transactional cache640-1and transactional cache640-2). Additionally, node620-1manages queues644athrough644dcorresponding to respective pages142athrough142d. Likewise, node620-2manages queues646athrough646dcorresponding to the same respective pages.

In this example, primary node620-1opens a first transaction (as shown as “TX1”) and secondary node620-2opens a second transaction (as shown as “TX2”). Further, the second transaction obtains a lock on page142b. Later, node620-1inserts lock requests of a first transaction for pages142aand142binto corresponding queues644aand644c. Additionally, node620-2inserts a lock request of a second transaction for page142ainto corresponding queue646a. Node620-1then sends peer permission request670-1to node620-2, identifying pages142aand142ato be locked in the first transaction. Likewise, node620-2sends peer permission request670-2to node620-1, identifying page142cto be locked in the second transaction.

As the second transaction already owns a lock on a page in the transactional cache, the second transaction has priority to obtain locks regardless of whether the transaction was opened by the secondary node. As a result, inFIG.6b, node620-1de-stages the lock request of the first transaction in queue644aand stages a lock request of the second transaction in the same queue. Node620-1then sends response680-1to node620-2indicating queue changes. Similarly, node620-2enqueues lock requests of the first transaction in queues646aand646b. Node620-2then sends response680-2to node620-1indicating queue changes. In this manner, deadlock does not occur because the second transaction does not block the first transaction from completing and vice versa.

FIG.7shows an example data path160ofFIG.1in greater detail. The data path160provides an arrangement of metadata used for accessing data in the data storage system116. In some examples, the data path160may be used to provide a predetermined page ordering of pages in the transactional cache140.

As shown, the data path160includes a namespace710, a mapping structure720(a “mapper”), a virtual block layer730, and a physical block layer740. The namespace710is configured to organize logical data, such as that of LUNs, file systems, virtual machine disks, snapshots, clones, and the like. In an example, the namespace710provides a large logical address space and is denominated in blocks712. The mapper720is configured to point logical blocks712in the namespace710to respective descriptors732of virtual blocks in the virtual block layer730. The mapper720may include multiple levels of pointers, such as tops722, mids724, and leaves726, which together are capable of mapping large amounts of data. The virtual block layer730provides a level of indirection between the mapper720and the physical block layer740, allowing physical blocks to be moved without disturbing pointers in the mapper720. Physical blocks742in the physical block layer740are typically compressed.

In an example, the multiple levels of pointers in mapper720may provide a predefined page ordering used selectively insert lock requests into queues of a transactional cache. In an example, tops722are higher in the predefined page ordering than mids724, and mids724are higher in the predefined page ordering than leaves726. Further, pointers within a particular level may provide more specific page ordering. For example, a first pointer within tops722may be higher than second pointer within tops722. Ordering pointers within a level may be performed in a variety of different manners, e.g., using indicators assigned to the pointers, offset locations within a level, and so forth. It should be understood that using the levels in mapper720to generate a predefined page ordering is merely an example and different manners of generating a predefined page ordering are possible.

An improved technique has been described for managing locks in a transactional cache. The technique includes opening, in the transactional cache, a first transaction identifying a first plurality of pages to be accessed and a second transaction identifying a second plurality of pages to be accessed, where the first plurality of pages has at least one page in common with the second plurality of pages. The technique further includes, after opening the first transaction and the second transaction, selecting a target page that is highest in the predefined page ordering out of the at least one page in common, where second plurality of pages includes a lower-ordered page that is lower in the predefined page ordering than the target page. The technique further includes, while the first transaction is open, inserting a first lock request of the second transaction into a queue of the target page and preventing insertion of a second lock request of the second transaction into a queue of the lower-ordered page.

Having described certain embodiments, numerous alternative embodiments or variations can be made. For example, although some arrangements have been described with reference to pages142athrough142d, these pages are merely an example. Other embodiments may include more or fewer pages or other storage objects. Similarly, although some arrangements have been described with reference to a first transaction and a second transaction, more or fewer transactions may be opened by the same or different nodes.

Also, although embodiments have been described that involve one or more data storage systems, other embodiments may involve computers, including those not normally regarded as data storage systems. Such computers may include servers, such as those used in data centers and enterprises, as well as general purpose computers, personal computers, and numerous devices, such as smart phones, tablet computers, personal data assistants, and the like.

Further, although features have been shown and described with reference to particular embodiments hereof, such features may be included and hereby are included in any of the disclosed embodiments and their variants. Thus, it is understood that features disclosed in connection with any embodiment are included in any other embodiment.

Further still, the improvement or portions thereof may be embodied as a computer program product including one or more non-transient, computer-readable storage media, such as a magnetic disk, magnetic tape, compact disk, DVD, optical disk, flash drive, solid state drive, SD (Secure Digital) chip or device, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), and/or the like (shown by way of example as medium218inFIG.2). Any number of computer-readable media may be used. The media may be encoded with instructions which, when executed on one or more computers or other processors, perform the process or processes described herein. Such media may be considered articles of manufacture or machines, and may be transportable from one machine to another.

As used throughout this document, the words “comprising,” “including,” “containing,” and “having” are intended to set forth certain items, steps, elements, or aspects of something in an open-ended fashion. Also, as used herein and unless a specific statement is made to the contrary, the word “set” means one or more of something. This is the case regardless of whether the phrase “set of” is followed by a singular or plural object and regardless of whether it is conjugated with a singular or plural verb. Also, a “set of” elements can describe fewer than all elements present. Thus, there may be additional elements of the same kind that are not part of the set. Further, ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein for identification purposes. Unless specifically indicated, these ordinal expressions are not intended to imply any ordering or sequence. Thus, for example, a “second” event may take place before or after a “first event,” or even if no first event ever occurs. In addition, an identification herein of a particular element, feature, or act as being a “first” such element, feature, or act should not be construed as requiring that there must also be a “second” or other such element, feature or act. Rather, the “first” item may be the only one. Also, and unless specifically stated to the contrary, “based on” is intended to be nonexclusive. Thus, “based on” should be interpreted as meaning “based at least in part on” unless specifically indicated otherwise. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and should not be construed as limiting.

Those skilled in the art will therefore understand that various changes in form and detail may be made to the embodiments disclosed herein without departing from the scope of the following claims.