Moving data between data stores

A data object may be moved from a source data store to a destination data store via replication. The replication is initiated when an original data object in a source data store that is capable of being both read from and being written to is read. Following the read, the original data object is then duplicated to a destination data store. The duplicate data object is provided with a state that indicates the duplicate object is duplicated from the source data store and can be read but cannot accept a data write. Subsequently, the state of the original data object is changed to can be read but cannot be written to using optimistic locking. Further, the state of the duplicate data object is also modified to being capable of both read from and written to with the use of optimistic locking. The replication is completed with the deletion of the original data object from the source data store.

BACKGROUND

A centralized consistent location service is a feature of a distributed data storage system. The consistent location service may be responsible for the coordination of data relocations between different data stores of the distributed data storage system. However, a distributed data storage system that uses a centralized consistent location service may need to frequently interact with the consistent location service during normal operation, thereby decreasing its operational efficiency. The maintenance of the consistent location service may also consume additional computing and technical support resources, thereby increasing the operational cost of the distributed data storage system. Additionally, any malfunction of the consistent location service may also detrimentally impact the operation of the distributed data storage system.

Moreover, a centralized consistent location service may not be present in a tiered data storage system. Generally speaking, a tiered data storage system stores data in different types of data stores based on access criteria, frequency of use, security concerns, and other factors. For example, important data of a business that are frequently accessed and updated in real time may be stored in the “first tier” data stores of tiered data storage system. The data stores of the “first tier” may reside on storage servers that provide the highest accessibility, durability and/or reliability. In contrast, less mission critical data of the business may be stored in the data store of a “second tier”. The data stores of the “second tier” may reside on storage servers that are less robust and reliable. However, these storage servers may be less expensive to operate. Finally, historical or archival data of the business may be stored in the data stores of a “third tier”. The data stores of the “third tier” may reside on storage servers that are the most economical to operate, but offer the least amount of accessibility, durability, and/or reliability. Thus, in this example, as a particular piece of data become less mission critical and more historical, the particular piece of data may be incrementally relocated from data stores of the “first tier”, to the data stores of the “second tier”, and then finally to the data stores of the “third tier”.

DETAILED DESCRIPTION

Overview

This disclosure is directed, in part, to the movement of data objects between tiered data stores of a data storage system without the use of a central consistent location service. The data storage system may be a tiered data storage system that includes data stores that resides in different tiers, in which each tier of data stores provide different access speed, durability, reliability, and/or operational cost capabilities. Accordingly, data objects may be moved between the data stores of the tiered data storage system as the access criteria, frequency of use, value, security needs, and/or other factors of each data object changes over time. The movement of the data objects between different data stores may be accomplished through a series of replication steps that moves each data object from a source data store to a destination data store. Moreover, the movement of the data objects through these replication steps may be protected by optimistic locking to prevent transaction conflicts, as well as mechanisms that provide error recovery and retry in the event of failure in the replication steps. Accordingly, the data relocation logics and mechanisms described herein may enable the efficient movement of data objects between different data stores without the use of a central consistent location service. In this way, the additional computing and technical support resources associated with maintaining the central consistent location service may be reduced or avoided. In various instances, the data storage system may be a database system that is based on the relational database management system (RDBMS) model, or a binary large object (blob) distributed storage system. As such, the data storage system may have guaranteed read-write consistency and optimistic locking capabilities.

In some embodiments, a data object may be moved from a source data store to a destination data store via replication. The replication is initiated when an original data object in a source data store that is capable of being both read from and being written to is read. Following the read, the original data object is then duplicated to a destination data store. The duplicate data object is provided with a state that indicates the duplicate object is duplicated from the source data store and can be read but cannot accept a data write. Subsequently, the state of the original data object is changed to can be read but cannot be written to using optimistic locking. Further, the state of the duplicate data object is also modified to being capable of both read from and written to with the use of optimistic locking. The replication is completed with the deletion of the original data object from the source data store.

Illustrative System Architecture

FIG. 1shows an illustrative computing environment100for moving data between data stores of a tiered data storage system without the use of a consistent location service. The environment100may include applications102(1)-102(N) that may reside on one or more client devices104, one or more servers106that include logics for moving data between tiered data stores, and a plurality of tiered data stores108(1)-108(N) of a tiered data storage system110that resides on one or more storage servers112.

Each of the client devices104may be electronic device that is capable of receiving, processing and transmitting data to another device. In various embodiments, each of the client devices104may be a laptop computer, a desktop computer, a server, or another electronic device that is equipped with network communication components, data processing components, and at least one electronic display for displaying data. The application102(1)-102(N) may include any application that uses a distributed data storage system. For example, the applications102(1)-102(N) may include a web transaction application that receives online purchase requests from users, an online banking application that provide users with web access to financial information, an corporate inventory application that keep real time track of inventory, and/or the like. In some embodiments, at least one of the applications102(1)-102(N) may also be implemented on the servers106, rather than on the one or more client devices104.

