Abstract:
The present invention provides a method and system for caching time series data. A computer system for caching time series data is disclosed. The computer system comprises one or more processors, at least one cache, and a computer readable storage medium. The computer readable storage medium contains instructions that, when executed by the one or more processors, causes the one or more processors to perform a set of steps comprising fetching the time series data from a time series data source, calculating one or more expiry timestamps, grouping the plurality of time series datum in to one or more time data chunks based on the one or more expiry timestamps, and storing a copy of the time series data and the one or more expiry timestamps in the at least one cache.

Description:
FIELD OF INVENTION 
       [0001]    The present invention relates to time series data, and in particular, it relates to caching of time series data. 
       BACKGROUND 
       [0002]    Time series data refers to sequences of data points measured over a. span of tune, often spaced at uniform time intervals. Time series data is often stored on a remote server known as historian. The historian is responsible for collecting raw time series data and cleaning raw time series data. For analysis and query purposes, time series data is fetched from the historian. However, due to the ever increasing size of tune series data, retrieval of time series data is an expensive operation in terms of network resources. 
         [0003]    There have been several approaches to optimize the retrieval of time series data. One such approach (US 20110153603, Adiba et al.; US 20110167486, Ayloo et al.) suggests the usage of a cache memory for holding recent time series data. However, this approach is often inefficient as the cached time series data is not reflective of the actual time series data. Time series data is mutable since corrections are often made to the time series data at a later point of time. When a correction is made to the actual time series data, the cached data is no longer valid. Since the current approach does not take into account the mutable nature of time series data, the current approach is inefficient. 
         [0004]    Therefore, in light of the above discussion, there is a need for a method and system which overcomes all the above stated problems. 
       BRIEF DESCRIPTION OF THE INVENTION 
       [0005]    The above-mentioned shortcomings, disadvantages and problems are addressed herein which will be understood by reading and understanding the following specification. 
         [0006]    In embodiments, the present invention provides a computer system for caching time series data. The computer system includes one or more processors, at least one cache, and a computer readable storage medium. The computer readable storage medium contains instructions that, when executed by the one or more processors, causes the one or more processors to perform a set of steps comprising: fetching the time series data from a time series data source, calculating one or more expiry timestamps, grouping the plurality of time series datum in to one or more time data chunks based on the one or more expiry timestamps and storing a copy of the time series data and the one or more expiry timestamps in the at least one cache 
         [0007]    The time series data includes a plurality of time series datum and a fetch timestamp. Each expiry timestamp from the one or more expiry timestamps is calculated using a composite function of the fetch timestamp of the time series data and a recording time associated with a time series datum, such that the expiry timestamp is inversely proportional to the recording time associated with the time series datum and directly proportional to the fetch timestamp of the time series data. Each time data chunk from the one or more time data chunks includes a distinct set of time series datum from the time series data. 
         [0008]    In an embodiment, the one or more processors are configured to receive a request for the time series data, decompose the request into one or more sub requests based on the one or more time data chunks of the time series data, determine the validity of the one or more time data chunks of the time series data based on the one or more expiry timestamps; and serve the one or more sub requests from one of a group consisting of the time series data source and the at least one cache, based on the validity of the one or more time data chunks of the time series data. 
         [0009]    In an embodiment, the one or more processors are configured to determine the validity of the one or more time data chunks by comparing an associated expiry timestamp with a request timestamp associated with the request. In an embodiment, the composite function is monotonically non-increasing function with a predetermined upper limit. In an embodiment, the at least one cache is a browser cache. 
         [0010]    In another aspect, the present invention provides a computer implemented method for caching time series data. The computer implemented method comprises fetching, by one or more processors, the time series data from a time series data source, calculating, by one or more processors, one or more expiry timestamps, grouping, by one or more processors, the plurality of time series datum in to one or more time data chunks based on the one or more expiry timestamps, and storing, by one or more processors, a copy of the time series data and the one or more expiry timestamps in at least one cache. 
         [0011]    Systems and methods of varying scope are described herein. In addition to the aspects and advantages described in this summary, further aspects and advantages will become apparent by reference to the drawings and with reference to the detailed description that follows. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1  illustrates a system for caching time series data, in accordance with various embodiments of the present invention; 
           [0013]      FIG. 2  illustrates a flowchart for serving time series data, in accordance with various embodiments of the present invention; 
           [0014]      FIG. 3  illustrates a flowchart for caching time series data, accordance with various embodiments of the present invention; 
           [0015]      FIG. 4  illustrates a flowchart for caching time series data and serving a request for time series data, in accordance with various embodiments of the present invention; and 
           [0016]      FIG. 5  illustrates a computer node for caching tune series data, in accordance with various embodiments of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0017]    In the following detailed description, reference is made to the accompanying drawings that form a part hereof and in which is shown by way of illustration specific embodiments, which may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the embodiments, and it is to be understood that other embodiments may be utilized and that logical, mechanical, electrical and other changes may be made without departing from the scope of the embodiments. The following detailed description is, therefore, not to be taken in a limiting sense. 
         [0018]      FIG. 1  illustrates a system  100  for caching time series data, in accordance with various embodiments of the present invention. 
         [0019]    The computing system  100  includes a user terminal  110 . In context of the present invention, the user terminal  110  refers to a workstation or a terminal used by a user  120 . The user terminal  110  includes one or more processors, a computer readable storage medium and at least one cache. The user terminal  110  allows the user  120  to retrieve the time series data from a historian server  130 , which is a time series data source. In an embodiment, the user terminal  110  includes a browser with a browser cache. The user  120  uses the browser to view the time series data. The browser stores the time series data in the browser cache for faster access. In another embodiment, the user terminal  110  stores time series in the at least one cache for faster access. In an embodiment, the user terminal  110  allows the user  120  to execute queries on the time series data present on the historian server  130 . 
         [0020]    The historian server  130  stores the time series data. The historian server  130  includes one or more processors, a computer readable storage medium and at least one server side cache. In an embodiment, the historian server  130  receives the time series data from a cluster of application servers  140 , which includes a plurality of time series data sources. In an example as shown in  FIG. 1 , the cluster of application servers  140  includes application server  142 , application server  144 , and application server  146 . Each application server from the cluster of application servers  140  generates a log file which contains the time series data. The log files are sent to the historian server  130  by the cluster of application servers  140 . In an embodiment, the cluster of application servers  140  are advertisements tracking servers that maintain logs about countable metrics, such as clicks &amp; impressions, etc. In an embodiment, the historian server  130  assimilates the log files, cleans the data in the log files by removing inconsistent and incomplete records and stores resultant time series data. In an embodiment, the historian server  130  stores recently accessed time series data in the least one server side cache for faster service. 
         [0021]    It will be appreciated by the person skilled in the art, that while  FIG. 1 , shows the historian server  130  as a single computing device, the historian server  130  can include multiple computing devices connected together. Similarly, it will be appreciated by the person skilled in the art, that While  FIG. 1  shows a single user terminal  110 , there can a plurality of computing devices connected to the historian  130 . The plurality of computing devices includes a chain of computing devices connected sequentially. The present invention is compatible with the chain of computing devices. 
         [0022]    Moreover, it will be appreciated by the persons skilled in the art that while  FIG. 1  shows four application servers  142 ,  144  and  146 , there can be one or more application servers in the cluster of application servers  140 . Further, the application servers can be used for a plurality of purposes such as factory metrics recording, product quality control and automation, weather monitoring, etc. 
         [0023]      FIG. 2  illustrates a flowchart  200  for serving a request for time series data, in accordance with various embodiments of the present invention. The flowchart  200  is implemented using the user terminal  110 . At step  205 , the flowchart  200  initiates. At step  210 , the user terminal  110  receives a request for time series data. In an example, at 7 pm the user  120  requests for time series data between 2 pm and 6 pm. The requested time series data has 6 time series datum, since the granularity of sampling is 1 hour in the current example 
         [0024]    At step  215 , the user terminal  110  calculates one or more expiry timestamps. Continuing the above mentioned example, the user terminal  110  calculates each expiry timestamp from the one or more expiry timestamps using a composite function of a recording time of a time series datum and the current time 7 pm. Each expiry timestamp calculated using the composite function is inversely proportional to the recording time associated with the time series datum (indicated using the notation T record ) and directly proportional to the current time (indicated using the notation T current ). A mathematical representation of the above statement is given below: 
         [0000]      if  T   current   &gt;T   current+X , then  T   expiry N   &gt;T   expiry N+X   1)
 
         [0000]      if  T   record N   &lt;T   record N+Y , then  T   expiry N   &gt;=T   expiry N+Y   2)
 
         [0025]    In an embodiment, the composite function is a monotonically non increasing function between recording timestamp and expiry timestamp, i.e., as the recording time increases the value of the expiry timestamp decreases. 
         [0026]    Continuing the example mentioned above, initially 6 expiry timestamps are calculated using the composite function; each expiry timestamp for each time series datum present in the tune series data. An illustration of a possible composite function with an upper limit of 24 hour is defined below: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 expiry timestamp T expiry = F composite (T record , T current ) 
               
               
                 F composite  (T record , T current )= { 
               
               
                 if (T current  - T record )&lt; 30 minutes, then T expiry  should be T current  + 2 minutes; 
               
               
                 else if 30 minutes &lt;=(T current  - T record )&lt; 5 hours, 
               
               
                 then T expiry  should be T current  + 15 minutes; 
               
               
                 else if 5 hours &lt;= (T current  - T record ) &lt; 24 hours, then T expiry  should be T current   
               
               
                 + 1 hour; 
               
               
                 else, T expiry  should be T current  + 24 hours; 
               
               
                 } 
               
               
                   
               
             
          
         
       
     
         [0027]    Using the abovementioned composite function, the following expiry timestamps are calculated: 
         [0028]    Time series datum 1 8 pm 
         [0029]    Time series datum 2 7:15 pm 
         [0030]    Time series datum 3 7:15 pm 
         [0031]    Time series datum 4 7:15 pm 
         [0032]    Time series datum 5 7:15 pm 
         [0033]    Time series datum 6 7:15 pm 
         [0034]    While the expiry timestamp is calculated for each time series datum in the time series data, there are only two distinct expiry timestamps: 8 pm and 7:15 pm. These two timestamps are final result of step  215 . 
         [0035]    At step  220 , the user terminal  110  decomposes the request into one or more sub requests based on the one or more expiry timestamps. Continuing the abovementioned example, the request is broken in two sub requests, the first sub request for the time series datum having expiry timestamp 8:00 pm and the second sub request for the time series data having expiry timestamp 7:15 pm. 
         [0036]    At step  225 , the user terminal serves the one or more sub request from at least one of the historian  130  and a cache memory. The user terminal  110  will query the cache memory to determine if a copy of time series data exists in the cache, if the copy of time series data exists in the cache the user terminal  110  serves a sub-request from the cache. If the cache does not contain the copy of the time series data, the user terminal  110  retrieves the time series data from the historian server  130 . At step  230 , the flowchart  200  terminates. 
         [0037]      FIG. 3  illustrates a flowchart  300  for caching the time series data, in accordance with various embodiments of the present invention. The flowchart  300  is implemented using the historian server  130 . 
         [0038]    At step  310 , the flowchart  300  initiates. At step  320 , the historian server  130  fetches the time series data from the application servers  140 . In an embodiment, the historian server  130  fetches the time series data in response to a determination that a valid copy of the time series data does not exist locally. In an embodiment, the historian server  130  fetches the time series data in response to a user query. In another embodiment, the historian server  130  automatically fetches the time series data in response to a pre-fetching policy. The time series data includes a plurality of time series datum and a fetch timestamp. The fetch timestamp indicates the time at which the time series data was fetched by the historian server  130 . In an embodiment, the historian server  130  records the fetch timestamp on receiving a request. 
         [0039]    For example, the time series data includes ten time series datum: {45, 65, 78, 90, 112, 120, 123, 145, 170, 210} and a fetch timestamp: 9 pm. The time series data has a sampling period of half an hour. The first time series datum 45 is recorded at 2 pm, the second time series datum 65 is recorded at 2:30 pm, and the rest of the time series data similarly recorded with a periodic interval of half an hour. The fetch timestamp 9 pin indicates that the time series data was fetched at 9 pm. 
         [0040]    At step  330 , the historian server  130  calculates one or more expiry timestamps. Each expiry timestamp from the one or more expiry timestamps is calculated using a composite function of a recording time of a time series datum and the fetch timestamp. Each expiry timestamp calculated using the composite function is inversely proportional to the recording time associated with the time series datum and directly proportional to the fetch timestamp of the time series data. A mathematical representation of the above statement is given below: 
         [0000]      if  T   fetch N   &gt;T   fetch N+X , then  T   expiry N   &gt;T   expiry N+X   1)
 
         [0000]      if  T   record N   &lt;T   record N+Y , then  T   expiry N   &gt;=T   expiry N+Y   2)
 
         [0041]    In an embodiment, the composite function is a monotonically non increasing function between recording timestamp and expiry timestamp, i.e., as the recording tune increases the value of the expiry timestamp decreases. 
         [0042]    Continuing the example mentioned above, initially 10 expiry timestamps are calculated using the composite function; each expiry timestamp for each time series datum present in the time series data. An illustration of a possible composite function with an upper limit of 24 hour is defined below: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 expiry timeStamp T expiry = F composite (T record , T fetch ) 
               
               
                 F composite  (T record , T fetch )= { 
               
               
                  if (T fetch  - T record )&lt; 30 minutes, then T expiry  should be T fetch  + 2 minutes; 
               
               
                  else if 30 minutes &lt;=(T fetch  - T record )&lt; 5 hours,  
               
               
                  then T expiry  should be T fetch  + 15 minutes; 
               
               
                  else if 5 hours &lt;= (T fetch  - T record ) &lt; 24 hours, 
               
               
                  then T expiry  should be T fetch  + 1 hour; 
               
               
                  else, T expiry  should be T fetch  + 24 hours; 
               
               
                  } 
               
               
                   
               
             
          
         
       
     
         [0043]    Using the abovementioned composite function, the following expiry timestamps are calculated: 
         [0044]    Time series datum 1 10 pm 
         [0045]    Time series datum 2 10 pm 
         [0046]    Time series datum 3 10 pm 
         [0047]    Time series datum 4 10 pm 
         [0048]    Time series datum 5 10 pm 
         [0049]    Time series datum 6 9:15 pm 
         [0050]    Time series datum 7 9:15 pm 
         [0051]    Time series datum 8 9:15 pm 
         [0052]    Time series datum 9 9:15 pm 
         [0053]    Time series datum 10 9:15 pm 
         [0054]    While the expiry timestamp is calculated for each tune series datum in the tune series data, there are only two distinct expiry timestamps: 10 pm and 9:15 pm. These two timestamps are final result of step  330 . 
         [0055]    At step  340 , the historian server  130  groups the plurality of time series datum into one or more time data chunks based on the one or more expiry timestamps. In an embodiment, all the time series datum which have the same expiry timestamp value are grouped together to form one time data chunk. Each time data chunk from the one or more time data chunks comprises a distinct set of time series datum from the time series data, i.e. no two time data chunks can have a common time series datum. 
         [0056]    Continuing the abovementioned example, the user terminal groups the ten time series datum into two time data chunks. The first time data chunk includes the tune series datum that have the expiry timestamp 10 pm (Time data chunk 1={45, 65, 78, 90, 112}). The second time data chunk includes the time series datum that have the expiry timestamp 9:15 pm (Time data chunk 2={120, 123, 145, 170, 210}). 
         [0057]    At step  350 , the historian server  130  stores a copy of the time series data and the one or more expiry timestamps in the at least one cache. Expiry timestamps serve as indicators about the validity of the time series data stored in the at least one cache. Any request for the time series data will check the expiry timestamps to verify if the time series data stored in the at least one cache is valid or not. At step  360 , the flowchart  300  terminates. 
         [0058]      FIG. 4  illustrates a flowchart  400  for caching time series data and serving a request for time series data, in accordance with various embodiments of the present invention. The flowchart.  400  is be implemented the historian server  130 . 
         [0059]    At step  405 , the flowchart  400  initiates. Steps  410 - 425  of the flowchart  300  are similar to the steps  310 - 350  of the flowchart  300 . At step  410 , as explained above, the historian server  130  fetches the time series data from the historian server  130 . 
         [0060]    At step  415 , as explained above, the historian server  130  calculates one or more expiry timestamps. Each expiry timestamp from the one or more expiry timestamps is calculated using a composite function of a recording time of a time series datum and the fetch timestamp. Each expiry timestamp calculated using the composite function is inversely proportional to the recording time associated with the time series datum and directly proportional to the fetch timestamp of the time series data. In an embodiment, the composite function is a monotonically non increasing function between recording timestamp and expiry timestamp, i.e., as the value of recording time increases the value of the expiry timestamp decreases. 
         [0061]    At step  420 , the historian server  130  groups the plurality of time series datum into one or more time data chunks based on the one or more expiry timestamps. In an embodiment, all the time series datum which have the same expiry timestamp value are grouped together to form one time data chunk. Each time data chunk from the one or more time data chunks comprises a distinct set of time series datum from the time series data, i.e. no two time data chunks can have a common time series datum. 
         [0062]    At step  425 , the historian server  130  stores a copy of the time series data and the one or more expiry timestamps in the at least one cache. At step  430 , the historian server  130  receives a request for the time series data. In an embodiment, the user  120  makes the request using the browser on the user terminal  110 . Continuing the abovementioned example, the user terminal receives a request for the time series data recorded between 2 pm and 6:30 pm at 9:45 pm. 
         [0063]    At step  435 , the historian server  130  decomposes the request into one or more sub requests based on the one or more time data chunks of the time series data. Continuing the abovementioned example, the request is broken in two sub requests, the first sub request for the first time data chunk and the second sub request for the second time data chunk. 
         [0064]    At step  440 , the historian server  130  determines the validity of the one or more time data chunks of the time series data based on the one or more expiry timestamps. Continuing the abovementioned example, the historian server  130  determines the validity of the first time data chunk and the second time data chunk. The first time data chunk has the expiry timestamp 10 pm, and therefore is valid at 9:45 pm. The second time data chunk has the expiry timestamp 9:15 pm, and therefore is invalid at 9:45 pm. 
         [0065]    At step  445 , the historian server  130  serves the one or more sub requests from one of a group consisting of the time series data source and the at least one cache, based on the validity of the one or more time data chunks of the time series data. Continuing the abovementioned example, the historian server  130  serves the first sub request by retrieving the first time data chunk from the at least one cache as the first time data chunk is still valid. Since the second time data chunk is invalid, the historian server  130  serves the second sub request by fetching the second time data chunk from the application servers  140 . At step  350 , the flowchart  300  terminates. 
         [0066]    By decomposing the request into sub request and chunking the time series data into time data chunks, the present invention is able to create an optimal caching policy for the time series data. Since older time series data values are less likely to change, the composite function is able to calculate expiry timestamps which are reflective of this property. Moreover, by dividing the request in sub requests, the present invention is able to ensure that only the time data chunks which are invalid are served from the time series sources and not the entire time series data. By doing so, the present invention is able to reduce network load and improve speed of access. 
         [0067]      FIG. 5  illustrates a computer node  500  for caching tune series data, in accordance with various embodiments of the present invention. The components of the computer node  500  include, but are not limited to, one or more processors  530 , a memory module  555 , a network adapter  520 , an input-output (I/O) interface  540  and one or more buses that couples various system components to one or more processors  530 . 
         [0068]    The one or more buses represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus. 
         [0069]    The computer node  500  typically includes a variety of computer system readable media. Such media may be any available media that is accessible by the computer node  500 , and includes both volatile and non-volatile media, removable and non-removable media. In an embodiment, the memory module  555  includes computer system readable media in the form of volatile memory, such as random access memory (RAM)  560  and at least one cache  570 . The computer node  500  may further include other removable/non-removable, non-volatile computer system storage media. In an embodiment, the memory module  555  includes a storage system  580 . 
         [0070]    The computer node  500  communicates with one or more external devices  550  and a display  510 , via input-output (I/O) interfaces  540 . In addition, the computer node  500  can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (for example, the Internet) via the network adapter  520 . 
         [0071]    It can be understood by one skilled in the art that although not shown, other hardware and/or software components can be used in conjunction with the computer node  500 . Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays. RAID systems, tape drives, and data archival storage systems, etc. In an embodiment, the configuration and capabilities of the historian  130  and the user terminal  110  is same as configuration and capabilities of the computer node  500 . 
         [0072]    As will be appreciated by one skilled in the art, aspects can be embodied as a system, method or computer program product. Accordingly, aspects of the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system” Furthermore, aspects of the present invention can take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon. 
         [0073]    Any combination of one or more computer readable medium(s) can be utilized. The computer readable medium can be a computer readable storage medium. A computer readable storage medium can be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), an optical fiber, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of the present invention, a computer readable storage medium can be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. 
         [0074]    Computer program code for carrying out operations for aspects of the present invention can be written in any combination of one or more programming languages, including an object oriented programming language and conventional procedural programming languages. 
         [0075]    This written description uses examples to describe the subject matter herein, including the best mode, and also to enable any person skilled in the art to make and use the subject matter. The patentable scope of the subject matter is defined by the claims, and may include other examples that occur to those skilled in the art. Such other examples are intended to be within the scope of the claims if they have structural elements that do not differ from the literal language of the claims, or if they include equivalent structural elements with insubstantial differences from the literal language of the claims.