KR101599113B1 - 중복제거 저장 시스템내에서 합성 백업 - Google Patents

Abstract

중복제거 저장 시스템은 새로운 입력 데이터가 이미 구축된 합성 백업들의 데이터에서 중복제거되도록 해주며, 그리고 이 목적을 위하여 상기 합성 백업들에 의하여 레퍼런스되는 데이터의 이미 존재하는 다이제스트들에 기초하여, 구축될 합성 백업들을 위한 중복제거 다이제스트들을 효율적으로 계산한다. 구축될 합성 백업의 복수의 입력 데이터 세그먼트들의 각 입력 데이터 세그먼트를 위해, 상기 입력 데이터 세그먼트에 의하여 레퍼런스되는, 저장된 데이터 세그먼트들의 복수의 중복제거 다이제스트들이 인덱스로부터 검색된다. 각각의 입력 데이터 세그먼트는 각각 복수의 고정-크기 데이터 서브-세그먼트들로 파티션된다. 데이터 서브-세그먼트를 위한 중복제거 다이제스트를 산출하는 계산이 수행되는데, 상기 계산은 상기 입력 데이터 서브-세그먼트에 의하여 레퍼런스되는 복수의 저장된 데이터 서브-세그먼트들의 검색된 중복제거 다이제스트들에 기초한다.

Description

중복제거 저장 시스템내에서 합성 백업{SYNTHETIC BACKUPS WITHIN DEDUPLICATION STORAGE SYSTEM}

본 발명은 전반적으로 컴퓨터, 그리고 좀 더 구체적으로 컴퓨팅 저장 환경에서 중복제거 (deduplication) 저장 시스템내에서 합성 백업을 용이하게 하는 것에 관련된 것이다.

중복제거란 여분의 (redundant) 데이터를 감소 및/또는 제거하는 것을 가리킨다. 데이터 중복제거 프로세스에서, 데이터의 중복 카피는 최소량의 여분 카피, 또는 데이터의 단일 카피를 각각 남기면서, 감소 또는 제거된다. 중복제거 프로세스의 사용은 필요한 저장 용량 및 네트워크 대역폭 (bandwidth)의 감소와 같은 다양한 장점을 제공한다. 이런 그리고 기타 장점들로 인하여, 중복제거는 최근 몇 년 사이에 (in recent years) 컴퓨팅 저장 시스템에서 매우 중요한 기술 분야로 부상하였다 (emerged). 중복제거 기능성의 제공에 대한 도전은 통상적으로 대용량 저장소에서 효율적으로 중복된 데이터 패턴을 찾는 것, 그리고 중복제거된 저장-효율적인 (storage-efficient) 형태로 데이터 패턴을 저장하는 것과 같은 측면을 포함한다.

백업 환경에서, 전체 (full) 백업은 백업되는 완전한 데이터 세트를 포함한다. 증분 (incremental) 백업은 전체 또는 증분 백업이든지 간에, 가장 최근의 백업 타임 이후 수정된 데이터 세트의 부분들만을 포함한다 (파일들의 해상도 (resolution)에서 정상적으로). 차등 (differential) 백업은 가장 최근의 전체 백업 이후 수정된 데이터 세트의 부분들만을 포함한다. 증분 및 차등 백업의 장점은 전체 백업보다 데이터를 덜 포함하기 때문에, 저장 및 처리 시간의 관점에서 더 효율적이란 것이다.

백업 데이터 세트를 특정 시점까지 (to a specific point in time) 완전히 복구하기 위해서는, 보통 그 시점 이전의 (preceding) 전체 백업이 복구되고, 그 다음 그 시점까지의 모든 후속 증분 백업이 시간순으로 (in their chronological order) 복구된다. 차등 백업을 이용하여 유사한 프로세스가 수행되지만, 이 경우 전체 백업이 복구된 이후, 오직 하나의 차등 백업만이 일반적으로 복구된다. 명확하게, 전술한 복구 동작은 시간이 많이 소요되고 (time consuming), 단일 백업의 복구보다 더 복잡하다.

위에서 설명된 복구 프로세스의 복잡성을 완화하기 위하여, 합성 백업의 개념 (notion)이 도입되었다. 합성 백업은 한 프로세스를 사용하여 백업 어플리케이션에 의하여 구축되는데, 이 프로세스에서, 특정 시점까지의, 전체 백업 및 그의 후속 증분 백업으로부터의 데이터는 합성 백업에 통합된다 (incorporated). 상기 생성된 합성 백업이 상기 특정 시점까지에 대응하는 실제적인 전체 백업이다. 전술한 백업은 ‘합성’ 백업이라고 일컬어지는데 (is termed) 왜냐하면 그것은, 데이터가 소스 (sources)로부터 읽혀서 백업으로 저장되는, 정상 백업 프로세스에 의해서가 아니라, 이미 존재하는 백업들의 데이터가 합성 백업을 구축하기 위해 사용되는, 합성 백업 프로세스에 의해서 생성되기 때문이다. 합성 백업을 복구하는 것은 전체 백업을 복구하는 것만큼 간단하며, 전술한 것과 같이 증분 또는 차등 백업들을 복구하는 프로세스보다 더 신속하게 수행된다. 합성 백업의 추가적인 장점은 데이터의 측면에서 동일한 전체 백업을 생성하는 것에 비하여, 합성 백업의 생성을 더 빠르게 할 수 있다는 것이다.

합성 백업이 제공하는 효율성 및 기타 특성들에 있어서의 장점들로 인하여, 합성 백업 기능 및 관련 아키텍처들을 하나의 중복제거 저장 시스템으로 통합하는 (integrate) 것이 바람직하다. 따라서, 중복제거 저장 시스템에서 합성 백업을 구축할 수 있도록 해주는 다양한 실시예가 제공된다. 오직 예로서만 제공되는, 한 실시예에서, 중복제거 저장 시스템은, 소스 및 타겟 데이터 세그먼트들 (segments)을 기술하는, 일련의 (a sequence of) 컴팩트한 (compact) 메타 데이터 명령들을 백업 어플리케이션으로부터 수신하며, 이 명령들에 기초하여 중복제거 저장 시스템은 합성 백업을 효율적으로 구축하는데, 기존 백업들의 데이터에 대한 레퍼런스들 (references)을 구축될 합성 백업을 위해 생성되는 메타데이터 구조 (metadata structure)에 추가함에 의해서 한다. 오직 예로서만 제공되는, 다른 실시예에서, 중복제거 저장 시스템은 새로운 입력 데이터가 이미 구축된 합성 백업들의 데이터에서 중복제거되도록 해주며, 그리고 이 목적을 위하여 구축될 합성 백업들을 위한 중복제거 다이제스트들을 효율적으로 계산하는데, 상기 합성 백업들에 의하여 레퍼런스되는 데이터의 이미 존재하는 다이제스트 (digests)에 기초하여 한다. 구축될 합성 백업의 복수의 입력 데이터 세그먼트들의 각 입력 데이터 세그먼트를 위해, 상기 입력 데이터 세그먼트에 의하여 레퍼런스되는, 저장된 데이터 세그먼트들의 복수의 중복제거 다이제스트들이 인덱스 (index)로부터 검색된다 (retrieved). 각각의 입력 데이터 세그먼트는 각각 복수의 고정-크기 (fixed-sized) 데이터 서브-세그먼트들로 파티션되고 복수의 입력 데이터 서브-세그먼트들 (sub-segments)의 각각은 복수의 저장된 데이터 서브-세그먼트들을 레퍼런스할 수 있다. 복수의 입력 데이터 서브-세그먼트들의 각각을 위해, 입력 데이터 서브-세그먼트를 위한 중복제거 다이제스트를 산출하는 계산이 수행되는데, 상기 계산은 상기 입력 데이터 서브-세그먼트들에 의하여 레퍼런스되는 복수의 저장된 데이터 서브-세그먼트들의 검색된 중복제거 다이제스트에 기초한다. 상기 복수의 서브-세그먼트 중복제거 다이제스트들은 합해져서 (aggregated) 각각 입력 데이터 세그먼트의 중복제거 다이제스트를 발생시킨다. 각각 입력 데이터 세그먼트의 상기 중복제거 다이제스트는 합성 백업의 중복제거 다이제스트를 형성한다.

전술한 예시적인 방법 실시예에 추가하여, 다른 예시적인 시스템 및 컴퓨터 제품 실시예들이 제공되고 이들도 전술한 장점들을 가져다준다 (supply).

본 발명의 실시예들이 다음에 첨부되는 도면들을 참조하여, 오직 예로서만, 기술될 것이다:
도 1은 하나의 예시적인 합성 백업 아키텍처를 도시한다;
도 2는 하나의 예시적인 합성 백업의 구축 흐름 (construction flow)을 도시한다;
도 3은 데이터 패턴에서 예시적인 레퍼런스 접근 방식 (approaches)을 도시한다;
도 4는 하나의 중복제거 저장 시스템에서 사용될 합성 백업을 구축하기 위한 하나의 예시적인 방법을 도시한다;
도 5는 하나의 예시적인 중복제거 프로세스를 도시한다;
도 6은 하나의 예시적인 최대의 그리고 시프트된 (maximal and shifted) 데이터 블록을 도시한다;
도 7은 입력 데이터 세그먼트를 위한 고유의 특성들 (distinguishing characteristics)인 k 및m 의 예시적인 계산을 도시한다.
도 8은 예시적인 고유의 특성들 (distinguishing characteristics (DC)) 및 저장 식별자 지수들 (storage identifiers (SI) indexes)을 도시한다;
도 9는 저장된 서브-세그먼트들을 가진 입력 서브-세그먼트의 예시적인 맵핑 (mapping)을 도시한다;
도 10a 및 도 10b는 합성 백업에서 데이터 세그먼트의 고유의 특성들을 계산하기 위한 하나의 예시적인 방법을 총괄적으로 (collectively) 도시한다; 그리고
도 11은 본 발명의 예시된 실시예들이 구현되는, 프로세서 디바이스를 포함하는, 중복제거 시스템의 하나의 예시적인 부분을 도시한다.