The storage servers112that implement the data stores108may be located in a single data center, or across multiple data centers. Moreover, the data centers may be located at a single geographical location, or across multiple geographical locations around the globe. In various embodiments, the data stores108(1)-108(N) may be traditional data store, such as a relational database management system (RDBMS) data store, or blob data stores. Additionally, the data stores108(1)-108(N) may be tiered data stores that have different characteristics. For example, the data store108(1) may be a first tier data store that has the highest accessibility, durability and/or reliability. On the other hand, the data store108(N) may be second tier data store that is less robust and reliable than the data store108(1). As part of a tiered data storage system110, the data stores108(1)-108(N) have guaranteed read-write consistency and optimistic locking capabilities. In alternative embodiments, the logics for moving data between the tiered data stores108(1)-108(N) may be provided in one or more of the storage servers112rather than on the servers106.

The client devices104, the server106, and the storage servers112may be communicatively connected by a network114. The network114may be a local area network (“LAN”), a larger network such as a wide area network (“WAN”), or a collection of networks, such as the Internet. Protocols for network communication, such as TCP/IP, may be used to implement the network114. Although embodiments are described herein as using a network such as the Internet, other distribution techniques may be implemented. In various embodiments, the applications102(1)-102(N) may communicate with the data stores108(1)-108(N) of the tiered data storage system110through the network114via a middleware interface layer, such as a database abstraction layer. The middleware interface layer may reside on at least one of the storage servers112or the server106to enable the applications102(1)-102(N) to store, modify, delete, and retrieve data from the tiered data stores108(1)-108(N).

The server106may include one or more processors116, a memory118, and user controls that enable a user to interact with the server106. User controls may include, but are not limited to, combinations of one or more of keypads, keyboards, mouse devices, touch screens, microphones, speech recognition packages, and any other suitable devices or other electronic/software selection methods. The memory118may include volatile and/or nonvolatile memory, removable and/or non-removable media implemented in any method or technology for storage of information, such as computer-readable instructions, data structures, program modules or other data. Such memory may include, but is not limited to, random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology; CD-ROM, digital versatile disks (DVD) or other optical storage; magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices; and RAID storage systems, or any other medium which can be used to store the desired information and is accessible by a computer system.

The operating system120may be stored in memory118. The operating system120may include components that enable the server106to receive data via various inputs (e.g., user controls, network interfaces, and/or memory devices), and process the data using the one or more processors116to generate output. The operating system120may include one or more components that present the output (e.g., display an image on an electronic display, store data in memory, transmit data to another electronic device, etc.). Additionally, the operating system120may include other components that perform various other functions generally associated with an operating system.

In addition to the operating system120, the memory118may further store other components, which may include routines, programs instructions, objects, and/or data structures that perform particular tasks or implement particular abstract data types. The movement of data objects between different data stores of the data stores108(1)-108(N) may be facilitated by a data relocation component122that is stored in the memory118. In alternative embodiments, rather than being stored in the memory118, the data relocation component122may reside in a similar memory that is in one of the storage servers112. A queue component124may also be stored in the memory118. In various embodiments, the queue component124may store data object relocation requests from the applications102(1)-102(N) so that such requests may be fulfilled by the data relocation component122. In some embodiments, the data relocation component122and the queue component122may be a part of the middleware interface layer. The data replication steps performed by the data relocation component122are further illustrated inFIGS. 2-8.

FIG. 2shows an illustrative block diagram of the initial steps for moving a data object between tiered data stores of a tiered data storage system110without the use of a consistent location service. As shown, a data object that is to be moved by the data relocation component122, such as the data object202(a), may include an identifier204and a state field206. The data object202(a) may be any piece of data within some type of data container. The state field206may be a piece of metadata that is associated with the data object202(a) and stored with the data object202(a). In embodiments in which the tiered data storage system110is a RDBMS, state field206may be stored in a data column (e.g., a SITE column) of a database table that also stores the data object202(a). In other embodiments in which the tiered data storage system110is a blob storage system, the state field206may be prefix or suffix metadata that is appended to the data object202(a) (e.g., a first byte of data or a last byte of data in the data object202(a)). In such embodiments, the data object202(a) may include special indicators that indicate the respective locations of the state field206and the substantive data in the data object202(a), so that the data relocation component122may access the two types of data via a sparse read and/or update. Accordingly, because the state field206may be either stored within the same table as the data object202(a), or actually stored within the data object202(a), the state field206may be protected by the same optimistic locking that protects the data object202(a).

In various embodiments, the state field206of the data object202(a) may hold up to three pieces of the information regarding the data object202(a): (1) a locking state; (2) a pointer to a data store; and (3) whether the data object202(a) has a state of “to” or “from” with respect to the data store, as embodied by one of a “to” indicator or a “from” indicator.

The locking state may be either “locked” or “unlocked”, as indicated by a corresponding indicator. Accordingly, the tiered data storage system110may be configured to selectively permit or refuse an application, such as the application102(1), write access to the data object202(a). Specifically, a state of “locked” is a restricted state that may indicate to the tiered data storage system110to permit an application to read the data in the data object202(a), but not to write to the data object202(a). In contrast, a state of “unlocked” is an unrestricted state that may indicate to the tiered data storage system110that an application is to be permitted both read and write access to the data object202(a).

The pointer in the state field206may point, depending on the circumstance, to a location of a source data store that the data object202(a) is originally duplicated from, or to a destination data store to which a copy of data object202(a) is created. For example, when the data object202(a) currently resides on a data store “A”, the state field206of the data object202(a) may include a pointer that points to a data store “B”. Likewise, when the data object202(a) currently resides on a data store “B”, the state field206may include a pointer that points to data store “A”.

