Efficient method to find changed data between indexed data and new backup

An apparatus, method, and system for updating a file index in a search engine in a data backup system to reflect file changes introduced in a new backup is disclosed. The operations comprise: generating a first external file, the first external file comprising file hashes for files already indexed in a file index in a search engine of a data backup storage system that are not associated with a deleted status; generating a second external file, the second external file comprising file hashes for files in a new backup; determining one or more file changes introduced in the new backup based on a comparison between the first external file and the second external file; and updating the file index in the search engine to reflect the one or more file changes introduced in the new backup.

FIELD OF THE INVENTION

Embodiments of the present invention relate generally to data storage systems. More particularly, embodiments of the invention relate to data indexing in a data backup storage system.

BACKGROUND

In a typical data protection scenario, backups are scheduled against the same target. Examples of such backups may include: 1) Backing up the same folder set according to scheduled policies that run daily, or 2) Backing up a Network Data Management Protocol (NDMP) device according to scheduled policies that run weekly. All files of these scheduled backups need to be indexed, so that they are available for search.

There are challenges associated with indexing backed up files. Backups can be very large. For example, if a customer wants to back up a whole NDMP device, one backup could contain as many as 500 million files. As backups are typically generated daily, all files in each of these large backups need to be indexed. It can be inefficient to index all files of all backups, as such indexing requires too many system resources, and there can be a large number of duplicates. Therefore, the general solution involves indexing only unique files and providing an effective way to map files to backups. Accordingly, when indexing files of a new backup, the first goal is to determine which files have already been indexed, and which previously existing files have been removed from the new backup.

An existing solution relies on an underlying indexing engine of the search engine (e.g., Elasticsearch) to avoid indexing duplicate files. For example, when Elasticsearch is used as the search engine, a unique hash identifier (id) is generated for each file, the existing solution uses a unique hash identifier (id) generated for each file as the Elasticsearch document identifier. Elasticsearch provides the ability to ensure that files with the same document identifier can only be ingested once into the index.

This existing solution relies on Elasticsearch, but Elasticsearch has a serious performance issue when hash-based identifiers are used. As more and more documents are ingested into the index, performance degrades significantly.

DETAILED DESCRIPTION

Embodiments of the disclosure relate to an apparatus, method, and system for updating a file index in a search engine in a data backup system to reflect file changes introduced in a new backup. A first external file may be generated, the first external file comprising file hashes for files already indexed in a file index in a search engine of a data backup storage system that are not associated with a deleted status. A second external file may be generated, the second external file comprising file hashes for files in a new backup. One or more file changes introduced in the new backup may be determined based on a comparison between the first external file and the second external file. Thereafter, the file index in the search engine may be updated to reflect the one or more file changes introduced in the new backup.

In one embodiment, the new backup is associated with a backup target indicative of a source of the new backup, and only file hashes for already-indexed files that are associated with the same backup target are included in the first external file.

In one embodiment, the backup target comprises a directory name or a virtual machine (VM) name.

In one embodiment, a file hash for each file is calculated based on a combination of a backup server identifier, a backup identifier, a file full path, and a time of last modification associated with the file.

In one embodiment, the one or more file changes introduced in the new backup comprise one or more files newly added in the new backup, one or more files that have been deleted in the new backup, or a combination thereof.

In one embodiment, updating the file index in the search engine to reflect the one or more file changes comprises adding one entry to the file index for each of the one or more files newly added in the new backup and/or associating a respective entry for each of the one or more files that have been deleted in the new backup with a deleted status.

In one embodiment, the file hashes in the first and second external files are sorted based on their values before determining the one or more file changes.

FIG.1is a block diagram illustrating a storage system according to one embodiment of the invention. Referring toFIG.1, system100includes, but is not limited to, one or more client systems101-102communicatively coupled to storage system104over network103. Clients101-102may be any type of clients such as a host or server, a personal computer (e.g., desktops, laptops, and tablets), a “thin” client, a personal digital assistant (PDA), a Web enabled appliance, or a mobile phone (e.g., Smartphone), etc. Alternatively, any of clients101-102may be a primary storage system (e.g., local data center) that provides storage to other local clients, which may periodically back up the content stored therein to a backup storage system (e.g., a disaster recovery site or system), such as storage system104. Network103may be any type of networks such as a local area network (LAN), a wide area network (WAN) such as the Internet, a fiber network, a storage network, or a combination thereof, wired or wireless. Clients101-102may be in physical proximity or may be physically remote from one another. Storage system104may be located in proximity to one, both, or neither of clients101-102.