도 1은 하나의 예시적인 합성 백업 아키텍처 (10)을 도시한다. 아키텍처 (10)은 도시한 바와 같이 타임 라인 (time line) (12)를 가로질러 구현된다. 전체 백업 (14)가 가장 앞선 시점에 만들어진다. 이 시간 이후로, 증분 백업 (16), (18) 및 (20)이 도시한 바와 같이 후속 간격들에서 (at subsequent intervals) 수행된다. 전체 백업 (14), 그리고 증분 백업 (16), (18) 및 (20)의 각각은 도시한 바와 같이 하나의 합성 백업 (22)로 통합될 수 있으며, 이하에서 이에 관하여 더욱 상세히 설명한다.

합성 백업 (22)와 같은 합성 백업의 구축은 통상적으로 기존 백업들 (14), (16), (18) 및 (20)으로부터 상기 합성 백업 (22)로 데이터를 카피하는 것으로 구성된다. 카피하는 것은 소스 백업들로부터 데이터 세그먼트들을 읽어들여 이들 데이터 세그먼트들을 상기 타겟 합성 백업으로 기록하는 백업 어플리케이션에 의하여 행하여 질 수도 있고; 또는 소스 및 타겟 데이터 세그먼트들을 식별하는 상기 백업 어플리케이션에 의하여 제공되는 정보를 이용하여 데이터의 카피하는 것을 행하는 저장 시스템에 의하여 좀 더 효율적으로 행해질 수 있다.

다음 도 2는 합성 백업의 예시적인 구축 흐름 (30)에서 이 두 경우들을 도시한다. 첫번째 경우, 그리고 이전에 설명한 바와 같이, 백업 어플리케이션 (32)는 소스 백업으로부터 데이터 세그먼트들을 읽어들여 이들 데이터 세그먼트들을 타겟 합성 백업에 기록하는데, 도시한 바와 같이 저장 디바이스 (40)과 통신하는 저장 서버 (36)과 통신함으로써 한다. 두번째 경우, 그리고 또한 이전에 설명한 바와 같이, 저장 디바이스 (42)와 통신하는, 저장 서버 (38)은 합성 백업을 구축하는 데이터를 카피하는데, 또한 도시한 바와 같이 백업 어플리케이션 (34)로부터 얻은 소스 및 타겟 데이터 세그먼트들을 식별하는 메타데이터 정보를 사용하여 한다.

상기 도시된 실시예들의 메커니즘은 중복제거 저장 시스템내에서 합성 백업의 효율적인 구축을 용이하게 한다. 중복제거 저장 시스템은 일반적으로 이미 존재하는 데이터의 세그먼트들의 관점에서 새로운 입력 데이터의 세그먼트들을 효율적으로 표현하도록 설계된다. 입력 데이터는 스토리지내 매치되는 세그먼트들을 찾도록 처리되고, 이들은 그 다음 상기 새로운 데이터를 저장하는 프로세스에서 레퍼런스된다 (상기 데이터 자체를 저장하는 것보다). 오직 매치되지 않은 데이터 세그먼트들만이 실제 데이터로서 스토리지에 기록된다. 상기 레퍼런스는, (레퍼런스없이) 실제 데이터로서 저장되는, 물리적 데이터 패턴들에 대한 것일 수 있고, 또는 물리적 및 논리적 패턴 양쪽 모두에 대한 것일 수 있는데, 후자는 그 자체로 물리적 및 논리적 패턴에 대한 한 세트의 레퍼런스이다.

합성 백업의 효율적인 구축을 위한 상기 도시된 실시예들의 첫번째 특징 (aspect)은 백업 어플리케이션이, 데이터 카피 동작들을 사용하여 합성 백업들을 구축하기 보다는, 중복제거 저장 시스템에 대해 일련의 컴팩트한 메타데이터 명령을 발행 (issue)할 수 있다는 것이며, 여기서 각각의 명령은 구축될 (타겟) 합성 백업내에 기존 (소스) 백업의 데이터 세그먼트 및 그의 지정된 위치를 명시한다. 상기 도시된 실시예들은 중복제거 저장 시스템내에서 합성 백업을 구축하기 위한 이 명령들의 효율적인 처리를 용이하게 한다.

상기 도시된 실시예들중 하나에서, 중복제거 저장 시스템 내의, 전술한 각각의 명령은 효율적으로 처리되어, 상기 명령에 의하여 레퍼런스되는 데이터 세그먼트와 관련된 상기 메타데이터가 검색되고, 이 정보에 기초하여 기존 백업 데이터 세그먼트에 대한 레퍼런스가 생성되어 구축되는 합성 백업의 메타데이터에 추가된다. 또한, 상기 백업 어플리케이션에 의하여 발행되는 입력 명령들은 처리 효율을 개선하기 위하여 상기 저장 시스템에 의하여 최적화될 수 있다 (optimized). 이 프로세스내에서 스토리지 접근 효율을 개선하기 위한, 하나의 예가 인접 소스 데이터 세그먼트들을 레퍼런스하는 명령들을 취합하는 것이다 (consolidating). 이 방법으로, 합성 백업이 고도의 효율적인 프로세스로 구축되는데, 이 과정에서 통상적/본질적으로 중복제거 저장 시스템에 의하여 지원되는 내부적이고 신속한 메타데이터 동작들인, 레퍼런싱 동작들을 사용한다.

상기 도시된 실시예들의 메커니즘은 또한 새로운 입력 데이터가 합성 백업들의 데이터에서 중복제거되도록 해준다. 이것은 중복제거 프로세스동안 스토리지내 유사한 데이터 세그먼트들의 검색을 위해 사용되는 (serves) 상기 합성 백업 데이터의 다이제스트를 계산하고, 이 다이제스트를, 이하 다이제스트 인덱스 (digests index)라고 일컫는, 중복제거가능 인덱스 (a deduplication facilitating index)에 삽입함으로써 성취할 수 있다. 새로운 입력 데이터가 처리될 때, 상기 입력 데이터의 다이제스트는 상기 다이제스트 인덱스내에서 계산 및 탐색된다. 만약 상기 인덱스내에서 매치되는 다이제스트들이 발견되면 (각각은 스토리지내 유사한 데이터 세그먼트를 가리킴), 그 다음 상기 스토리지내에서 정확히 매치되는 데이터 세그먼트들을 리파인 (refine) 및 식별하기 위하여 추가의 프로세스가 사용된다. 이런 식으로, 합성 백업들의 데이터는 중복제거 프로세스내에서 새로운 입력 데이터와 추후 매치될 수가 있다.

또한, 상기 도시된 실시예들의 메커니즘에서, 합성 백업 데이터의 다이제스트들은, 상기 합성 백업 데이터 자체에 기초하여 새롭게 계산되지 않고, 상기 합성 백업에 의하여 레퍼런스되는 데이터 세그먼트들의 이미 존재하는 저장된 다이제스트들에 기초하여 효율적으로 계산된다. 이것은 상기 합성 백업의 구축동안 합성 백업 데이터에 대한 접근을 감소시키고, 또한 나아가서 상기 데이터 자체에 기초한 다이제스트의 계산을 감소시키도록 해준다. 상기 도시된 실시예들의 메커니즘은 합성 백업의 중복제거 다이제스트들의 계산을 현저히 (significantly) 가속화하는데 (accelerate), 그리하여 합성 백업의 전체적인 구축 시간을 현저히 개선한다. 중복제거를 위한 데이터의 다이제스트들을 계산하고 사용하는 방법은, 도시된 실시예들이 실현될 수 있는 중복제거 저장 시스템의 한 예시적 실시예에서 구현될 수 있으며, 이는 “효율적인 데이터 검색, 저장 및 감소를 위한 시스템 및 방법 ("Systems and Methods for Efficient Data Searching, Storage and Reduction")”이라는 제목의 미국 특허 번호 7,523,098에도 명시되어 있으며, 이 특허의 관련 부분은 여기서 참조로 포함된다.

상기 도시된 실시예들중 한 예는 다음과 같이 요약된다. 합성 백업의 입력 데이터 세그먼트를 위하여, 입력 데이터 세그먼트에 의하여 레퍼런스되는, 저장된 데이터 세그먼트들의 세밀한 (fine-grained) 중복제거 다이제스트들이 인덱스로부터 검색된다. 상기 입력 데이터 세그먼트는 고정 크기의 서브-세그먼트들로 파티션되고, 이들 서브-세그먼트들 각각은 다수의 저장 서브-세그먼트들을 레퍼런스할 수 있다 (정렬 (alignment)에 따라서). 각각의 입력 서브-세그먼트를 위하여, 상기 입력 서브-세그먼트를 위한 중복제거 다이제스트를 산출하는 계산이 수행되는데, 상기 계산은 상기 입력 서브-세그먼트에 의하여 레퍼런스되는 저장된 서브-세그먼트의 검색된 중복제거 다이제스트에 기초한다. 이 계산이 완료될 수 없는 특정 경우들에 있어서, 중복제거 다이제스트는 상기 입력 서브-세그먼트의 데이터에 기초하여 계산된다. 하지만 이들 경우들의 빈도 (frequency)는 이 계산이 완료될 수 있는 경우에 비하여 통상적으로 낮다. 상기 입력 서브-세그먼트들의 계산된 다이제스트들은 그 다음 합해져서 상기 입력 데이터 세그먼트의 중복제거 다이제스트를 산출한다 (produce). 합성 백업의 모든 데이터 세그먼트들의 중복제거 다이제스트들은 전체 합성 백업의 중복제거 다이제스트를 형성한다.

이미 존재하는 데이터의 세그먼트들의 관점에서 새로운 입력 데이터의 세그먼트들을 표시하는 능력은 중복제거 저장 시스템들에서 특별한 (inherent) 것이다. 상기 입력 데이터는 처리되어 스토리지내 매치되는 세그먼트들을 찾고, 이 세그멘트들이 그 다음에 (데이터 그 자체를 저장하지 않고) 새로운 데이터를 저장하는 프로세스에서 레퍼런스된다. 오직 매치되지 않은 데이터 세그먼트들만이 실제 데이터로서 스토리지에 기록된다.

레퍼런싱 기능을 구현하는 몇가지 방법이 있다. 일반적으로, 레퍼런싱은 물리적 데이터 패턴들 또는 논리적 데이터 패턴들에 기초하여 구현될 수 있다. 첫번째 대안에서, 새로운 데이터 패턴은 (레퍼런스들이 없이) 실제 데이터로서 저장되어 있는 데이터 패턴들을 레퍼런스하고, 어떤 종류의 저장 식별자를 사용하여 레퍼런스될 수 있다. 그러한 데이터 패턴들은 물리적 데이터 패턴으로 일컬어진다. 두번째 대안에서, 새로운 데이터 패턴은 물리적 데이터 패턴들 및 논리적 데이터 패턴들 양쪽 모두를 레퍼런스할 수 있으며, 이 때 논리적 데이터 패턴들은 그 자체로 물리적 및 논리적 패턴들 대한 그러한 레퍼런스의 한 세트이다.

