Recovery and fault-tolerance of a real time in-memory index

• US 8,924,476 B1
• Filed: 03/30/2012
• Issued: 12/30/2014
• Est. Priority Date: 03/30/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Granstrm, Johan Georg, Cherukuwada, Sai Suman, Andersson, Klas Olof Daniel
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): CELANI, NICHOLAS P
• Application Number:
  US13/435,894
• Time in Patent Office: 1,005 Days
• Field of Search: 709/204
• US Class Current: 709/204
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/489 using time information
• CPC Class Codes: H04N 21/23103 using load balancing strategies, e.g. by placing or distributing content on different disks, different memories or different servers storage management G06F3/0604; allocation of resources considering the load in multiprogramming arrangements G06F9/505; techniques for rebalancing the load in a distributed system G06F9/5083; access to distributed or replicated servers, e.g. load balancing, in data networks H04L67/1001
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568
• CPC Class Codes: H04N 21/23113 involving housekeeping operations for stored content, e.g. prioritizing content for deletion because of storage space restrictions storage management, e.g. defragmentation G06F3/0604; snloading stored programs G06F9/445; housekeeping operations in file systems, e.g. deletion policies G06F16/10; buffering arrangements in a network node or in an end terminal in packet networks H04L49/90
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand

Abstract

Techniques for recovery and fault-tolerance of a real time in-memory index are presented. A queue management component controls a queue component to have it communicate respective data segments of a data stream to respective partitions of a repository, based on a randomizing function, a stream ID of the data stream, and respective segment numbers of the respective segments. The repository stores data streams for a defined period of time. A driver component distributes queries to the partitions of the repository to request data stream segments, and the repository can provide segments that have not yet expired. The driver component aggregates the results to reproduce the data stream, which can be provided to a requesting client. When a partition is recovering from being offline, the partition can request that the queueing system re-deliver data segments over a specified time period, and the queue component can re-deliver the desired data segments.

Claims

1. A system, comprising:

at least one memory that stores computer executable components; and

at least one processor that executes the following computer executable components stored in the at least one memory;

a queue component that distributes respective messages of a plurality of messages to respective partitions of a set of partitions of a repository, wherein the respective messages include respective data segments of a data stream communicated via a data communication network; and

a queue management component that manages distribution of the respective messages to the respective partitions of the repository based at least in part on respective segment numbers and respective stream identifiers associated with the respective messages, wherein, in response to a recovery-related request for re-delivery of a subset of the respective data segments of the data stream that had been sent to a partition of the set of partitions during a specified period of time, the queue component re-delivers the subset of the respective data segments to the partition to facilitate recovery of the subset of the respective data segments by the partition, wherein the specified period of time is determined as a function of a time of the recovery-related request, a stream expiry time associated with the data stream, and a maximum length of the data stream.

2. The system of claim 1, wherein the respective data segments of the data stream are associated with the respective segment numbers, wherein a segment number of the respective segment numbers identifies a location of a corresponding data segment of the respective data segments in the data stream relative to other data segments of the respective segments.

3. The system of claim 1, wherein a stream identifier of the respective stream identifiers is associated with a data segment of the respective segments and identifies the data stream with which the data segment is associated.

4. The system of claim 1, wherein the queue management component determines a routing number for a data segment associated with a message of the plurality of messages based at least in part on a segment number and a stream identifier associated with the data segment, and assigns distribution of the message to the partition of the set of partitions of the repository based at least in part on the routing number.

5. The system of claim 1, wherein the queue management component adjusts distribution of the respective messages in response to identification of a change in a number of available partitions of the repository.

6. The system of claim 5, wherein, in response to a new partition being added to the set of partitions, the queue management component updates a number indicative of a total number of partitions in the set of partitions in relation to previously existing partitions of the set of partitions.

7. The system of claim 1, further comprising a driver component that distributes queries over the respective partitions of the set of partitions to obtain the respective data segments stored in the respective partitions, and aggregates the respective data segments of the data stream in a segment order, based at least in part on the respective segment numbers, to facilitate providing the data stream to a client.

8. The system of claim 7, wherein the driver component is stateless and is replicated in response to demand.

