FILE TABLE INDEX AGGREGATE STATISTICS

• US 20180300350A1
• Filed: 04/18/2017
• Published: 10/18/2018
• Est. Priority Date: 04/18/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: MAINALI, Shane Kumar, VARADARAJAN, Krishnan, ZHANG, Quan, DEVARAJU, Jegan, SUN, Zichen, FENG, Hao, WANG, Ju, CHABLANI, Manish
• Granted Patent: US 10,909,074 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Embodiments provide a method to collect aggregate information or usage data quickly and efficiently with minimal lag. Additionally, the system can use this aggregate information internally for improved load balancing, better data placement, optimization, and enhanced debugging. The system can quickly look at aggregate information across a huge amount of data and drill down cheaply because the aggregate information is generated using existing processes. Aggregated statistics storage and collection may be built on top of an LSM tree used to store a persistent index for a cloud storage system. The statistics may also represent the result of an operation (e.g., max, min, sum, average) on selected parameter(s) or attribute(s) of stored data. Aggregate statistics values may be efficiently maintained during index merge and garbage collection processes or any other index management. As delta LSM trees are merged into a base LSM tree, the aggregates are updated in delta fashion.

Claims

1. A storage system, comprising:

a stream layer comprising a plurality of storage nodes for storing user data; and

a partition layer comprising a plurality of table servers each configured to manage data storage in assigned partitions and to create a file table index for each partition, wherein the file table index comprises a tree structure having leaf pages having data sorted in key order and one or more levels of parent pages above the leaf pages, wherein the parent pages comprise indexing keys and pointers to one or more child pages, and wherein statistics are stored with the leaf page data and aggregated statistics are stored with the pointers in the parent pages.

2. The system of claim 1, wherein the aggregated statistics in parent pages are created based upon statistics or aggregated statistics in a child page.

3. The system of claim 1, wherein the statistics in the leaf pages correspond to one or more attributes of customer data in the leaf pages, and wherein each of the aggregated statistics in a first parent index page are associated with a group of leaf pages in a key-sequence order.

4. The system of claim 1, wherein the table server is configured to collect statistics from a particular key range by iterating from a low key to a high key and accumulating an aggregated value from the statistics at each key in the range.

5. The system of claim 1, wherein the table servers are configured to:

store aggregate statistics with one or more child-page pointers in a hierarchical manner across multiple layers of index pages.

6. The system of claim 1, wherein the table servers are configured to:

maintain a base file table index for a partition;

create a delta file table index for data written to the partition; and

merge the delta file table index into the base file table index to create a new file table index.

7. The system of claim 1, wherein a file table garbage collection function is configured to gradually backfill aggregates for existing data.

8. The system of claim 1, wherein querying across a partition to collect statistics is performed at least in part by collecting aggregated statistics from parent index pages without obtaining statistics directly from keys in a key range associated with the parent index page.

9. The system of claim 1, wherein the table servers are configured to:

query across a plurality of partitions by aggregating results of individual queries to each of the plurality of partitions.

10. A computer-implemented method for aggregating statistics in a distributed storage system, comprising:

creating a file table index for data stored in the distributed storage system, the file table index comprising a tree structure having leaf pages with data sorted in key order and one or more levels of parent pages above the leaf pages, the parent pages comprise keys and pointers to one or more child pages;

storing statistics for each key in the leaf pages;

storing aggregated statistics with the pointers in the parent pages.

11. The method of claim 10, wherein the aggregated statistics in parent pages are created based upon statistics or aggregated statistics in a child page.

12. The method of claim 10, wherein the statistics in the leaf pages correspond to one or more attributes associated with data stored in the leaf pages, and wherein each of the aggregated statistics in a first parent index page are associated with a group of leaf pages in a key-sequence order.

13. The method of claim 10, further comprising:

collecting statistics from a selected key range by iterating from a low key to a high key and accumulating an aggregated statistics value using the statistics at each key in the range.

14. The method of claim 13, further comprising:

adding the aggregated statistics value along with a child-page pointer to a parent index page.

15. The method of claim 14, further comprising:

iterating across all keys in a partition to add aggregated statistics values along with child-page pointers in a hierarchical manner across all parent index pages in the file table index.

16. The method of claim 10, further comprising:

maintaining a base file table index for a partition;

creating a delta file table index for data written to the partition; and

merging the delta file table index into the base file table index to create a new file table index, wherein the base file table index generates new leaf pages and new parent index pages and removes old leaf pages and parent index pages.

17. The method of claim 16, wherein the new file table index is created by:

creating a new leaf page having keys found in an original leaf page of the base file table index combined in sequence with the keys that were not found in the base file table index;

creating a new parent index page having at least a key and a pointer to the new leave page;

removing the original leaf page; and

removing an original parent page that pointed to the original leaf page.

18. The method of claim 10, further comprising:

backfilling aggregated statistics for existing data using a file table garbage collection function.

19. The method of claim 10, further comprising:

querying across a partition to collect statistics for a key range by collecting at least some aggregated statistics from parent index pages without obtaining statistics directly from customer data in the key range.

20. The method of claim 10, further comprising:

querying across a plurality of partitions by aggregating results of individual queries to each of the plurality of partitions.