상기 두가지 레퍼런싱 방식 (52), (54)가 다음의 도 3에서 레퍼런싱 패턴 (50)으로서 총괄적으로 도시된다. 물리적 데이터 패턴들을 레퍼런스하기 위하여 도시된 예 (A)에서, 새로운 데이터 패턴 (56), (58)은 도시한 바와 같이 물리적 데이터 패턴들 (60)-(74) (즉, 실제 데이터)로서 저장된 데이터 패턴들을 레퍼런스한다. 논리적 데이터 패턴들을 레퍼런스하기 위하여 도시된 예 (B)에서, 새로운 데이터 패턴 (76)은 도시된 바와 같이 논리적 데이터 패턴들 (78), (80)뿐만 아니라 물리적 데이터 패턴들 (82)-(96) 양쪽 모두를 레퍼런스한다.

상기 도시된 실시예들중 하나에서, 중복제거된 데이터는 스토리지 블록들내에 물리적 데이터 패턴들로서 저장되는데, 이 때 각각의 스토리지 블록은 연관된 레퍼런스 카운트 특성 (reference count property)을 갖는다. 새로운 데이터 세그먼트를 저장하기 위해서는, 상기 새로운 세그먼트는 기존 데이터 세그먼트들과 매치되고 (매치되는 데이터를 찾기 위해 독립적인 방법을 사용하며, 이 방법은 다양한 방식을 사용하여 구현될 수 있다), 매치되는 데이터 세그먼트들의 메타데이터는 검색되며, 그 다음 상기 매치되는 데이터 세그먼트에 의하여 레퍼런스되는 스토리지 블록들을 가리키는 새로운 데이터 패턴 (물리적 데이터 패턴들을 포함하는)을 위해 레퍼런스들이 생성된다. 이들 레퍼런스들은 새로운 데이터 패턴을 위해 생성된 메타데이터 파일내의 레코드들로 캡슐화된다 (encapsulated). 스토리지 블록들은 전체적으로 또는 부분적으로 레퍼런스될 수 있으며, 이 정보는 상기 메타데이터 레코드들에 표시된다. 어떠한 기존 데이터 세그먼트와도 매치되지 않는 새로운 데이터 세그먼트를 저장하기 위하여, 그것의 데이터는 스토리지 블록들에 저장되고, 레퍼런스들이 이들 블록들에 생성되어 그것의 메타데이터 파일에 추가된다. 하나의 스토리지 블록이 레퍼런스되면, 그것의 레퍼런스 카운트 특성값은 그 블록에 만들어지는 새로운 레퍼런스들의 수에 따라 중분된다 (incremented). 스토리지 블록이 즉, 그 블록을 레퍼런스하는 데이터 세그먼트를 삭제함으로써 디-레퍼런스되면 (de-referenced), 그것의 레퍼런스 카운트 특성값은 제거되는 레퍼런스들의 수에 따라 감분된다 (decremented). 스토리지 블록의 레퍼런스 카운트 특성값이 0보다 더 큰 경우, 상기 블록은 스토리지내에 유지되어야 한다. 상기 값이 0이 되면, 상기 블록은 스토리지로부터 제거될 수 있다.

이제 도 4를 살펴보면, 중복제거 저장 시스템에서 사용을 위한 합성 백업을 구축하기 위한 하나의 예시적인 방법 (100)을 도시한다. 한 실시예에서, 방법 (100)은 컴퓨팅 환경들내에서 중복제거 시스템 컴포넌트들, 또는 다양한 기타 처리, 네트워킹 및 스토리지 컴포넌트들을 사용하여 구현될 수 있다. 당업자가 이해하듯이, 방법 (100)에서 여러 단계들은 특정 어플리케이션에 적합하도록 하기 위해 여러 다른 방법들로 구현될 수 있다. 또한, 상기 방법은 하드웨어, 소프트웨어, 펌웨어, 또는 컴퓨팅 환경에서 동작하는 또는 컴퓨팅 환경과 달리 연관된 그들의 조합과 같은 다양한 수단들에 의해서 구현될 수도 있다. 예를 들면, 다음에 도시된 예시적인 방법들뿐만 아니라, 상기 방법 (100)은 그 안에 컴퓨터-판독가능 프로그램 코드 부분을 가진 컴퓨터-판독가능 저장 매체를 포함하는 컴퓨터 프로그램 제품으로서 부분적 또는 전체적으로 실시될 수 있다. 상기 컴퓨터-판독가능 저장 매체는 디스크 드라이브 (disk drives), 플래시 메모리 (flash memory), 디지털 다기능 디스크 (digital versatile disks (DVDs)), 컴팩트 디스크 (compact disks (CDs)) 및 이전에 설명되었듯이 기타 형태의 저장 매체를 포함한다.

방법 (100)은 단계 (102)에서 시작하여 단계 (104)에서 구축될 합성 백업을 위하여 스토리지내에서 메타데이터 파일을 생성한다. 합성 백업과 관련된 연속적인 (Successive) 명령들은 처리 효율을 개선하기 위하여, 가능할 경우 (as applicable) 최적화되어 (optimized) 취합된다 (consolidated). 구체적으로, 인접 소스 데이터 세그먼트들을 레퍼런스하는 명령들이 메타데이터에 대한 접근 효율을 개선하기 위하여 취합된다. 일련의 최적화된 명령들이 생성된다 (단계 106). 첫번째로 최적화된 명령이 검토된다 (단계 108). 각각의 최적화된 명령을 위하여, 상기 명령에 의해서 표시된 소스 데이터 세그먼트와 연관된 메타데이터 세그먼트가 스토리지로부터 검색된다. 상기 메타데이터 정보는 일반적으로 스토리지 블록들 (상기 소스 데이터 세그먼트를 구성하는 데이터 패턴들을 포함하는)에 대한 레퍼런스들을 포함한다 (단계 110).

이 메타데이터 세그먼트는 오직 상기 소스 데이터 세그먼트만을 반영하도록 요구될 때 조정된다 (be adjusted) (단계 112). 구체적으로, 예를 들면, 소스 데이터 세그먼트의 엣지들 (edges)에서 스토리지 블록에 대한 레퍼런스들은 상기 레퍼런스된 블록들의 더 짧은 부분들 (shorter portions)을 표시하기 위해 조정될 수 있다. 상기 조정된 메타데이터 세그먼트는 합성 백업의 메타데이터 파일에 카피 (첨부)된다 (단계 114). 이 메타데이터 세그먼트에 의하여 레퍼런스되는 상기 스토리지 블록의 레퍼런스 카운트 특성값들은 증분되는데, 각각의 블록에 대하여, 상기 메타데이터 세그먼트내에서 전술한 블록에 대한 레퍼런스 수에 따라 증분된다 (단계 116). 만약 추가적으로 최적화된 명령이 존재한다면 (단계 118), 상기 방법 (100)은 추가적인 처리를 위하여 단계 (110)으로 되돌아온다. 그렇지 않으면, 상기 방법 (100)은 종료된다 (단계 120). 전술한 (foregoing) 예시적인 방법을 사용함으로써, 합성 백업이, 매우 효율적인 프로세스로 구축되는데, 이것은 통상적으로 중복제거 저장 시스템들에 의하여 특별하게 (inherently) 지원되는 내부적이며 신속한 메타데이터 동작들인 레퍼런싱 동작들을 사용하여, 구축된다.

상기 도시된 실시예들 중 한 예로서, 일단 생성된 합성 백업은 그것의 오리지네이팅 (originating) 백업과 독립적이고, 백업 어플리케이션에 의하여 그대로 (as such) 검토될 수 있다. 말하자면, 상기 합성 백업을 구축하기 위하여 데이터가 레퍼런스되는, 일부 또는 전부의 백업들이 삭제된다면, 상기 합성 백업은 그대로 남는다 (remains intact). 이것은 상기 도시된 실시예들 중 한 예로서, 정규 (regular) 백업들이 저장되는 것과 같은 방식으로 합성 백업이 중복제거 저장 시스템에서 저장되는 것에 기인한다. 구체적으로, 유사한 메타데이터 스트럭처가 합성 및 정규 백업들을 위해 생성되고, 스토리지 블록들은 합성 및 정규 백업들과 동일한 방식으로 레퍼런스된다. 상기 특성에서 고유한 장점은 새로운 합성 백업들의 구축시 상기 합성 백업이 백업 어플리케이션에 의하여 레퍼런스될 수 있다는 것이다.

또한, 새로운 입력 데이터를 합성 백업내 포함된 데이터에서 중복제거되도록 할 수 있는 것이 장점이며 (beneficial), 특히 상기 합성 백업이 구축되었던 백업들의 일부 혹은 전부가 스토리지로부터 이미 삭제된 경우는 더욱 그러하다 (상기 합성 백업이 이용용이하게 남아있는 한, 그것의 레퍼런스된 스토리지 블록도 이용용이하게 남아있슴을 주목할 것). 그러한 중복제거를 용이하게 하기 위해서, 합성 백업들내에 포함된 데이터는 새로운 백업들의 데이터와 매치를 위하여 이용가능하게 되어야 한다. 이 이용가능성의 구현은 데이터 중복제거 프로세스내에서 새로운 데이터와 기존 데이터의 매칭 프로세스를 실현하기 위해 사용되는 특정 방법에 따라 달라진다.

