Temporal based data string intern pools

• US 9,197,710 B1
• Filed: 09/21/2011
• Issued: 11/24/2015
• Est. Priority Date: 07/20/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Matthews, Jacob Burton, Deshpande, Mayur Venktesh, Marifet, Kasem, Wogulis, James Lee
• Primary Examiner(s): DUDEK JR, EDWARD J
• Application Number:
  US13/239,285
• Time in Patent Office: 1,525 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3048 where the topology of the computing system or computing system component explicitly influences the monitoring activity, e.g. serial, hierarchical systems
• CPC Class Codes: G06F 11/3072 where the reporting involves data filtering, e.g. pattern matching, time or event triggered, adaptive or policy-based reporting
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/875 Monitoring of systems including the internet
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04L 67/55 Push-based network services
• CPC Class Codes: H04L 67/75 Indicating network or usage conditions on the user display

Abstract

Configurations for providing temporal based data string intern pools that reuse data strings and decrease unnecessary operations to memory. A data structure representing a string intern pool is allocated for a first time period and one or more strings associated with event data communications are stored in the data structure. To optimize memory usage, if a string associated with an event tracking data communication is located within the data structure, a pointer is then assigned to the string instead of storing the string in the data structure. In a second time period, a second data structure is allocated for another string intern pool and matching strings from event tracking data communications are assigned to pointers for existing strings in the second data structure. The first data structure is maintained during the second time period but no additional strings are written to the first data structure.

Claims

1. A machine-implemented method comprising:

allocating memory for a first data structure;

designating the first data structure as a dead intern pool;

allocating memory for a second data structure;

designating the second data structure as a live intern pool;

during a first interval that is part of a rolling window of time,

obtaining a first string extracted from low-latency web traffic data,

determining the live intern pool does not store the first string,

adding the first string to the live intern pool responsive to the determination that the live intern pool does not store the first string,

obtaining a second string from the low-latency web traffic data,

determining the live intern pool stores the second string, and

assigning a pointer identifying a memory location storing the second string responsive to the determination that the live intern pool stores the second string; and

at an end of the first interval that is part of the rolling window of time,

deallocating memory storing the dead intern pool,

designating the live intern pool as the dead intern pool,

allocating memory for a new data structure, and

designating the new data structure as the live intern pool.

2. The method of claim 1, wherein determining the live intern pool does not store the first string further comprises

determining the dead intern pool does not store the first string;

wherein the adding step comprises adding the first string to the live intern pool responsive to the determination that the live intern pool and the dead intern pool do not store the first string; and

during an interval that is part of a rolling window of time, the method further comprising

obtaining a third string from the low-latency web traffic data,

determining the live intern pool does not store the third string,

determining the dead intern pool stores the third string, and

assigning a pointer identifying a memory location storing the third string responsive to the determination that the dead intern pool stores the third string.

3. The method of claim 1, wherein designating the first data structure as a dead intern pool comprises assigning a first data structure pointer identifying a memory location storing the first data structure;

wherein designating the second data structure as a live intern pool comprises assigning a second data structure pointer identifying a memory location storing the second data structure; and

wherein, at an end of the interval that is part of the rolling window of time,

deallocating memory storing the dead intern pool comprises deallocating memory at a memory location identified by the first data structure pointer,

designating the live intern pool as the dead intern pool comprises assigning the first data structure pointer identifying a memory location identified by the second data structure pointer, and

designating the new data structure as the live intern pool comprises assigning the second data structure pointer identifying a memory location storing the new data structure.

4. The method of claim 1, wherein the interval is a predetermined duration, equivalent to the duration of a second interval in the rolling window of time.

5. The method of claim 4, wherein the first interval and the second interval in the rolling window of time are consecutive.

6. The method of claim 1, wherein the rolling window of time has a predetermined duration.

7. The method of claim 1, wherein:

allocating memory for a first data structure comprises allocating memory block of a predetermined size;

allocating memory for a second data structure comprises allocating memory block of the predetermined size; and

allocating memory for a new data structure comprises allocating memory block of the predetermined size.

8. The method of claim 1, wherein the first string is associated with a first event tracking data communication, the first event tracking data communication comprising event tracking data for tracking an activity associated with a source of the first event tracking data communication.

9. The method of claim 8, wherein the event tracking data includes web site traffic data included in a Hypertext Transfer Protocol (HTTP) request associated with a web site.

10. The method of claim 1, wherein the second string is associated with a second event tracking data communication, the second event tracking data communication comprising event tracking data for tracking an activity associated with a source of the second event tracking data communication.

11. A system of maintaining string intern pools, comprising:

a first data structure designated as a dead intern pool;

a second data structure designated as a live intern pool;

a buffer module queuing and transmitting low-latency web tracking data;

an extraction module extracting a first string and a second string from a low-latency web tracking datum;

a time interval manager keeping track of one or more contiguous time intervals;

a data structure manger

determining the live intern pool does not store a first string,

adding the first string to the live intern pool responsive to the determination that the live intern pool does not store the first string,

determining the live intern pool stores the second string,

assigning a pointer identifying a memory location storing the second string responsive to the determination that the live intern pool stores the second string; and

an intern pool manager, at each end of an interval that is part of a rolling window of time,

deallocating a memory storing the dead intern pool,

designating the live intern pool as the dead intern pool,

allocating memory for a new data structure, and

designating the new data structure as the live intern pool.

12. The system of claim 11, wherein the data structure manager further comprises:

determining the dead intern pool does not store the first string; and

wherein the data structure manager adding the first string to the live intern pool comprises adding the first string to the live intern pool responsive to the determination that the live intern pool and the dead intern pool do not store the first string.

13. The system of claim 12, wherein the extraction module further comprises

extracting a third string from the low-latency web traffic datum;

and

wherein the data structure manager further comprises

determining the live intern pool does not store the third string,

determining the dead intern pool stores the third string, assigning a pointer identifying a memory location storing the third string responsive to the determination that the dead intern pool stores the third string.

14. The system of claim 11 further comprising:

a first data structure pointer identifying a memory location storing the first data structure;

a second data structure pointer identifying a memory location storing the second data structure; and

wherein the intern pool manager, at each end of an interval that is part of a rolling window of time, comprises

deallocating the dead intern pool by deallocating memory at a memory location identified by the first data structure pointer,

designating the live intern pool as the dead intern pool by assigning the first data structure pointer identifying a memory location identified by the second data structure pointer, and

designating the allocated data structure as the live intern pool by assigning the second data structure pointer identifying a memory location storing the new data structure.

15. The system of claim 11, wherein the time interval manager further comprises measuring intervals of equivalent, predetermined durations.

16. The system of claim 11, wherein the time interval manager further comprises measuring consecutive intervals of time.

17. The system of claim 11, wherein the time interval manager further comprises measuring intervals for a rolling window of time of predetermined duration.

18. The system of claim 11, wherein the intern pool manager further comprises allocating memory for a new data structure of a predetermined size.

19. The system of claim 11, wherein the first string is associated with a first event tracking data communication, the first event tracking data communication comprising event tracking data for tracking an activity associated with a source of the first event tracking data communication.

20. The system of claim 11, wherein the second string is associated with a second event tracking data communication, the second event tracking data communication comprising event tracking data for tracking an activity associated with a source of the second event tracking data communication.