The state field206may include one of a “to” indicator (destination indicator) or a “from” indicator (source indicator) that is related to the pointer in the state field206. Each of the “to” indicator and the “from” indicator may be a duplication indicator that indicate a direction of duplication. The “from” indicator may be present in the state field206when the data object202(a) is duplicated from another data object that is stored in source data store. In contrast, the “to” indicator may be present in the state field206when the data object202(a) is a duplicate data object that has been duplicated to a destination data store. In various embodiments, the three types of information described above may be stored in the state field206as a single data string, such as comma separate values (CSV). For example, the state field206may contain the information: “locked, to, database B”.

The data object202(a) may further include a version number208that is changed by the tiered data storage system110each time the data in the data object202(a) is modified. For example, in an instance in which the data object202(a) is a text document, the version number208may be changed when the content of the text document is modified. Moreover, since the state field206of the data object202(a) is provided with the same optimistic locking protection, the version number208may also change when the information in the state field206is modified in any way for any reason. In various embodiments, the version number may be an incrementally updated value, a globally unique identifier (GUID), a current time, or a Lamport time. As further described below, with the use of the state field206and the version number208, the data relocation component122may move the data object202(a) from a source data store to a destination data store in an optimistically consistent manner.

As further shown inFIG. 2, the data relocation component122may instantiate a worker function210to “move” the data object202(a) from a source data store “A”212to a destination data store “B”214via a series replication steps. The data relocation component122may instantiate the worker function210upon a request from an application, such as the application102(1). In various embodiments, the data store “A”210and the data store “B”212may belong to the same tier of the tiered data storage system110, or belong to different tiers of the tiered data storage system110. As further described below, the “move” actually involves the creation of a duplicate data object202(b) in the data store “B”214that contains the substantive data of the data object202(a), and the deletion of the data object202(a) from the data store “A”212. Once created, the duplicate data object202(b) may include its own state field216, a version number218, and an identifier220that is identical to the identifier204.

The information in the state field206of the data object202(a) and information in the state field206of the data object202(b) during the replication steps may be illustrated inFIG. 2by a table222. Specifically, column224of the table222may show information in the state field206of the data object202(a). Likewise, column226of the table222may show information in the state field216of the data object202(b). The data relocation component122may use the information in the state field206of the data object202(a) and the state field216of the data object202(b) to ensure optimistic consistency during the replication steps.

As shown in table222, at step “1” of the replication, the worker function210may verify that the original data object202(a) in the data store “A”212has a state of “unlocked”, as indicated by the state field206. The “unlocked” state means that the data object202(a) may be both read and modified by an application. No other information is otherwise contained in the state field206. At this point, as shown in the column226, no corresponding state exists as the data object202(b) and its corresponding state field216do not yet exist.

At step “2” of the replication, the worker function210may read the data that is in the data object202(a), as well as the version number208of the data object202(a). As shown in column224, the state of the data object202(a) remains “unlocked” at this step.

At step “3” of the replication, the worker function210may create a duplicate of the original data object202(a), which is the data object202(b), in the data store “B”214. As described above, the duplicate data object202(b) may be created with its own identifier220that is identical to the identifier204, as well as its own state field216. At this point, the state field216may hold the information “locked (from) (data store A)”, which indicates that the data object202(b) is locked from write attempts by an application, and that the data object202(b) is duplicated from the data store “A”212.

The creation of the data object202(b) on the data store “B”214may be protected by redundant duplication prevention. In other words, prior to creating the data object202(b), the worker function210may verify that a data object with an identifier that is identical to the identifier204does not already exist on the data store “B”214. Thus, the worker function210may only create the data object202(b) if no such data object preexists. Conversely, the worker function210may abort the creation of the data object202(b) and reattempt the replication if the worker function210determines that a data object with the identifier204already exists on the data store “B”214.

At step “4” of the replication, the worker function210may change the information in state field206of the data object202(a) to “locked (to) (data store B)”, as shown in the column224. The changed information in the state field206may indicate that the data object202(a) is locked from any write attempts by an application, and that the data object202(a) is duplicated to the data store “B”214. On the other hand, as shown in column226, the information in the state field216of the data object202(b) may remain as “locked (from) (data store A)” at step “4”.

The change of the state field206of the data object202(a) at step “4” may be protected by optimistic locking. Recall that the version number208of the data object202(a) was read by the worker function210at step “2” of the replication. Moreover, the version number208of the data object202(a) may be changed if any data in the data object202(a), including the state field206, is modified by another worker function. Thus, the worker function210may pass the version number208, as read at step “2”, to the optimistic concurrency logics of the tiered data storage system110. In turn, the tiered data storage system110may read the version number208for a second time prior to saving the change to the information in the state field206. The tiered data storage system110may only save the change to the information in the state field206when the version number208that it received from the worker function210matches the current version number208that the tiered data storage system110read for itself. As a result, if the version number208had already been changed prior to step “4” due to some data modification by another worker function, the tiered data storage system110may reject the change to the information in the state field206of the data object202(a). In turn, the worker function210may abort the change and delete the data object202(b) from the data store “B”214. However, in some embodiments, the worker function210may abort the change without deleting the data object202(b) from the data store “B”214. Instead, as further described below, the data object202(b) in the data store “B” may simply be overwritten during a retry attempt of the move of the data object202(a) to the data store “B”214.

