Systems for storing data streams in a distributed environment
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.
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.