Storage system104may include or represent any type of servers or a cluster of one or more servers (e.g., cloud servers). For example, storage system104may be a storage server used for various different purposes, such as to provide multiple users or client systems with access to shared data and/or to back up (or restore) data (e.g., mission critical data). Storage system104may provide storage services to clients or users via a variety of access interfaces and/or protocols such as file-based access protocols and block-based access protocols. The file-based access protocols may include the network file system (NFS) protocol, common Internet file system (CIFS) protocol, and direct access file system protocol, etc. The block-based access protocols may include the small computer system interface (SCSI) protocols, Internet SCSI or iSCSI, and Fibre channel (FC) protocol, etc. Storage system104may further provide storage services via an object-based protocol and Hadoop distributed file system (HDFS) protocol.

In one embodiment, storage system104includes, but is not limited to, storage service engine106(also referred to as service logic, service module, or service unit, which may be implemented in software, hardware, or a combination thereof), optional deduplication logic107, and one or more storage units or devices108-109communicatively coupled to each other. Storage service engine106may represent any storage service related components configured or adapted to provide storage services (e.g., storage as a service) to a variety of clients using any of the access protocols set forth above. For example, storage service engine106may include backup logic121and restore logic122. Backup logic121is configured to receive and back up data from a client (e.g., clients101-102) and to store the backup data in any one or more of storage units108-109. Restore logic122is configured to retrieve and restore backup data from any one or more of storage units108-109back to a client (e.g., clients101-102).

Storage units108-109may be implemented locally (e.g., single node operating environment) or remotely (e.g., multi-node operating environment) via interconnect120, which may be a bus and/or a network (e.g., a storage network or a network similar to network103). Storage units108-109may include a single storage device such as a hard disk, a tape drive, a semiconductor memory, multiple storage devices such as a redundant array system (e.g., a redundant array of independent disks (RAID)), a system for storage such as a library system or network attached storage system, or any other appropriate storage device or system. Some of storage units108-109may be located locally or remotely accessible over a network.

In response to a data file to be stored in storage units108-109, according to one embodiment, deduplication logic107is configured to segment the data file into multiple segments (also referred to as chunks) according to a variety of segmentation policies or rules. Deduplication logic107may choose not to store a segment in a storage unit if the segment has been previously stored in the storage unit. In the event that deduplication logic107chooses not to store the segment in the storage unit, it stores metadata enabling the reconstruction of the file using the previously stored segment. As a result, segments of data files are stored in a deduplicated manner, either within each of storage units108-109or across at least some of storage units108-109. The metadata, such as metadata110-111, may be stored in at least some of storage units108-109, such that files can be accessed independent of another storage unit. Metadata of each storage unit includes enough information to provide access to the files it contains.

In one embodiment, storage system104further includes a storage manager or storage controller (not shown) configured to manage storage resources of storage system104, such as, for example, storage space and processing resources (e.g., processor, memory, network resources). The storage manager or controller may be accessed by an administrator of management console or server160remotely via a management or configuration interface (not shown). The administrator can provision and manage storage resources based on a set of policies, rules, and/or service level agreements. The storage resources may be virtualized into a pool of virtual storage resources, where underlying physical storage resources represented by the corresponding virtual storage resources may be implemented locally, remotely (e.g., hosted by another storage system), or both. The virtual storage resources can be provisioned, allocated, and/or defined by an administrator or automatically by the storage manager based on a set of software-defined policies. The virtual storage resources may be represented in one or more virtual machines (e.g., virtual storage systems) managed by one or more virtual machine managers (VMMs). Each of the virtual machines can be provisioned to provide a particular type of storage services (e.g., file-based, block-based, object-based, or HDFS) to a client based on a storage policy or service level agreement associated with that particular client as part of software-defined storage services.

Referring toFIGS.2A and2B, diagrams200A,200B illustrating performance issues related to using hash-based document identifiers with the indexing engine of Elasticsearch are shown.FIG.2A, which shows average ingestion speeds, shows that the ingestion speed associated with using hash-based document identifiers starts about 20% slower than the ingestion speed associated with using native Elasticsearch-generated identifiers. But over time, as the number of files increases, the ingestion speed associated with using hash-based document identifiers very rapidly drops.