On the other hand, if the two readings of the version number208match, the optimistic concurrency logic of the tiered data storage system110may permit the changes made by the worker function210to the state field206to be saved. Moreover, because the worker function210changed the state field206, the optimistic concurrency logics of the tiered data storage system110may subsequently change the version number208of the data object202(a).

Next, as further shown in column226, the worker function210may change the information in the state field216so that the state of the data object202(b) is “unlocked” at step “5” of the replication. In this way, the state field216may no longer indicate that the data object202(b) was duplicated from data store “A”212. Further, the “unlocked” state means that the data object202(b) may be both read and modified at this point. On the other hand, as shown in the column224, the information in the state field216of the data object202(a) may remain as “locked (to) (data store B)” at step “5”.

The change of the information in the state field216of the data object202(b) at step “5” may also be protected by optimistic locking. Thus, the worker function210may pass the version number218, which the worker function210obtained during the creation of the data object202(b), to the optimistic concurrency logics of the tiered data storage system110. In turn, the tiered data storage system110may read the version number218for a second time prior to saving the change to the information in the state field216. Thus, the tiered data storage system110may only save the change to the information in the state field216when the version number218that it received from the worker function210matches the version number218that the tiered data storage system110read for itself. As a result, if the version number218had already been changed prior to step “5” due to some data modification by another worker function, the tiered data storage system110may reject the change to the information in the state field216of the data object202(b). In turn, the worker function210may abort the change.

On the other hand, if the two readings of the version number218match, the optimistic concurrency logic of the tiered data storage system110may permit the changes made by the worker function210to the state field216to be saved. Moreover, because the worker function210changed the state field216, the optimistic concurrency logics of the tiered data storage system110may subsequently change the version number218of the data object202(b).

At step “6” of the replication, the worker function210may delete the data object202(a) (along with the state field206and version number208) from the data store “A”212to complete the “move” of the data object202(a) to the data store “B”214. Thus, as shown in the column224, the state field206no longer exists due to the deletion of the data object202(b). The worker function210may inform the data relocation component122of the completion once it finishes the replication.

In various embodiments, the data relocation component122may make use of guaranteed retries throughout the replication described above. Accordingly, in cases of replication failures or aborts, a worker function, such as the worker function210, may infer the step in the replication where the failure occurred, and resume the replication from the next appropriate step in a retry attempt. This inference is possible because the combination of state fields at each replication step is unique. For example, assuming that data in the data object202(a) was found to have been previously modified when the worker function210reached step “4”, and optimistic locking resulted in the abort of replication by the worker function210. Subsequently, at the retry attempt, the worker function210may be reinitiated by the data relocation component122to resume at step “2”, that is, once again read the data in the data object202(a), as well as the version number208of the data object202(a), and create the data object202(b) on the data store “B”214. In some instances, this creation of the data object202(b) during retry may overwrite any existing data object202(b) that is left on the data store “B”214from the previously aborted replication. Thus, assuming that the version number208remains the same in this retry through step “4”, the worker function210may complete the replication during this second retry attempt.

In some embodiments, the data relocation component122may be configured to repeat the performance of retry attempts until a successful completion of the replication is reached. In such embodiments, the data relocation component122may employ an exponential back off algorithm to time such retry attempts. For example, the exponential back off may decrease the rate at which repeated retries are attempted so that the possibility of conflicting with data modifications by other worker functions is gradually reduced, and the chance of a successful replication completion is gradually increased.

The role of optimistic locking in protecting each replication that “moves” a data object from a first data store to a second data store, as well as the utility of inferring a step where a failure occurred and retrying a replication from the next appropriate step, may be apparent in a scenario in which multiple worker function are concurrently attempting the sane data object move. In an example scenario, when two worker functions are concurrently moving the data object202(a) from the data store “A”212to the data store “B”214, a first worker function may complete the creation of the data object202(b) on the data store “B”214by performing the replication through step “3” before experiencing a delay. However, a second worker function that is initiated shortly after the first worker function may be stopped by redundant duplication prevention from creating the same data object202(b) on the data store “B”214. At which point the second worker function will attempt a retry.

During the retry attempt, the data relocation component122may determine that first worker function has already completed the replication through step “3”. As a result, the data relocation component122may cause the second worker function to proceed with step “4” of the replication. If the first worker thread is still experiencing the delay, the second worker function may successfully change the information in the state field206to “locked (to) (data store B)”. This successful information change to state field206also means that the version number208of the data object202(a) may be changed by the optimistic concurrency logics of the tiered data storage system110. At this point in the example scenario, the second worker function may experience a delay.

Subsequently, the first worker function may emerge from its delay and attempt to perform step “4”. However, since the version number208of the data object202(a) had already changed because step “4” has been completed by the second worker function, optimistic locking may cause the first worker function to fail and retry. Upon the retry attempt, the data relocation component122may determine that the first worker function has already completed the replication through step “4”. As a result, data relocation component122may cause the first worker function to proceed with step “5” and successfully change the state in the state field216of the data object202(b) to “unlocked”. This successful state change to state field216also means that the version number208of the data object202(a) may be changed by optimistic concurrency logics of the tiered data storage system110. Thus, if the second worker function emerges from its delay and attempts to also perform step “5” (i.e., change the state in the state field216to “unlocked”), optimistic locking may cause the second worker function to fail and retry.

