Tag coexistence detection

Abstract

In various embodiments, a method for optimizing data storage includes receiving an input data stream, where each data record received in the data stream is tagged with a group of one or more tags. The method further includes, for each data record of data records that have been received in the data stream, using the group of one or more tags of the corresponding data record to update a data structure tracking coexistence implications of tags that have been observed together in the groups of tags of the data records. The method further includes using the data structure tracking coexistence implications of tags to optimize a query.

1 . A method for optimizing data storage, comprising:
 receiving a time series data stream comprising a plurality of data records, wherein each data record received in the time series data stream is tagged with a group of one or more tags;   identifying one or more implications based on tags that have been observed together in the groups of one or more tags of the plurality of data records, wherein an implication indicates that a query of a first tag has a response that is identical to a query of a second tag;   tracking coexistence implications of tags that have been observed together in the groups of one or more tags of the data records; and   using the coexistence implications of tags to optimize a query.   
     
     
         2 . The method of  claim 1 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 updating a query planning data structure.   
     
     
         3 . The method of  claim 1 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 updating a query planning data structure to store non-redundant metrics for at least one tag of the groups of one or more tags.   
     
     
         4 . The method of  claim 1 , wherein a query planning data structure is stored in a volatile memory. 
     
     
         5 . The method of  claim 1 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 updating a telemetry data structure.   
     
     
         6 . The method of  claim 1 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 updating a telemetry data structure to store a non-redundant association of a tag to metrics.   
     
     
         7 . The method of  claim 1 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 updating an index data structure.   
     
     
         8 . The method of  claim 1 , further comprising:
 updating a data structure tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the plurality of data records based on the one or more implications.   
     
     
         9 . The method of  claim 8 , wherein the tracking the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records comprises:
 determining whether a tag of the group of one or more tags is new;   responsive to the determination that the tag is new, storing the tag and associated implications as an added entry in the data structure;   determining whether another entry in the data structure is consistent with the added entry; and   responsive to the determination that the other entry is inconsistent with the added entry, correcting the inconsistent entry in the data structure.   
     
     
         10 . The method of  claim 8 , further comprising:
 using the data structure to reduce a storage size of a stored version of at least one of the received data records.   
     
     
         11 . The method of  claim 8 , wherein the data structure is stored in a non-volatile memory. 
     
     
         12 . A system for optimizing data storage, comprising:
 a processor configured to:
 receive a time series data stream comprising a plurality of data records, wherein each data record received in the time series data stream is tagged with a group of one or more tags; 
 identify one or more implications based on tags that have been observed together in the groups of one or more tags of the plurality of data records, wherein an implication indicates that a query of a first tag has a response that is identical to a query of a second tag; 
 track coexistence implications of tags that have been observed together in the groups of one or more tags of the data records; and 
 use the coexistence implications of tags to optimize a query; and 
   a volatile memory coupled to the processor and configured to store the coexistence implications of tags that have been observed together in the groups of one or more tags of the data records.   
     
     
         13 . The system of  claim 12 , wherein the volatile memory is further configured to store a query planning data structure, wherein the query planning data structure optimizes responses to queries. 
     
     
         14 . The system of  claim 13 , wherein the processor is further configured to update the query planning data structure using the coexistence implications of the tags that have been observed together in the groups of one or more tags of the data records. 
     
     
         15 . The system of  claim 13 , wherein the processor is further configured to update the query planning data structure to store non-redundant metrics for at least one tag of the groups of one or more tags using the coexistence implications of the tags that have been observed together in the groups of one or more tags of the data records. 
     
     
         16 . The system of  claim 12 , further comprising a non-volatile memory coupled to the processor and configured to store a telemetry data structure, wherein the telemetry data structure is configured to store a non-redundant association of a tag to metrics. 
     
     
         17 . The system of  claim 16 , wherein the processor is further configured to update the telemetry data structure to remove a redundant association of a tag to metrics using the coexistence implications of the tags that have been observed together in the groups of one or more tags of the data records. 
     
     
         18 . The system of  claim 12 , further comprising a non-volatile memory coupled to the processor and configured to store an index data structure. 
     
     
         19 . The system of  claim 12 , wherein the processor is further configured to use reduce a storage size of a stored version of at least one of the received data records using the coexistence implications of the tags that have been observed together in the groups of one or more tags of the data records. 
     
     
         20 . A computer program product for optimizing data storage, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
 receiving a time series data stream comprising a plurality of data records, wherein each data record received in the time series data stream is tagged with a group of one or more tags;   identifying one or more implications based on tags that have been observed together in the groups of one or more tags of the plurality of data records, wherein an implication indicates that a query of a first tag has a response that is identical to a query of a second tag;   tracking coexistence implications of tags that have been observed together in the groups of one or more tags of the data records; and   using the coexistence implications of tags to optimize a query.