FIG.2Bshows the amount of time it takes to index a 10,000-item bulk file. When native Elasticsearch-generated identifiers are used, the amount of time stays fairly consistently below one second (with only brief small spikes), even as the total number of items in the index increases. However, when hash-based identifiers are used, the amount of time quickly begins to encounter spikes stretching into minutes for the same operation. As the index approaches 3 million items in size, the spikes associated with using hash-based identifiers become the norm, and the ingestion speed is reduced to a crawl.

In one embodiment, the search engine (e.g., Elasticsearch) is not used to avoid indexing duplicate files. Thus, the search engine do not need to use hash-based identifiers as document identifiers. The differences between data that has been indexed with previous backups and data in a new backup may be determined independently from the search engine. Only changed data is then imported into the search engine for indexing. As the hash-based identifiers are not used as document identifiers of the search engine, the performance issue described in detail above can be resolved. In one embodiment, a memory controllable way may be used to determine the differences, thus accommodating the potentially large size of the backup.

In one embodiment, when ingesting files, the c (e.g., Elasticsearch) is configured to generate native document identifiers for the files. For each file ingested, a unique file hash is also written to the search engine: the file hash may be calculated based on a combination of a backup server identifier, a backup identifier, a file full path, and a time of last modification associated with the file. Any suitable hashing algorithm, such as MD5, or others, may be used in the calculation of the file hash.

In one embodiment, each of the indexed files is also assigned in the search engine with a property indicative of a backup target (hereinafter the property may be simply referred to as Backup Target). The Backup Target property identifies the source of the file (a folder name or a virtual machine “VM” name). In one embodiment, files in the new backup are compared against only the already-indexed data that has the same Backup Target. This is to exploit the fact that the most duplication is found in the backup sequence associated with a same Backup Target.

Assume the new backup is a backup of a folder named “MyFolder.” In other words, the Backup Target property is “MyFolder.” The hashes of existing already-indexed files from the same backup target may be read from the search engine (e.g., Elasticsearch) with the query: Backup Target=“MyFolder” and Status !=“deleted” (that is, the Backup Target property associated with the file is “MyFolder” and the status of the file indicates the file has not been deleted). The query operation may use a memory-efficient scroll query method.

The file hashes obtained from the query may be exported to a first external file (e.g., “lastbackup.txt”) (external to the search engine) and sorted by the values of the hashes. An external (to the search engine) sorting method (e.g., with a merge sort algorithm) may be used to control memory usage. The file metadata from the new backup is read, and a hash generated for each file based on the above-described hashing scheme. The hashes and the metadata (name, path, last modified time, etc.) are stored in a second external file (e.g., “newbackup.txt”) and sorted by values of the hashes.

The hashes in the first and the second external files are compared. In particular, the two external files may be read in chunks. If a hash exists in the second external file but does not exist in the first external file, then the corresponding file is a newly added file that has not been indexed. If a hash exists in the first external file but does not exist in the second external file, then the file has been deleted in the new backup.

The newly added files thus identified are then ingested into the search engine. Status for the files that are identified as having been deleted in the new backup can be changed to “deleted.”

If there are additional new backups to be processed, the second external file may be renamed to serve as a first external file (e.g., renaming “newbackup.txt” to “lastbackup.txt”) for the processing of the next new backup. The operations comprising generating a new second external file, comparing the two external files, updating the index in the search engine, and renaming the second external file may be repeated until all new backups have been processed.

Referring toFIG.3, a diagram300illustrating an example method for updating a file index in a search engine based on a new backup according to one embodiment is shown. The hashes of existing already-indexed files from the same backup target may be read from the search engine (e.g., Elasticsearch)310, as described in detail above. The file hashes obtained from the query may be exported to a first external file (cache)330and sorted by the values of the hashes. The file metadata from the new backup320is read, and a hash generated for each file based on the above-described hashing scheme. The hashes and the metadata (name, path, last modified time, etc.) are stored in a second external file (cache)340and sorted by the values of the hashes.

The hashes in the first external cache330and in the second external cache340are compared. If a hash exists in the second external file but does not exist in the first external file, then the corresponding file is a newly added file that has not been indexed. If a hash exists in the first external file but does not exist in the second external file, then the file has been deleted in the new backup. Thus, at block350, files6and7have been identified as newly added files from the new backup320, and files3and4have been identified as having been deleted in the new backup320.

