IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0657043
(2015-03-13)
|
등록번호 |
US-9904722
(2018-02-27)
|
발명자
/ 주소 |
- Shevade, Upendra Bhalchandra
- Rogers, Gregory Rustin
- Hendrie, Christopher Ian
|
출원인 / 주소 |
- Amazon Technologies, Inc.
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
0 인용 특허 :
12 |
초록
▼
For a given cross-data-store transaction request at a storage service, a coordinator transmits respective voting transition requests to a plurality of log-based transaction managers (LTMs) configured for the respective data stores to which writes are directed in the transaction. The LTMs transmit re
For a given cross-data-store transaction request at a storage service, a coordinator transmits respective voting transition requests to a plurality of log-based transaction managers (LTMs) configured for the respective data stores to which writes are directed in the transaction. The LTMs transmit responses to the coordinator based on data-store-specific conflict detection performed using contents of the voting transition requests and respective data-store-specific state transition logs. The coordinator determines a termination status of the cross-data-store transaction based on the LTMs' responses, and provides an indication of the termination status to the LTMs.
대표청구항
▼
1. A distributed storage system, comprising: a plurality of data stores, including a first data store with a first log-based transaction manager (LTM) and a second data store with a second LTM; andone or more cross-data-store transaction coordinators (CTCs), including a particular CTC; wherein the p
1. A distributed storage system, comprising: a plurality of data stores, including a first data store with a first log-based transaction manager (LTM) and a second data store with a second LTM; andone or more cross-data-store transaction coordinators (CTCs), including a particular CTC; wherein the particular CTC is configured to: determine, based at least in part on an examination of at least a portion of a particular log-structured transaction request repository, that a first cross-data-store transaction request (CTR) has been generated by a client-side component of the distributed storage system, wherein the first CTR includes a first write operation directed to the first data store and a second write operation directed to the second data store;transmit, as part of a first phase of a distributed commit protocol for the first CTR, (a) a first voting transition request (VTR) indicative of the first write operation to the first LTM, and (b) a second VTR indicative of the second write operation to the second LTM;determine, based at least in part on an analysis of respective responses received from the first and second LTMs to the first and second VTRs, a type of terminating transition request (TTR) to be transmitted to the first and second LTMs during a second phase of the distributed commit protocol, wherein the type is selected from a set comprising at least (a) a commit transition request and (b) an abort transition request; and wherein the first LTM is configured to: transmit, during the first phase, based on a result of a first conflict detection analysis of the first VTR with respect to at least a portion of a first persistent log of state transition records, a response to the particular CTC indicating that the first VTR has been conditionally accepted pending a receipt of a first TTR from the particular CTC;determine, prior to receiving the first TTR, whether to accept a different transition request based at least in part on a second conflict detection analysis of the different transition request with respect to at least the first VTR; andmodify, subsequent to receiving the first TTR during the second phase, the first persistent log to indicate a result of the first CTR. 2. The system as recited in claim 1, wherein the first CTR comprises a logical constraint descriptor to be used to determine whether to transmit the first and second VTRs, wherein the logical constraint descriptor comprises one or more of: (a) a de-duplication signature or (b) a sequencing signature. 3. The system as recited in claim 1, wherein the first CTR comprises one or more of: (a) a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR or (b) a second read set descriptor indicative of an object read from the second data store by the client-side component prior to generating the first CTR. 4. The system as recited in claim 1, wherein the first CTC is further configured to: include, in the first VTR, based at least in part on an examination of the first CTR, a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR; and wherein the first LTM is configured to utilize the first read set descriptor to perform the first conflict detection analysis. 5. The system as recited in claim 1, wherein a particular data store of the first and second data stores comprises one of: a non-relational database system, a relational database system, a storage service that implements a web services interface allowing access to unstructured data objects, an in-memory database, or an instance of a distributed cache. 6. A method, comprising: obtaining, by a transaction coordinator of a distributed storage system, an indication of a first cross-data-store transaction request (CTR), wherein the first CTR includes a first storage operation directed to a first data store and a second storage operation directed to a second data store;transmitting, by the transaction coordinator, (a) a first voting transition request (VTR) indicative of the first storage operation to a first log-based transaction manager (LTM) of the first data store, and (b) a second VTR indicative of the second storage operation to a second LTM of the second data store;receiving, at the transaction coordinator, based at least in part on a result of respective conflict detection analyses performed by the first LTM and the second LTM, respective responses to the first and second VTRs, wherein the conflict detection analysis performed by the first LTM comprises an examination of at least a portion of a first persistent log of state transition records of the first data store;generating, by the transaction coordinator based at least in part on the respective responses, a termination status for the first CTR to be transmitted to the first and second LTMs, wherein the termination status is selected from a set comprising at least (a) a committed status and (b) an aborted status;determining, by the first LTM subsequent to receiving the first VTR and prior to receiving an indication of the termination status, whether to accept a different transition request based at least in part on a result of a conflict detection analysis of the different transition with respect to at least the first VTR; andmodifying, by the first LTM subsequent to receiving an indication of the termination status, the first persistent log. 7. The method as recited in claim 6, wherein said obtaining the indication of the first CTR comprises examining, by the transaction coordinator in an order corresponding to an insertion sequence number assigned by a CTR admission controller, one or more entries of a particular persistent log established for storing CTRs. 8. The method as recited in claim 6, further comprising: transmitting, by the transaction coordinator, subsequent to determining that a second CTR does not conflict with the first CTR and prior to generating the termination status of the first CTR, a third VTR to the first LTM, wherein the third VTR is indicative of a third storage operation of the second CTR. 9. The method as recited in claim 6, wherein the first CTR comprises a logical constraint descriptor to be used to determine whether to request an implementation of at least a subset of storage operations of the first CTR, wherein the logical constraint descriptor comprises one or more of: (a) a de-duplication signature or (b) a sequencing signature. 10. The method as recited in claim 6, further comprising: receiving, by a CTR admission controller, a second CTR comprising a de-duplication signature;determining, by the CTR admission controller based at least in part on the de-duplication signature, that the second CTR is a duplicate of a third CTR for which a committed termination status was generated by the transaction coordinator; andtransmitting, by the CTR admission controller to a source from which the second CTR was received, a response indicating that the second CTR has been committed. 11. The method as recited in claim 6, wherein the first CTR is generated by a client-side component of the distributed storage service, and wherein the first CTR comprises one or more of: (a) a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR or (b) a second read set descriptor indicative of an object read from the second data store by the client-side component prior to generating the first CTR. 12. The method as recited in claim 6, wherein the first CTR is generated by a client-side component of the distributed storage service, further comprising: including, by the transaction coordinator in the first VTR, based at least in part on an examination of the first CTR, a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR; andutilizing, by the first LTM, the first read set descriptor to perform the first conflict detection analysis. 13. The method as recited in claim 6, further comprising: including, by the transaction coordinator in the first VTR, based at least in part on an examination of the first CTR, a first conflict check delimiter; andutilizing, by the first LTM, the first conflict check delimiter to select one or more entries of a first persistent log to be examined to determine whether the first VTR is to be accepted. 14. The method as recited in claim 6, further comprising: including, by the transaction coordinator in the first VTR, based at least in part on an examination of the first CTR, a first logical constraint descriptor to be used to determine whether the first VTR is to be accepted by the first LTM, wherein the logical constraint descriptor comprises one or more of: (a) an exclusion signature or (b) a required signature. 15. The method as recited in claim 6, wherein the storage system comprises (a) a third data store, (b) a second transaction coordinator responsible for coordinating cross-data-store transactions which include writes directed to the first data store and the third data store but not the second data store, (c) a third transaction coordinator responsible for coordinating cross-data-store transactions which include writes directed to the second data store and the third data store but not the first data store, and (d) a fourth transaction coordinator responsible for coordinating cross-data-store transactions which include writes directed to the first, second and third data stores. 16. The method as recited in claim 15, wherein the storage system comprises (a) a first log-structured repository to store cross-data-store transaction requests for transactions which include writes directed to the first data store and the second data store but not the third data store, (b) a second log-structured repository to store cross-data-store transaction requests for transactions which include writes directed to the first data store and the third data store but not the first data store, (c) a third log-structured repository to store cross-data-store transaction requests for transactions which include writes directed to the second data store and the third data store but not the first data store and (d) a fourth log-structured repository to store cross-data-store transaction requests for transactions which include writes directed to the first, second and third data stores. 17. The method as recited in claim 6, wherein the first persistent log modified by the first LTM comprises a plurality of replica nodes within respective availability containers of a provider network, further comprising: storing, by the first LTM prior to receiving an indication of the termination status, a respective replica of at least a portion of the first VTR at individual ones of the plurality of replica nodes. 18. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implements a cross-data-store transaction coordinator of a storage service, wherein the cross-data-store transaction coordinator is configured to: obtain an indication of a first cross-data-store transaction request (CTR), wherein the first CTR includes a first storage operation directed to a first data store and a second storage operation directed to a second data store;transmit (a) a first voting transition request (VTR) indicative of the first storage operation to a first log-based transaction manager (LTM) of the first data store, and (b) a second VTR indicative of the second storage operation to a second LTM of the second data store;receive, based at least in part on a result of respective conflict detection analyses performed by the first LTM and the second LTM, respective responses to the first and second VTRs, wherein the conflict detection analysis performed by the first LTM comprises an examination of at least a portion of a first persistent log of state transition records of the first data store;generate, based at least in part on the respective responses, a termination status for the first CTR to be transmitted to the first and second LTMs, wherein the termination status is selected from a set comprising at least (a) a committed status and (b) an aborted status. 19. The non-transitory computer-accessible storage medium as recited in claim 18, wherein to obtain the indication of the first CTR, the cross-data-store transaction coordinator is configured to examine, in an order corresponding to an insertion sequence number assigned by a CTR admission controller, one or more entries of a particular persistent log established for storing CTRs. 20. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the first CTR comprises a logical constraint descriptor to be used to determine whether to initiate an implementation of at least a subset of storage operations of the first CTR, wherein the logical constraint descriptor comprises one or more of: (a) a de-duplication signature or (b) a sequencing signature. 21. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the first CTR is generated by a client-side component of the distributed storage service, and wherein the first CTR comprises one or more of: (a) a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR or (b) a second read set descriptor indicative of an object read from the second data store by the client-side component prior to generating the first CTR. 22. The non-transitory computer-accessible storage medium as recited in claim 18, wherein the first CTR is generated by a client-side component of the distributed storage service, wherein the cross-data-store transaction coordinator is configured to: include, in the first VTR, based at least in part on an examination of the first CTR, a first read set descriptor indicative of an object read from the first data store by the client-side component prior to generating the first CTR. 23. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors implements a log-based transition manager (LTM) associated with a particular data store of a storage service, wherein the LTM is configured to: in response to receiving a voting transition request (VTR) from a cross-data-store transaction coordinator (CTC), wherein the VTR indicates a particular write operation directed to the data store, determine, based on an examination of a read set indicated in the VTR and at least a subset of entries of a persistent log, that the VTR is to be conditionally accepted pending a receipt of a terminating transition request (TTR) corresponding to the VTR from the CTC; andstore a particular entry in the persistent log indicative of conditional acceptance of the particular write operation of the first VTR;in response to receiving, prior to the receipt of the TTR, a single-data-store transition request (STR) from a client of the storage system, determine, based on a detection of a read-write conflict between a read set indicated in the STR and at least the particular entry, that the STR is to be rejected; andin response to receiving a TTR from the CTC, determine whether to modify the persistent log to indicate that the particular write operation is to be committed.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.