Methods 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 method for storing and retrieving data, comprising the steps of:
receiving a plurality of data-streams, wherein the plurality of data-streams are received from a plurality of distributed devices, wherein the plurality of distributed devices are connected via a network, wherein each one of the plurality of data-streams comprise data-elements;
storing the data-elements of the received plurality of data-streams, wherein the stored data-elements are stored in a plurality of block-stores, wherein the block-stores are stored on the plurality of distributed devices;
allocating the stored data-elements to data-blocks of the block-stores, wherein each one of the block-stores comprises one or more data-blocks, wherein each data-block comprises the stored data-elements of only one of the received plurality of data-streams, wherein the data-blocks of a single data-stream are logically grouped, and wherein each one of the data-blocks are read and written as a single unit;
assigning to each one of the data-blocks a block-identifier, wherein the block-identifier is globally unique;
further allocating the block-allocated data-elements to events of the data-blocks, wherein each one of the data-blocks comprise one or more events, wherein each one of the events comprises the block-allocated data-elements of the corresponding data-block;
assigning to each one of the event-allocated data-elements a token-name, wherein each one of the event-allocated data-elements has a token-name, wherein the token-names are human-readable names;
reading stream-schema of the received plurality of data-streams, wherein each one of the received plurality of data-streams has a stream-schema, wherein each stream-schema further comprises a list of token-names for the event-allocated data-elements of the corresponding data-stream, wherein the event-allocated data-elements of the corresponding data-stream are 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;
generating indices for the event-allocated data-elements based on the corresponding index-definition and the corresponding list of token-names;
executing at least one query of the event-allocated data-elements based on at least one of the indices; and,
retrieving the event-allocated data-elements based on results from at least one query.
2. A method 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. A method 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. A method of claim 3 , wherein each of the index-pages further comprises a reference to a block-identifier for a corresponding data-block.
5. A method 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. A method of claim 1 , wherein the data-elements have a common structure.
7. A method of claim 6 , wherein the common structure of the data-elements is an unrestricted-structure.
8. A method of claim 6 , wherein each stream-schema corresponds to a common structure of each one of the events of the corresponding data-stream.
9. A method 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. A method of claim 1 , wherein the stored data-elements comprise compound-data.
11. A method of claim 10 , wherein the compound-data is selected from a group consisting of lists and objects.
12. A method of claim 1 , wherein the block-stores support concurrent readers and writers.
13. A method 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. A method of claim 1 , further comprising the steps of:
receiving a request to write data of a data-stream from a distributed device;
reading the stream-schema of the received data-stream;
allocating local-memory to buffer each one of the events of the corresponding data-stream; and
caching metadata of the stream-schema.
15. A method of claim 1 , further comprising the step of:
caching metadata of the stream-schema of the received plurality of data-streams, wherein each stream-schema comprises metadata for the corresponding data-stream.
16. A method of claim 1 , further comprising the steps of:
filling a buffer until the buffer reaches a block-size provided by the block-size information for the data-blocks of the corresponding data-stream; and
flushing the buffer into a file-system utilized by the targeted block-store, wherein the buffer is capable of being reused for the data-elements of the received plurality of data-streams.
17. A method of claim 1 , further comprising the step of:
allocating more than one buffer to a single data-stream, wherein concurrent-writers are utilized in the same distributed device.
18. A method of claim 1 , comprising the step of:
performing a transaction 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. A method of claim 3 , further comprising the steps of:
accessing the index-set and the index-page for the data-blocks, wherein each index-definition has a set of constraints that control which data-elements in a data-stream are returned;
translating the constraints 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;
analyzing the data-blocks with each Boolean-expression;
determining a candidate set of data-blocks that contain matching-events for a Boolean-expression;
only if a Boolean-expression fails to determine a set of candidate data-blocks, setting a candidate set of data-blocks to comprise all data-blocks in the corresponding data-stream;
retrieving the candidate set of data-blocks; and
evaluating the candidate set of data-blocks.
20. A method of claim 19 , further comprising the steps of:
updating at least one of the candidate set of data-blocks with updated data-blocks, wherein at least one of the events is removed in the updated data-blocks; and
ignoring false-positives returned from a query of the updated data-blocks.
21. The method of claim 1 , further comprising the step of:
using the results from the at least one query 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. A method of claim 1 , further comprising the step of:
removing data-blocks based on a file-deletion operation and updated indices that reference that data block.
23. A method of claim 22 , wherein the file-deletion operation is a batched operation.
24. A method of claim 22 , wherein the file-deletion operation is performed on a subsequent index-update operation.
25. A method 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. A method of claim 25 , wherein a locking service is utilized by the file-system.
27. A method of claim 3 , furthering comprising the step of:
flushing pending data-blocks and corresponding index-pages and index-sets.
28. A method 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. A method of claim 1 , further comprising the steps of:
compressing the data-blocks, the index-pages and the index-sets;
flushing the compressed data-blocks, index-pages and index-sets; and
decompressing the flushed data-blocks, index-pages and index-sets.
30. A method of claim 1 , wherein at least one of the plurality of distributed devices is a distributed storage device.
31. A method of claim 1 , wherein at least one of the plurality of distributed devices is a sensor.
32. A method of claim 1 , wherein at least one of the plurality of distributed devices is an infrastructural equipment.
33. A method of claim 1 , wherein at least one of the indices is a hash-index.
34. A method of claim 1 , wherein at least one of the indices is a range-index.
35. A method of claim 1 , wherein at least one of the indices is an interval-index.
36. A method of claim 1 , wherein at least one of the indices is a full-text index.
37. A method 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. A method of claim 1 , wherein at least one of the block-stores stores data based on a Distinguished Encoding Rules (DER) message-transfer syntax.
39. A method of claim 38 , wherein the Distinguished Encoding Rules (DER) message-transfer syntax is based on a X.690 International Telecommunication Union (ITU)-T recommendation.