Systems for storing data streams in a distributed environment

• US 8,959,075 B2
• Filed: 03/03/2014
• Issued: 02/17/2015
• Est. Priority Date: 05/24/2011
• Status: Active Grant

• Current Assignee: Mr. Yusefzadeh, Bahram Nmn
• Original Assignee: Red Lambda Incorporated
• Inventors: Bird, Robert, Leko, Adam, Whitlock, Matthew
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US14/194,945
• Publication Number:
  US 20140207728A1
• Time in Patent Office: 351 Days
• Field of Search: 707/706, 707/707, 707/711, 726/2
• US Class Current: 707/706
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses

Abstract

Systems and methods for storing and retrieving data elements transmitted via data streams received from distributed devices connected via a network. The received data elements may be stored in block stores on the distributed devices. The stored data-elements may be allocated to data-blocks of a block-store that have assigned block-identifiers and further allocated to events of the data-blocks that have assigned token-names. Stream-schema of the received data-streams may comprise a list of token-names and an index-definition for each corresponding data-stream. Indices may be generated for the event-allocated data-elements. A query may be executed in order to retrieve data-elements of the received data-streams based on the indices.

Claims

1. A system for storing and retrieving data, comprising:

a plurality of distributed devices adapted to communicate via a network, wherein each one of the plurality of distributed devices comprises a processor;

a plurality of data-streams received from the plurality of distributed devices, each one of the plurality of data-streams comprises data-elements;

a plurality of block-stores that are stored on the plurality of distributed devices, the plurality of block-stores store via the processors the data-elements of the received plurality of data-streams;

one or more data-blocks of the block-stores, the stored data-elements allocated to the one or more data-blocks, each one of the block-stores comprising one or more data-blocks, each data-block comprising the stored data-elements of only one of the received plurality of data-streams, the data-blocks of a single data-stream are logically grouped, and each one of the data-blocks are read and written as a single unit;

a block-identifier assigned to each one of the data-blocks, the block-identifier being globally unique;

events of the one or more data-blocks, the block-allocated data-elements further allocated to the events of the data-blocks, each one of the data-blocks comprise one or more events, each one of the events comprising the block-allocated data-elements of the corresponding data-block;

token-names assigned to each one of the event-allocated data-elements, each one of the event-allocated data-elements has a token-name, the token-names being human-readable names;

stream-schema of the received plurality of data-streams, each one of the received plurality of data-streams having a stream-schema, each stream-schema further comprising a list of token-names for the event-allocated data-elements of the corresponding data-stream, the event-allocated data-elements of the corresponding data-stream being capable of being identified based on the list of token-names, wherein each stream-schema further comprises an index-definition for each corresponding data-stream; and

,

indices generated for the event-allocated data-elements based on the corresponding index-definition and the corresponding list of token-names, whereby at least one query for the event-allocated data-elements may be executed in order to retrieve data-elements of the received plurality of data-streams, the at least one query is based on at least one of the indices.

2. The system of claim 1, wherein each of the plurality of block-stores stores the stored data-elements of two or more of the received plurality of data-streams.

3. The system of claim 1, wherein each index-definition comprises an index-page and an index-set for each of the data-blocks of the corresponding data-stream, and wherein the stream-schema further comprises block-size information for the data-blocks of the corresponding data-stream, wherein the block-size information provides a maximum block-size for data-blocks within the corresponding data-stream.

4. The system of claim 3, wherein each of the index-pages further comprises a reference to a block-identifier for a corresponding data-block.

5. The system of claim 3, wherein the index-page further comprises page-data summarized-information of the data-blocks of the corresponding data-stream, and wherein the index-set further comprises root-data summarized-information of the index-pages of the corresponding index-definition.

6. The system of claim 1, wherein the data-elements have a common structure.

7. The system of claim 6, wherein the common structure of the data-elements is an unrestricted-structure.

8. The system of claim 6, wherein each stream-schema corresponds to a common structure of each one of the events of the corresponding data-stream.

9. The system of claim 1, wherein the data-elements have different structures, wherein each stream-schema corresponds to varying structures of the events of the corresponding data-streams.

10. The system of claim 1, wherein the stored data-elements comprise compound-data.

11. The system of claim 10, wherein the compound-data is selected from a group consisting of lists and objects.

12. The system of claim 1, wherein the block-stores support concurrent readers and writers.

13. The system of claim 1, wherein the data-elements that are received from a distributed device are stored in a targeted block-store only when the distributed device has write-access to a file-system utilized by the targeted block-store.