도시된 실시예들의 특징들을 포함하는 한 예시적인 중복제거 저장 시스템에서, 새로운 입력 데이터에서 중복제거를 위하여 저장된 데이터를 이용가능하게 하는 것은, 중복제거 프로세스 동안 스토리지내 유사한 데이터 세그먼트의 검색을 위해 사용되는, 그 데이터의 다이제스트를 계산하고, 이 다이제스트를 이하 다이제스트 인덱스 (the digests index )라고 일컫는, 중복제거가능 인덱스 (a deduplication facilitating index)에 삽입함으로써 구현된다. 그 다음, 새로운 입력 데이터가 처리될 때, 상기 입력 데이터의 다이제스트는 상기 다이제스트 인덱스내에서 계산되고 탐색된다. 이 인덱스는 새로운 데이터의 다이제스트를 고려하여 (given) 저장된 데이터의 매치되는 다이제스트의 탐색을 가능하게 해준다. 만약 상기 인덱스내에서 매치되는 다이제스트들이 발견되면 (각각은 스토리지내 유사한 데이터 세그먼트를 가리킴), 그 다음 상기 스토리지내에서 정확히 매치되는 데이터 세그먼트를 리파인하여 (refine) 식별하기 위하여 추가적인 프로세스가 사용된다. 그 후에, 상기 입력 데이터의 다이제스트들은, 상기 다이제스트 인덱스로 삽입되는데 (그래서 새로운 데이터를 현재의 입력 데이터와 매치되도록 해준다), 이는 상기 입력 데이터와 매치되는 저장된 데이터의 다이제스트들의 일부 혹은 전부를 인덱스로부터 치환 (displacing)할 수 있다.

다음, 도 5는 앞서 논의된 사항을 염두에 두면서 하나의 예시적인 중복제거 프로세스 (130)을 도시한다. 방법 (130)은 새로운 입력 데이터를 위한 개별적인 다이제스트들을 계산함으로써 (단계 134) 시작된다 (단계 132). 상기 다이제스트 인덱스들 (149)는 저장된 데이터의 매치하는 다이제스트들을 위하여 탐색된다 (단계 136). 만약 매치가 발견되면 (단계 138), 그 다음 상기 매치하는 데이터 세그먼트들이 스토리지내 저장된 데이터 (150)으로부터 검색된다 (단계 142). 검색된 데이터 및 상기 다이제스트들의 정보를 사용하여, 스토리지내 정확한 매치 데이터 세그먼트들이 리파인되고 식별된다 (단계 144). 상기 정확한 매치들의 정보를 사용하여, 새로운 입력 데이터는, 미스매치들의 데이터에 더하여 (단계 146), 이미 저장된 데이터 (매치에 기초하여)에 대한 레퍼런스들의 세트로서 저장된다. 상기 새로운 입력 데이터의 다이제스트들은 상기 다이제스트 인덱스에 저장되는데, 이는 만약 상기 매치 데이터 세그먼트가 존재한다면, 아마도 그것들을 치환할 것이다 (단계 148). 단계 138로 되돌아와서, 만약 매치가 발견되지 않으면, 상기 새로운 입력 데이터는 이미 저장된 데이터에 대한 레퍼런스없이 저장된다 (단계 140). 상기 방법 (130)은 그 다음 종료된다 (단계 152).

합성 백업의 데이터 다이제스트를 계산하여 그것을 상기 다이제스트 인덱스에 삽입함으로써, 합성 백업의 데이터는 중복제거 프로세스내에서 추후 새로운 입력 데이터와 매치될 수 있다. 합성 백업의 데이터 다이제스트를 계산하는 가능한 하나의 방법은 상기 합성 백업의 구축 동안 이 데이터를 스토리지로부터 검색하여 이 데이터에 기초하여 다이제스트들을 계산하는 것이다. 하지만, 상기 도시된 실시예들 중 한 예에서, 합성 백업은 데이터 자체에 대한 어떠한 접근없이 오직 메타데이터 동작들만을 사용하여 구축되고 (말하자면, 백업 어플리케이션은 저장 시스템에 메타데이터 명령을 제공하고, 그 다음 그 명령들은 합성 백업을 구축하기 위하여 오직 메타데이터 동작들만을 수행한다), 또한 데이터에 대한 접근 및 데이터에 관한 동작들은 메타데이터에 접근 및 메타데이터에 관한 동작들보다 현저히 느리기 때문에 (데이터의 크기는 통상적으로 연관된 메타데이터에 대한 그것보다 훨씬 크므로), 그러므로 합성 백업의 구축 프로세스내에서 데이터의 접근 및 검색은 이 프로세스를 현저히 지체시킬 수 (slow) 있으며 잠재적으로 그것의 효율을 감소시킨다.

이 문제를 해결 (address)하기 위하여, 상기 도시된 실시예들 중 한 예는 상기 합성 백업 데이터의 다이제스트들을 효율적으로 계산하는 방법을 제공하는데, 이것은 데이터 자체에 대한 접근을 최소화한다. 이와 관련하여, 상기 합성 백업 데이터의 다이제스트들은 (상기 데이터 자체에 기초하여 새롭게 계산되는 것이 아니라) 상기 합성 백업에 의하여 레퍼런스되는 데이터 세그멘트들의 이미 존재하는 저장된 다이제스트들에 기초하여 효율적으로 계산된다. 이 방법은 더욱 세밀한 다이제스트들의 합 (aggregates of finer grain digests)으로서 계산되는 다이제스트들에 대해 일반적으로 적용될 수 있다.

다음에서, 데이터의 중복제거 다이제스트들의 예시적인 계산이 제공된다. 첫번째 단계로서, 입력 데이터는 세그먼트들로 파티션되는데, 각각의 세그먼트는 중복제거를 위해 처리된다. 한 실시예에서, 그러한 데이터 세그먼트 각각의 크기는 16MB이다. 그러한 세그먼트 각각을 위하여, 탐색 (search) 및 표시 (representation)를 위한 상기 세그먼트의 중복제거 다이제스트들을 각각 구성하는, k 및m 고유의 특성들 (k and m distinguishing characteristics)이 도 7에 도시된 다음의 예시적인 방법 (170)을 사용하여 계산된다. k 값은 통상적으로 낮으며 (low) (가령, 몇 십), m 값은 10보다 더 낮을 수 있다 (lower).

방법 (170)은 단계 (172)에서 시작하여, 단계 (174)에서 입력 데이터 세그먼트내 모든 블록을 위해 해쉬값 (hash value)을 계산하는데, 여기에서 이들 블록들의 크기는 실질적으로 상기 입력 데이터 세그먼트 (가령, 4KB)의 크기보다 작으며, 상기 블록들은 오버랩하는데, 다시 말하면, 상기 입력 데이터 세그먼트내 위치 l에서 하나의 블록이 시작한다고 할 때 (상기 위치는 바이트로 명시된다), 다음 블록의 위치는 위치 l+1 내에서 시작한다. 한 실시예에서, 이들 해쉬값들은 롤링 해쉬 펑션 (rolling hash function)을 사용하여 계산된다. 그러한 해쉬 펑션으로, 상기 해쉬값들이 데이터의 연속적인 블록들에 기초하여 효율적으로 계산되어, 각각의 블록이 이전 블록의 시작 바이트 다음 1 바이트마다 시작하도록 한다. 롤링 해쉬 펑션이 갖는 장점은 일단 데이터 블록에 대한 상기 해쉬값이 알려지면, 다음 블록에 대한 해쉬값의 계산은 (이전 블록의 시작 바이트 다음 1 바이트마다 시작함) 0(1) 동작에서 달성될 수 있다는 것이다.

이전 단계에서 데이터 세그먼트를 위해 발생된 해쉬값들중, k 최대 (maximal) 해쉬값들이 선택되어 그들 값들의 내림차순으로 (in descending order) 정렬되는데, 이 순서를 중요성 순서 (order of significance)라고 일컫는다. k 최대 블록들이라고 일컫는, k 최대 해쉬값들에 대응하는 블록들은 (계산에 있어서 다음 단계의 목적을 위해) 상기 최대 해쉬값들과 동일 순서로 논리적으로 정렬된다 (단계 176). 최대 블록들 (k 최대 해쉬값들과 연관됨)보다 1 바이트 뒤에 오는 블록들이 선택되어, 최대 블록과 동일 순서로 논리적으로 정렬된다. 이들 블록들은 쉬프트된 블록 (shifted blocks )이라고 일컫는다. 도 6은, 이전에, 최대 블록 (162), 그들의 개별 위치 (166), 그들의 개별 쉬프트된 블록 (164), 그리고 그들의 개별 쉬프트된 위치 (168)을 설명하는 시나리오 (160)을 도시한다.

다시 도 7로 돌아와서, 다음 단계로서, 상기 쉬프트된 블록들의 k 해쉬값들은 유사성 탐색 (similarity search)의 목적을 위해 상기 입력 데이터 세그먼트의 고유의 특성들이 되도록 선택된다 (단계 180). 이들 고유의 특성들은 그 다음에 스토리지내 유사한 데이터 세그먼트들을 위한 다이제스트 인덱스를 탐색하는데 사용된다. 새로운 입력 데이터 세그먼트의 유사성 탐색 동안, k 고유의 특성들은 아마도 상기 다이제스트 인덱스내에서 탐색될 수 있다. 최종적으로, 그들의 중요성 순서에 있어서, k가 m 보다 클 때, m 첫번째 쉬프트된 블록들의 해쉬값들은, 상기 다이제스트 인덱스내 표시의 목적을 위해 상기 입력 데이터 세그먼트의 고유의 특성들이 되도록 선택된다 (단계 182). 이 고유의 특성들은 그 다음에 상기 입력 데이터 세그먼트를 표시하기 위하여 다이제스트 인덱스내 저장되며, 그 다음의 새로운 입력 데이터 세그먼트들이 유사성 탐색동안 그 입력 데이터 세그먼트를 찾도록 해준다. 방법 (170)은 그 다음 종료된다 (단계 184).

상기 최대값들은 유니폼 (uniform)이 아닌 수치 분포 (numeric distribution)를 갖는다는 점에 유의한다. 하지만, 양호한 해쉬 펑션을 사용하면, 이 단계에서 선택된 상기 고유의 특성들의 수치 분포는 유니폼에 매우 근접하게 되는데, 따라서 이 방식으로 선택된 고유의 특성들이 데이터의 세그먼트들을 특별하게 식별하는데 더욱 효과적이 된다. 해쉬값들의 모든 반복가능한 선택 기준이 도 7의 단계 (176)에 적용가능하다는 점에 또한 유의한다. 예를 들면, k 최소 해쉬값들, 또는 데이터 세그먼트를 위하여 계산된 모든 해쉬값들의 중앙값 (median)에 가장 근접한 k 해쉬값들, 또는 일부 미리 결정된 상수 (predetermined constant)에 가장 근접한 k 해쉬값들을 선택할 수 있다. 또한, 최대 해쉬값에 대응하는 블록의 1바이트 쉬프트를 사용하지 않고, 기타 미리 결정된 반복가능한 쉬프트가 사용될 수 있거나, 또는 위치에 따라 다른 시프트들 및/또는 계산된 해쉬값에 따라 다른 쉬프트들이 사용될 수 있다. 최대 해쉬값들 및 1 바이트의 쉬프트들을 사용하는 것은 하나의 예시적인 실시예이다.

