Caching Systems And Methods

• US 20150234922A1
• Filed: 10/20/2014
• Published: 08/20/2015
• Est. Priority Date: 02/19/2014
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: Snowflake Computing Inc. (Snowflake, Inc.)
• Inventors: Dageville, Benoit, Cruanes, Thierry, Zukowski, Marcin
• Granted Patent: US 11,809,451 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: A61F 5/566 Intra-oral devices
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5016 : the resource being the memory
• CPC Class Codes: G06F 9/5044 : considering hardware capabilities
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 : involving task migration
• CPC Class Codes: H04L 67/1095 : Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Example caching systems and methods are described. In one implementation, a method identifies multiple files used to process a query and distributes each of the multiple files to a particular execution node to execute the query. Each execution node determines whether the distributed file is stored in the execution node'"'"'s cache. If the execution node determines that the file is stored in the cache, it processes the query using the cached file. If the file is not stored in the cache, the execution node retrieves the file from a remote storage device, stores the file in the execution node'"'"'s cache, and processes the query using the file.

Claims

1. A method comprising:

identifying a plurality of files used to process a query;

distributing each of the plurality of files to a particular execution node, wherein each execution node is configured to execute the query with the files distributed to that execution node;

determining, by each execution node, whether the distributed file is stored in the execution node'"'"'s cache;

responsive to determining that the distributed file is stored in the execution node'"'"'s cache, processing, using one or more processors, the query using the file stored in the cache; and

responsive to determining that the distributed file is not stored in the execution node'"'"'s cache;

retrieving the file from a remote storage device;

storing the file in the execution node'"'"'s cache; and

processing, using the one or more processors, the query using the file.

2. The method of claim 1, further comprising updating metadata information based on files currently stored locally in the execution node'"'"'s cache.

3. The method of claim 1, wherein storing the file in the execution node'"'"'s cache includes determining whether to store the distributed file in a fast memory device or a slower storage device.

4. The method of claim 3, wherein determining whether to store the distributed file in a fast memory or a slower storage device includes implementing a least recently used (LRU) algorithm.

5. The method of claim 4, wherein the LRU algorithm further identifies data to remove from a particular execution node'"'"'s cache.

6. The method of claim 1, wherein distributing each of the plurality of files to a particular execution node includes analyzing metadata associated with the execution nodes.

7. The method of claim 1, wherein each execution node'"'"'s cache includes a first storage portion and a second storage portion, wherein the first storage portion is significantly faster than the second storage portion.

8. The method of claim 1, wherein the received query includes a single instruction that is applied to the plurality of files substantially simultaneously.

9. The method of claim 1, wherein retrieving the file from a remote storage device includes:

determining which portions of the file are used to process the query; and

retrieving only the portions of the file used to process the query from the remote storage device.

10. The method of claim 1, further comprising storing the portions of the file used to process the query in the execution node'"'"'s cache.

11. The method of claim 1, further comprising modifying a data structure of the retrieved file prior to storing the file in the execution node'"'"'s cache.

12. The method of claim 11, wherein modifying the data structure of the retrieved file includes decrypting the retrieved file.

13. The method of claim 11, wherein modifying the data structure of the retrieved file includes decompressing the retrieved file.

14. An apparatus comprising:

a resource manager configured to identify a plurality of files used to process a query; and

an execution platform coupled to the resource manager, the execution platform including a plurality of execution nodes configured to process the query using the plurality of files, each execution node including a cache configured to store data retrieved from a plurality of remote storage devices, the execution platform further configured to distribute the plurality of files to at least one of the plurality of execution nodes based on metadata associated with the plurality of execution nodes, each execution node further including a processor configured to process the query using at least one of the plurality of files;

wherein the execution platform is further configured to determine whether the files are stored in an execution node'"'"'s cache, responsive to determining that a particular file is not stored in the execution node'"'"'s cache, the execution platform is configured to instruct the execution node to retrieve the file from the remote storage device, cache the retrieved file in the execution node'"'"'s cache, and process the query using the retrieved file.

15. The apparatus of claim 14, wherein each execution node'"'"'s cache includes a memory device and a disk storage device.

16. The apparatus of claim 15, wherein the execution platform is further configured to determine whether to cache a file in the memory device or the disk storage device of the execution node'"'"'s cache.

17. The apparatus of claim 14, wherein the execution platform is segmented into a plurality of virtual warehouses, each virtual warehouse including a portion of the plurality of execution nodes.

18. The apparatus of claim 14, wherein the execution platform is further configured to modify a data structure associated with a particular file prior to caching the particular file.

19. An apparatus comprising:

a resource manager configured to identify a plurality of files used to process a query; and

means for executing data processing tasks, the means for executing including a plurality of execution nodes configured to process the query using the plurality of files, each execution node including a cache configured to store data retrieved from a plurality of remote storage devices, the means for executing distributing the plurality of files to at least one of the plurality of execution nodes based on metadata associated with the plurality of execution nodes, each execution node further including a processor configured to process the query using at least one of the plurality of files;

the means for executing further determining whether the files are stored in an execution node'"'"'s cache, responsive to determining that a particular file is not stored in the execution node'"'"'s cache, the means for executing instructs the execution node to retrieve the file from the remote storage device, cache the retrieved file in the execution node'"'"'s cache, and process the query using the retrieved file.

20. The apparatus of claim 19, wherein the caches in the plurality of execution nodes comprise a distributed cache managed by the means for executing data processing tasks.