14. The system of claim 1, further comprising:

a request to write data of a data-stream, wherein the request is received from a distributed device, wherein the stream-schema of the received data-stream is capable of being read; and

local-memory allocated to buffer each one of the events of the corresponding data-stream, wherein metadata of the stream-schema is capable of being cached.

15. The system of claim 1, further comprising:

metadata of the stream-schema of the received plurality of data-streams, wherein metadata of the stream-schema is capable of being cached, wherein each stream-schema comprises metadata for the corresponding data-stream.

16. The system of claim 1, further comprising:

a buffer filled until the buffer reaches a block-size provided by the block-size information for the data-blocks of the corresponding data-stream; and

a file-system utilized by the targeted block-store, wherein the buffer is capable of being flushed into the file-system, wherein the buffer is capable of being reused for the data-elements of the received plurality of data-streams.

17. The system of claim 1, further comprising:

more than one buffer allocated to a single data-stream, wherein concurrent-writers are utilized in the same distributed device.

18. The system of claim 1, further comprising:

a transaction performed on the event-allocated data-elements, wherein the transaction is one transaction selected from the group consisting of querying, retrieving, accessing, updating, and deleting.

19. The system of claim 3, further comprising:

each index-definition having a set of constraints that control which data-elements in a data-stream are returned, wherein the index-set and the index-page for the data-blocks are capable of being accessed;

the constraints capable of being translated into a Boolean-expression, wherein the Boolean-expression is selected from a group consisting of a product-of-sums expression and a sum-of-products expression, wherein each Boolean-expression is translated independently;

the data-blocks analyzed with each Boolean-expression;

a candidate set of data-blocks for matching-events of a Boolean-expression, the candidate set of data-blocks having zero matching-events capable of being set to comprise all data-blocks in the corresponding data-stream;

the candidate set of data-blocks capable of being retrieved; and

the candidate set of data-blocks capable of being evaluated.

20. The system of claim 19, further comprising:

at least one of the candidate set of data-blocks updated with updated data-blocks, wherein at least one of the events is removed in the updated data-blocks, wherein false-positives returned from a query of the updated data-blocks are ignored.

21. The system of claim 1, further comprising:

the results from the at least one query used as input to a streaming-query, wherein the streaming-query provides join and windowing operations for data-elements of the received plurality of data-streams.

22. The system of claim 1, further comprising:

data-blocks removed based on a file-deletion operation and updated indices that reference that data block.

23. The system of claim 22, wherein the file-deletion operation is a batched operation.

24. The system of claim 22, wherein the file-deletion operation is performed on a subsequent index-update operation.

25. The system of claim 1, wherein at least one of the block-stores requires a file-system that supports concurrent updates to directory-structures, wherein the at least one of the block-stores requires that writes to data-blocks are atomic, wherein the data-blocks of the at least one of block-stores are consistent for each query performed after new data-blocks are written.

26. The system of claim 25, wherein a locking service is utilized by the file-system.

27. The system of claim 3, furthering comprising:

pending data-blocks and corresponding index-pages and index-sets capable of being flushed.

28. The system of claim 1, wherein at least one of the block-stores has unconstrained concurrency, wherein the unconstrained concurrency of the at least one of the block-stores is limited by file-system capabilities.

29. The system of claim 1, further comprising:

the data-blocks, the index-pages and the index-sets capable of being compressed;

the compressed data-blocks, index-pages and index-sets capable of being flushed; and

the flushed data-blocks, index-pages and index-sets capable of being decompressed.

30. The system of claim 1, wherein at least one of the plurality of distributed devices is a distributed storage device.

31. The system of claim 1, wherein at least one of the plurality of distributed devices is a sensor.

32. The system of claim 1, wherein at least one of the plurality of distributed devices is an infrastructural equipment.

33. The system of claim 1, wherein at least one of the indices is a hash-index.

34. The system of claim 1, wherein at least one of the indices is a range-index.

35. The system of claim 1, wherein at least one of the indices is an interval-index.

36. The system of claim 1, wherein at least one of the indices is a full-text index.

37. The system of claim 1, wherein at least one of the block-stores stores data based on an Abstract Syntax Notation One (ASN.1) encoding standard.

38. The system of claim 1, wherein at least one of the block-stores stores data based on a Distinguished Encoding Rules (DER) message-transfer syntax.

39. The system of claim 38, wherein the Distinguished Encoding Rules (DER) message-transfer syntax is based on a X.690 International Telecommunication Union (ITU)-T recommendation.