Upon retry, the data relocation component122may determine that the first worker function has completed the replication through step “5”. Thus, the data relocation component122may cause the second worker function to perform step “6” to complete the “move” of the data object202(a) to the data store “B”214by deleting the data object202(a) from the data store “A”212. At this point, when the first worker function attempts to perform step “6”, it may determine that the “move” of the data object202(a) is already completed as the data object202(a) no longer exists on the data store “A”212and the state of the data object202(b) is unlocked. Having made such a determination, the data relocation component122may permanently terminate the first worker function.

As can be ascertained from the above description, in a scenario in which two worker functions are concurrently moving the same data object from a source data store to a destination data store, one worker function is likely to succeed at each step while the other worker function is likely to encounter an optimistic lock error and retry. In this way, replication progress may be made via the combination of the two worker functions “leapfrogging” over each other until the replication is completed.

In some instances, a worker function initiated by the data relocation component122to move a data object for a first time or retry the move of a data object from a source data store to a destination data store may encounter a data object in the source data store that does not have an “unlocked” state. In such instances, the data relocation component122may cause the worker function to perform differently based on (1) information in the state field of the data object; (2) the presence or absence of a corresponding duplicate data object in the destination data store; and/or (3) if applicable, the information in the state field of the duplicate data object in the destination data store. Such different behaviors by the worker function are illustrated below inFIGS. 3-8. It will be appreciated that in such figures, the reference to a specific numbered “step”, e.g., step “4”, refers to a step that is similar to its corresponding step described inFIG. 2. Furthermore, while the steps of each replication carried out by the data relocation component122is described as being implemented by a worker function, it will be appreciated that each “worker function”, as used throughout, may refer to a collection of tasks performed by various logics of the data relocation component122to implement each replication.

FIG. 3shows an illustrative block diagram of a scenario in which a worker function is permanently terminated during replication by the data relocation component122based on information in a state field of a data object in a source data store. As shown inFIG. 3, a worker function210may be trying to move a data object202(a) from the data store “A”212to the data store “B”214for a first time, as previously described inFIG. 2. However, while performing step “1” of the replication described inFIG. 2, the worker function210may determine that the state field206of the data object202(a) holds the information “locked (from) (data store B)” or “locked (to) (data store C)”. The “locked (from) (data store B)” may occur when another worker function is in the process of moving a duplicate of the data object202(a) from the data store “B”214back to the data store “A”212. The “locked (to) (data store C)” may occur when another worker function is in the process of moving the data object202(a) from the data store “A”212to another data store that is not the data store “B”214. Accordingly, once the worker function210determines that another move of the data object202(a) by a different worker function to some data store other than the data store “B”214is already in progress, the data relocation component122may permanently terminate the worker function210to abort the attempt to move the data object202(a) from the data store “A”212to the data store “B”214.

Likewise, in additional embodiments, if the worker function210encounters the same information in the state field206of the data object202(a) during a retry of the same move, the data relocation component122may also permanently terminate the worker function210.

FIG. 4shows an illustrative block diagram of a scenario in which a worker function may forcibly modify the information in a state field of a data object that is to be moved from a source data store to a destination data store. As shown inFIG. 4, a worker function402may be trying to move a data object404from a data store “B”406to a data store “C”408. However, while performing step “1” of the replication, the worker function210may determine that the state field410of the data object404holds the information “locked (from) (data store A)”. In other words, it is likely that another worker function that is moving the data object404from the data store “A”412to the data store “B”406is either still in progress or has failed prematurely. In such a scenario, the data relocation component122may force the completion of the move of the data object404to the data store “B” by using the worker function402to take over and complete the move of the data object404from the data store “A”412to the data store “B”406. In various scenarios, if the other worker function stopped at step “3”, the worker function402may perform step “4” through step “6” to complete the move of the data object404from the data store “A”412to the data store “B”406. However, if the other worker function stopped at step “4”, the worker function may perform “step “5” and step “6” to complete the move of the data object404from the data store “A”412to the data store “B”406. Thus, at the end of the move of the data object404to the data store “B”406, the information in the state field410of the data object404is “unlocked”. Subsequently, the worker function402may complete the move of the data object404to the data store “C”408using replication steps that are similar to the replication steps described inFIG. 2, i.e., step “2” through step “6”.

In some embodiments, the data relocation component122may wait for a predetermined amount of time prior to forcibly change the information in the state field410of the data object404from “locked (from) (data store A)” to “unlocked”. The predetermined amount of time may present the other worker function with an opportunity to complete its replication steps in order to finish the move of the data object404to data store “B”406.

FIG. 5shows an illustrative block diagram of recovery from a scenario in which replication by a worker function fails during concurrent moves of a data object between three tiered data stores. As shown inFIG. 5, a worker function502may be moving a data object504(a) from a data store “A”506to a data store “B”508. However, the worker function502may prematurely fail near the completion of the replication (e.g. at step “4” or step “5”). As a result, as shown in row510, the information in the state field512of the data object504(a) may still be “locked (to) (data store B)”. Moreover, a duplicate data object504(b) may be present in the data store “B”508. As further shown in row510, the duplicate data object504(b) may have a state field514that holds the information “unlocked” if the worker function502failed on step “5”, and the information “locked (from) (data store A)” if the worker function502failed on step “4”. As a result, the worker function502may be in the process of attempting a retry to complete the replication.