The newly added files thus identified are then ingested into the search engine. Status for the files that are identified as having been deleted in the new backup320can be changed to “deleted.”

If there are additional new backups to be processed, the second external cache may be renamed to serve as a first external cache for the processing of the next new backup. The operations comprising generating a new second external cache base on the next new backup, comparing the two external caches, updating the index in the search engine, and renaming the second external cache may be repeated until all new backups have been processed.

Referring toFIG.4, a diagram400illustrating index updates in the search engine based on daily backups according to one embodiment is shown. As illustrate inFIG.4, the relevant Backup Target here is the folder “FolderA”420. On October 3, a first backup of the folder “FolderA”420comprising files “File1” through “File5” is created. As all five files are newly added, they are all ingested into the search engine410for indexing. Thereafter, before performing the daily backup of the folder “FolderA”420on October 4, files “File3” and “File4” have been deleted from the folder420, and files “File6” and “File7” have been newly added to the folder420. Thus, after performing the backup of the folder “FolderA”420on October 4, these data changes in the new daily backup are determined using the operations described in detail above. The file index in the search engine410is updated accordingly. In particular, new entries are created for files “File6” and “File7,” and the status associated with files “File3” and “File4” is changed to “deleted.”

Furthermore, before performing the daily backup of the folder “FolderA”420on October 5, the file “File2” has been deleted from the folder420, and the file “File3” has been re-added to the folder420. Thus, after performing the backup of the folder “FolderA”420on October 5, these data changes in the new daily backup are determined using the operations described in detail above. It should be appreciated that the re-added file “File3” is simply identified as a newly added file distinct from the previously deleted file “File3, even though their contents may be the same, because they have different file hashes as a result of having different backup identifiers and different times of last modification. The file index in the search engine410is then updated accordingly. In particular, a new entry is created for the re-added file “File3,” and the status associated with the file “File2” is changed to “deleted.”

It should be appreciated that because the time of last modification is used in the calculation of the file hash, a file content change will be treated as deletion of the original file and addition of a new file. It should be further appreciated that when a file is already indexed, but is not found in a new backup, the index entry is updated with a status of “deleted”. If a previously-deleted file is added back in another backup, the file would have a new time of last modification. Therefore even if re-added file has the same content, it will be indexed as a new file distinct from the previously-deleted file.

Furthermore, if a file's content is updated, the time of last modification would also change. Therefore the update of file content will be treated as deletion of the old version of the file (with the status of the entry in the index updated to reflect the “deleted” status), and addition of the new version of the file as a new file (with a new entry in the index).

Referring toFIG.5, a diagram500illustrating backup file indexing performance according to embodiments is shown. As can be seen inFIG.5, when up to 400 million items are processed with a duration of up to 40 hours, the index rate is stable at around 4000 items per second with no perceptible performance degradation as the size of the index increases. This represents a significant improvement over the previous existing solution, where the index rate drops to 1000 items per second after ingesting just 3 million items into the search engine.

FIG.6is a flow diagram illustrating a process600of updating a file index in a search engine in a data backup system to reflect file changes introduced in a new backup according to one embodiment of the disclosure. Process600may be performed by processing logic that includes hardware (e.g. circuitry, dedicated logic, etc.), software (e.g., embodied on a non-transitory computer readable medium), or a combination thereof. For example, process600may be performed by processors1501ofFIG.7. Referring toFIG.6, at block610, a first external file may be generated, the first external file comprising file hashes for files already indexed in a file index in a search engine of a data backup storage system that are not associated with a deleted status. At block620, a second external file may be generated, the second external file comprising file hashes for files in a new backup. At block630, one or more file changes introduced in the new backup may be determined based on a comparison between the first external file and the second external file. At block640, the file index in the search engine may be updated to reflect the one or more file changes introduced in the new backup.

Processing module/unit/logic1528, components and other features described herein can be implemented as discrete hardware components or integrated in the functionality of hardware components such as ASICS, FPGAs, DSPs or similar devices. In addition, processing module/unit/logic1528can be implemented as firmware or functional circuitry within hardware devices. Further, processing module/unit/logic1528can be implemented in any combination hardware devices and software components.