상기 예시적인 방법 (170)은, 주어진 데이터 세그먼트를 위해, 최대한 (to a high extent), 특별하고 (unique), 확실하며 (robust), 잘 분포된 (well spread) 그리고 반복가능한 (repeatable) 고유의 특성들을 산출한다. 특별하다 함 (unique)은 두 개의 다른 데이터 세그먼트들이, 충분히 높은 확률로, 두 개의 다른 특성들의 세트에 할당됨을 의미한다. 확실하다 함 (robust)은 데이터 세그먼트가 제한된 변화들 (가령, 컨텐츠의 25%까지)을 겪는다 (undergoes)하더라도 데이터 세그먼트에 할당된 특성들은 매우 안정적 (fairly constant)으로 남아있을 것임을 의미한다. 잘 분포된다 (well spread) 함은 특성의 위치들이 일반적으로 데이터 세그먼트에 대해 유니폼하게 분포됨을 의미한다. 반복가능하다 (repeatable)함은 데이터 세그먼트의 특정 형태는 항상 동일 고유의 특성들의 값들을 산출할 것이라는 것을 의미한다.

유사성 탐색을 위하여 k 고유의 특성들을 사용하고 다이제스트 인덱스내 표시를 위하여 m 고유의 특성들을 사용하는 이유는 최대 해쉬값들상에서 두 개의 가능한 효과들이 존재하기 때문이며, 이들은 새로운 데이터 세그먼트를 그와 유사한 저장된 데이터 세그먼트들과 관련하여 수정 (modifications)함으로써 발생될 수 있다. 첫번째 효과는 최대 해쉬값이 사라질 수 있다는 것인데 왜냐하면 그의 대응하는 블록을 구성하는 데이터가 수정되었기 때문이다. 두번째 효과는 수정된 데이터가 더 높은 최대 해쉬값을 도입할 수 있다는 것이며, 이는 따라서 이전의 최대 해쉬값을 치환할 수 있다. 상기 두번째 효과를 해결하기 위하여, k 고유의 특성들을 사용하여 유사성 탐색이 진행되며, 한편 데이터 세그먼트는 m 고유의 특성들을 사용하여 표시된다.

한 실시예에서, 입력 데이터 세그먼트는 각각 복수의 고정 크기 서브-세그먼트들로 파티션된다. 상기 세그먼트들의 고정 크기의 가능한 값은 몇 십 또는 몇 백 킬로바이트들, 예를 들면 512KB가 될 수 있다. k값은 상기 서브-세그먼트들의 고정 크기보다 작다. 다이제스트 인덱스내 스토리지를 위해, 유사성 탐색을 위한 상기 k 고유의 특성들이 전체 데이터 세그먼트에 대해 계산되는 동안, m 고유의 특성들은, 전체 데이터 세그먼트 뿐만아니라, 서브-세그먼트들 각각에 대해서 계산된다.

또한, 한 실시예에서, 상기 다이제스트 인덱스는 두 개의 펑션 (아마도 두 개의 내부적인 인덱스 스트럭처들에)을 제공한다. 첫번째 펑션에서, 고유의 특성 인덱스 또는 DC 인덱스라고 일컫는, 상기 인덱스는 전체 데이터 세그먼트들의 m 고유의 특성들을 저장하고, 탐색할 고유의 특성값들을 고려하여, 저장된 데이터 세그먼트들의 매치되는 고유의 특성들을 찾을 수 있도록 해준다. 매치되는 고유의 특성 각각의 인덱스 기록은 그의 개별적인 데이터 세그먼트의 저장 위치 및 그의 개별적인 데이터 세그먼트내에서 상기 고유의 특성의 특정한 위치에 대한 포인터를 또한 포함한다. 두번째 펑션에서, 저장 식별자 인덱스 또는 SI 인덱스라고 일컫는, 상기 인덱스는 데이터 서브-세그먼트들의 m 고유의 특성들을 저장하고, 서브-세그먼트들의 저장 식별자들 (저장 식별자는 스토리지내에서 그들의 개별 데이터 서브-세그먼트들의 위치를 필수적으로 식별한다)이 주어지면, 상기 명시된 서브-세그먼트들의 고유의 특성들을 찾을 수 있도록 한다. 검색된 고유의 특성의 인덱스 기록 각각은 자신의 값, 전술한 고유의 특성과 연관된 최대 해쉬값 및 전술한 고유의 특성의 저장 위치를 포함한다.

도 8은 예시적인 고유의 특성들 (DC) 및 저장 식별자 (SI) 인덱스들, 그리고 상기 인덱스들을 사용하는 예시적인 방법 (190)을 도시한다. 블록 192에서, 입력 데이터 세그먼트의 k 고유의 특성들에 대한 탐색이 이루어진다. 이것들은, 블록 194에서, 상기 DC 인덱스로 제공되는데, 이는 각각의 데이터 세그먼트에 대한 m 고유의 특성들을 저장한다. 상기 탐색 결과는 블록 196에 도시되며, 유사한 저장된 데이터 세그먼트들의 매치되는 고유의 특성들을 포함한다. 블록 198에서, 저장된 서브-세그먼트들의 저장 식별자들/위치들을 사용하여 탐색이 이루어진다. 이것들은, 블록 200에서, 상기 SI 인덱스로 제공되는데, 이는 각각의 데이터 서브-세그먼트에 대한 m 고유의 특성들을 저장한다. 상기 탐색 결과는 블록 (202)에 도시되며, 명시된 저장 데이터 서브-세그먼트들의 고유의 특성들을 포함한다.

상기 DC 인덱스는 스토리지내 유사 데이터 세그먼트를 찾기 위하여, 입력 데이터 세그먼트의 유사성 탐색 프로세스에서 사용된다. 상기 SI 인덱스는 다음의 몇가지 목적들을 위하여 사용되는데, (1) 합성 백업 고유의 특성들의 최적화된 계산, 다음에 상세히 설명한다, ; (2) 한 세트의 데이터 세그먼트들이 스토리지로부터 삭제되면, 이들 데이터 세그먼트들의 고유의 특성들은 상기 SI 인덱스로부터 검색되고 그 다음 DC (SI 인덱스로부터의 정보를 사용하여) 및 SI 인덱스 양쪽 모두로부터 삭제된다; 그리고 (3) 데이터 세그먼트의 고유의 특성들이 DC 인덱스로부터 제거되어야 한다면 (가령, 더 새로운 데이터 세그먼트의 고유의 특성들로 대체를 위해), 그것의 고유의 특성들이 상기 SI 인덱스로부터 검색되고 그 다음 DC 인덱스로부터 제거된다.

이제 도 10a 및 10b를 살펴보면, 기존 고유의 특성에 기초하여, 합성 백업내 데이터 세그먼트의 고유의 특성들을 계산하는 예시적인 방법 (200)이 총괄적으로 도시된다. 방법 (200)은 단계 (202)에서 시작하여, 단계 (204)에서 입력 데이터 세그먼트에 의하여 레퍼런스되는 저장된 데이터 서브-세그먼트들을 결정한다. 이것은 백업 어플리케이션에 의하여 제공되는 메타데이터 명령들에 기초하여 이루어지는데, 이에 의하여 상기 합성 백업내 데이터 세그먼트가 구축된다. 이들 메타데이터 명령들은 주어진 세그먼트를 구축하는데 사용될 저장된 데이터를 명시한다. 이 정보로부터 상기 저장 시스템은 입력 데이터 세그먼트에 의하여 레퍼런스되는 저장된 서브-세그먼트들 (및 그들의 저장 식별자들)을 추론한다 (deduces).

상기 레퍼런스된 서브-세그먼트들의 고유의 특성들 (각각의 서브-세그먼트에 대한 m 고유의 특성들)이 상기 SI 인덱스로부터 검색된다 (단계 206). 상기 합성 백업으로부터의 입력 데이터 세그먼트는 고정 크기의 서브-세그먼트들로 파티션되는데, 그것의 크기는 저장된 서브-세그먼트들의 크기와 동일하다 (단계 208). 첫번째 입력 서브-세그먼트가 검토된다 (단계 210). 상기 입력 서브-세그먼트 각각의 서브-세그먼트를 위하여, 다음이 수행된다. 상기 입력 서브-세그먼트는 적어도 하나 그리고 f 저장된 서브-세그먼트들까지 레퍼런스한다. 만약 서브-세그먼트의 크기가 합성 백업에 의하여 레퍼런스되는 스토리지내 데이터 세그먼트의 최소 크기보다 작다고 가정하면, 저장된 서브-세그먼트들과 상기 입력 서브-세그먼트의 정렬에 따라, 상기 입력 서브-세그먼트는 하나와 네개의 저장된 서브-세그먼트들 사이에서 레퍼런스할 수 있다. 이것은 이전의 도 9에서 도시된다. 이 도면에서, 상기 입력 서브-세그먼트들은 그들이 레퍼런스하는 저장된 서브-세그먼트의 위에 도시되며, 굵은 (solid) 수직선 (vertical line)은 서브-세그먼트의 정렬 경계 (alignment boundaries)를 나타낸다. 이 도면의 파트 (A) 및 (B)는 하나의 연속적인 저장된 세그먼트를 레퍼런스하는 입력 서브-세그먼트를 도시하며, 파트 (C)-(E)는 두개의 분리된 저장된 세그먼트들을 레퍼런스하는 입력 서브-세그먼트를 도시한다. 만약 서브-세그먼트의 크기가 합성 백업에 의하여 레퍼런스되는 스토리지내 데이터 세그먼트의 최소 크기보다 클 수 있다고 가정하면, 입력 서브-세그먼트는 f 저장된 서브-세그먼트들까지 레퍼런스할 수 있고, 여기서 f 는 합성 백업에 의하여 레퍼런스되는 저장된 데이터 세그먼트의 최소 크기로 나눈 다음 2를 곱한 (왜냐하면 각각의 레퍼런스는 두개의 저장된 서브-세그먼트들과 연관되어 있기 때문임) 입력 서브-세그먼트의 크기와 동일하다.

