Determining and extracting changed data from a data source

• US 8,924,429 B1
• Filed: 04/16/2014
• Issued: 12/30/2014
• Est. Priority Date: 03/18/2014
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Fisher, William, Maag, Peter
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US14/254,773
• Time in Patent Office: 258 Days
• Field of Search: 707/695, 707/802
• US Class Current: 707/802
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

According to certain aspects, a computer system may be configured to obtain information indicating a plurality of groupings of data of a data source, the information indicating a number of data items included in each of the plurality of groupings; determine a first grouping of the plurality of groupings including one or more data items that have changed by comparing a first number of data items included in the first grouping and a historical number of data items included in each of the plurality of groupings; access data items included in the first grouping from the data source; compare the data items included in the first grouping to data items of a corresponding compressed local version of the first grouping of data items; extract changed data items of the first grouping; and forward the extracted changed data items to a destination system.

Claims

1. A computer system configured to obtain changed data from a data source, the computer system comprising:

one or more hardware computer processors configured to execute code in order to cause the system to;

obtain information indicating a plurality of groupings of data of a data source, the information indicating a number of data items included in each of the plurality of groupings;

determine a first grouping of the plurality of groupings including one or more data items that have changed by comparing a first number of data items included in the first grouping and a historical number of data items included in each of the plurality of groupings;

access data items included in the first grouping from the data source;

compare the data items included in the first grouping to data items of a corresponding local version of the first grouping to determine which data items of the first grouping from the data source have changed, wherein the corresponding local version of the first grouping of data items is a compressed version of the first grouping of data items;

extract the changed data items of the first grouping; and

forward the extracted changed data items to a destination system.

2. The system of claim 1, wherein the compressed version of the first grouping of data items is a space-efficient probabilistic data structure including information about data items included in the first grouping at a first time prior to said obtaining the information indicating the plurality of groupings of the data of the data source.

3. The system of claim 2, wherein the space-efficient probabilistic data structure is configured to determine whether a particular data item included in the first grouping was included in the first grouping at the first time.

4. The system of claim 3, wherein the Bloom filter is selected from a plurality of Bloom filters that can each include a different number of data items.

5. The system of claim 2, wherein the space-efficient probabilistic data structure is a Bloom filter.

6. The system of claim 1, wherein the compressed version of the data does not comprise a copy of the data items of the first grouping.

7. The system of claim 1, wherein the corresponding local version of the data is stored on first storage and the extracted changed data items forwarded to the destination system are stored on second storage, wherein the first storage has a smaller storage capacity than the second storage.

8. The system of claim 7, wherein the first storage is a Network Attached Storage (NAS).

9. The system of claim 1, wherein the data source is a database or a file.

10. The system of claim 1, wherein the plurality of groupings is based on timestamps of respective data items, wherein the timestamps indicate respective times at which data items were last updated.

11. A method of obtaining changed data from a data source, the method comprising:

obtaining, by one or more hardware computer processors, information indicating a plurality of groupings of data of a data source, the information indicating a number of data items included in each of the plurality of groupings;

determining, by the one or more hardware computer processors, a first grouping of the plurality of groupings including one or more data items that have changed by comparing a first number of data items included in the first grouping and a historical number of data items included in each of the plurality of groupings;

accessing, by the one or more hardware computer processors, data items included in the first grouping from the data source;

comparing, by the one or more hardware computer processors, the data items included in the first grouping to data items of a corresponding local version of the first grouping to determine which data items of the first grouping from the data source have changed, wherein the corresponding local version of the first grouping of data items is a compressed version of the first grouping of data items;

extracting, by the one or more hardware computer processors, the changed data items of the first grouping; and

forwarding, by the one or more hardware computer processors, the extracted changed data items to a destination system.

12. The method of claim 11, wherein the compressed version of the first grouping of data items is a space-efficient probabilistic data structure including information about data items included in the first grouping at a first time prior to said obtaining the information indicating the plurality of groupings of the data of the data source.

13. The method of claim 12, wherein the space-efficient probabilistic data structure determines whether a particular data item included in the first grouping was included in the first grouping at the first time.

14. The method of claim 12, wherein the space-efficient probabilistic data structure is a Bloom filter.

15. The method of claim 11, wherein the compressed version of the data does not comprise a copy of the first grouping.

16. The method of claim 11, wherein the corresponding local version of the data is stored on first storage and the extracted changed data items forwarded to the destination system are stored on second storage, wherein the first storage has a smaller storage capacity than the second storage.

17. The method of claim 16, wherein the first storage is a Network Attached Storage (NAS).

18. The method of claim 11, wherein the data source is a database or a file.

19. The method of claim 11, wherein the plurality of groupings is based on timestamps of respective data items, wherein the timestamps indicate respective times at which data items were last updated.

20. A non-transitory computer readable storage medium comprising instructions for obtaining changed data from a data source that cause a computer processor to:

obtain information indicating a plurality of groupings of data of a data source, the information indicating a number of data items included in each of the plurality of groupings;

determine a first grouping of the plurality of groupings including one or more data items that have changed by comparing a first number of data items included in the first grouping and a historical number of data items included in each of the plurality of groupings;

access data items included in the first grouping from the data source;

compare the data items included in the first grouping to data items of a corresponding local version of the first grouping to determine which data items of the first grouping from the data source have changed, wherein the corresponding local version of the first grouping of data items is a compressed version of the first grouping of data items,

wherein the compressed version of the first grouping of data items is a space-efficient probabilistic data structure including information about data items included in the first grouping at a first time prior to said obtaining the information indicating the plurality of groupings of the data of the data source, and wherein the space-efficient probabilistic data structure is configured to determine whether a particular data item included in the first grouping was included in the first grouping at the first time;

extract the changed data items of the first grouping; and

transmit the extracted changed data items to a destination system.