Systems and methods for a memory model for sparsely updated statistics

Patent metadata

Field	Value
Publication number	US-9760283-B2
Application number	US-201514867335-A
Country	US
Kind code	B2
Filing date	Sep 28, 2015
Priority date	Sep 28, 2015
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

Systems and methods for managing sparsely updated counters in memory include, for a given interval of time and N counters associated with the given interval, managing a first set of the N counters in a first level of storage in the memory, wherein the first level of storage utilizes a hash table to store a counter identifier and a value for each of the first set; and responsive to filling up the first level of storage for a given user in the given interval, managing the first set and a second set of the N counters in a second level of storage in the memory, wherein the set utilizes memory buckets to incrementally store the first set and the second set.

First claim

What is claimed is:

1. A method for managing sparsely updated counters in memory, the method comprising:
for a given interval of time and N counters associated with the given interval, managing a first set of the N counters in a first level of storage in the memory, wherein the first level of storage utilizes a hash table to store a counter identifier and a value for each of the first set; and
responsive to filling up the first level of storage for a given user in the given interval, managing the first set and a second set of the N counters in a second level of storage in the memory, wherein the second level utilizes memory buckets to incrementally store the first set and the second set,
wherein the first level stores an independent set of statistic counters for each user in a same amount of storage for each user with the counter identifier uniquely identifying each of the statistics counters, and wherein the second level stores a distinct set of statistic counters for a given company based on counters seen across all users of the given company.

2. The method of claim 1 , wherein the first set comprises up to N active counters and N active is smaller than N.

3. The method of claim 1 , wherein the first set comprises up to N active counters and N active is smaller than N, wherein the second set comprises up to X counters and N active +X is less than N.

4. The method of claim 1 , wherein the hash table is a linear probing hash table configured to store both the counter identifier and the value.

5. The method of claim 4 , wherein hash entries in the hash table are located sequentially in the memory, and wherein hash entries comprise a key array associated with the counter identifier and a value array associated with the value.

6. The method of claim 1 , wherein, responsive to filling up the first level of storage for a given user in the given interval, the first set is moved to the second level of storage and subsequent counters are updated or added in the second level of storage.

7. The method of claim 1 , wherein the second level of storage utilizes data structures for an Active ID map per company and a per user counter bucket.

8. The method of claim 1 , wherein the counters are associated with a user in a cloud system configured to monitor users for distributed security.

9. The method of claim 1 , further comprising:
analyzing past data to determine most frequently used counters in an interval; and
utilizing the most frequently used counters in the first level and less frequently used counters in the second level.

10. A server configured to manage sparsely updated counters in memory, comprising:
a network interface;
a processor; and
memory storing instructions that, when executed, cause the processor to
for a given interval of time and N counters associated with the given interval, manage a first set of the N counters in a first level of storage in the memory, wherein the first level of storage utilizes a hash table to store a counter identifier and a value for each of the first set; and
responsive to filling up the first level of storage for a given user in the given interval, manage the first set and a second set of the N counters in a second level of storage in the memory, wherein the second level utilizes memory buckets to incrementally store the first set and the second set,
wherein the first level stores an independent set of statistic counters for each user in a same amount of storage for each user with the counter identifier uniquely identifying each of the statistics counters, and wherein the second level stores a distinct set of statistic counters for a given company based on counters seen across all users of the given company.

11. The server of claim 10 , wherein the first set comprises up to N active counters and N active is smaller than N.

12. The server of claim 10 , wherein the first set comprises up to N active counters and N active is smaller than N, wherein the second set comprises up to X counters and N active +X is less than N.

13. The server of claim 10 , wherein the hash table is a linear probing hash table configured to store both the counter identifier and the value.

14. The server of claim 13 , wherein hash entries in the hash table are located sequentially in the memory, and wherein hash entries comprise a key array associated with the counter identifier and a value array associated with the value.

15. The server of claim 10 , wherein, responsive to filling up the first level of storage for a given user in the given interval, the first set is moved to the second level of storage and subsequent counters are updated or added in the second level of storage.

16. The server of claim 10 , wherein the second level of storage utilizes data structures for an Active ID map per company and a per user counter bucket.

17. The server of claim 10 , wherein the counters are associated with a user in a cloud system configured to monitor users for distributed security.

18. The server of claim 10 , wherein the memory storing instructions that, when executed, further cause the processor to
analyze past data to determine most frequently used counters in an interval; and
utilize the most frequently used counters in the first level and less frequently used counters in the second level.

19. A distributed security system, comprising:
a plurality of servers forming a cloud system, wherein a plurality of users are each communicatively coupled to the plurality of servers;
at least one node communicatively coupled to the cloud system, wherein the at least on node is configured to
for a given interval of time and N counters associated with the given interval, manage a first set of the N counters in a first level of storage in the memory, wherein the first level of storage utilizes a hash table to store a counter identifier and a value for each of the first set; and
responsive to filling up the first level of storage for a given user in the given interval, manage the first set and a second set of the N counters in a second level of storage in the memory, wherein the second level utilizes memory buckets to incrementally store the first set and the second set,
wherein the first level stores an independent set of statistic counters for each user in a same amount of storage for each user with the counter identifier uniquely identifying each of the statistics counters, and wherein the second level stores a distinct set of statistic counters for a given company based on counters seen across all users of the given company.

20. The distributed security system of claim 19 , wherein the first set comprises up to N active counters and N active is smaller than N, wherein the second set comprises up to X counters and N active +X is less than N.

Assignees

• KALIPATNAPU Satish
• Pangeni Sushil
• Gaurav Kumar
• Balaiah Chakkaravarthy Periyasamy
• Zscaler Inc

Inventors

• KALIPATNAPU Satish
• Pangeni Sushil
• Gaurav Kumar
• Balaiah Chakkaravarthy Periyasamy

Classifications

• G06F3/0653

  Monitoring storage devices or systems · CPC title

• G06F3/0604 Primary

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title