도 10a로 돌아와서, 입력 서브-세그먼트에 의하여 레퍼런스되는 스토리지 서브-세그먼트의 수는 r로 표시된다 (denoted). 상기 레퍼런스된 서브-세그먼트들의 각각은 상기 SI 인덱스로부터 검색된 m 고유의 특성들과 연관되어 있으며(도 9에서 도시한 바와 같이), 그리고 이들 r x m 고유의 특성들은 다음과 같이 검토된다. 상기 고유의 특성들의 각각과 연관된 최대 해쉬값들이 검토된다. 상기 SI 인덱스로부터 검색된 고유의 특성 각각의 기록에서 그것의 연관된 최대 해쉬값이 또한 포함되어 있슴에 유의한다. 스토리지내 r 레퍼런스된 서브-세그먼트의 서브-세그먼트 j의 고유의 특성들과 연관된 최대 해쉬값들의 세트는

로서 표시된다. 스레시홀드 해쉬값은

로서 계산된다 (단계 212).

만약 상기 입력 서브-세그먼트가 단일 저장된 세그먼트이상을 레퍼런스하고 (도 9 (c)-(e) 부분에서 예를 든 것과 같이), 서브-세그먼트의 고유의 특성들이 또한 그의 마지막 블록의 바이트에 기초하여 계산된다면, 두 개의 레퍼런스된 저장된 세그먼트들 사이에서 스플릿 (split)이, 도 9에서 블록 b1 및 b2로 표시된, 스플리트 위치의 모든 사이드들상에, 일어나는, 상기 입력 서브-세그먼트내 위치에 인접한 블록들이 로드되고, 해쉬값들이, 이전에 명시된 방법을 사용하여, 블록 b1 의 각 바이트 오프셋에 대해 계산된다 (단계 214). 후보 해쉬값들의 서브-세트는 상기 레퍼런스된 서브-세그먼트들의 r x m 고유의 특성들과 연관된 최대 해쉬값들과, 다음의 방법을 사용하여, 이전 단계에서 계산된 해쉬값들을 포함하는 해쉬값들의 세트로부터 계산된다. 만약 해쉬값이 h^T와 같거나 크고 그의 저장 위치가 상기 입력 서브-세그먼트의 경계내에 있다면, 하나의 해쉬값이 해쉬값들의 상기 서브-세트내에 포함된다 (단계 216).

만약 상기 후보 해쉬값들의 세트에서 해쉬값들의 수는 m과 같거나 크면 (단계 218) 다음이 수행된다. 이 세트의 상기 해쉬값들은 그들 값들의 내림차순으로 정렬된다 (단계 222). 첫번째 (즉, 가장 큰) m 해쉬값들을 사용하여 m 고유의 특성들을 계산하고, 각각의 해쉬값 v를 위해 그의 고유의 특성이 상기 해쉬값 v와 연관된 블록에 대하여 1 바이트 쉬프트된 블록의 해쉬값이 되게 선택되도록 한다 (단계 224). 만약 검토될 상기 해쉬값 v가 레퍼런스된 서브-세그먼트들의 r x m 고유의 특성들의 세트로부터 하나의 고유의 특성과 연관되어 있다면, 그의 고유의 특성값은 상기 SI 인덱스로부터 검색된 개별 기록으로부터 즉각 이용가능하다. 만약 검토될 상기 해쉬값 v가 단계 (214)에서 계산된 해쉬값들 중에 있다면, 그의 고유의 특성값은 단계 (214)에서 계산된 해쉬값들의 세트로부터 즉각 이용가능하다. 이전 단계에서 계산된 상기 m 고유의 특성들은 입력 서브-세그먼트의 m 고유의 특성들로서 지정된다 (단계 226). 상기 지정된 고유의 특성들은 나중에 SI 인덱스내에 저장되며 (그들의 개별 입력 서브-세그먼트와 연관되어), 그리고 또한 나중에 DC 인덱스내에 저장될 전체 입력 데이터 세그먼트의 m 고유의 특성들을 계산하기 위한 기초로서 사용된다 (이에 관해서는 다음에 상세히 설명됨). 단계 (228)은 상기 입력 세그먼트에서 추가적인 서브-세그먼트가 존재하는지 질의하며 (queries), 만일 존재한다면, 상기 방법 (200)은 추가 처리를 위하여 단계 (212)로 되돌아온다.

단계 (218)로 되돌아와서, 상기 후보 해쉬값의 세트에서 해쉬값들의 수가 m보다 낮으면 다음이 수행된다. 상기 입력 서브-세그먼트의 개별 데이터가 스토리지로부터 검색되고 그것의 고유의 특성들이 상기 데이터에 기초하여 계산된다 (단계 220). 이 경우 상기 서브-세그먼트의 m 고유의 특성들은 기존의 고유의 특성들에 기초하여 계산될 수 없다. 하지만, 그들의 저장 위치들의 관점에서 고유의 특성들의 기대된 유니폼 분포에 기초한, 이 경우의 빈도는 상기 입력 서브-세그먼트의 m 고유의 특성들이 기존의 고유의 특성들에 기초하여 계산될 수 있는 경우에 비해 상대적으로 낮아야 한다. 다시, 방법 (200)은, 단계 (228)로 되돌아가서, 가능한 경우, 추가 처리를 위하여 단계 (212)로 되돌아온다.

만약 단계 (228)에서, 추가의 서브-세그먼트들이 존재하지 않으면, 입력 데이터 세그먼트의 m 고유의 특성들은 다음의 방법을 사용하여 계산된다. 상기 입력 세그먼트에 s 서브-세그먼트들이 있다고 가정하면, 상기 입력 세그먼트의 모든 서브-세그먼트들을 위해 계산된 s x m 고유의 특성들의 세트가 검토된다. 이 세트의 고유의 특성들은 그들의 개별 최대 해쉬값들의 내림차순으로 정렬된다 (단계 230). 이런 순서에서 이 세트의 첫번째 m 고유의 특성들 (말하자면, 가장 큰 개별 최대 해쉬값들을 가진 m 고유의 특성들)은, 상기 입력 데이터 세그먼트의 m 고유의 특성들이 되도록 선택된다 (단계 232). 이들 고유의 특성들은 나중에 DC 인덱스내에 저장된다 (그들의 개별 입력 데이터 세그먼트와 연관되어). 상기 방법 (200)은 그 다음 종료된다 (단계 234).

합성 백업에 의하여 레퍼런스되는 데이터 세그먼트들의 기존의 저장된 다이제스트들에 기초한, 합성 백업 데이터 다이제스트의 효율적인 계산을 위해 위에서 명시된 상기 방법 (200)은 계산 프로세스 동안 데이터 자체에 대한 접근 (access)을 최소화하며, 따라서 다이제스트 계산 프로세스 및 합성 백업의 전체적인 구축 시간 양쪽 모두를 현저하게 가속화한다.

도 11은 중복제거 시스템 (250)의 한 예시적인 부분 (252)를 도시하는데, 이전에 도시된 실시예들이 구현되는 프로세서 디바이스를 포함한다. 중복제거 시스템 (250)의 부분 (252)는 컴퓨터 환경내에서 다음에 도시된 실시 예들의 메커니즘들이 구현되는 부분으로서 동작가능하다 (operable). 하지만, 도 11은 오직 예로서 제공된 것이며, 예시적인 다양한 실시예들이 구현될 수 있는 특정한 아키텍처들로서 어떠한 제한을 진술하거나 암시하려는 의도가 없슴을 이해하여야 할 것이다. 도 11에서 도시된 아키텍처에 대하여 많은 수정들이 본 발명의 상세한 설명과 청구된 주제의 범위와 정신을 벗어남이 없이 만들어질 수 있다

부분 (252)는 프로세서 (254) 및 랜덤 액세스 메모리 (random access memory (RAM))와 같은 메모리 (256)을 포함한다. 상기 중복제거 시스템 (250)은 편의상 도시되지 않은 디스플레이와 같은 몇가지 컴포넌트들에 연결되어 동작하며, 그래픽 유저 인터페이스, 키보드, 마우스, 프린터등 상에서 사용자들에게 윈도우즈 (windows)와 같은 이미지를 제공한다. 물론, 당업자는 상기 컴포넌트들간의 어떠한 조합, 또는 어떠한 수의 다른 컴포넌트, 주변 기기, 그리고 기타 디바이스들이 상기 중복제거 시스템 (250)에서 사용될 수 있슴을 이해한다.

도시된 실시예에서, 상기 중복제거 시스템 (250) 및/또는 부분 (252)는 상기 메모리 (256)내 저장된 운영 체제 (operating system (OS)) (258) (가령, z/OS, OS/2, LINUX, UNIX, WINDOWS, MAC OS)의 제어하에 동작하며, 입력 및 명령을 받아들이고 결과를 제시하기 위하여 사용자와 인터페이스한다 (interfaces). 본 발명의 한 실시예에서, 상기 OS (258)은 본 발명에 따라서 합성 백업 기능을 용이하게 한다. 이 목적을 위하여, OS (258)은 다음에 설명되는 예시적인 방법에서 다양한 프로세스 및 메커니즘을 수행하도록 적용된 태스크 스케쥴링 모듈 (task scheduling module) (264)를 포함한다.

상기 중복제거 시스템 (250) 및/또는 부분 (252)는 컴파일러 (262)를 실행하는데 이것은 COBOL, PL/1, C, C++, JAVA, ADA, BASIC, VISUAL BASIC 또는 어떠한 기타 프로그래밍 언어와 같은 프로그래밍 언어로 기록된 응용 프로그램 (260)으로 하여금 상기 프로세서 (254)에 의하여 판독가능한 코드로 변환되도록 해준다. 완료된 이후, 상기 응용 프로그램 (260)은 상기 컴파일러 (262)를 이용하여 발생된 관계 및 로직을 사용하여 상기 중복제거 시스템 (250)의 메모리 (256)에 저장된 데이터에 접근하여 조작한다 (manipulates).