In the meantime, a second worker function516may be concurrently initiated by the data relocation component122to move the data object504(b) to a data store “C”518. The worker function516may have either successfully completed or substantially completed the move of the data object504(b) to the data store “C”518before the attempted retry by the worker function502. It will be appreciated if the worker function502had failed at step “4”, that worker function516may have forced the data object504(b) from the state of “locked (from) (data store A)” to a state of “unlocked”, using the operations described inFIG. 4, prior to proceeding with its own move.

Thus, as shown in row520, when the worker function502ascertains that state of the data object504(a) as part of its retry attempt, the worker function502may discover that the state field512is either missing or holds the information “locked (to) (data store C)”. For example, the state field512may be missing if the worker function516has completed its move. Alternatively, the state field512may be “locked (to) (data store C)” if the worker function516has completed the move through step “4” of the replication. Thus, since the worker function502is able to determine that the state field512is either missing or is not “locked (from) (data source A)”, the worker function502at this point may determine that the data object504(b) has already been located by another worker function (e.g., worker function516). As a result, as shown in row522, the data relocation component122may cause the worker function502to delete the data object504(a) from the data store “A”506to complete its replication (i.e., state field512no longer exists).

FIG. 6shows an illustrative block diagram of recovery from a scenario in which replication by a worker function fails during concurrent moves of a data object mutually between two tiered data stores. As illustrated inFIG. 6, a worker function602may be in the process of moving a data object604(a) from a data store “A”606to a data store “B”608. However, the worker function602may fail partway through the replication (e.g., at step “4” or at step “5”). Thus, as shown in row610, a duplicate data object604(b) of the data object604(a) may be present on the data store “B”608. The data object604(b) may include a state field612that holds a corresponding state of “unlocked” or “locked (from) (data store A)”. Further, a state field614of the data object604(a) may hold the information “locked (to) (data store B)”.

In the meantime, a worker function616may have successfully performed a second “move” of the data object604(b) back to the data store “A”606. In the actual completion of such a move, the worker function614may have determined that the data object604(a) already exists on data store “A”606, so the worker function616may have completed its replication by skipping to and performing steps “4” through step “6”. In other words, the worker function616may have first changed the state of the data object604(b) to “locked (to) (data store A)”, then changed the state of the data object604(a) to unlocked, and finally deleted the data object604(b).

Accordingly, a shown in row618, the data object604(b) may no longer exist on the data store “B”608when the worker function602now attempts the retry. Consequently, recognizing that while the state of the data object604(a) had switched from a state of “locked (to) (data store B)” to a state of “unlocked” at this retry attempt, while data object604(b) no longer exists on the data store “B”608, the data relocation component122may cause the worker function602that is retrying the first move of the data object604(a) to abort the replication attempt.

FIG. 7shows an illustrative block diagram of recovery from a scenario in which replication by a worker function fails during concurrent moves of a data object mutually between two tiered data stores, in which duplicate data objects are locked to each other.

As illustrated inFIG. 7, a worker function702initiated by the data relocation component122may be in the process of moving a data object704(a) from a data store “A”706to a data store “B”708. However, the worker function702may fail partway through its replication (e.g., at step “4” or at step “5”). Thus, a duplicate data object704(b) of the data object704(a) may be present on the data store “B”708. In the meantime, a worker function710that is also initiated by the data relocation component122may be in the process of moving the data object704(b) from the data store “B”708back to the data store “A”706. However, the worker function710may also fail partway through its replication after performing step “4”. Thus, as shown in row712, the state field714of the data object704(a) may hold the information “locked (to) (data store B)”, while the state field716of the data object704(b) may hold the information “locked (to) (data store A)” in such a scenario.

At this point, each of the worker function702and worker function710may attempt to remedy such a mutual lock and reattempt its own replication. In various embodiments, having recognize the existence of such mutual “locked to” states, the worker function702may attempt to convert the state of the data object704(b) from “locked (to) (data store A)” to “locked (from) (data store A)”. Such a change to the information in the state field716of the data object704(b) may enable the worker function702to complete its replication for data object704(a). However, at the same time, worker function710may also recognize these mutual “locked to” states in the course of its retry attempt. Accordingly, the worker function710may attempt to convert the state of the data object704(a) from “locked (to) (data store B)” to “locked (from) (data store B)”, so that the worker function710may also complete its replication for the data object704(b). Thus, as further describe inFIG. 8, the resolution of such conflicting retry attempts by the worker function702and the worker function710may be accomplished via the use exponential back off and optimistic locking.