9. The system of claim 1, wherein the repository maintains one or more data streams, including the data stream, for a defined period of time, wherein the repository determines the stream expiry time of the data stream based at least in part on a time when a last data segment of the data stream was received by the repository.

10. The system of claim 1, wherein the partition of the set of partitions, to facilitate the recovery of the subset of the respective data segments of the data stream when the partition is available after being unavailable, generates the recovery-related request and transmits the recovery-related request to the queue component to request that the queue component re-deliver the subset of the respective data segments that were sent during the specified period of time, wherein the specified period of time is determined based at least in part on the time of the recovery-related request minus the stream expiry time associated with the data stream minus the maximum stream length of the data stream.

11. A method, comprising:

employing at least one processor to facilitate execution of code instructions retained in at least one memory device, the at least one processor, in response to execution of the code instructions, causing a device to perform operations comprising;

distributing respective messages of a plurality of messages via a queue to respective partitions of a plurality of partitions of a repository, wherein the respective messages include respective data segments of a data stream that is communicated via a communication network;

controlling distribution of the respective messages to the respective partitions of the repository as a function of respective segment numbers and respective stream identifiers of the respective messages; and

in response to a request to re-send a subset of the respective data segments of the data stream that had been sent to a partition of the plurality of partitions during a specified period of time, transmitting the subset of the respective data segments to the partition to facilitate recovery by the partition, wherein the specified period of time is determined based at least in part on a time of the request, a stream expiration time associated with the data stream, and a value that is based on a defined data stream length associated with the data stream.

12. The method of claim 11, further comprising:

linking the respective segment numbers to the respective data segments of the data stream, wherein a segment number of the respective segment numbers identifies a location of a corresponding data segment of the respective data segments in the data stream in relation to other data segments of the respective segments.

13. The method of claim 11, further comprising:

linking a stream identifier associated with the data stream to the respective data segments of the data stream to facilitate identifying the respective data segments as being associated with the data stream.

14. The method of claim 11, further comprising:

determining a routing number for a data segment associated with a message of the plurality of messages as a function of a segment number and a stream identifier associated with the data segment; and

assigning distribution of the message to the partition of the plurality of partitions of the repository as a function of the routing number.

15. The method of claim 11, further comprising:

adjusting distribution of the respective messages to a subset of the respective partitions in response to identifying a change in a number of available partitions of the repository.

16. The method of claim 11, further comprising:

communicating queries to the respective partitions of the plurality of partitions to obtain a portion of the respective data segments; and

aggregating the portion of the respective data segments of the data stream in a segment order, based at least in part on the respective segment numbers of the respective data segments in the portion of respective data segments, to provide at least a portion of the data stream to a client.

17. The method of claim 11, further comprising:

replicating a driver in response to demand, wherein the driver facilitates aggregating at least a portion of the respective data segments of the data stream in a segment order, based at least in part on the respective segment numbers of the respective data segments in the portion of respective data segments.

18. The method of claim 11, further comprising:

maintaining one or more data streams, including the data stream, in the repository for a defined period of time; and

identifying the stream expiration time of the data stream as a function of a time when a last data segment of the data stream was received by the repository to facilitate the maintaining of the data stream in the repository for the defined period of time.

19. The method of claim 11, further comprising:

receiving the request; and

executing a recovery-related operation to identify the subset of the respective data segments for re-sending to the partition, wherein the subset of the respective data segments were previously sent to the partition during the specified period of time, to facilitate recovering the subset of the respective data segments of the data stream by the partition when the partition becomes available after being unavailable.

20. A computer program product, comprising:

a non-transitory computer-readable storage medium storing computer-executable instructions that, in response to execution, cause a system including at least one processor to perform operations, comprising;

providing respective messages of a plurality of messages via a queue to respective partitions of a plurality of partitions of a repository, wherein the respective messages include respective data segments of a data stream that is received over a data communication network;

managing distribution of the respective messages to the respective partitions of the repository as a function of respective segment numbers and respective stream identifiers associated with the respective data segments; and

in response to a request to re-send a subset of the respective data segments of the data stream that had been sent to a partition of the plurality of partitions during a defined period of time, sending the subset of the respective data segments to the partition to facilitate recovery by the partition, wherein the defined period of time is determined as a function of a time the request is made, a stream expiry time associated with the data stream, and a value that is based on a defined length associated with the data stream.