본 발명에 의거한 메커니즘 및 프로세스를 추가로 실시 및 실행하기 위하여, 메모리 (256), 프로세서 (254), 응용 프로그램 (260) 및 기타 컴퓨터 프로세싱, 네트워킹, 및 스토리지 컴포넌트와 함께 (in conjunction with), OS (258)은 합성 백업 기능성을 수행 및 용이하게 하는 추가적인 모듈을 실행할 수 있는데, 이것은 편의상 도시되지 않는다. 당업자가 이해하듯이, 현재 도시된 것과 같은 이들 추가적인 모듈의 메커니즘은 다양한 형태 및 아키텍처로 실시될 수 있다. 따라서, 현재 도면에서 다시 태스크 스케쥴링 모듈 (264)를 도시하는 것은 상기 중복제거 시스템 (250) 및/또는 부분 (252)에서 가능한 컴퓨팅 컴포넌트사이에 논리적인 관계를 나타내기 위하여 의도되었고, 특정한 물리적 스트럭처 또는 관계를 의미하려고 의도되지는 않는다.

한 실시예에서, 상기 OS (258), 상기 응용 프로그램 (260), 상기 컴파일러 (262), 뿐만 아니라 상기 태스크 스케쥴링 모듈 (264) 및 추가적인 모듈들을 실행하는 명령은 컴퓨터-판독가능 매체에서 명백히 (tangibly) 구현되며, 이것은 짚 (zip) 드라이브, 디스크, 하드 드라이브, DVD/CD-ROM, 디지털 테이프, SSD등과 같은 하나 또는 그 이상의 고정식 (fixed) 또는 착탈식 (removable) 데이터 저장 디바이스를 포함할 수 있다. 또한, 상기 OS (258) 및 응용 프로그램 (260)은, 상기 중복제거 시스템 (250) 및/또는 부분 (252)에 의하여 판독되고 실행될 때, 그것들로 하여금 본 발명을 실행 및/또는 사용하는데 필요한 단계들을 수행하도록 하는 명령들을 포함한다. 어플리케이션 프로그램 (260) 및 OS (258)의 명령들은 또한 명백히 메모리 (206)에 구현될 수 있으며, 그리고/또는 다양한 컴포넌트를 통한 네트워크 기능성을 통해 전송 또는 접근될 수 있다. 따라서, 여기서 사용될 수 있는 “제품 (article of manufacture)”, “프로그램 저장 디바이스 (program storage device)” 및 “컴퓨터 프로그램 제품 (computer program product)”이라는 용어는 어떠한 컴퓨터 판독가능 디바이스 또는 매체로부터 접근 및/또는 동작가능한 컴퓨터 프로그램을 모두 포함 (encompass)한다.