FIG. 8shows illustrative block diagrams of the states of the duplicate data objects during different recoveries from the scenario described inFIG. 7, in which duplicate data objects are locked to each other. As shown in scenario802, the state of the data object704(a) may initially be “locked (to) (data store B)”, and the state of data object704(b) may initially be “locked (to) (data store A)”. However, the worker function702is able to change the state of data object704(b) to “locked (from) (data store A)” before the worker function710makes its own change attempt to the state of data object704(a). In various embodiments, the precedence of the change by the worker function702may be due to the use of exponential back off. Moreover, once the worker function702has successfully changed the state of data object704(b), optimistic locking may prevent an ensuing attempt by the worker function710to change the state of the data object704(a). As a result, the worker function702may resume its performance of step “5” to change the state of the data object704(b) on the data store “B”708to “unlocked”, and complete its replication by deleting the data object704(a) from the data store “A”706in step “6”.

Subsequently, when the worker function710retries again, it may determine that while the state of the data object704(b) is “unlocked”, the data object704(a) no longer exists on the data store “A”706. Thus, the data relocation component122may conclude that the data object704(a) had already been relocated, and therefore terminate any further retry attempts by the worker function710.

Alternatively, as shown in scenario804, the state of the data object704(a) may initially be “locked (to) (data store B)”, and the state of data object704(b) may initially be “locked (to) (data store A)”. However, the worker function710is able to change the state of data object704(a) to “locked (from) (data store B)” before the worker function702makes its own change attempt to the state of data object704(b). In various embodiments, the precedence of the change by the worker function710may be due to the use of exponential back off. Moreover, once the worker function710has successfully changed the state of data object704(a), optimistic locking may prevent an ensuing attempt by the worker function702to change the state of the data object704(b). As a result, the worker function710may resume its performance of step “5” to change the state of the data object704(a) on the data store “A”706to “unlocked”, and complete its replication by deleting the data object704(b) from the data store “B”708in step “6”.

Subsequently, when the worker function702retries again, it may determine that while the state of the data object704(a) is “unlocked”, the data object704(b) no longer exists on the data store “B”708. Thus, the data relocation component122may conclude that the data object704(b) had already been relocated, and therefore terminate any further retry attempts by the worker function702.

Returning toFIG. 1, the data relocation component122may be configured to periodically check the data objects stored in the tiered data storage system110to determine whether a data object is to be moved from a first data store to a second data store based one or more relocation criteria. For example, the data relocation component122may be configured by a user to move data objects that are more than one year old from a “first tier” data store to a “second tier” data store for archival purposes. Accordingly, the data relocation component122may check on a periodic interval (e.g., once every hour, once a day, once a day) for any data objects that meets such relocation criteria, and automatically move data objects that fulfill such relocation criteria.

In other instances, an application, such as the application102(1), may directly activate the data relocation component122to move data objects from a first data store to a second data store. For example, the application102(1) may maintain an archive schedule for the data objects that it interacts with, and thus may activate the data relocation component122at its discretion to move data objects between the data stores of different tier levels. In some of such instances, the application102(1) may determine that a data object is to be moved at a precise time. Thus, the application102(1) may directly communicate the request to the data relocation component122for fulfillment.

However, in other of such instances in which the exact time of completion for a move request is not important, the application102(1) may pass a move request to the queue component124. In such instances, the data relocation component122may pull move requests from the queue component124to complete each move request at a time determined by the data relocation component122.

In some embodiments, the queue component124may be a distributed queue messaging service that guarantees at-least-once delivery. Moreover, each move request may not be removed from the queue component124until the data relocation component122has completed the move request. Accordingly, a move request may remain in the queue component124until the data relocation component122explicitly informs the queue component124that the move of a data object is completed.

Illustrative Operations

FIGS. 9-11show illustrative processes900-1100that implement techniques for moving data between data stores without the use of a consistent location service. Each of the processes900-1100is illustrated as a collection of blocks in a logical flow graph, which represents a sequence of operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions stored on one or more computer-readable storage media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described blocks can be combined in any order and/or in parallel to implement the process. For discussion purposes, the processes800-1100are described with reference to the computing environment100ofFIG. 1.

FIG. 9is a flow diagram of an illustrative process900for moving a data object between data stores of a data storage system via data object replication. In some embodiments, the data stores may reside at the same tier level or different tier levels on a tiered data storage system. At block902, a worker function initiated by the data relocation component122may begin the replication by read an original data object with a state of “unlocked” in its state field. In various embodiments, the worker function may accomplish the read by loading the data object into a memory. Further, the worker function may also read a version number of the original data object. The version number may be an incrementally updated value, a globally unique identifier (GUID), a current time, or a Lamport time. The original data object may further include an identifier that uniquely identifies the original data object. However, as described inFIG. 3, if the worker function determines that the original data object is already “locked (to)” another data store that is not the destination data store at block902, the worker function may be permanently terminated.

At block904, the worker function may store a duplicate of the “unlocked” data object to a destination data store based on the “unlocked” data object that is read. The duplicate data object may have an identifier that is identical to the identifier of the original data object. The duplicate data object may be provided with a state of “locked (from) (source data store)” in its state field, as well as its own version number. In some embodiments, the worker function may abort the store of the duplicate data object if a data object with the same identifier is already present in the destination data store. In which case, the worker function may abort and retry at the next step in the replication.

At block906, the worker function may change the state of the original data object to “locked (to) (destination data store)” using optimistic locking. In various embodiments, the optimistic locking may be implemented using the version number read at block902. Thus, any modification to the original data object, including its corresponding state field, may result in a change in the version number read at block902. Accordingly, the worker function may only change the state of the original data object if the original data object has not been modified since it was read at block902. Otherwise, the worker function may abort the change to the state of the original data object, delete the duplicate data object from the destination data store, and retry the replication by once again reading the original data object.