본 발명의 실시예들은 하나 또는 그 이상의 관련 소프트웨어 응용 프로그램들 (260)을 포함할 수 있는데, 이들은, 예를 들어, 저장 영역 통신망 (storage area network (SAN))과 같은 컴퓨터 디바이스들의 네트워크를 포함하는 분산된 컴퓨터 시스템을 관리하는 기능들을 포함한다. 따라서, 프로세서 (254)는 하나 또는 그 이상의 저장 관리 프로세서 (storage management processor (SMP)) 및 기타 특별한 디바이스를 포함할 수 있다. 상기 어플리케이션 프로그램 (260)은 단일 컴퓨터 및/또는 중복제거 시스템 (250)내에서 또는 컴퓨팅 디바이스들의 네트워크를 포함하는 분산된 컴퓨터 시스템의 일부분으로서 동작할 수 있다. 상기 네트워크는 근거리 통신망 (local area network (LAN)) 및/또는 인터넷 접속 (공공 접속 또는 가상 사설망 (virtual private network (VPN)일 수 있다), 혹은 파이버 채널 SAN이나 당업자는 이해할 수 있는 기타 알려진 네트워크를 통하여 접속되는 하나 또는 그 이상의 컴퓨터들을 포함할 수 있다. (파이버 채널 SAN은 통상적으로 컴퓨터들이 저장 시스템들과 커뮤니케이션하는데에만 사용되고 서로에게는 사용되지 않는다).

당업자가 이해하는 바와 같이, 본 발명의 실시예들은 시스템, 방법 또는 컴퓨터 프로그램 제품으로 구현될 수 있다. 따라서, 본 발명의 실시예들은 전적으로 하드웨어 구현의 형태, 전적으로 소프트웨어 구현의 형태 (펌웨어, 상주 소프트웨어, 마이크로-코드등) 또는 소프트웨어 및 일반적으로 “회로”, “모듈” 또는 “시스템”으로 불리는 하드웨어의 조합 구현의 형태를 취할 수 있다. 게다가, 본 발명의 실시예들은 하나 또는 그 이상의 컴퓨터 판독가능 매체(들)상에 컴퓨터 판독가능 프로그램 코드를 갖는 하나 또는 그 이상의 컴퓨터 판독가능 매체(들)에 구현되는 컴퓨터 프로그램 제품의 형태를 취할 수 있다.

하나 또는 그 이상의 컴퓨터 판독가능 매체(들)의 모든 조합이 사용될 수 있다. 컴퓨터 판독가능 매체는 컴퓨터 판독가능 신호 매체 또는 컴퓨터 판독가능 저장 매체일 수 있다. 컴퓨터 판독가능 저장 매체는 예를 들면, 전자 (electronic), 자기 (magnetic). 광학 (optical), 전자기 (electromagnetic), 적외선 (infrared) 또는 반도체 (semiconductor) 시스템, 장치 또는 디바이스, 또는 전술한 것들의 어떠한 적절한 조합일 수 있고 이에 국한되지는 않는다. 컴퓨터 판독가능 저장 매체의 좀 더 구체적인 예 (비완전 목록 (non-exhaustive list))는 다음을 포함한다: 하나 또는 그 이상의 전선을 가진 배선 (electrical connection), 휴대용 컴퓨터 디스켓, 하드 디스크, 랜덤 액세스 메모리 (RAM), 리드-온리 메모리 (ROM), 소거 및 프로그램가능 ROM (EPROM, 또는 플래시 메모리), 광섬유 (optical fiber), 자기 저장 디바이스, 또는 전술한 것들의 어떠한 적절한 조합. 본 명세서의 맥락 (context)에서, 컴퓨터 판독가능 저장 매체는 명령 실행 시스템, 장치 또는 디바이스들과 관련하여, 또는 이들에 의한 사용을 위해 그것들과 연관된 프로그램을 보유, 또는 저장할 수 있는 모든 형태의 매체일 수 있다.

컴퓨터 판독가능 매체상에 구현된 프로그램 코드는 무선, 유선, 광케이블 (optical fiber cable), 무선 주파수 (RF)등 또는 전술한 것들의 적절한 조합등을 포함하는 모든 매체 (이에 국한되지는 않지만)를 사용하여 전송될 수 있다. 본 발명의 실시예들의 동작을 수행하기 위한 컴퓨터 프로그램 코드는 하나 또는 그 이상 프로그래밍 언어의 어떤 조합으로 기록될 수 있으며, 이 언어에는 자바 (Java), 스몰토크 (Smalltalk), C++등과 같은 객체 지향형 프로그래밍 언어 (object oriented programming language) 및 “C” 프로그래밍 언어 또는 이와 유사한 프로그래밍 언어들과 같은 종래의 순차 프로그래밍 언어 (conventional procedural programming languages)를 포함한다. 상기 프로그램 코드는, 독립 (stand-alone) 소프트웨어 패키지로서, 전적으로 사용자의 컴퓨터상에서, 부분적으로 사용자의 컴퓨터상에서, 부분적으로 사용자의 컴퓨터 및 원격 컴퓨터상에서 또는 전적으로 원격 컴퓨터 또는 서버상에서 실행될 수 있다. 후자의 시나리오에서, 원격 컴퓨터는 LAN 또는 WAN을 포함하는, 어떠한 형태의 네트워크를 통해서 사용자의 컴퓨터와 접속될 수 있으며, 또는 이러한 접속은 (가령, 인터넷 서비스 공급자를 이용한 인터넷을 통하여) 외부 컴퓨터와도 접속될 수 있다.

본 발명의 여러 형태들이 본 발명의 실시예들에 따른, 방법의 흐름도 도시 (flowchart illustrations) 및/또는 블록 다이어그램 (block diagrams), 장치 (시스템) 그리고 컴퓨터 프로그램 제품을 참조하여 설명되었다. 흐름도 도시 및/또는 블록 다이어그램 각각의 블록 그리고 흐름도 도시 및/또는 블록 다이어그램의 조합은 컴퓨터 프로그램 명령들에 의하여 실행될 수 있슴을 이해할 수 있을 것이다. 이 컴퓨터 프로그램 명령들은 범용 컴퓨터의 프로세서, 특수 목적 컴퓨터, 또는 기계를 생산하는 기타 프로그램가능한 데이터 처리 장치에 제공되어, 컴퓨터의 프로세서나 기타 프로그램가능한 데이터 처리 장치를 통하여 실행될 때, 그러한 명령들이 흐름도 및/또는 블록 다이어그램이나 블록에 규정된 기능/동작 (acts)을 구현하는 수단을 생성하도록 한다. 컴퓨터, 기타 프로그램가능한 데이터 처리 장치, 또는 기타 디바이스에 특정한 방식으로 기능하도록 지시하는 이 컴퓨터 프로그램 명령들은 또한 컴퓨터 판독가능 매체에 저장되어서, 이 컴퓨터 판독가능 매체에 저장된 명령들이 흐름도 및/또는 블록 다이어그램이나 블록에 규정된 기능/작용을 구현하는 명령들을 포함하는 제품을 생성하도록 한다. 이 컴퓨터 프로그램 명령들은 컴퓨터, 기타 프로그램가능한 데이터 처리 장치, 또는 기타 디바이스에 로드되어 (loaded) 일련의 동작 단계들이 컴퓨터 실행 프로세스를 생산하기 위하여 컴퓨터, 기타 프로그램가능 장치, 또는 기타 디바이스상에서 수행되도록 하고, 그렇게 하여 컴퓨터 또는 기타 프로그램가능 장치상에서 실행되는 상기 명령들이 흐름도 및/또는 블록 다이어그램이나 블록에 규정된 기능/작용을 구현하는 프로세스를 제공하도록 한다.

상기 도면들에서 흐름도와 블록 다이어그램은 본 발명의 다양한 실시예들에 따른 시스템, 방법 및 컴퓨터 프로그램 제품의 가능한 구현들의 아키텍처, 기능 및 동작을 도시한다. 이와 관련하여, 흐름도와 블록 다이어그램내의 각각의 블록은 모듈, 세그먼트 (segment), 또는 코드의 부분을 표시하는데, 이는 지정된 논리적 기능(들)을 구현하는 하나 또는 그 이상의 실행가능한 명령들을 포함한다. 어떤 다른 실시예들에서, 블록에서 표시된 기능들은 도면에서 표시된 순서와 다르게 (out of the order) 발생할 수도 있슴을 이해하여야 한다. 예를 들면, 연속으로 도시된 두 개의 블록들이, 실제로는, 동시에 실질적으로 실행될 수도 있고, 또는 블록들은 관련 기능에 따라 때때로 역순으로 실행될 수도 있다. 블록 다이어그램의 각각의 블록 및/또는 흐름도 도시, 그리고 블록 다이어그램들에서 블록들 및/또는 흐름도 도시의 조합은 특수 목적 하드웨어와 컴퓨터 명령들의 조합의 지시된 기능들 또는 동작들, 또는 조합들을 수행하는 특수 목적 하드웨어 기반 시스템에 의하여 구현될 수 있다.

본 발명에 대한 하나 또는 그 이상의 실시예들이 상세히 기술되었으나, 당업자는 이하 기술되는 청구항의 범위를 벗어나지 않고 상기 실시예들에 대한 다양한 변형들과 개량들이 만들어질 수 있슴을 이해한다.

Claims (11)

1. 중복제거 저장 시스템(a deduplication storage system)에서 복수의 새로운 입력 데이터 세그먼트들을 위해, 프로세서 디바이스에 의한 합성 백업(a synthetic backup)의 구축을 용이하게(facilitating) 하는 방법에 있어서, 상기 합성 백업은 기존의 전체 백업(a full, existing backup)인 오리지네이팅 백업(originating backup)과는 독립적이고 상기 오리지네이팅 백업으로부터 구축되며, 상기 방법은:
   상기 복수의 새로운 입력 데이터 세그먼트들의 각각의 새로운 입력 데이터 세그먼트를 위해, 상기 새로운 입력 데이터 세그먼트들에 의하여 레퍼런스되는(referenced), 저장된 데이터 세그먼트들의 복수의 저장된 중복제거 다이제스트들을 검색하는 단계 - 상기 저장된 데이터 세그먼트들은 상기 오리지네이팅 백업으로부터 취해진 데이터이고, 상기 복수의 저장된 중복제거 다이제스트들은 상기 저장된 데이터 세그먼트들로부터 계산된 중복제거 다이제스트임 -;
   각각의 새로운 입력 데이터 세그먼트를 각각 복수의 고정-크기 데이터 서브-세그먼트들(fixed-sized data sub-segments)로 파티션하는 단계(partitioning);
   상기 복수의 고정-크기 데이터 서브-세그먼트들의 각각을 위해, 상기 합성 백업의 구축 동안, 검색된 상기 복수의 저장된 중복제거 다이제스트들에 기초하여 복수의 새로운 입력 데이터 세그먼트들의 중복제거 다이제스트들 각각을 계산하는 단계;
   각각의 새로운 입력 데이터 세그먼트의 중복제거 다이제스트를 발생시키기 위하여 상기 복수의 새로운 입력 데이터 세그먼트 중복제거 다이제스트들의 각각을 합하는 단계(aggregating);
   각각의 새로운 입력 데이터 세그먼트의 상기 중복제거 다이제스트의 매칭을 위해, 상기 저장된 데이터 세그먼트들의 상기 복수의 저장된 중복제거 다이제스트들을 탐색하는 단계 - 이에 의해 각각의 새로운 입력 데이터 세그먼트의 중복을 제거함(deduplicate) -; 및
   각각의 새로운 입력 데이터 세그먼트의 상기 중복제거 다이제스트들로부터 상기 합성 백업의 중복제거 다이제스트를 형성하는 단계;를 포함하는
   방법.
2. 삭제
3. 제1항에 있어서,
   상기 탐색하는 단계 이후에, 인덱스 내 상기 복수의 새로운 입력 데이터 세그먼트들의 중복제거 다이제스트들을 저장하는 단계를 더 포함하고, 상기 복수의 새로운 입력 데이터 세그먼트들의 중복제거 다이제스트들 중 하나의 입력 데이터 세그먼트 중복제거 다이제스트와 매치되는 상기 복수의 저장된 중복제거 다이제스트들 중 하나의 저장된 중복제거 다이제스트는 상기 새로운 입력 데이터 세그먼트의 중복제거 다이제스트에 의해 치환되는(displaced)
   방법.
4. 제1항에 있어서,
   상기 중복제거 저장 시스템 내 메타데이터 파일을 생성하는 단계; 및
   연속적인 저장 명령들을 최적화하는 단계;를 더 포함하는
   방법.
5. 제4항에 있어서, 각각의 최적화된 저장 명령을 위해, 상기 방법은:
   상기 최적화된 저장 명령에 의하여 표시된 상기 새로운 입력 데이터 세그먼트와 연관된 메타데이터 세그먼트를 검색하는 단계,
   상기 메타데이터 세그먼트를 오직 상기 새로운 입력 데이터 세그먼트만 레퍼런스하도록 조정하는 단계,
   상기 조정된 메타데이터 세그먼트를 상기 합성 백업의 메타데이터 파일에 복사하는 단계, 및
   상기 메타데이터 세그먼트에 의하여 레퍼런스되는 각각의 스토리지 블록을 위해, 레퍼런스 카운트값을 증분시키는 단계(incrementing)를 더 포함하는
   방법.
6. 제1항에 있어서, 복수의 새로운 입력 데이터 세그먼트들의 중복제거 다이제스트들의 각각을 계산하는 단계는:
   상기 복수의 새로운 입력 데이터 세그먼트 내 각각의 블록을 위한 해쉬값을 바이트 오프셋으로 (in byte offsets) 계산하는 단계;
   중요성 순서에 따라 (according to an order of significance), 선택된 복수의 최대 해쉬값들을 내림차순으로 (in descending order) 정렬하는 단계;
   상기 최대 해쉬값들 (hash values)과 연관된 블록들에 관한 결정된 위치들에 있는 블록들을 쉬프트된 블록들 (shifted blocks)로서 식별하는 단계;
   상기 복수의 새로운 입력 데이터 데이터 세그먼트들 중 첫 번째 고유의 특성 (distinguishing characteristic)을 위해, 상기 쉬프트된 블록들의 해쉬값들의 서브세트 (subset)를 선택하는 단계; 및
   상기 복수의 새로운 입력 데이터 세그먼트들 중 두 번째 고유의 특성을 위해, 상기 쉬프트된 블록들의 해쉬값들의 추가 서브세트를 선택하는 단계를 포함하는
   방법.
7. 제6항에 있어서, 상기 두 번째 고유의 특성을 저장하기 위해 상기 복수의 새로운 입력 데이터 세그먼트들에 대한 고유의 특성(DC) 인덱스(distinguishing characteristics (DC) index)를 구성하는 단계, 및 상기 첫 번째 고유의 특성을 저장하기 위해 상기 복수의 새로운 입력 데이터 세그먼트들에 대한 저장 식별자(SI) 인덱스 (storage identifiers (SI) index)를 구성하는 단계를 더 포함하는
   방법.
8. 제7항에 있어서,
   상기 첫 번째 및 두 번째 고유의 특성(DC)을 계산하는 단계를 더 포함하는
   방법.
9. 삭제
10. 중복제거 저장 시스템(a deduplication storage system)에서 복수의 새로운 입력 데이터 세그먼트들을 위해, 합성 백업(a synthetic backup)의 구축을 용이하게(facilitating) 하는 시스템에 있어서, 상기 합성 백업은 기존의 전체 백업(a full, existing backup)인 오리지네이팅 백업(originating backup)과는 독립적이고 상기 오리지네이팅 백업으로부터 구축되며, 상기 시스템은:
    메모리; 및
    중복제거 컴퓨팅 저장 시스템에서 동작가능하고, 상기 메모리와 통신하는 적어도 하나의 프로세서 디바이스;를 포함하고,
    상기 적어도 하나의 프로세서 디바이스는:
    상기 복수의 새로운 입력 데이터 세그먼트들의 각각의 새로운 입력 데이터 세그먼트를 위해, 상기 새로운 입력 데이터 세그먼트들에 의하여 레퍼런스되는(referenced), 저장된 데이터 세그먼트들의 복수의 저장된 중복제거 다이제스트들을 검색하고 - 상기 저장된 데이터 세그먼트들은 상기 오리지네이팅 백업으로부터 취해진 데이터이고, 상기 복수의 저장된 중복제거 다이제스트들은 상기 저장된 데이터 세그먼트들로부터 계산된 중복제거 다이제스트들임 -,
    각각의 새로운 입력 데이터 세그먼트를 각각 복수의 고정-크기 데이터 서브-세그먼트들(fixed-sized data sub-segments)로 파티션하고,
    상기 복수의 고정-크기 데이터 서브-세그먼트들의 각각을 위해, 상기 합성 백업의 구축 동안, 검색된 상기 복수의 저장된 중복제거 다이제스트들에 기초하여 복수의 입력 중복제거 다이제스트들 각각을 계산하고,
    각각의 새로운 입력 데이터 세그먼트의 중복제거 다이제스트를 발생시키기 위하여 상기 복수의 새로운 입력 데이터 세그먼트들의 중복제거 다이제스트들의 각각을 합하고,
    각각의 새로운 입력 데이터 세그먼트의 상기 중복제거 다이제스트의 매칭을 위해, 상기 저장된 데이터 세그먼트들의 상기 복수의 저장된 중복제거 다이제스트들을 탐색하고 - 이에 의해 각각의 새로운 입력 데이터 세그먼트의 중복을 제거함(deduplicate) -, 그리고
    각각의 새로운 입력 데이터 세그먼트의 상기 중복제거 다이제스트들로부터 상기 합성 백업의 중복제거 다이제스트를 형성하도록 구성되는
    시스템.
11. 컴퓨터 판독가능 매체에 있어서,
    상기 컴퓨터 판독가능 매체는, 중복제거 저장 시스템에서 복수의 새로운 입력 데이터 세그먼트들을 위해, 합성 백업의 구축을 용이하게 하는 컴퓨터 프로그램을 포함하고,
    상기 컴퓨터 프로그램은, 컴퓨터에 의하여 실행될 때 상기 청구항 제1항, 제3항 내지 제8항 중 어느 한 항에 기재된 방법의 모든 단계들을 수행하도록 하는 컴퓨터 프로그램 코드를 포함하는,
    컴퓨터 판독가능 매체.

Images