At block908, the worker function may modify the state of the duplicate data object to “unlocked” using optimistic locking. In various embodiments, optimistic locking may be implemented via a comparison of the version number that the duplicate data object was created with at block904, and the version number read at the time of the attempt to change the state to “unlocked”. In this way, the optimistic locking may prevent conflicts arising from move attempts by other worker functions. For example, the optimistic locking may prevent the worker function from conflicting with another worker function that is also trying to move the original data object from the source data store to the destination data store via replication. At block910, the worker function may complete the replication by deleting the original data object from the source data store.

In various embodiments, when the worker function fails to complete the data object replication, such as due to optimistic locking or some other type of failure, the worker function may be configured by the data relocation component122to infer the step in the replication at which the failure occurred, as well as resume the replication at the next appropriate step until the replication is completed. However, as described above with respect to the scenarios inFIGS. 3, and5-6, the data relocation component122may permanently terminate some retry attempts by the worker function in selective scenarios. Thus, by selectively terminating retry attempts and ensuring that worker functions perform the steps of replication using optimistic locking, the data relocation component122may warrant that even when a particular data object is concurrently moved by multiple data object moves to one or more data stores, the particular data object will be not be lost, no multiple duplication of the particular data object will occur, and the particular data object always is moved to one of the data stores.

FIG. 10is a flow diagram of an illustrative process1000for reading data from a data store of the data storage system during a replication that moves a data object from a source data store to a destination data store. In various embodiments, the data stores may be a part of the tiered data storage system110. At block1002, the data relocation component122may receive an application request to read data from a data object stored in a data store. In some embodiments, the data store may be part of the tiered data storage system110.

At decision block1004, the data relocation component122may determine whether the state of the requested data object is “unlocked”. If the state of the requested data object is “unlocked”, (“yes” at decision block1004), the process1000may continue to block1006. At block1006, the data relocation component122may read the data from the requested data object and provide the read data to the application.

However, if the state of the requested data object is “locked” (“no” at decision block1004), the process1000may proceed to block1006. At block1006, the data relocation component122may determine that a state of a corresponding data object in a counterpart data store that has the same identifier as the requested data object. The data relocation component122may determine the counterpart data store by obtaining the identity of the counterpart data store from a relevant in-progress data object move.

At decision block1010, the data relocation component122may determine whether the state of the corresponding data object is “unlocked”. If the state of the corresponding data object is “unlocked”, (“yes” at decision block1010), the process1000may continue to block1012. At block1012, the data relocation component122may read the data from the corresponding data object and provide the read data to the application.

However, if the state of the corresponding data object is “locked” (“no” at decision block1010), the process1000may proceed to block1014. At block1014, the data relocation component122may read the data from either the requested data object or the corresponding data object and provide the read data to the application.

FIG. 11is a flow diagram of an illustrative process1100for performing forced retries to recover from a failure during a replication that moves a data object from a source data store to a destination data store. In various embodiments, the data stores may be a part of the tiered data storage system110.

At block1102, a current worker function that is initiated by the data relocation component122may encounter a data object on a source data store that has a state of “locked (from)” a data store that is not a destination data store when attempting to relocate the data object to the destination data store. In various embodiments, such a state of the data object may be the result of the data object being moved by another worker function from some other data store to the source data store in which the other worker function experienced a failure, or a slow replication of the data object by the other worker function from the other data store to the source data store.

At block1104, the data relocation component122may cause the current worker function to wait for a predetermined amount of time for the state of the data object to change to “unlocked”. Such a state change may occur if the slow replication is finally completed by the other worker function.

Thus, at decision block1106, if the data relocation component122determines at the end of the predetermined time period that state of the data object is “unlocked”, the process1100may then proceed to block1108. At block1108, the data relocation component122may cause the current worker function to perform the relocation of the data object to the destination data store via replication.

However, if the data relocation component122determines at the end of the predetermined amount of time that the state of the data object is still not “unlocked”, the process1100may then proceed to block1110. At block1110, the data relocation component may cause the current worker function to take over and complete the failed or otherwise incomplete replication to move the data object from the other data store to the source data store by performing any replication step that remains. For example, if the other worker function stopped at step “3”, the worker function402may perform step “4” through step “6” to complete the move of the data object from the other data store to the source data store. However, if the other worker function stopped at step “4”, the worker function may perform “step “5” and step “6” to complete the move of the data object from the other data store to the source data store. The completion of the replication may change the state of the data object from the state of being “locked (from)” the other data store that is not the destination data store to “unlocked”. Subsequently, the process1100may loop back to block1108, at which point the current worker function may perform the relocation of the data object to the destination data store via replication.

In summary, by providing each data object stored in data storage system with an optimistic locking protected state field that includes (1) a locking state; (2) a “to” or “from” state; and (3) a pointer to another data store, the data relocation logics and mechanisms described herein may enable the efficient movement of data objects between data stores without the use of a central consistent location service. Moreover, it will be appreciated that while the data object move via replication is described above with respect to a tiered data storage system, most of the embodiments described above may also be implemented on a non-tiered data storage system.

CONCLUSION