KR20130045246A

KR20130045246A - 데이터 저장 디바이스들에 대한 액세스들의 공간적인 분포에 기초하는 캐싱

Info

Publication number: KR20130045246A
Application number: KR1020127025001A
Authority: KR
Inventors: 아르빈드 프루씨
Original assignee: 마벨 월드 트레이드 리미티드
Priority date: 2010-02-24
Filing date: 2011-02-23
Publication date: 2013-05-03
Also published as: US8812790B2; EP2539821A1; JP2013520756A; US8539162B2; CN102884512B; CN102884512A; US20140089597A1; JP5700262B2; US20110208919A1; EP2539821B1; KR101779992B1; WO2011106458A1

Abstract

저장 시스템들에 대한 액세스들의 공간적인 분포(spatial distribution)의 양을 정하고(quantify), 저장 시스템들 내의 저장 어드레스들에 대한 참조들(references)의 공간적인 로컬리티(spatial locality)를 결정하기 위한, 방법들, 시스템들, 및 컴퓨터 저장 매체 상에 엔코드된 컴퓨터 프로그램들을 포함하는 장치들이 개시된다. 일 양상에서, 본 발명의 방법은 데이터 저장 시스템에 대한 액세스들의 다수의 별개의 그룹들에 기초하여 그 데이터 저장 시스템에 대한 액세스들의 공간적인 분포의 측정(measure)을 결정하는 단계, 및 결정된 공간적인 분포의 측정에 기초하여, 데이터 저장 시스템에 대해 이용되는 캐싱 방침(caching policy)을 조정하는 단계를 포함한다.

Description

데이터 저장 디바이스들에 대한 액세스들의 공간적인 분포에 기초하는 캐싱{CACHING BASED ON SPATIAL DISTRIBUTION OF ACCESSES TO DATA STORAGE DEVICES}

관련 출원들에 대한 상호 참조

본 출원은, 35 U.S.C. §119(e) 하에서, 2010년 2월 24일 출원되었으며 그 명칭이 "Quantifying Spatial Locality on a Block Device by Sampling Ops and its Application on Cache"인 미국 특허 출원 제61/307,789호의 우선권을 주장하며, 그 전체는 본원에 참조로서 통합된다.

본 출원은 데이터 저장 디바이스들에 대한 액세스들의 공간적인 분포(spatial distribution)에 기초하는 저장 디바이스들에 대한 캐싱(caching)에 관한 것이다.

저장 디바이스들의 예들은 하드 디스크 드라이브들 및 광학 디스크 드라이브들을 포함한다. 전형적으로, 저장 디바이스들은 순환하는 저장 매체(rotating storage medium) 상에 블록들로 데이터를 저장한다. 블록 사이즈들은 종종 킬로바이트(KB)로 측정된다. 예를 들어, 저장 매체는 자기 디스크들, 광학 디스크들 등을 포함할 수 있다. 따라서, 이러한 저장 디바이스들은 전형적으로 반도체 메모리보다 더 느린 액세스 시간들을 갖는다. 결과적으로, 데이터는 이러한 저장 매체 보다 반도체 메모리로부터 더 빠르게 판독될 수 있다.

많은 저장 디바이스들은, 호스트에 의해 반복적으로 요청되거나 또는 호스트에 의해 요청될 수 있는 데이터를 저장하기 위한, 캐시 메모리라 불리는 반도체 메모리를 포함한다. 전형적으로, 이러한 저장 디바이스들은 캐시 메모리에 대한 데이터의 캐싱을 제어하는 캐시 제어기를 포함한다. 예를 들어, 호스트가 판독 커맨드를 발행하면, 캐시 제어기는 먼저, 요청된 데이터가 캐시 메모리 내에서 이용가능한지를 결정한다. 요청된 데이터가 캐시 메모리 내에서 이용가능하지 않다면, 캐시 미스(cache miss)가 발생되며, 저장 매체로부터 데이터가 검색되어, 호스트에 포워딩된다. 캐시 제어기는 캐시 메모리 내에 데이터를 캐싱할 수 있다.

호스트가 동일한 데이터를 다시 요청하면, 이 데이터는 캐시 메모리 내에서 발견되며(즉, 캐시 히트(cache hit)가 발생된다), 그 캐시 메모리로부터 호스트로 출력된다. 호스트는, 저장 매체로부터 보다, 캐시 메모리로부터 데이터를 더 빠르게 수신한다. 부가적으로, 호스트에 의해 요청되는 데이터에 기초하여, 기타 관련된 데이터가 캐싱될 수 있는 바, 이는 호스트가 이러한 기타 관련된 데이터를 요청할 수 있음을 예상하여 이루어지는 것이다. 하지만, 캐시 메모리의 사이즈가 제한된다. 이에 따라, 캐싱될 수 있는 데이터의 양 또한 제한된다. 따라서, 캐시 제어기는 캐시 메모리로부터 데이터를 선택적으로 삭제할 수 있다. 예를 들어, 일정 시간 기간 동안 호스트에 의해 요청되지 않은 데이터가 캐시 메모리로부터 삭제될 수 있다. 호스트가 캐시 메모리에 저장된 데이터 이외의 데이터를 요청할 때에도, 데이터가 삭제될 수 있다. 캐시 메모리로부터 데이터를 선택적으로 삭제함으로써, 호스트에 의해 이용될 가능성이 더 큰 데이터가 캐싱될 수 있다.

본 명세서는 저장 시스템들에 대한 액세스의 공간적인 분포의 양을 정하고(quantify), 저장 시스템들 내의 저장 어드레스들에 대한 참조들(references)의 공간적인 로컬리티(spatial locality)를 결정하기 위한 기술들을 개시한다. 저장 위치라고도 지칭될 수 있는 어드레스는 특정의 저장 디바이스 상의 위치의 물리적인 어드레스이거나, 또는 이러한 어드레스는 가상 볼륨(virtual volume) 내의 위치의 논리적인 위치일 수 있다. 저장 시스템 상의 어드레스에 대한 참조는, 액세스되는 어드레스에 저장된 데이터에 대해 판독 동작 또는 기록 동작을 수행하기 위해 그 저장 시스템을 액세스하는 것과 관련된다. 일반적으로, 저장 시스템은 개별적인 저장 디바이스들(예를 들어, 하드 드라이브들) 뿐 아니라, 저장 디바이스들의 결합들, 예를 들어 RAID(redundant array of independent disks), NAS(network attached storage), SAN(storage area network)을 포함한다. 저장 디바이스들의 결합에 대한 공간적인 로컬리티는, 다수의 물리적인 드라이브들에 걸쳐있는(span) 논리 디바이스들(블록 디바이스들이라고도 불림)에 해당할 수 있다.

일반적으로, 본 명세서에서 개시되는 발명의 일 양상은 데이터 처리 장치에 의해 수행되는 방법들로 구현될 수 있는 바, 이러한 방법들은 데이터 저장 시스템에 대한 액세스들의 다수의 별개의 그룹들에 기초하여 그 데이터 저장 시스템에 대한 액세스들의 공간적인 분포의 측정(measure)을 결정하는 단계의 동작들을 포함한다. 이러한 방법들은 결정되는 공간적인 분포의 측정에 기초하여, 데이터 저장 시스템에 대해 이용되는 캐싱 방침(caching policy)을 조정하는 단계를 더 포함한다.

상기 및 기타 구현들은 하기의 특징들 중에서 하나 이상을 포함할 수 있다. 상기 방법들은 데이터 저장 시스템에 대한 상이한 참조 액세스들(reference accesses)에 기초하여 그 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계를 포함할 수 있다. 상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계는, 난수 발생(random number generation)에 기초하여 데이터 저장 시스템에 대한 상이한 참조 액세스들을 결정하는 단계를 포함할 수 있다. 상기 캐싱 방침을 조정하는 단계는 데이터 저장 시스템으로부터의 데이터의 프리페칭(pre-fetching)의 양을 변경하는 단계를 포함할 수 있다.

상기 방법들은 또한, 데이터 저장 시스템에 대한 동일한 참조 액세스에 기초하여, 그 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계를 포함할 수 있다. 상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계는, 2개의 상이한 공간적인 범위들에 기초하여 데이터 저장 시스템에 대한 액세스들의 2개의 별개의 그룹들을 식별하는 단계를 포함할 수 있다. 또한, 상기 공간적인 분포의 측정을 결정하는 단계는, 제 1 수(number)와 제 2 수를 비교하는 단계를 포함할 수 있다. 제 1 수는 2개의 별개의 그룹들 중 하나에 해당할 수 있고, 제 2 수는 2개의 별개의 그룹들 중 다른 하나에 해당할 수 있다. 또한, 상기 캐싱 방침을 조정하는 단계는, 상기 제 2 수와 제 1 수의 비교에 기초하여, 데이터 저장 시스템의 상이한 영역들로부터 데이터를 선택적으로 프리페칭하는 단계를 포함할 수 있다.

본 양상의 다른 구현들은 해당하는 시스템들, 장치, 및 컴퓨터 저장 디바이스들 상에 엔코드되어, 상기 방법들의 동작들을 수행하도록 구성된 컴퓨터 프로그램들을 포함한다.

다른 양상에 따르면, 개시되는 발명은 또한, 저장 매체, 캐시 디바이스, 및 이러한 매체 및 캐시 디바이스와 통신 가능하게 결합되는 제어기를 포함하는 저장 시스템으로 구현될 수 있다. 제어기는 컴퓨터 시스템의 메모리 또는 프로세서와 인터페이스하도록 구성된다. 또한, 제어기는 저장 시스템과 관련된 어드레스 참조들의 특정된 양(specified quantity)을 수신하도록 구성된다. 제어기는 또한, 어드레스 참조들의 수신되는 특정된 양에 적어도 부분적으로 기초하여, 저장 시스템의 어드레스들에 대한 참조들의 공간적인 분포를 결정하고, 상기 결정된 공간적인 분포를 이전에 결정된 공간적인 분포와 상기 저장 시스템의 공간적인 로컬리티 메트릭(spatial locality metric)으로 결합하도록 구성된다. 또한, 제어기는 데이터를 캐싱하는 데에 이용하기 위해 이러한 공간적인 로컬리티 메트릭을 상기 저장 매체로부터 상기 캐시 디바이스로 출력하도록 구성된다.

상기 및 기타 구현들은 하기의 특징들 중에서 하나 이상을 포함할 수 있다. 몇몇 구현들에서, 캐시 디바이스는 캐시 메모리를 포함할 수 있다. 몇몇 구현들에서, 캐시 디바이스는 디바이스 제어기를 더 포함할 수 있다.

공간적인 분포의 결정을 수행하기 위해, 제어기는 공간적인 분포의 이전의 결정과 공간적인 분포의 상기 결정 간의 어드레스 참조들의 임의의 양(random quantity)을 생략(omit)하도록 더 구성될 수 있다. 또한, 공간적인 로컬리티 메트릭은 결정된 공간적인 분포와 이전에 결정된 공간적인 분포의 가중 합(weighted sum)을 포함할 수 있다. 또한, 제어기는 저장 시스템의 어드레스에 대한 참조를 수신하도록 더 구성될 수 있는 바, 수신되는 어드레스 참조는 저장 시스템 상의 소정의 블록 오프셋(block offset)에 해당한다. 부가적으로, 제어기는 캐시 디바이스 내에서 수신된 어드레스 참조에 대한 캐시 미스를 검출하고, 이러한 캐시 미스의 검출에 응답하여, 공간적인 로컬리티 메트릭의 현재 값에 따라 캐시 디바이스에 캐싱하기 위한 저장 시스템의 소정의 블록 오프셋과 관련된 데이터를 선택하도록 구성된다.

몇몇 다른 실시예들에서, 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는, (i) 공간적인 로컬리티 메트릭의 현재 값이 제 1 값과 이러한 제 1 값 보다 큰 제 2 값 사이인 경우, 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 특정된 양의 데이터, (ii) 공간적인 로컬리티 메트릭의 현재 값이 제 2 값 보다 큰 경우, 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 특정된 양 보다 많은 데이터, 및 (iii) 공간적인 로컬리티 메트릭의 현재 값이 제 1 값 미만인 경우, 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 특정된 양 미만의 데이터를 포함할 수 있다. 예를 들어, 공간적인 로컬리티 메트릭의 현재 값이 제 1 값 미만인 경우, 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는 0(zero) 이다. 다른 예에서, 공간적인 로컬리티 메트릭의 현재 값이 제 2 값 보다 큰 경우, 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 특정된 양의 두배의 데이터를 포함한다.

몇몇 다른 구현들에서, 상기 저장 시스템 상에서의 상기 결정된 공간적인 분포는, 어드레스 참조들의 수신되는 특정된 양의 제 1 어드레스 참조의 블록 오프셋으로부터 제 1 거리 내에 있는, 상기 어드레스 참조들의 수신되는 특정된 양의 제 1 부분(fraction)을 포함할 수 있다. 부가적으로, 상기 저장 시스템 상에서의 상기 결정된 공간적인 분포는, 어드레스 참조들의 수신되는 특정된 양의 제 1 어드레스 참조의 블록 오프셋으로부터 제 2 거리 내에 있는, 상기 어드레스 참조들의 수신되는 특정된 양의 제 2 부분을 포함할 수 있다. 제 2 거리는 제 1 거리 보다 더 길며, 이에 따라 상기 결정된 공간적인 분포는 제 1의 더 짧은 거리에 대한 제 1 부분의 비(ratio)를 나타내는 공간 분포의 단범위 컴포넌트(short-range component), 및 제 2의 더 긴 거리에 대한 제 2 부분의 다른 비를 나타내는 공간 분포의 장범위 컴포넌트(long-range component)를 갖는다. 공간적인 로컬리티 메트릭은, 공간적인 분포의 단범위 및 장범위 컴포넌트들 각각에 해당하는 단범위 및 장범위 공간적인 로컬리티 메트릭들을 포함할 수 있다. 또한, 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는, (i) 단범위 공간적인 로컬리티 메트릭의 현재 값이 장범위 공간적인 로컬리티 메트릭의 현재 값 보다 큰 경우, 소정의 블록 오프셋으로부터 제 1 거리 미만에 위치되는 어드레스들, (ii) 단범위 및 장범위 공간적인 로컬리티 메트릭들의 현재 값들이 실질적으로 같은 경우, 소정의 블록 오프셋으로부터 제 2 거리 미만에 위치되는 어드레스들, 및 (iii) 단범위 공간적인 로컬리티 메트릭의 현재 값이 장범위 공간적인 로컬리티 메트릭의 현재 값 보다 작은 경우, 소정의 블록 오프셋으로부터 제 2 거리와 제 1 거리 사이에 위치되는 어드레스들에 해당할 수 있다.

본 명세서에서 개시되는 발명의 특정의 구현들은 하기의 장점들 중에서 하나 이상을 포함할 수 있다. 본 명세서에서 개시되는 시스템들 및 기술들은 저장 시스템에 대한 액세스들의 공간적인 분포의 현재 패턴들에 따라 캐싱될 데이터의 최적의 양을 결정하는 데에 이용될 수 있다. 또한, 개시되는 기술들은 현재의 공간적인 로컬리티 패턴들에 기초하여 데이터를 프리페치할 저장 시스템의 영역들을 식별하는 데에 이용될 수 있다.

본 명세서에서 개시되는 발명의 하나 이상의 구현들의 상세사항들이 첨부 도면들 및 하기의 상세한 설명에서 설명된다. 본 발명의 다른 특징들, 양상들 및 장점들은 하기의 상세한 설명, 도면들 및 청구항들로부터 명백해질 것이다.

도 1a-1h는 저장 시스템에 해당하는 공간적인 로컬리티 메트릭들의 예들을 도시한다.
도 2a-2c는 저장 시스템의 공간적인 로컬리티의 메트릭에 기초하여 그 저장 시스템의 하나 이상의 저장 디바이스 상에 저장된 데이터를 캐싱하기 위한 시스템의 일 예의 양상들을 도시한다.
도 3은 저장 시스템의 공간적인 로컬리티 메트릭을 업데이트하기 위한 방법의 일 예를 도시한다.
도 4a 및 4b는 저장 시스템의 공간적인 로컬리티 메트릭의 현재 값에 따라 그 저장 시스템에 저장된 데이터를 캐싱하기 위한 방법의 일 예의 앙상들을 도시한다.
도 5a 및 5b는 저장 시스템의 다른 공간적인 로컬리티 메트릭의 현재 값에 따라 그 저장 시스템에 저장된 데이터를 캐싱하기 위한 방법의 다른 예의 앙상들을 도시한다.
도 6a-6d는 데이터 저장 시스템에 대한 액세스들의 공간적인 분포의 측정에 기초하여 그 데이터 저장 시스템에 대해 이용되는 캐싱 방침을 조정하기 위한 방법의 일 예의 양상들을 도시한다.
여러 도면들에서 같은 참조 부호들 및 지시들(designations)은 같은 요소들을 나타낸다.

작지만 빠른 랜덤 액세스 또는 고상의 (예를 들어, 플래시) 메모리를 레버리징(leveraging)함으로써 저장 시스템들(예를 들어, 하드 드라이브들과 같은 개별적인 저장 디바이스들, 또는 저장 디바이스들의 결합)에 대해 캐싱하는 것이 특히 대중적이다. 대부분의 캐싱 시스템들은, 블록이 호스트에 의해 액세스를 위해 참조되지만, 참조되는 블록이 캐시 메모리 내에서 발견되지 않는 캐시 미스가 발생될 때에, 데이터의 블록을 캐싱한다. 하지만, 호스트는 캐시된 블록을 다시 이용할 필요가 없다. 결과적으로, 캐시 미스의 발생들에만 기초하여 블록들을 캐싱하는 것은, 호스트에 의해 다시 이용되지 않을 수도 있는 블록들로 캐시 메모리를 파퓰레이트(populate)할 수 있게 되며, 이에 의해 호스트에 의해 반복적으로 이용될 수 있는 다른 데이터를 캐싱하는 데에 이용가능한 캐시 메모리의 양을 감소시키게 된다. 하지만, 호스트(예를 들어, 마이크로소프트 익스체인지(Microsoft Exchange), SQL 서버(SQL Server), 오라클(Oracle) 등) 상에서 실행되고 있는 애플리케이션들에 의존하여, 가상 볼륨은 각각의 애플리케이션들에 대해 특유할 수 있는 시간적인 및/또는 공간적인 액세스 패턴들을 경험할 수 있다. 이 때문에, 저장 시스템 상의 어드레스들에 대한 참조들의 합리적으로 높은 시간적인 및/또는 공간적인 로컬리티가 있을 때에는, 약속들(promises)을 캐싱하는 것이 이득이 된다.

저장 시스템의 어드레스들에 대한 참조들의 시간적인 로컬리티는 단위 시간 마다 참조되는 저장 시스템 상의 어드레스들의 개수를 나타내거나, 또는 동등하게는, 시간적인 로컬리티는 저장 시스템 상의 어드레스들에 대한 참조들의 레이트(rate)를 나타낸다. 또한, 시간적인 로컬리티는 저장 시스템에 대해, 또는 저장 시스템 상의 하나 이상의 영역들에 대해 모니터될 수 있으며, 그리고 캐싱 알고리즘은 저장 시스템 상의 어드레스들에 대한 참조들의 모니터되는 레이트에 기초하여 구현될 수 있다.

저장 시스템의 어드레스들에 대한 참조들의 공간적인 로컬리티는 단위 어드레스 공간 마다 참조되는 저장 시스템 상의 어드레스들의 개수를 나타내거나, 또는 동등하게는, 공간적인 로컬리티는 저장 시스템 상의 어드레스들에 대한 참조들의 공간 밀도(spatial-density)를 나타낸다. 예를 들어, 저장 시스템의 특정 어드레스가 참조될 때, 공간적인 로컬리티는 근처의 메모리 위치들이 미래에 참조될 확률(probability)을 제공한다. 본 명세서에서, 저장 시스템의 어드레스들에 대한 참조의 공간적인 로컬리티라는 용어는, 저장 시스템에 대한 액세스들의 공간적인 분포라는 용어와 서로 교환가능하게 이용된다는 것을 주목한다. 또한, 공간적인 로컬리티는 저장 시스템에 대해, 또는 저장 시스템 상의 하나 이상의 영역들에 대해 모니터될 수 있으며, 그리고 캐싱 알고리즘은 저장 시스템 상의 어드레스들에 대한 참조들의 모니터되는 공간 밀도에 기초하여 구현될 수 있다. 이러한 방식으로, 이를 테면 공간 밀도가 높을 때, 캐시 메모리에 의해 제공되는 제한된 공간이 저장 시스템의 블록들을 캐싱하는 데에 최적으로 이용될 수 있다.

본 명세서에서는, 도 1a-1h와 관련하여, 저장 시스템에 대한 액세스들의 공간적인 분포들의 다수의 표현들이 하기에서 설명된다. 또한, 도 3 및 6a-6d와 관련하여, 저장 시스템들에 대한 액세스들의 공간적인 분포들을 측정하기 위한 다양한 기술들이 하기에서 설명된다. 또한, 도 4a-4b 및 5a-5b와 관련하여, 저장 시스템에 대한 액세스들의 공간적인 분포의 측정들에 따라 그 저장 시스템 상에 저장된 데이터를 캐싱하기 위한 기술들이 하기에서 설명된다. 이러한 기술들은 도 2a-2c와 관련하여 하기에서 설명되는 시스템들에서 구현될 수 있다.

도 1a의 테이블 1은 저장 시스템(140)에 해당하는 공간적인 로컬리티 메트릭(110)의 일 예를 포함한다. 공간적인 로컬리티 메트릭(110)은 저장 시스템(140)에 대한 액세스들의 공간적인 분포의 측정이거나, 또는 동등하게는, 저장 시스템의 공간적인 로컬리티(150)의 측정이다. 공간적인 로컬리티(150)의 값(샘플이라고도 지칭됨)은, 저장 시스템(140) 상의 어드레스들에 대해 "m"개의 참조들의 시퀀스를 이용함으로써, 저장 시스템(140) 상의 어드레스 공간의 사이즈 "A₁"에 대해 결정될 수 있다. 도 1b는 저장 시스템(140)의 일부분, 및 공간적인 로컬리티(150)의 값을 결정하는 데에 이용되는 참조 (READ/WRITE) 동작에 해당하는 블록 오프셋(block offset) "X_n"을 도시한다. 도 1b에 도시된 바와 같이, 사이즈 "A₁"의 어드레스 공간은

으로부터

까지 블록 오프셋 "X_n" 상에 중심을 두는 어드레스 간격에 걸쳐있다. 저장 시스템(140) 상에서의 전형적인 블록 사이즈는 4KB이지만, 사이즈 "A₁"은, 이를 테면 64KB, 128KB, 256KB 또는 512 KB일 수 있다. 몇몇 구현들에서, 저장 시스템(140) 상의 어드레스들에 대한 "m"개의 참조들의 시퀀스는 블록 오프셋 "X_n"에 해당하는 참조 동작(reference operation) 다음에 오는 "m"개의 연속적인 동작들에 해당한다. 숫자 "m"은, 예를 들어 m=15의 값으로 프리셋될 수 있다.

공간적인 로컬리티(150)의 값은 0(제로)으로 초기화된다. 이후, "m"개의 참조들의 시퀀스에 해당하는 어드레스들이 참조 동작에 해당하는 블록 오프셋 "X_n"으로부터 거리

내에 있는 지에 대해 "m"개의 결정들이 이루어지며, 이러한 "m"개의 결정들 중에서 각각의 포지티브(positive) 결정에 대해, 공간적인 로컬리티(150)의 값이 1 만큼 증분될 수 있다. 예를 들어, "m"개의 참조들의 시퀀스로부터 "k"개의 참조들이 참조 동작에 해당하는 블록 오프셋 "X_n" 상에 중심을 두는 사이즈 "A₁"의 어드레스 공간 내의 어드레스들에 해당한다면, 공간적인 로컬리티(150)는 "k"의 정수 값을 가지며, 여기서 0≤k≤m 이다. 다른 예에서, 공간적인 로컬리티(150)는 노멀라이즈(normalize)되고, "k/m"의 부분 값(fractional value)을 가지며, 여기서 0≤k/m≤1 이다. 공간적인 로컬리티(150)의 노멀라이즈된 값들의 이용은, 이를 테면 저장 시스템(140) 상의 어드레스들에 대한 참조들의 상이한 개수들, 예를 들어 "m₁", "m₂"..를 갖는 시퀀스들을 이용하여 결정된 공간적인 로컬리티(150)의 값들을 비교할 수 있게 한다. "m"-값들의 다른 예들은 5, 10, 15, 20, 30, 50, 100 등이 있다. 또한, 상기 예들에서의 공간적인 로컬리티(150)는 차원이 없다(dimensionless)는 것을 주목해야 한다.

일단 상기 설명한 바와 같이 공간적인 로컬리티(150)의 값이 결정되면, 공간적인 로컬리티 메트릭(110)의 인스턴트 값(instant value)이, 공간적인 로컬리티(150)의 결정된 값과 공간적인 로컬리티 메트릭의 이전에 계산된 값 사이의 가중 평균(weighted average)으로서 계산될 수 있다. 예를 들어, 공간적인 로컬리티 메트릭(110)의 인스턴트 값은,

로서 계산될 수 있다.

S_A1(instant) 및 S_A1(previous)의 표기들은 공간적인 로컬리티 메트릭(110)의 각각의 인스턴트 및 이전 값들을 나타낸다. s(A₁, M; n)의 표기는, 저장 시스템(140) 상의 어드레스 공간의 사이즈 "A₁"에 대해, 그리고 블록 오프셋 "X_n"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여 결정되는 공간적인 로컬리티(150)의 값을 나타낸다. 가중치 "β"는 공간적인 로컬리티 메트릭(110)의 현재 값을 계산함에 있어서 공간적인 로컬리티 메트릭 히스토리의 영향의 측정을 나타낸다.

몇몇 구현들에서, 가중치 "β"가 작은 값을 가질 때, 예를 들어 β<0.15 일 때, 공간적인 로컬리티 메트릭(110)의 인스턴트 값은 공간적인 로컬리티 메트릭 히스토리에 대해 심하게(heavily) 가중될 수 있다. 하지만, 가중치 "β"가 큰 값들을 가질 때, β>0.85 일 때, 공간적인 로컬리티 메트릭 히스토리는 공간적인 로컬리티 메트릭(110)의 인스턴트 값에 대해 작은 영향을 가질 수 있다. 후자의 경우, 공간적인 로컬리티 메트릭(110)의 인스턴트 값에 대한 주요한 기여(contribution)는 공간적인 로컬리티(150)의 현재 결정된 값으로부터 비롯된다.

하지만, 공간적인 로컬리티(150)의 이후의 값은, 블록 오프셋 "X_n ₊₁"에 해당하는 다른 동작 및 다른 참조 동작 다음에 오는 "m"개의 동작의 다른 시퀀스와 관련하여, 상기 설명한 바와 같이 결정될 수 있다. 이러한 다른 동작은, 본 명세서에서 하기 설명되는 바와 같이, 예를 들어 시간에 기초하여, 또는 다수의 동작들에 기초하여, 또는 임의의 팩터(factor)에 기초하여 결정될 수 있다. 도 1b는 다른 참조 동작과 관련된 블록 오프셋 "X_n ₊₁"을 도시한다. 이를 테면, "m"개의 참조들의 다른 시퀀스에 해당하는 어드레스들이 다른 참조 동작에 해당하는 블록 오프셋 "X_n ₊₁"로부터 거리

내에 있는 지에 대해 "m"개의 결정들이 이루어지며, 이러한 "m"개의 결정들 중에서 각각의 포지티브 결정에 대해, 공간적인 로컬리티(150)의 값이 1 만큼 증분될 수 있다. 또한, 공간적인 로컬리티 메트릭(110)의 이후의 인스턴트 값 S_A1(instant)이, 공간적인 로컬리티 메트릭(110)의 이전에 계산된 인스턴트 값을 공간적인 로컬리티 메트릭(110)의 이전 값 S_A1(previous)으로서 이용하고, 블록 오프셋 "X_n ₊₁"에 해당하는 동작과 관련하여 저장 시스템(140) 상의 어드레스 공간의 사이즈 "A1"에 대해 결정되는 공간적인 로컬리티(150)의 값 s(A₁, m; n+1)을 이용하여, 방정식 (1)에 따라 계산된다.

공간적인 로컬리티 메트릭(110)의 인스턴트 및 이전 값들은 서로와 관련되고, 방정식 (1)에 따라 공간적인 로컬리티(150)의 값과 관련되기 때문에, 상기 양들을 결정함에 있어서의 조직적인 에러들(systematic errors)이 전파되어, 방정식 (1)에서의 계산의 정확성에 영향을 미칠 수 있다. 하지만, 공간적인 로컬리티 메트릭(110)의 계산의 정확성은 공간적인 로컬리티(150)의 연속적인 결정들 사이에서 임의 개수의 동작들을 스킵(skip)함으로써 증가될 수 있는데, 이는 주기적인 특성을 갖는 인공물들(artifacts)의 영향이 이러한 방식으로 감소되기 때문이다. 이에 따라, 임의 개수인 "r"개의 동작들이, 블록 오프셋 "X_n"에 해당하는 참조 동작과 관련된 "m"개의 동작들의 시퀀스에서 마지막 "m번째" 동작 이후에, 그리고 블록 오프셋 "X_n ₊₁"에 해당하는 다른 참조 동작 이전에, 스킵될 수 있다. 임의 개수 "r"은 0과 "N" 사이에서 발생될 수 있는바, 여기서 "N"은 공간적인 로컬리티(150)의 값의 연속적인 결정들 사이에서 스킵될 수 있는 최대 개수의 동작들을 나타낸다. 수 "N"은, 예를 들어 N=10의 값으로 프리셋될 수 있다. 몇몇 구현들에서, 연속적인 참조 동작들 사이에서 스킵하기 위한 동작들의 개수는 기간 간격들에 기초하여 결정될 수 있다. 예를 들어, 스킵되어야 하는 동작들은 소프트웨어/펌웨어에서 프리셋될 수 있는 값을 갖는 시간 간격들 동안 일어날 수 있다. 다른 예에서, 스킵되어야 하는 동작들은 소프트웨어/펌웨어에서 프리셋될 수 있는 최소 시간 간격과 최대 시간 간격 사이에서 무작위로 발생되는 값들을 갖는 시간 간격들 동안 일어날 수 있다. 후자의 경우, 최소 및 최대 시간 간격들은 소프트웨어/펌웨어에서 프리셋될 수 있다.

도 1a 및 1b와 관련하여 상기 설명된 바와 같이, 공간적인 로컬리티(150)는 메모리 사이즈 "A₁"에 대해 결정되는 저장 시스템(140) 상의 어드레스들에 대한 참조들의 공간 밀도를 나타낸다. 하지만, 어드레스들에 대한 참조들의 다수의 공간 밀도들은, 다수의 상이한 메모리 사이즈들 "A₁", "A₂", "A₃",.. 각각에 대해 공간적인 로컬리티(150)의 컴포넌트들을 결정함으로써 저장 시스템(140)에 대해 모니터될 수 있다. 예를 들어, 공간적인 로컬리티(150)의 단범위, 중간 범위 및 장범위 컴포넌트들에 해당하는 다음의 부등식 A₁< A₂< A₃를 충족시키기 위해, 상이한 메모리 사이즈들이 선택될 수 있다(예를 들어, A₁ 값은 64KB 이고, A₂ 값은 128KB 이고, A₃ 값은 256KB 이며, 그리고 A₄ 값은 512KB 일 수 있다).

도 1c의 테이블 2는 저장 시스템(140)에 해당하는 공간적인 로컬리티 메트릭들(112 및 114)의 예들을 포함한다. 단범위의 공간적인 로컬리티 메트릭(112)은 공간적인 로컬리티(150)의 단범위 컴포넌트와 관련되며, 그리고 장범위의 공간적인 로컬리티 메트릭(114)은 공간적인 로컬리티(150)의 장범위 컴포넌트와 관련된다. 도 1a-1b와 관련된 상기 개시와 유사하게, 공간적인 로컬리티(150)의 단범위 컴포넌트는 메모리 사이즈 "A₁"에 대해 결정되며, 그리고 공간적인 로컬리티(150)의 장범위 컴포넌트는, 메모리 사이즈 "A₁" 보다 큰 메모리 사이즈 "A₂"(즉, A₁<A₂)에 대해 결정된다. 예를 들어, 공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 값들은 저장 시스템(140) 상의 어드레스들에 대한 "m"개의 참조들의 시퀀스들을 이용하여 결정될 수 있다. 도 1d는 저장 시스템(140)의 일부, 및 저장 시스템(140) 상의 어드레스 공간의 각각의 사이즈들 "A₁" 및 "A₂"에 대해 공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 값들을 결정하는 데에 이용되는 참조 동작에 해당하는 블록 오프셋 "X_n"을 도시한다. 도 1d에 도시된 바와 같이, 더 작은 사이즈 "A₁"을 갖는 어드레스 공간은

으로부터

까지 블록 오프셋 "X_n" 상에 중심을 두는 저장 시스템(140)의 일부에 걸쳐있으며, 그리고 더 큰 사이즈 "A₂"를 갖는 다른 어드레스 공간은

으로부터

까지 블록 오프셋 "X_n" 상에 중심을 두는 저장 시스템(140)의 다른 부분에 걸쳐있다. 이를 테면, 사이즈 "A₁"은 64KB 일 수 있고, 사이즈 "A₂"는 128 KB 일 수 있다. 수직 타원들(vertical ellipses)에 의해 표현되는 다른 공간적인 로컬리티 메트릭들은 각각 공간적인 로컬리티(150)의 다른 컴포넌트들에 해당할 수 있다. 공간적인 로컬리티의 이러한 다른 컴포넌트들은, 예를 들어 (메모리 사이즈 A<<"A₁"에 대해 결정되는) 극 단범위 컴포넌트(ultra-short-range component), (메모리 사이즈 "A₁"<A<"A₂"에 대해 결정되는) 중간 범위 컴포넌트(intermediate-range component), (메모리 사이즈 A>>"A₁₂"에 대해 결정되는) 극 장범위 컴포넌트(ultra-long-range component) 등일 수 있다.

공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 값들은 0(제로)으로 초기화된다. 이후, "m"개의 참조들의 시퀀스에 해당하는 어드레스들이 참조 동작에 해당하는 블록 오프셋 "X_n"으로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 세트가 이루어지며, 그리고 "m"개의 참조들의 시퀀스에 해당하는 어드레스들이 참조 동작에 해당하는 블록 오프셋 "X_n"으로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 다른 세트가 이루어진다. "m"개의 결정들의 세트 중에서 각각의 포지티브 결정에 대해, 공간적인 로컬리티(150)의 단범위 컴포넌트의 값은 1 만큼 증분될 수 있으며, 그리고 "m"개의 결정들의 다른 세트 중에서 각각의 포지티브 결정에 대해, 공간적인 로컬리티(150)의 장범위 컴포넌트의 값은 1 만큼 증분될 수 있다.

예를 들어, "m"개의 참조들의 시퀀스로부터의 "u"개의 참조들이 참조 동작에 해당하는 블록 오프셋 "X_n" 상에 중심을 두는 사이즈 "A₁"의 어드레스 공간 내의 어드레스들에 해당한다면, 공간적인 로컬리티(150)의 단범위 컴포넌트는 "u/A₁"의 값을 가지며(여기서, 0≤u≤m 이다); 그리고 "m"개의 참조들의 시퀀스로부터의 "v"개의 참조들이 참조 동작에 해당하는 블록 오프셋 "X_n" 상에 중심을 두는 사이즈 "A₂"의 어드레스 공간 내의 어드레스들에 해당한다면, 공간적인 로컬리티(150)의 장범위 컴포넌트는 "v/A₁"의 값을 갖는다(여기서, 0≤v≤m 이다). 주목할 사항으로서, 공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들은 1/(메모리 사이즈)의 치수를 가지며, 예를 들어 1/KB로 표현될 수 있다. 또한, 공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 값들을 각각의 메모리 사이즈들 "A₁" 및 "A₂"에 대한 각각의 카운트들 "u" 및 "v"의 각각의 비(ratio)로서 표현하게 되면, 단범위 및 장범위 공간적인 로컬리티(150)의 값들을 비교할 수 있게 한다.

다른 예에서, 공간적인 로컬리티(150)의 단범위 컴포넌트는 "u/m/A₁"의 값을 가지며(여기서, 0≤u/m≤1 이다), 그리고 공간적인 로컬리티(150)의 장범위 컴포넌트는 "v/m/A₂"의 값을 갖는다(여기서, 0≤v/m≤1 이다). 공간적인 로컬리티(150)의 각각의 단범위 및 장범위 컴포넌트들을 표현하기 위해 노멀라이즈된 카운트들 "u/m" 및 "v/m"을 이용하게 되면, 각각 단범위 및 장범위 컴포넌트들의 각 쌍들에 대해, 저장 시스템(140) 상의 어드레스들에 대한 참조들의 상이한 개수들, 예를 들어 "m₁", "m₂"..를 갖는 시퀀스들을 이용하여 결정된 공간적인 로컬리티의 장범위 컴포넌트들과 저장 시스템(140) 상의 어드레스들에 대한 참조들의 상이한 개수들, 예를 들어 "m₁", "m₂"..를 갖는 시퀀스들을 이용하여 결정된 공간적인 로컬리티의 단범위 컴포넌트들을 비교할 수 있게 한다.

일단 상기 설명한 바와 같이 공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 값들이 결정되면, 단범위의 공간적인 로컬리티 메트릭(112) 및 장범위의 공간적인 로컬리티 메트릭(114)의 인스턴트 값들이 각각 계산될 수 있다. 예를 들어, 단범위의 공간적인 로컬리티 메트릭(112)의 인스턴트 값은, 방정식 (1)에 따라, 공간적인 로컬리티(150)의 단범위 컴포넌트의 결정된 값과 단범위의 공간적인 로컬리티 메트릭의 이전에 계산된 값 간의 가중 평균으로서 계산된다. 현재의 상황에서, 방정식 (1)을 참조하면, S_A1(instant) 및 S_A1(previous)의 표기들은 단범위의 공간적인 로컬리티 메트릭(112)의 각각의 인스턴트 및 이전 값들을 나타내며, 그리고 s(A₁, m; n)의 표기는, 블록 오프셋 "X_n"에 해당하는 동작과 관련하여, 그리고 블록 오프셋 "X_n"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여 결정되는 공간적인 로컬리티(150)의 단범위 컴포넌트의 값을 나타낸다. 유사하게, 장범위의 공간적인 로컬리티 메트릭(114)의 인스턴트 값은, 공간적인 로컬리티(150)의 장범위 컴포넌트의 결정된 값과 장범위의 공간적인 로컬리티 메트릭의 이전에 계산된 값 간의 가중 평균으로서 다음과 같이 계산된다.

S_A2(instant) 및 S_A2(previous)의 표기들은 공간적인 로컬리티 메트릭(110)의 각각의 인스턴트 및 이전 값들을 나타낸다. s(A₂, m; n)의 표기는, 블록 오프셋 "X_n"에 해당하는 동작과 관련하여, 그리고 블록 오프셋 "X_n"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여 결정되는 저장 시스템(140) 상의 어드레스 공간의 사이즈 "A₂"에 대한 공간적인 로컬리티(150)의 인스턴트 값을 나타낸다.

공간적인 로컬리티(150)의 단범위 및 장범위 컴포넌트들의 이후의 값들은, 블록 오프셋 "X_n ₊₁"에 해당하는 다른 동작 및 다른 참조 동작 다음에 오는 "m"개의 동작들의 다른 시퀀스와 관련하여, 상기 설명한 바와 같이 결정될 수 있다. 이를 테면, "m"개의 참조들의 다른 시퀀스에 해당하는 어드레스들이 다른 참조 동작에 해당하는 블록 오프셋 "X_n ₊₁"로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 세트가 이루어지며, 그리고 "m"개의 참조들의 다른 시퀀스에 해당하는 어드레스들이 다른 참조 동작에 해당하는 블록 오프셋 "X_n ₊₁"로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 다른 세트가 이루어진다. "m"개의 결정들의 세트 중에서 각각의 포지티브 결정에 대해, 공간적인 로컬리티(150)의 단범위 컴포넌트의 값은 1 만큼 증분될 수 있으며, 그리고 "m"개의 결정들의 다른 세트 중에서 각각의 포지티브 결정에 대해, 공간적인 로컬리티(150)의 장범위 컴포넌트의 값은 1 만큼 증분될 수 있다. 또한, 단범위의 공간적인 로컬리티 메트릭(112)의 이후의 인스턴트 값 S_A1(instant)이, 단범위의 공간적인 로컬리티 메트릭(112)의 이전에 계산된 인스턴트 값을 단범위의 공간적인 로컬리티 메트릭(112)의 이전 값 S_A1(previous)으로서 이용하고, 블록 오프셋 "X_n ₊₁"에 해당하는 동작과 관련하여 결정되는 단범위의 공간적인 로컬리티(150)의 값 s(A₁, m; n+1)을 이용하여, 방정식 (1)에 따라 계산된다. 또한, 장범위의 공간적인 로컬리티 메트릭(114)의 이후의 인스턴트 값 S_A2(instant)이, 장범위의 공간적인 로컬리티 메트릭(114)의 이전에 계산된 인스턴트 값을 장범위의 공간적인 로컬리티 메트릭(114)의 이전 값 S_A2(previous)로서 이용하고, 블록 오프셋 "X_n ₊₁"에 해당하는 동작과 관련하여 결정되는 공간적인 로컬리티(150)의 장범위 컴포넌트의 값 s(A₂, m; n+1)을 이용하여, 방정식 (2)에 따라 계산된다.

도 1a-1d와 관련하여 상기 설명된 공간적인 로컬리티 메트릭들(110, 112 및 114)은, 전체적으로 저장 시스템(140)의 어드레스들에 대한, 또는 저장 시스템(140)의 특정 영역의 어드레스들에 대한 참조들의 공간적인 패턴들을 특징화(characterize)하는 데에 이용될 수 있다. 하지만, 저장 시스템에 대한 액세스들은 그 저장 시스템의 하나의 영역으로부터 다른 영역까지 달라지는(즉, 영역 마다 달라지는) 공간적인 로컬리티들을 나타낸다는 것이 실험적으로 관찰되었다. 이러한 관찰에 기초하여, 저장 시스템은 저장 시스템(140)의 부분들 또는 서브섹션들을 나타내는 다수의 (고정된 또는 가변 사이즈의) 영역들 R₁, R₂, ...,로 분할될 수 있으며, 이러한 영역들은 저장 시스템(140)의 각 영역에 대해 공간적인 로컬리티(150)를 결정하기 위해 개별적으로 모니터될 수 있다. 이러한 방식으로, 더 높은 공간적인 로컬리티를 갖는 영역들 내의 블록들이 우선순위(priority)를 가지며 캐싱될 수 있으며, 및/또는 더 낮은 공간적인 로컬리티를 갖는 영역들 내의 블록들 보다 더 긴 시간 기간들 동안 캐시 메모리 내에 유지될 수 있다.

도 1e의 테이블 3은 저장 시스템(140)의 각각의 영역들 R_i 및 R_j의 공간적인 로컬리티 메트릭들의 예들을 포함한다. 영역 R_i(120)의 공간적인 로컬리티 메트릭은 저장 시스템의 영역 R_i의 공간적인 로컬리티와 관련되며, 그리고 영역 R_j(130)의 공간적인 로컬리티 메트릭은 저장 시스템의 영역 R_j의 공간적인 로컬리티와 관련된다. 타원들에 의해 표현되는 다른 공간적인 로컬리티 메트릭들은, 저장 시스템(140)의 R₁, R₂, ,,,, R_N 영역들의 다른 영역들에 각각 해당한다. 영역들 R_i 및 R_j의 공간적인 로컬리티들은 도 1a-1b와 관련된 상기 개시와 유사하게 결정될 수 있다. 예를 들어, 영역 R_i의 공간적인 로컬리티의 값은 저장 시스템(140)의 영역 R_i 상의 어드레스들에 대한 "m"개의 참조들의 시퀀스를 이용하여 결정될 수 있다. 또한, 영역 R_j의 공간적인 로컬리티의 값은 저장 시스템(140)의 영역 R_j 상의 어드레스들에 대한 "m"개의 참조들의 다른 시퀀스를 이용하여 결정될 수 있다.

도 1f는 저장 시스템(140)의 일부, 및 이러한 저장 시스템(140)의 영역 R_i 상의 어드레스 공간의 사이즈 "A₁"에 대해 영역 R_i의 공간적인 로컬리티의 값을 결정하는 데에 이용되는 참조 동작에 해당하는 영역 R_i의 블록 오프셋 "X_a _,i"을 도시한다. 사이즈 "A₁"을 갖는 어드레스 공간은,

으로부터

까지 블록 오프셋 "X_a _,i" 상에 중심을 두는 저장 시스템(140)의 영역 R_i의 일부 위에 걸쳐 있다. 도 1f에는 또한, 저장 시스템(140)의 영역 R_j 상의 어드레스 공간의 사이즈 "A₁"에 대해 영역 R_j의 공간적인 로컬리티의 값을 결정하는 데에 이용되는 다른 참조 동작에 해당하는 영역 R_j의 블록 오프셋 "X_b _,j"가 도시되어 있다. 사이즈 "A₁"을 갖는 어드레스 공간은,

으로부터

까지 블록 오프셋 "X_b _,j" 상에 중심을 두는 저장 시스템(140)의 영역 R_i의 일부 위에 걸쳐 있다.

영역들 R_i 및 R_j의 공간적인 로컬리티들의 값들은 0(제로)으로 초기화될 수 있다. 이후, 저장 시스템(140)의 영역 R_i 상의 "m"개의 어드레스들의 시퀀스에 해당하는 어드레스들이 참조 동작에 해당하는 블록 오프셋 "X_a _,i"로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 세트가 이루어지며, 그리고 "m"개의 결정들의 세트 중에서 각각의 포지티브 결정에 대해, 영역 R_i의 공간적인 로컬리티의 값이 1 만큼 증분될 수 있다. 또한, 저장 시스템(140)의 영역 R_j 상의 "m"개의 어드레스들의 다른 시퀀스에 해당하는 어드레스들이 다른 참조 동작에 해당하는 블록 오프셋 "X_b _,j"로부터 거리

내에 있는 지에 대해 "m"개의 결정들의 다른 세트가 이루어지며, 그리고 "m"개의 결정들의 다른 세트 중에서 각각의 포지티브 결정에 대해, 영역 R_j의 공간적인 로컬리티의 값이 1 만큼 증분될 수 있다.

예를 들어, 저장 시스템(140)의 영역 R_i 상의 어드레스들에 대한 "m"개의 참조들의 시퀀스 중에서 "u"개의 참조들이 참조 동작에 해당하는 블록 오프셋 "X_a _,i" 상에 중심을 두는 사이즈 "A₁"의 어드레스 공간 내의 어드레스들에 해당한다면, 영역 R_i의 공간적인 로컬리티는 "u"의 정수 값을 가지며(여기서, 0≤u≤m 이다); 그리고 저장 시스템(140)의 영역 R_j 상의 어드레스들에 대한 "m"개의 참조들의 다른 시퀀스 중에서 "v"개의 참조들이 다른 참조 동작에 해당하는 블록 오프셋 "X_b _,j" 상에 중심을 두는 사이즈 "A₁"의 어드레스 공간 내의 어드레스들에 해당한다면, 영역 R_j의 공간적인 로컬리티는 "v"의 정수 값을 갖는다(여기서, 0≤v≤m 이다). 다른 예에서, 영역 R_i의 공간적인 로컬리티는 노멀라이즈되고, "u/m"의 부분 값을 가지며(여기서 0≤u/m≤1 이다), 그리고 영역 R_j의 공간적인 로컬리티는 노멀라이즈되고, "v/m"의 부분 값을 갖는다(여기서 0≤v/m≤1 이다). 영역들 R_i 및 R_j의 공간적인 로컬리티들에 대한 노멀라이즈된 값들의 이용은, 저장 시스템(140)의 영역들 R_i 및 R_j상의 어드레스들에 대한 참조들의 상이한 개수들, 예를 들어 "m₁", "m₂"..를 갖는 시퀀스들을 이용하여 결정된 영역들 R_i 및 R_j의 공간적인 로컬리티들을 비교할 수 있게 한다.

일단 상기 설명한 바와 같이 영역 R_i의 공간적인 로컬리티의 값이 결정되면, 영역 R_i(120)의 공간적인 로컬리티 메트릭의 인스턴트 값이, 영역 R_i의 공간적인 로컬리티의 결정된 값과 영역 R_i의 공간적인 로컬리티 메트릭의 이전에 계산된 값 사이의 가중 평균으로서 계산될 수 있다. 예를 들어, 영역 R_i(120)의 공간적인 로컬리티 메트릭의 인스턴트 값은,

으로서 계산될 수 있다.

및

의 표기들은 영역 R_i(120)의 공간적인 로컬리티 메트릭의 각각의 인스턴트 및 이전의 값들을 나타낸다.

의 표기는, 블록 오프셋 "X_a _,i"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여, 그리고 블록 오프셋 "X_a _,i"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_i 상의 어드레스 공간의 사이즈 "A₁"에 대해 결정되는 영역 R_i의 공간적인 로컬리티의 값을 나타낸다. 또한, 일단 상기 설명한 바와 같이 영역 R_j의 공간적인 로컬리티의 값이 결정되면, 영역 R_j(130)의 공간적인 로컬리티 메트릭의 인스턴트 값이, 영역 R_j의 공간적인 로컬리티의 결정된 값과 영역 R_j의 공간적인 로컬리티 메트릭의 이전에 계산된 값 사이의 가중 평균으로서 계산될 수 있다. 예를 들어, 영역 R_j(130)의 공간적인 로컬리티 메트릭의 인스턴트 값은,

로서 계산될 수 있다.

및

의 표기들은 영역 R_j(130)의 공간적인 로컬리티 메트릭의 각각의 인스턴트 및 이전의 값들을 나타낸다.

의 표기는, 블록 오프셋 "X_b _,j"에 해당하는 동작 다음에 오는 "m"개의 참조들의 다른 시퀀스를 이용하여, 그리고 블록 오프셋 "X_b _,j"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_j 상의 어드레스 공간의 사이즈 "A₁"에 대해 결정되는 영역 R_j의 공간적인 로컬리티의 값을 나타낸다.

하지만, 영역 R_i의 공간적인 로컬리티의 이후의 값들은, 상기 설명한 바와 같이, (도 1f에 도시되지 않은) 블록 오프셋 "X_a _+1,i"에 해당하는 다른 동작, 및 다른 참조 동작 다음에 오는 "m"개의 동작들의 다른 시퀀스와 관련하여 결정될 수 있다. 이를 테면, "m"개의 참조들의 다른 시퀀스에 해당하는 어드레스들이 다른 참조 동작에 해당하는 블록 오프셋 "X_a _+1,i"로부터 거리

내에 있는 지에 대해 "m"개의 결정들이 이루어지며, 이러한 "m"개의 결정들 중에서 각각의 포지티브 결정에 대해, 영역 R_i의 공간적인 로컬리티의 값이 1 만큼 증분될 수 있다. 또한, 영역 R_i(120)의 공간적인 로컬리티 메트릭의 이후의 인스턴트 값

은, 블록 오프셋 "X_a _+1,i"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_i 상의 어드레스 공간의 사이즈 "A1"에 대해 결정되는 영역 R_i의 공간적인 로컬리티의 값

을 이용하여, 그리고 영역 R_i(120)의 공간적인 로컬리티 메트릭의 이전에 계산된 인스턴트 값을 영역 R_i(120)의 공간적인 로컬리티 메트릭의 이전의 값

으로서 이용하여, 방정식 (3)에 따라 계산된다.

부가적으로, 영역 R_j의 공간적인 로컬리티의 이후의 값들은, 상기 설명한 바와 같이, (도 1f에 도시되지 않은) 블록 오프셋 "X_b _+1,i"에 해당하는 부가적인 동작, 및 부가적인 참조 동작 다음에 오는 "m"개의 동작들의 부가적인 시퀀스와 관련하여 결정될 수 있다. 이를 테면, "m"개의 참조들의 부가적인 시퀀스에 해당하는 어드레스들이 부가적인 참조 동작에 해당하는 블록 오프셋 "X_b _+1,j"로부터 거리

내에 있는 지에 대해 "m"개의 결정들이 이루어지며, 이러한 "m"개의 결정들 중에서 각각의 포지티브 결정에 대해, 영역 R_j의 공간적인 로컬리티의 값이 1 만큼 증분될 수 있다. 또한, 영역 R_j(130)의 공간적인 로컬리티 메트릭의 이후의 인스턴트 값

은, 블록 오프셋 "X_b _+1,j"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_j 상의 어드레스 공간의 사이즈 "A1"에 대해 결정되는 영역 R_j의 공간적인 로컬리티의 값

를 이용하여, 그리고 영역 R_j(130)의 공간적인 로컬리티 메트릭의 이전에 계산된 인스턴트 값을 영역 R_j(130)의 공간적인 로컬리티 메트릭의 이전의 값

로서 이용하여, 방정식 (4)에 따라 계산된다.

또한, 도 1c-1f와 관련하여 상기 설명된 공간적인 로컬리티 메트릭들(112, 114, 120 및 130)은, 이를 테면 도 1h와 관련하여 하기에서 설명되는 바와 같이 저장 시스템(140)의 다수의 영역들 각각에 대한 단범위 및 장범위의 공간적인 로컬리티 메트릭들을 계산하기 위해 결합될 수 있다. 또한, 다수의 캐싱 알고리즘들이, 도 4a-4b 및 도 5a-5b와 관련하여 하기에서 설명되는 저장 시스템(140)의 개별적인 영역들의 단범위 및 장범위 메트릭들의 인스턴트 값들에 따라 구현될 수 있다.

도 1g의 테이블 4는 저장 시스템(140)의 영역들 R_i 및 R_j의 단범위 및 장범위의 공간적인 로컬리티 메트릭들의 예들을 포함한다. 영역 R_i의 단범위의 공간적인 로컬리티 메트릭(122)은 영역 R_i의 공간적인 로컬리티의 단범위 컴포넌트와 관련되며, 그리고 영역 R_j의 단범위의 공간적인 로컬리티 메트릭(132)은 영역 R_j의 공간적인 로컬리티의 단범위 컴포넌트와 관련된다. 영역 R_i의 장범위의 공간적인 로컬리티 메트릭(124)은 영역 R_i의 공간적인 로컬리티의 장범위 컴포넌트와 관련되며, 그리고 영역 R_j의 장범위의 공간적인 로컬리티 메트릭(134)은 영역 R_j의 공간적인 로컬리티의 장범위 컴포넌트와 관련된다. 저장 시스템(140)의 소정의 영역에 대한 수직의 타원들은 테이블 2와 관련하여 상기 설명된 다른 공간적인 로컬리티 메트릭들에 해당한다. 공간적인 로컬리티(150)의 소정의 컴포넌트에 대한 수평의 타원들은 테이블 3과 관련하여 상기 설명된 저장 시스템(140)의 다른 영역들에 해당한다.

영역 R_i의 단범위의 공간적인 메트릭(122)은 방정식 (3)에 기초하여 계산될 수 있는 바, 여기서

및

의 표기들은 영역 R_i의 단범위의 공간적인 로컬리티 메트릭(122)의 각각의 인스턴트 및 이전의 값들을 나타내며; 그리고

의 표기는, 블록 오프셋 "X_a _,i"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여, 그리고 블록 오프셋 "X_a _,i"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_i 상의 어드레스 공간의 사이즈 "A₁"에 대해 결정되는 영역 R_i의 공간적인 로컬리티의 단범위 컴포넌트의 값을 나타낸다. (블록 오프셋 "X_a _,i"는 도 1h에 도시된다.) 또한, 영역 R_i의 공간적인 로컬리티의 단범위 컴포넌트는, 저장 시스템(140)의 영역 R_i에 적용되는 도 1c 및 1d와 관련된 상기 개시에 따라 결정될 수 있다. 영역 R_j의 단범위의 공간적인 로컬리티 메트릭(132)은 방정식 (4)에 기초하여 계산될 수 있는 바, 여기서

및

의 표기들은 영역 R_j의 단범위의 공간적인 로컬리티 메트릭(132)의 각각의 인스턴트 및 이전의 값들을 나타내며; 그리고

의 표기는, 블록 오프셋 "X_b _,j"에 해당하는 동작 다음에 오는 "m"개의 참조들의 다른 시퀀스를 이용하여, 그리고 블록 오프셋 "X_b _,j"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_j 상의 어드레스 공간의 사이즈 "A₁"에 대해 결정되는 영역 R_j의 공간적인 로컬리티의 단범위 컴포넌트의 값을 나타낸다. (블록 오프셋 "X_b _,j"는 도 1h에 도시된다.) 또한, 영역 R_j의 공간적인 로컬리티의 단범위 컴포넌트는, 저장 시스템(140)의 영역 R_j에 적용되는 도 1c 및 1d와 관련된 상기 개시에 따라 결정될 수 있다

영역 R_i의 장범위의 공간적인 메트릭(124)은,

로서 계산될 수 있다.

및

의 표기들은 영역 R_i의 장범위의 공간적인 로컬리티 메트릭(124)의 각각의 인스턴트 및 이전의 값들을 나타낸다.

의 표기는, 블록 오프셋 "X_a _,i"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여, 그리고 블록 오프셋 "X_a _,i"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_i 상의 어드레스 공간의 사이즈 "A₂"에 대해 결정되는 영역 R_i의 공간적인 로컬리티의 장범위 컴포넌트의 값을 나타낸다. 부가적으로, 영역 R_i의 공간적인 로컬리티의 장범위 컴포넌트는, 저장 시스템(140)의 영역 R_i에 적용되는 도 1c 및 1d와 관련된 상기 개시에 따라 결정될 수 있다. 영역 R_j의 장범위의 공간적인 로컬리티 메트릭(134)은,

로서 계산될 수 있다.

및

의 표기들은 영역 R_j의 장범위의 공간적인 로컬리티 메트릭(134)의 각각의 인스턴트 및 이전의 값들을 나타낸다.

의 표기는, 블록 오프셋 "X_b _,j"에 해당하는 동작 다음에 오는 "m"개의 참조들의 시퀀스를 이용하여, 그리고 블록 오프셋 "X_b _,j"에 해당하는 동작과 관련하여 저장 시스템(140)의 영역 R_j 상의 어드레스 공간의 사이즈 "A₂"에 대해 결정되는 영역 R_j의 공간적인 로컬리티의 장범위 컴포넌트의 값을 나타낸다. 부가적으로, 영역 R_j의 공간적인 로컬리티의 장범위 컴포넌트는, 저장 시스템(140)의 영역 R_j에 적용되는 도 1c 및 1d와 관련된 상기 개시에 따라 결정될 수 있다.

도 2a는 저장 시스템의 공간적인 로컬리티의 메트릭에 기초하여 저장 시스템(200)의 하나 이상의 디바이스들 상에 저장된 데이터를 캐싱하기 위한 시스템의 일 예를 도시한다. 이러한 공간적인 메트릭은 도 1a-1h와 관련하여 상기 설명된 하나 이상의 메트릭들(110, 112, 114, 120, 122, 124, 130, 132 및 134) 중 임의의 것일 수 있다. 저장 시스템(200)은 호스트 시스템(200/201') 외부에 있거나, 또는 또는 이러한 호스트 시스템의 일부일 수 있다. 몇몇 구현들에서, 저장 시스템(200)은 하나 이상의 저장 디바이스들(220), 캐시 디바이스(230) 및 제어기(210)를 포함하는 바, 제어기(210)는 다수의 통신 경로들(20, 40, 50 및 70)을 통해 하나 이상의 저장 디바이스들(220) 및 캐시 디바이스(230)와 통신가능하게 결합된다. 하나 이상의 저장 디바이스들(220)은 개별적인 저장 디바이스들(예를 들어, 하드 드라이브들) 뿐 아니라, 예를 들어 RAID, NAS 및 SAN과 같은, 저장 디바이스들의 결합들일 수 있다.

몇몇 구현들에서, 제어기(210)는 저장 시스템(200)의 외부에 배열될 수 있다. 또한, 제어기(210)는 통신 경로(10)를 통해 호스트 시스템(201/201')의 프로세서(202) 및/또는 메모리 시스템(206)과 인터페이스하도록 구성된다. 부가적인 통신 경로들(30 및 60)이 저장 시스템(200)과 메모리 시스템(206) (및/또는 프로세서(202)) 사이에 확립될 수 있다. 도 2b는 캐시 메모리(234')를 포함하는 캐시 디바이스(230')의 구현의 제 1 예를 도시한다. 이러한 제 1 구현에서, (캐시 히트들 및 캐시 미스들을 발생시키는 것을 포함하는) 저장 시스템(200)의 캐싱 기능은 제어기(210)에 의해 수행된다. 도 2c는 캐시 메모리(234") 및 디바이스 제어기(238)를 포함하는 캐시 디바이스(230")의 구현의 제 2 예를 도시한다. 이러한 제 2 구현에서, (캐시 히트들 및 캐시 미스들을 발생시키는 것을 포함하는) 저장 시스템(200)의 캐싱 기능은 캐시 디바이스(230")의 디바이스 제어기(238)에 의해 수행된다.

제어기(210)는 주문형 반도체(Application Specific Integrated Circuit, ASIC), 전자 회로, (공유되는, 또는 전용의, 또는 그룹) 프로세서 및/또는 하나 이상의 소프트웨어 또는 펌웨어 프로그램들을 실행하는 (공유되는, 전용의, 또는 그룹) 메모리, 결합 논리 회로(combinatorial logic circuit), 및/또는 설명되는 기능을 제공하는 기타 적절한 컴포넌트들의 일부이거나, 또는 이들을 포함할 수 있다. 예를 들어, 제어기(210)는 저장 시스템(200)의 공간적인 로컬리티 메트릭을 발생시키고 업데이트하도록 구성된다.

제어기(210)는 저장 시스템(200)과 관련된 어드레스 참조들 중 특정된 양(specified quantity)인 "m"개 어드레스 참조들을, 메모리 시스템(206)으로부터 (통신 경로(10)를 통해) 수신할 수 있다. 예를 들어, 어드레스 참조들 중에서 "m"개의 양은 프로그램으로(programmatically) 특정될 수 있다. 또한, "m"개의 양은 저장 디바이스들(220)의 타입, 호스트 시스템(201/201')에 의해 실행되는 애플리케이션의 타입 등에 기초하여 변경될 수 있다. 예를 들어, "m"개의 양은 저장 시스템(200) 상의 어드레스들에 대한 15개의 참조들과 같게 설정될 수 있다. "m" 값들의 다른 예들은 5, 10, 15, 20, 30, 50, 100 등이 있다.

또한, 제어기(210)는, 저장 시스템(200) 상에서의 공간적인 로컬리티를, 연속적인 어드레스 참조들의 제 1 어드레스 참조의 블록 오프셋 "X_n"으로부터 제 1 거리 내에 있는 연속적인 어드레스 참조들 중에서 수신되는 특정된 양인 "m"개의 어드레스 참조들의 부분(fraction)으로서 결정하도록 구성된다. 저장 시스템(200) 상에서의 공간적인 로컬리티의 결정은 도 2a-2h 중 임의의 것과 관련하여 본 명세서에서 상기 설명된 바와 같이 수행될 수 있다. 또한, 저장 시스템(200) 상에서의 공간적인 로컬리티를 결정하는 것의 일부로서, 제어기(210)는 공간적인 분포의 이전의 결정과 공간적인 분포의 현재의 결정 사이에서 임의의 양을 생략하도록 구성될 수 있다. 주기적인 인공물들에 의해 도입되는 조직적인 에러들(systematic errors)은 이러한 랜덤한 샘플링(random sampling)을 수행함으로써 감소될 수 있다. 따라서, 저장 시스템(200) 상에서의 공간적인 로컬리티의 정확성이 증가될 수 있다. 주목할 사항으로서, 난수 발생은 (예를 들어, 미리 정해진 씨드(seed) 및 모듈로 오퍼레이터(modulo operator)에 기초하는) 의사 난수 발생(pseudorandom number generation), 또는 (예를 들어, 우주 배경 방사(cosmic background radiation)를 검출하기 위한 센서와 같은, 랜덤한 입력의 소스에 기초하는) TRNG(true random number generation) 중에서 어느 하나일 수 있다.

또한, 제어기(210)는 결정된 공간적인 로컬리티와 이전에 결정된 공간적인 로컬리티를 저장 시스템(200)의 공간적인 로컬리티 메트릭으로 결합하도록 구성된다. 저장 시스템(200)의 공간적인 로컬리티 메트릭들의 많은 예들이 도 2a-2h와 관련하여 상기에서 설명되었다. 예를 들어, 특정의 메모리 사이즈에 해당하는 공간적인 로컬리티 메트릭은, 도 2a 및 2b와 관련하여 상기 설명된 바와 같이, 저장 시스템(200)에 대해 전체적으로 계산될 수 있다. 다른 예로서, 작은 메모리 사이즈 및 큰 메모리 사이즈 각각에 해당하는 단범위 및 장범위의 공간적인 로컬리티 메트릭들은, 도 2c 및 2d와 관련하여 상기 설명된 바와 같이, 저장 시스템(200)에 대해 전체적으로 계산될 수 있다. 또 다른 예로서, 특정의 메모리 사이즈에 해당하는 공간적인 로컬리티 메트릭들은, 도 2e 및 2f와 관련하여 상기 설명된 바와 같이, 저장 시스템(200)의 각각의 영역들에 대해 계산될 수 있다. 또한, 작은 메모리 사이즈 및 큰 메모리 사이즈 각각에 해당하는 단범위 및 장범위의 공간적인 로컬리티 메트릭들은, 도 2g 및 2h와 관련하여 상기 설명된 바와 같이, 저장 시스템(200)의 다수의 영역들 각각에 대해 계산될 수 있다. 방정식 1 내지 6에 따르면, 상기 언급한 공간적인 로컬리티 메트릭들 각각은 결정된 공간적인 로컬리티와 이전에 결정된 공간적인 로컬리티 메트릭의 가중 합을 포함한다.

제어기(210)는 계산된 공간적인 로컬리티 메트릭들 중 하나 이상을 이용하거나, 또는 (통신 경로(70)를 통해) 캐시 디바이스(230)에 하나 이상의 저장 디바이스들(220)로부터의 데이터를 캐싱하기 위해 (통신 경로(50)를 통해) 디바이스 제어기(224)에 공간적인 로컬리티 메트릭들 중 하나 이상을 제공할 수 있다. 공간적인 로컬리티 메트릭의 현재 값에 기초하는 다양한 캐싱 기술들이 도 5a-5b 및 도 6a-6b와 관련하여 하기에서 설명된다.

제어기(210)는 또한, 메모리 시스템(206)으로부터 (통신 경로(10)를 통해) 저장 시스템(200)의 어드레스에 대한 참조를 수신하도록 구성된다. 수신되는 어드레스 참조는 저장 시스템(200) 상의 소정의 블록 오프셋 "X"에 저장되는 데이터에 해당할 수 있다. 제어기(210)는 수신된 참조를 (통신 경로(20)를 통해) 캐시 디바이스(230)에 전달(relay)할 수 있다. 참조되는 데이터가 캐시 디바이스(230)에 캐시되어 있다면, 캐시 히트가 발생될 수 있으며, 참조되는 데이터는 캐시 디바이스(230)로부터 (통신 경로(30)를 통해) 메모리 시스템(206)에 제공된다. 몇몇 구현들에서, 통신 경로(30)는 반대 방향(reverse-direction)으로 가로지르는(traversed) 경로들(20 및 10)에 대응할 수 있다. 하지만, 참조되는 데이터가 캐시 디바이스(230) 내에 캐시되어 있지 않다면, 캐시 미스가 발생될 수 있으며, 그리고 참조되는 데이터는 하나 이상의 저장 디바이스들(220)로부터 (통신 경로(60)를 통해) 메모리 시스템(206)에 제공된다. 몇몇 구현들에서, 통신 경로(60)는 반대 방향으로 가로지르는 경로들(50 및 10)에 대응한다. 제어기(210)는 또한, (통신 경로(40)를 통해) 캐시 디바이스(230) 내에서의 수신된 어드레스 참조에 대한 캐시 미스를 검출하도록 구성된다. 몇몇 구현들에서, 통신 경로(40)는 반대 방향으로 가로지르는 경로(20)에 대응한다. 캐시 미스의 검출에 응답하여, 제어기(210)는 또한, 도 5a-5b 및 6a-6b와 관련하여 하기에서 설명되는 바와 같이, (통신 경로(70)를 통한) 공간적인 로컬리티 메트릭의 현재 값에 따라 캐시 디바이스(230)에 캐싱하기 위해, (통신 경로(50)를 통해) 저장 시스템(200)의 소정의 블록 오프셋 "X"과 관련된 데이터를 선택하도록 구성된다. 몇몇 구현들에서, 통신 경로(70)는 반대 방향으로 가로지르는 경로들(50 및 40)에 대응한다.

도 3은 저장 시스템의 공간적인 로컬리티 메트릭을 발생시키고 업데이트하기 위한 방법(300)의 일 예를 도시한다. 방법(300)은, 도 2a와 관련하여 상기 설명된 제어기(210), 캐시 디바이스(230) 및 프로세서(202) 중에서 하나 이상을 포함하는 데이터 처리 장치에 의해 수행될 수 있다.

360에서, 캐시 메모리에 캐싱될 저장 시스템으로부터의 데이터를 결정하기 위해, 업데이트된 공간적인 로컬리티 메트릭이 출력된다. 이러한 공간적인 로컬리티 메트릭은 하기에서 설명되는 적어도 양상들(310-350)을 주기적으로 수행하기 위해 데이터 처리 장치에 의해 업데이트된다. 360에 따라 업데이트될 수 있는 공간적인 로컬리티 메트릭들의 예들은 도 2a-2h와 관련하여 상기 설명되었다.

310에서, 저장 시스템 상의 어드레스 참조가 수신된다. 320에서, 수신된 어드레스 참조가 특정된 양의 어드레스 참조들을 갖는 어드레스 참조들의 시퀀스 내의 최초(initial) 어드레스인 것으로 결정되는 것에 응답하여, 그 시퀀스 내의 최초 어드레스의 블록 오프셋이 기록된다. 시퀀스 내의 어드레스 참조들의 특정된 양은 "m"으로 표시되며, 이를 테면 m=15로 프리셋될 수 있다. 하지만, 시퀀스 내의 어드레스 참조들의 특정된 양 "m"은 소프트웨어/펌웨어에서 변경될 수 있다.

330에서, 수신된 어드레스 참조가 시퀀스 내의 이후의 어드레스 참조인 것으로 결정되는 것에 응답하여, 이후의 어드레스 참조가 그 시퀀스 내의 최초 어드레스의 기록된 블록 오프셋으로부터 특정된 거리 내에 있는 지의 여부를 결정한다. 어드레스 공간 내의 특정된 거리는 "A₁"으로 표시되며, A₁=64KB, 128KB, 256KB 등일 수 있다. 결정의 결과가 포지티브하다면(즉, 이후의 어드레스 참조가 시퀀스 내의 최초 어드레스의 기록된 블록 오프셋으로부터 특정된 거리 "A₁" 내에 있다면), 그 시퀀스 내의 최초 어드레스의 기록된 블록 오프셋의 특정된 거리 "A₁" 내의 어드레스 참조들의 카운트가 증분된다. 이러한 카운트는 "k"로 표시되며, 정수값 0≤k≤m 을 가질 수 있다.

340에서, 시퀀스 내의 어드레스 참조들의 특정된 양 "m" 및 카운트 "k"에 기초하여, 저장 시스템 상의 공간적인 로컬리티를 얻는다. 몇몇 실시예들에서, 이러한 공간적인 로컬리티를 얻는 것은, 시퀀스 내의 최초 어드레스의 기록된 블록 오프셋으로부터 특정된 거리 내에 있는 그 시퀀스 내의 어드레스 참조들의 카운트의 프랙션(fraction) "k/m"을 결정하는 것을 포함한다. 결정된 프랙션은 0≤k/m≤1 의 부등식을 만족시킨다. 이러한 방식으로 노멀라이즈되는 공간적인 로컬리티의 값들은, 참조들의 상이한 양들 "m₁", "m₂", ..을 갖는 어드레스 참조들의 각각의 시퀀스들에 기초하여 결정되는 공간적인 로컬리티들 "k₁/m₁", "k₂/m₂",...를 비교하는 데에 이용될 수 있다. 예를 들어, 4의 제 1 공간적인 로컬리티가, 소정의 저장 시스템 상의 어드레스들에 대해 12개의 참조들을 갖는 제 1 시퀀스를 이용함으로써 그 소정의 저장 시스템에 대해 결정된다. 이후, 6의 제 2 공간적인 로컬리티가, 소정의 저장 시스템 상의 어드레스들에 대해 30개의 참조들을 갖는 제 2 시퀀스를 이용함으로써 그 소정의 저장 시스템에 대해 결정된다. 그 이후, 3의 제 3 공간적인 로컬리티가, 소정의 저장 시스템 상의 어드레스들에 대해 6개의 참조들을 갖는 제 3 시퀀스를 이용함으로써 그 소정의 저장 시스템에 대해 결정된다. 제 1, 2 및 3 공간적인 로컬리티들의 원래의 값(raw value)들을 비교하기가 더 어렵긴 하지만, 노멀라이즈된 값들은, 3/6=0.50의 제 3 공간적인 로컬리티가 4/12=0.33의 제 1 공간적인 로컬리티 보다 더 크고, 후자(즉, 4/12=0.33의 제 1 공간적인 로컬리티)가 6/30=0.20의 제 2 공간적인 로컬리티 보다 더 큰 것으로 용이하게 결정하는 데에 이용될 수 있다.

또한, 수신된 어드레스 참조가, "m"개의 어드레스 참조들의 이전의 시퀀스의 마지막(m번째) 어드레스 참조와 "m" 개의 어드레스 참조들의 이후의 시퀀스 내의 처음(첫 번째) 어드레스 참조 사이의 임의의 양인 "r"개의 어드레스 참조들 중 하나인 것으로 결정되는 것에 응답하여, 수신된 어드레스 참조는 공간적인 로컬리티를 얻는 것으로부터 생략될 수 있다. 난수 "r"은 부등식 0≤r≤N 을 만족시키도록 선택될 수 있는 바, 여기서 N은 공간적인 로컬리티를 얻는 것으로부터 생략될 수 있는 최대 개수의 동작들로서 소프트웨어/펌웨어에서 프리셋될 수 있다. 예를 들어, m=20 이고, N=10 이면, 저장 시스템 상의 어드레스들에 대한 첫 번째 20개의 참조들은 공간적인 로컬리티를 얻는 데에 이용되고, 다음의 4개의 참조들(21-23)은 공간적인 로컬리티를 얻는 데에 이용되지 않고, 다음의 20개의 참조들(24-43)은 이용되고, 다음의 7개의 참조들(44-50)은 이용되지 않고, 다음의 20개의 참조들(51-70)은 이용되고, 다음의 10개의 참조들(71-80)은 이용되지 않고, 다음의 20개의 참조들(81-100)은 이용되고, 다음의 2개의 참조들(101-102)은 이용되지 않고, 다음의 20개의 참조들(103-122)은 이용되고, 제로 참조들(zero references)은 스킵되고, 다음의 20개의 참조들(123-142)은 이용되며, 다음의 7개의 참조들(143-149)은 이용되지 않으며, 기타 등등이다. 이러한 예에서, (0과 10 사이의) 난수들 4, 7, 10, 2, 0, 7...의 동작들은 저장 시스템 상의 공간적인 로컬리티의 연속적인 결정들 사이에서 생략되었다. 상기 설명한 랜덤한 샘플링은, 주기적으로 발생되는 인공물들의 기여를 줄임으로써, 공간적인 로컬리티 메트릭 계산의 정확성을 증가시키는 데에 기여한다.

350에서, 얻어진 공간적인 로컬리티를 이전에 얻어진 공간적인 로컬리티와 공간적인 로컬리티 메트릭으로 결합시킴으로써, 저장 시스템의 공간적인 로컬리티 메트릭이 적어도 부분적으로 업데이트된다. 이렇게 결합시키는 것은, 예를 들어 방정식 1-6 중 어느 하나 또는 그 이상에 따라, 얻어진 공간적인 로컬리티와 이전에 얻어진 공간적인 로컬리티의 가중 합을 발생시키는 것을 포함한다. 이러한 가중치(weight)는 β로 표시되며(여기서, 0<β≤1), 그리고 공간적인 로컬리티 메트릭의 이력 값들(historical values)에 의해 공간적인 로컬리티 메트릭의 인스턴트 값에 대한 바이어스(bias)를 나타내도록 선택될 수 있다. 예를 들어, 0(제로)에 가까운 가중치 β는, 공간적인 로컬리티 메트릭이 이력 값들에 의해 지배(dominate)되며, 그리고 인스턴트 값은 공간적인 로컬리티 메트릭에 작은 기여를 가짐을 나타낸다. 다른 예에서, 1에 가까운 가중치 β는, 공간적인 로컬리티 메트릭의 인스턴트 값이 공간적인 로컬리티 메트릭에 대해 지배적인 기여를 하며, 이력 값들은 공간적인 로컬리티 메트릭에 작은 기여를 함을 나타낸다. 실제로, 가중치 β =1 일 때, 이력 값들은 공간적인 로컬리티 메트릭의 값을 계산하는 데에 어떠한 역할도 하지 않는다. 후자의 경우, 저장 시스템의 공간적인 로컬리티 메트릭은 저장 시스템의 공간적인 로컬리티와 동일하다.

370에서, 수신된 어드레스 참조에 대한 캐시 미스가 검출된다. 이러한 수신된 어드레스 참조는 저장 시스템 상의 소정의 블록 오프셋에 해당한다. 380에서, 캐시 미스의 검출에 응답하여, 그리고 공간적인 로컬리티 메트릭의 현재 값에 따라, 소정의 블록 오프셋과 관련된 데이터가 선택적으로 결정되며, 선택적으로 결정된 데이터는 캐시 메모리에 캐싱될 수 있다.

도 4a는 저장 시스템의 공간적인 로컬리티 메트릭의 현재 값에 따라 그 저장 시스템 상에 저장된 데이터를 캐싱하기 위한 방법(400)의 일 예의 양상들을 도시한다. 방법(400)은, 370에서, 캐시 미스를 검출하는 것에 응답하여, 데이터를 캐싱하기 위해 방법(300)과 결합될 수 있다. 방법(400)은 또한, 도 2a와 관련하여 상기 설명된 제어기(210), 캐시 디바이스(230) 및 프로세서(202) 중에서 하나 이상을 포함하는 데이터 처리 장치에 의해 수행될 수 있다. 또한, 방법(400)은 도 2a-2h와 관련하여 상기 설명된 공간적인 메트릭들 중 임의의 것에 적용될 수 있다.

370에서, 저장 시스템의 어드레스에 대한 수신된 참조에 대한 캐시 미스가 검출된다. 도 4b는 캐시 미스에 해당하는 저장 시스템(240) 상의 어드레스와 관련된 블록 오프셋 "X"을 도시한다.

캐시 미스를 검출하는 것에 응답하여, 410에서, 공간적인 로컬리티 메트릭의 현재 값이 제 1 값과 제 1 값 보다 큰 제 2 값 사이라는 공간적인 로컬리티 메트릭의 평가가 이루어진다. 공간적인 로컬리티 메트릭의 이러한 값의 범위는 특정의 간격, 예를 들어 공간적인 로컬리티 메트릭의 이력 값들의 25 퍼센트(percentile)와 75 퍼센트 사이의 범위에 해당하도록 소프트웨어/하드웨어에서 특정될 수 있다. 다른 예에서, 공간적인 로컬리티 값들의 특정 간격은 이력 값들의 5 퍼센트와 95 퍼센트 사이로 특정될 수 있다. 몇몇 실시예들에서, 이력 값들은 저장 시스템에 의해 유지될 수 있다. 몇몇 구현들에서, 이력 값들은 저장 시스템에 대해 외부적으로 유지될 수 있는 바, 예를 들어 호스트 시스템(201/201')에 의해 유지될 수 있다. 공간적인 로컬리티의 N(예를 들어, N=250)개의 세트의 이력 측정들로부터 k번째 퍼센트(예를 들어, k=25)를 계산하기 위해, N개의 이력 측정들은 먼저 가장 작은 값으로부터 가장 큰 값으로 분류(sort)된다. k번째 퍼센트는 N개의 측정들의 분류된 세트의 k*N/100 측정의 값에 해당한다. 이 경우, 공간적인 로컬리티 메트릭의 이력 값들의 25 퍼센트는 200개의 공간적인 로컬리티 측정들의 분류된 세트 내의 50번째 공간적인 로컬리티 측정의 값(25*200/100)에 해당한다. 유사하게, 공간적인 로컬리티 메트릭의 이력 값들의 5 퍼센트는 200개의 공간적인 로컬리티 측정들의 분류된 세트 내의 10번째 공간적인 로컬리티 측정의 값(5*200/100)에 해당한다. 임의의 다른 퍼센트 값들은 이러한 방식으로 계산될 수 있으며, 예를 들어 410에서의 평가와 관련하여 설명된 특정의 간격의 하위 및 상위 경계(bound)들을 설정하는 데에 이용될 수 있다.

420에서, 캐시 메모리에 캐싱하기 위한 데이터가, 410에서의 평가의 결과에 응답하여, 소정의 블록 오프셋 "X" 부근의 인접하는 메모리로부터 특정된 양의 데이터를 포함하도록 선택적으로 결정된다. 도 4b에서, 특정된 양의 데이터는 "Δ"로 표시된다. 몇몇 구현들에서, 특정된 양의 데이터 "Δ"는, 저장 시스템(240) 상의 공간적인 로컬리티를 결정하는 데에 이용되는 메모리 사이즈 "A₁"에 관련될 수 있다. 이를 테면, 특정된 양의 데이터 "Δ"는 메모리 사이즈 "A₁"의 배수이거나, 같거나, 또는 일부분일 수 있다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하며, 그리고 이력 값들의 5-95 사이의 퍼센트의 공간적인 로컬리티 메트릭의 인스턴트 값을 평가하는 것에 응답하여(여기서, 공간적인 로컬리티 메트릭은 메모리 사이즈 A₁=64KB에 기초하여 결정됨), 캐싱될 데이터의 양이 Δ=A₁=64KB가 되도록 선택적으로 결정되며, 캐싱되는 데이터는 메모리 간격(X-32KB, X+32KB)으로부터 선택된다.

캐시 미스를 검출하는 것에 응답하여, 430에서, 공간적인 로컬리티 메트릭의 현재 값이 제 2 값 보다 큰 것으로 공간적인 로컬리티 메트릭의 평가가 이루어진다. 공간적인 로컬리티 메트릭의 이러한 큰 인스턴트 값은, (캐시 미스에 해당하는 저장 시스템(240) 상의 어드레스와 관련된) 블럭 오프셋 "X"에 인접하는 어드레스들이 가까운 미래에 (즉, 이후의 "m"개의 판독/기록 동작들 동안) 참조될 가능성을 나타낸다.

440에서, 430에서의 평가의 결과에 응답하여, 캐시 메모리에 캐싱하기 위한 데이터가 소정의 블록 오프셋 "X" 부근의 인접하는 메모리로부터 특정된 양의 데이터 "Δ" 이상을 포함하도록 선택적으로 결정된다. 몇몇 구현들에서, 공간적인 로컬리티 메트릭의 현재 값이 제 2 값 보다 큰 경우, 캐시 메모리에 캐싱하기 위해 선택적으로 결정된 데이터는 (도 4b에 도시된) 소정의 블록 오프셋 "X" 부근의 인접하는 메모리로부터 특정된 양의 데이터 "Δ"의 두배를 포함한다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하면, 그리고 이력 값들의 95 퍼센트 보다 큰 공간적인 로컬리티 메트릭의 인스턴트 값을 평가하는 것에 응답하여(여기서, 특정된 양의 데이터 Δ=64KB 이다), 캐싱될 데이터의 양은 2Δ=128KB가 되도록 선택적으로 결정되고, 캐싱되는 데이터는 메모리 간격(X-64KB, X+64KB)으로부터 선택된다.

캐시 미스를 검출하는 것에 응답하여, 450에서, 공간적인 로컬리티 메트릭의 현재 값이 제 1 값 보다 작은 것으로 공간적인 로컬리티 메트릭의 평가가 이루어진다. 공간적인 로컬리티 메트릭의 이러한 작은 인스턴트 값은, (캐시 미스에 해당하는 저장 시스템(240) 상의 어드레스와 관련된) 블럭 오프셋 "X"에 인접하는 어드레스들이 가까운 미래에 (즉, 이후의 "m"개의 판독/기록 동작들 동안) 참조될 가능성을 나타낸다.

460에서, 450에서의 평가의 결과에 응답하여, 캐시 메모리에 캐싱하기 위한 데이터가 소정의 블록 오프셋 "X" 부근의 인접하는 메모리로부터 특정된 양의 데이터 "Δ" 미만을 포함하도록 선택적으로 결정된다. 몇몇 구현들에서, 공간적인 로컬리티 메트릭의 현재 값이 제 1 값 보다 작은 경우, 캐시 메모리에 캐싱하기 위해 선택적으로 결정된 데이터는 0 이다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하면, 그리고 이력 값들의 5 퍼센트 보다 작은 큰 공간적인 로컬리티 메트릭의 인스턴트 값을 평가하는 것에 응답하여(여기서, 특정된 양의 데이터 Δ=64KB 이다), 캐싱될 데이터의 양은 0(제로)이 되도록 선택적으로 결정된다.

도 5a는 저장 시스템의 단범위 및 장범위 로컬리티 메트릭들의 현재 값들에 따라 그 저장 시스템 상에 저장된 데이터를 캐싱하기 위한 다른 방법(500)의 일 예의 양상들을 도시한다. 방법(500)은 370에서 캐시 미스를 검출하는 것에 응답하여, 데이터를 캐싱하기 위해 방법(300)과 결합될 수 있다. 방법(500) 또한, 도 2a와 관련하여 상기 설명된 제어기(210), 캐시 디바이스(230) 및 프로세서(202) 중에서 하나 이상을 포함하는 데이터 처리 장치에 의해 수행될 수 있다.

도 2c-2d 및 도 2g-2h와 관련하여 상기 설명한 바와 같이, 공간적인 로컬리티의 단범위 컴포넌트는, 특정되는 메모리 사이즈 "A₁"에 의해 분할되는 시퀀스 내의 최초 어드레스의 블록 오프셋 "X_n" 상에 중심을 두는 특정된 메모리 사이즈 "A₁"의 간격 내에 있는 "m"개의 어드레스 참조들의 시퀀스 내의 어드레스 참조들의 카운트 "k₁"의 프랙션 "k₁/m"으로서 결정될 수 있다. 공간적인 로컬리티의 장범위 컴포넌트는, 특정되는 다른 메모리 사이즈 "A₂"(여기서, A₁<A₂ 이다)에 의해 분할되는 시퀀스 내의 최초 어드레스의 블록 오프셋 "X_n" 상에 중심을 두는 특정되는 다른 메모리 사이즈 "A₂"의 다른 간격 내에 있는 "m"개의 어드레스 참조들의 시퀀스 내의 어드레스 참조들의 다른 카운트 "k₂"의 다른 프랙션 "k₂/m"으로서 결정될 수 있다.

몇몇 구현들에서, 공간적인 로컬리티의 단범위 컴포넌트는, 시퀀스 내의 최초 어드레스의 블록 오프셋 "X_n" 상에 중심을 두는 특정된 메모리 사이즈 "A₁"의 간격 내에 있는 "m"개의 어드레스 참조들의 시퀀스 내의 어드레스 참조들의 카운트 "k₁"로서 결정될 수 있는 한편, 공간적인 로컬리티의 장범위 컴포넌트는, 시퀀스 내의 최초 어드레스의 블록 오프셋 "X_n" 상에 중심을 두는 특정된 다른 메모리 사이즈 "A₂"의 다른 간격 내에 있지만, 시퀀스 내의 최초 어드레스의 블록 오프셋 "X_n" 상에 중심을 두는 특정된 메모리 사이즈 "A₁"의 다른 간격 내에는 없는 "m"개의 어드레스 참조들의 시퀀스 내의 어드레스 참조들의 다른 카운트 "k₂"로서 결정될 수 있다.

또한, 단범위의 공간적인 로컬리티 메트릭(S_A1)은 방정식들 1, 3 또는 4를 통해 결정되는 공간적인 로컬리티의 단범위 컴포넌트 s(A₁, m; n)과 관련되며, 장범위의 공간적인 로컬리티 메트릭(S_A2)은 방정식들 2, 5 또는 6을 통해 결정되는 공간적인 로컬리티의 장범위 컴포넌트 s(A₂, m; n)과 관련된다.

도 5a로 돌아가면, 370에서, 저장 시스템의 어드레스에 대해 수신되는 참조에 대한 캐시 미스가 검출된다. 도 5b는 캐시 미스에 해당하는 저장 시스템(240) 상의 어드레스와 관련된 블록 오프셋 "X"을 도시한다. 또한, 도 5b는 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈(A₁)의 간격 및 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈(A₂)의 다른 간격을 도시하며, 메모리 사이즈들(A₁및 A₂)은 저장 시스템(240)의 각각의 단범위 및 장범위의 공간적인 로컬리티 메트릭들에 해당한다.

캐시 미스를 검출하는 것에 응답하여, 510에서, 단범위의 공간적인 로컬리티 메트릭의 현재 값이 장범위의 공간적인 로컬리티 메트릭의 현재 값 보다 큰 것으로, 단범위 및 장범위의 공간적인 로컬리티 메트릭들의 평가가 이루어진다. 단범위의 공간적인 로컬리티 메트릭의 큰 인스턴트 값은 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈 "A₁"의 간격 내의 어드레스들에 대한 참조들의 큰 공간 밀도를 나타내며, 장범위의 공간적인 로컬리티 메트릭의 작은 인스턴트 값은 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈 "A₂"의 다른 간격 내의 어드레스들에 대한 참조들의 작은 공간 밀도를 나타낸다. 메모리 사이즈(A₁)의 간격 및 메모리 사이즈(A₂)의 다른 간격은 공통의 중심(X)을 갖기 때문에, 평가(510)의 결과는 필연적으로, 에지 부분들

및

내의 어드레스들에 대한 참조들의 개수가 메모리 사이즈(A₂)의 중심 부분

내의 어드레스들에 대한 참조들의 개수 보다 작을 것으로 기대됨을 의미한다.

결과적으로, 520에서, 캐시 메모리에 캐싱하기 위한 데이터는 블록 오프셋 "X"에 중심을 두는 메모리 사이즈(A₁)를 갖는 간격 내의 어드레스들을 갖도록 선택된다. 도 4a 및 4b와 관련하여 상기 설명한 바와 같이, 프리페치되는 데이터의 양은 메트릭 결정에 이용되는 사이즈(예를 들어, A₁)와 같을 수 있지만, 반드시 그럴 필요는 없다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하면, 그리고 단범위의 공간적인 로컬리티 메트릭의 인스턴트 값이 장범위의 공간적인 로컬리티 메트릭의 인스턴트 값 보다 큰 것으로 평가되는 것에 응답하여, 그리고 또한 단범위의 공간적인 로컬리티 메트릭에 해당하는 메모리 사이즈 A₁=64KB 일 때, 캐싱될 데이터는 메모리 간격(X-32KB, X+32KB)으로부터 선택된다.

또한, 캐시 미스를 검출하는 것에 응답하여, 530에서, 단범위의 공간적인 로컬리티 메트릭의 현재 값이 장범위의 공간적인 로컬리티의 현재 값과 실질적으로 같은 것으로, 단범위 및 장범위의 공간적인 로컬리티 메트릭들의 평가가 이루어진다. 메트릭 값들은, 이러한 두개의 메트릭 값들 간의 차이들이 메트릭의 측정으로부터 비롯되는 노이즈(예를 들어, 측정 반복가능성(measurement repeatability) 등에 인한 노이즈) 보다 작거나 같을 때에, 실질적으로 같은 것으로 고려된다. 단범위 및 장범위의 공간적인 로컬리티 메트릭들의 인스턴트 값들이 상당히 같은 것(substantial equality)은, 블록 오프셋(X) 상에 중심을 두는 메모리 사이즈(A₁)의 간격 내의 그리고 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈(A₂)의 다른 간격 내의 어드레스들에 대한 참조들의 실질적으로 같은 공간 밀도들을 나타낸다. 메모리 사이즈(A₁)의 간격 및 메모리 사이즈(A₂)의 다른 간격은 공통의 중심(X)을 갖기 때문에, 평가(530)의 결과는 필연적으로, 어드레스들에 대한 참조들이 메모리 사이즈(A₂)의 다른 간격의 에지 부분들

및

와 메모리 사이즈(A₂)의 다른 간격의 중심 부분

간에 균일하게 분포될 것으로 기대됨을 의미한다.

결과적으로, 540에서, 캐시 메모리에 캐싱하기 위한 데이터가 블록 오프셋(X) 상에 중심을 두는 메모리 사이즈(A₂)를 갖는 간격 내의 어딘가에 있는 어드레스들을 갖도록 선택된다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하면, 그리고 단범위의 공간적인 로컬리티 메트릭의 인스턴트 값이 장범위의 공간적인 로컬리티 메트릭의 인스턴트 값과 실질적으로 같은 것으로 평가되는 것에 응답하여, 그리고 또한 장범위의 공간적인 로컬리티 메트릭에 해당하는 메모리 사이즈 A₂=128KB 일 때, 캐싱될 데이터는 메모리 간격(X-64KB, X+64KB)으로부터 선택된다.

또한, 캐시 미스를 검출하는 것에 응답하여, 550에서, 단범위의 공간적인 로컬리티 메트릭의 현재 값이 장범위의 공간적인 로컬리티 메트릭의 현재 값 보다 작은 것으로, 단범위 및 장범위의 공간적인 로컬리티 메트릭들의 평가가 이루어진다. 단범위의 공간적인 로컬리티 메트릭의 작은 인스턴트 값은 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈(A₁)의 간격 내의 어드레스들에 대한 참조들의 작은 공간 밀도를 나타내며, 그리고 장범위의 공간적인 로컬리티 메트릭의 큰 인스턴트 값은 블록 오프셋 "X" 상에 중심을 두는 메모리 사이즈(A₂)의 다른 간격 내의 어드레스들에 대한 참조들의 큰 공간 밀도를 나타낸다. 메모리 사이즈(A₁)의 간격 및 메모리 사이즈(A₂)의 다른 간격은 공통의 중심(X)을 갖기 때문에, 평가(550)의 결과는 필연적으로, 메모리 사이즈(A₂)의 다른 간격의 에지 부분들

및

내의 어드레스들에 대한 참조들의 개수가 메모리 사이즈(A₂)의 다른 간격의 중심 부분

내의 어드레스들에 대한 참조들의 개수 보다 클 것으로 기대됨을 의미한다.

결과적으로, 560에서, 캐시 메모리에 캐싱하기 위한 데이터가, 블록 오프셋 "X"에 중심을 두는 메모리 사이즈(A₂)의 다른 간격의 에지 부분들

및

내의 어드레스들을 갖도록 선택된다. 예를 들어, "X"에 해당하는 캐시 미스를 검출하면, 그리고 단범위의 공간적인 로컬리티 메트릭의 인스턴트 값이 장범위의 공간적인 로컬리티 메트릭의 인스턴트 값 보다 작은 것으로 평가되는 것에 응답하여, 그리고 또한 단범위 및 장범위의 공간적인 로컬리티 메트릭들에 해당하는 각각의 메모리 사이즈들이 A₁=64KB 및 A₂=128KB 일 때, 캐싱될 데이터는 메모리 간격들(X-64KB, X-32KB) 및 (X+32KB, X+64KB)로부터 선택된다.

도 6a는 저장 데이터 시스템에 저장된 데이터를 캐싱하기 위한 방법(600)의 다른 예를 도시한다. 방법(600)은, (i) 캐시 미스를 검출하는 것에 응답하여 프리페치될 데이터의 양을 결정하고, (ii) 검출되는 캐시 미스와 관련된 어드레스 위치에 대해, 결정되는 데이터의 양을 프리페치하기 위해 저장 시스템의 영역을 선택하도록, 예를 들어 시스템(200) 내에서 구현될 수 있다.

630에서, 데이터 저장 시스템에 대한 액세스들의 다수의 별개의 그룹들에 기초하여, 데이터 저장 시스템에 대한 액세스들의 공간적인 분포의 측정이 (예를 들어, 제어기(200)에 의해) 결정된다. 630에서 수행되는 공간적인 분포의 측정을 결정하기 위한 구현의 예는 도 6d와 관련하여 하기에서 설명된다. 또한, 도 1a-1h는 공간적인 분포들의 구현들의 예들을 나타낸다. 예를 들어, 공간적인 분포는 저장 시스템의 어드레스들에 대한 참조들의 하나 이상의 공간적인 로컬리티들(예를 들어, 150)에 의해 표현되며, 그리고 공간적인 분포의 측정들은 하나 이상의 공간적인 로컬리티들 각각에 해당하는 공간적인 로컬리티 메트릭들(예를 들어, 110)에 의해 표현될 수 있다.

640에서, 결정된 공간적인 분포의 측정에 기초하여, 데이터 저장 시스템에 대해 이용되는 캐싱 방침이 (예를 들어, 제어기(210)에 의해) 조정된다. 640에서 수행되는 캐싱 방침을 조정하는 구현들의 예들은 도 6c 및 6d와 관련하여 하기에서 설명된다.

도 6b는 방법(600)의 선택적인 양상을 도시한다. 610에서, 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들이, 그 데이터 저장 시스템에 대한 상이한 참조 액세스들에 기초하여 (예를 들어, 제어기(210)에 의해) 식별된다. 예를 들어, 액세스들의 별개의 그룹들은 데이터 저장 시스템의 어드레스들에 대한 참조들의 두개 이상의 시퀀스들에 기초하여 식별될 수 있으며, 이에 따라 도 1b 및 1d에 도시된 바와 같이, 각 시퀀스들 내의 제 1 참조는 저장 매체(140)의 각각의 선행하는 시퀀스, 예를 들어 X_n, X_n ₊₁, ... 내의 제 1 참조와 관련된 어드레스와 상이한 어드레스와 관련된다. 이러한 방식으로 식별되는 액세스들의 별개의 그룹들은, 예를 들어 두개 이상의 시퀀스들 X_n, X_n ₊₁, ... 각각 내의 제 1 참조의 각각의 시간들(times)에 해당하는 다수의 측정 시간들에서 공간적인 분포의 측정들을 결정하기 위해 이용될 수 있다.

데이터 저장 시스템에 대한 상이한 참조 액세스들에 기초하여 그 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 것은, 612에서, 난수 발생에 기초하여, (예를 들어, 제어기(210)에 의해) 데이터 저장 시스템에 대한 상이한 참조 액세스들을 결정하는 것을 포함할 수 있다. 예를 들어, 데이터 저장 시스템의 어드레스들에 대한 참조들의 상기의 두개 이상의 시퀀스들은, 각 시퀀스들 X_n, X_n+1, ... 내의 제 1 참조가 선행하는 시퀀스 내의 마지막 참조 이후 임의 개수의 참조들 이후에 선택되도록, 식별될 수 있다. 이러한 랜덤한 샘플링은 상기의 다수의측정 시간들에서 측정되는 공간적인 분포에 대한 측정 정확도를 증가시킬 수 있다.

도 6c는 방법(600)의 다른 선택적인 양상을 나타낸다. 구체적으로, 640에서 수행되는 캐싱 방침의 조정은, 642에서, 도 4b에 도시된 바와 같이, 데이터 저장 시스템으로부터 프리페치되는 데이터의 양을 (예를 들어, 제어기(210)에 의해) 변경하는 것을 포함할 수 있다. 예를 들어, 공간적인 분포(예를 들어, 110)의 측정이 미리 결정된 임계치(threshold)를 초과하는 경우, 미리 결정되는 양의 데이터(예를 들어, "2Δ")가, 캐시 미스를 발생시킨 참조와 관련된 어드레스 "X"에 인접하는 데이터 저장 시스템의 영역으로부터 캐싱된다. 하지만, 공간적인 분포(예를 들어, 110)의 측정이 미리 결정된 임계치를 초과하지 않는 경우, 미리 결정되는 다른 양의 데이터(예를 들어, "Δ")가 동일한 영역으로부터 캐싱된다.

도 6d는 방법(600)의 다른 선택적인 양상을 도시한다. 620에서, 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들이, 도 1d에 나타낸 바와 같이, 예를 들어 저장 매체(140)의 어드레스(X_n)에 해당하는 동일한 참조 액세스에 기초하여, (예를 들어, 제어기(210)에 의해) 식별된다. 몇몇 구현들에서, 액세들의 별개의 그룹들은, 데이터 저장 시스템(140)의 어드레스(X_n)와 관련된 제 1 참조를 갖는 그 데이터 저장 시스템의 어드레스들에 대한 참조들의 시퀀스에 기초하여 식별될 수 있다. 이러한 방식으로 식별되는 액세스들의 별개의 그룹들은, 예를 들어 (이를 테면, 어드레스(X_n)와 관련된) 제 1 참조의 시간에 해당하는 측정 시간에서 공간 분포(예를 들어, 112 및 114)의 각각의 공간적인 컴포넌트들의 측정들을 결정하는 데에 이용될 수 있다. 공간 분포(예를 들어, 112 및 114)의 공간적인 컴포넌트들은, 시퀀스 내의 제 1 참조에 해당하는 어드레스에 대한 각각의 거리들(예를 들어, 도 1d에 도시한 바와 같이, 어드레스(X_n) 주위의 거리들 A₁ 및 A₂)에 기초하여, (예를 들어, 제어기(210)에 의해) 결정될 수 있다.

몇몇 구현들에서, 액세스들의 별개의 그룹들은 데이터 저장 시스템의 어드레스들에 대한 참조들의 두개 이상의 시퀀스들에 기초하여 (예를 들어, 제어기(210)에 의해) 식별될 수 있는 바, 이러한 두개 이상의 시퀀스들 각각은 (i) (이를 테면, 어드레스(X_n)와 관련된) 데이터 저장 시스템의 어드레스와 관련된 공통의 제 1 참조, 및 (ii) 도 1a와 관련하여 상세히 설명된 상이한 개수들의 참조들, N₁ 및 N₂를 갖는다. 두개 이상의 시퀀스들에 기초하여 식별되는 액세스들의 각각의 별개의 그룹들은, 예를 들어 (이를 테면, 어드레스(X_n)와 관련된) 제 1 참조에 해당하는 측정 시간에서의 공간 분포의 각각의 시간적인 컴포넌트들(temporal-components)의 측정들을 결정하는 데에 이용될 수 있다. 이러한 시간적인 컴포넌트들은 두개 이상의 참조들의 시퀀스들에 해당하는 각각의 상이한 개수의 참조들, N₁ 및 N₂에 기초하여 결정될 수 있다.

데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 것은, 622에서, 2개의 상이한 공간적인 범위들(예를 들어, 도 1d에 도시된 바와 같이, 어드레스(X_n) 주위의 거리들 A₁ 및 A₂)에 기초하여, 데이터 저장 시스템에 대한 액세스들의 2개의 별개의 그룹들을 (예를 들어, 제어기(210)에 의해) 식별하는 것을 포함할 수 있다. 예를 들어, 액세스들의 2개의 그룹들은, 데이터 저장 시스템의 어드레스(X_n)와 관련된 제 1 참조를 갖는 참조들의 시퀀스에 기초하여 식별될 수 있다. 이러한 방식으로 식별되는 액세스들의 2개의 그룹들은, 예를 들어 (이를 테면, 어드레스(X_n)와 관련된) 제 1 참조의 시간에 해당하는 측정 시간에서 공간적인 로컬리티의 단범위 및 장범위 메트릭(예를 들어, 112 및 114)을 결정하는 데에 이용될 수 있다. 단범위 및 장범위의 공간적인 로컬리티 메트릭들(예를 들어, 112 및 114)은, 시퀀스 내의 제 1 참조와 관련된 어드레스에 대한 각각의 짧은 거리 및 긴 거리(예를 들어, 도 1d에 도시된 바와 같이, 어드레스(X_n) 주위의 거리들 A₁ 및 A₂)에 기초하여, (예를 들어, 제어기(210)에 의해) 결정될 수 있다.

630에서 수행되는 공간적인 분포의 측정을 결정하는 것은, 632에서, (예를 들어, 제어기(210)에 의해) 제 1 수와 제 2 수를 비교하는 것을 포함할 수 있는 바, 제 1 수는 2개의 별개의 그룹들 중 하나에 해당하고, 제 2 수는 2개의 별개의 그룹들 중 다른 하나에 해당한다. 몇몇 구현들에서, 622에서 결정되는 단범위 및 장범위의 공간적인 로컬리티 메트릭들(예를 들어, 112 및 114)은, 예를 들어 데이터 저장 시스템의 어드레스(예를 들어, X)와 관련된 캐시 미스가 검출되는 시간에, 그 데이터 저장 시스템에 대한 어드레스들의 현재의 공간적인 분포에 대한 정보를 얻기 위해 비교될 수 있다.

640에서 수행되는 캐싱 방침의 조정은, 644에서, (예를 들어, 제어기(210)에 의해), 제 1 수와 제 2 수의 비교에 기초하여, (예를 들어, 도 5b에 나타낸) 데이터 저장 시스템의 상이한 영역들로부터 데이터를 선택적으로 프리페칭하는 것을 포함할 수 있다. 몇몇 구현들에서, 캐싱 방침은 캐시 미스를 검출할 때에 조정될 수 있는 바, 이는 예를 들어 데이터를 프리페칭할 어드레스 공간의 영역(이 영역은 검출된 캐시 미스와 관련된 어드레스인 X에 대해 선택된다)을 (예를 들어, 제어기(210)에 의해) 선택함으로써, 그리고 단범위 및 장범위의 공간적인 로컬리티 메트릭들(예를 들어, 112 및 114)의 현재 값들의 비교에 기초하여 이루어진다.

몇 개의 실시예들이 상기에서 상세히 설명되었으며, 다양한 변형들이 가능하다. 본 명세서에서 설명된 기능적인 동작들을 포함하는 개시되는 내용은, 이를 테면 본 명세서에서 개시된 구조적인 수단, 및 가능하게는 하나 이상의 데이터 처리 장치로 하여금 설명되는 동작들을 수행하게 하도록 동작가능한 프로그램(이를 테면, 메모리 디바이스, 저장 디바이스, 머신 판독가능한 저장 기판, 또는 다른 물리적인 머신 판독가능한 매체, 또는 이들중 하나 이상의 결합일 수 있는, 컴퓨터 판독가능한 매체에 엔코드되는 프로그램)을 포함하는 구조적인 그 등가물들과 같은, 전자 회로, 컴퓨터 하드웨어, 펌웨어, 소프트웨어, 또는 이들의 결합들로 구현될 수 있다.

용어 "데이터 처리 장치"는, 예를 들어 프로그램가능한 프로세서, 컴퓨터, 또는 다수의 프로세서들 또는 컴퓨터들을 포함하는, 데이터를 처리하기 위한 모든 장치, 디바이스들 및 머신들을 포함한다. 이러한 장치는, 하드웨어 이외에, 문제의(in question) 컴퓨터 프로그램을 위한 실행 환경을 생성하는 코드, 예를 들어 프로세서 펌웨어, 프로토콜 스택, 데이터베이스 관리 시스템, 운영 체제, 또는 이들 중 하나 이상의 결합을 구성하는 코드를 포함할 수 있다.

(컴퓨터 프로그램, 소프트웨어, 소프트웨어 애플리케이션, 스크립트, 또는 코드라고도 알려져있는) 프로그램은, 컴파일형(compiled) 또는 해석형(interpreted) 랭귀지들, 또는 선언형(declarative) 또는 절차형(procedural) 랭귀지들을 포함하는, 임의의 형태의 프로그래밍 랭귀지로 기록될 수 있으며, 그리고 예를 들어 독립형 프로그램(stand-alone program), 또는 모듈, 컴포넌트, 서브루틴, 또는 컴퓨터 환경에서 이용하기에 적절한 다른 유닛을 포함하는 임의의 형태로 배치될 수 있다. 프로그램이 반드시 파일 시스템 내의 파일에 해당할 필요는 없다. 프로그램은 다른 프로그램들 또는 데이터를 보유하는 파일(예를 들어, 마크업 랭귀지 도큐먼트로 저장되는 하나 이상의 스크립트들)의 일부 내에, 또는 문제의 프로그램에 전용되는 단일 파일 내에, 또는 다수의 통합된 파일들(coordinated files)(예를 들어, 하나 이상의 모듈들, 서브프로그램들, 또는 코드의 부분들을 저장하는 파일들) 내에 저장될 수 있다. 프로그램은 하나의 컴퓨터 상에서, 또는 하나의 사이트에 위치되거나 다수의 사이트들에 걸쳐서 분산되며, 통신 네트워크에 의해 서로 연결되는 다수의 컴퓨터들 상에서 실행되도록 배치될 수 있다.

본 명세서가 많은 특정 사항들을 포함하기는 하지만, 이러한 사항들은 청구되는 발명의 범위에 대해 제한하는 것이 아니라, 본 발명의 특정의 실시예들에 대한 특정한 피쳐들의 설명들로서 해석되어야 한다. 본 명세서에서 개별적인 실시예들의 환경에서 설명된 특정 피쳐들은 또한 단일의 실시예에서 결합하여 구현될 수 있다. 반대로, 단일의 실시예의 환경에서 설명된 다양한 피쳐들 또한, 다수의 실시예들에서 개별적으로, 또는 임의의 적절한 서브결합으로 구현될 수 있다. 또한, 피쳐들이 특정의 결합들로 동작하고 심지어 처음에 이러한 것으로서 청구되는 것으로서 상기 설명되기는 하였지만, 몇몇 경우들에 있어서, 청구되는 결합으로부터의 하나 또는 그 보다 많은 피쳐들은 그 결합으로부터 삭제될 수 있으며, 그리고 청구되는 결합은 서브결합 또는 서브결합의 변형에 대한 것일 수 있다.

유사하게, 동작들이 도면들에서 특정 순서로 도시되어 있기는 하지만, 이것은, 바람직한 결과들을 달성하기 위해, 이러한 동작들이 도시된 특정 순서로 또는 순차적인 순서로 수행되어야 하거나, 또는 도시된 모든 동작들이 수행되어야 함을 요구하는 것으로서 이해되서는 안된다. 특정의 환경들에서는, 멀티태스킹(multitasking) 및 병렬 처리(parallel processing)가 유익할 수 있다. 또한, 상기 설명된 실시예들에서의 다양한 시스템 컴포넌트들의 분리가, 모든 실시예들에서 이러한 분리를 요구하는 것으로서 이해되서는 안된다.

다른 실시예들은 하기의 청구항들의 범위 내에 포함된다.

Claims

데이터 처리 장치에 의해 수행되는 방법으로서,
데이터 저장 시스템에 대한 액세스들의 다수의 별개의 그룹들에 기초하여, 상기 데이터 저장 시스템에 대한 액세스들의 공간적인 분포(spatial distribution)의 측정(measure)을 결정하는 단계; 및
상기 결정되는 공간적인 분포의 측정에 기초하여, 상기 데이터 저장 시스템에 대해 이용되는 캐싱 방침(caching policy)을 조정하는 단계를 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 1 항에 있어서,
상기 데이터 저장 시스템에 대한 상이한 참조 액세스들(reference accesses)에 기초하여, 상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계를 더 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 2 항에 있어서,
상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계는, 난수 발생(random number generation)에 기초하여 상기 데이터 저장 시스템에 대한 상이한 참조 액세스들을 결정하는 단계를 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 1 항에 있어서,
상기 데이터 저장 시스템에 대한 동일한 참조 액세스에 기초하여, 상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계를 더 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 4 항에 있어서,
상기 데이터 저장 시스템에 대한 액세스들의 별개의 그룹들을 식별하는 단계는, 2개의 상이한 공간적인 범위들에 기초하여 상기 데이터 저장 시스템에 대한 액세스들의 2개의 별개의 그룹들을 식별하는 단계를 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 5 항에 있어서,
상기 공간적인 분포의 측정을 결정하는 단계는, 제 1 수(number)와 제 2 수를 비교하는 단계와, 여기서 상기 제 1 수는 상기 2개의 별개의 그룹들 중 하나에 해당하고, 상기 제 2 수는 상기 2개의 별개의 그룹들 중 다른 하나에 해당하며; 그리고
상기 캐싱 방침을 조정하는 단계는, 상기 제 1 수와 상기 제 2 수의 비교에 기초하여, 상기 데이터 저장 시스템의 상이한 영역들로부터 데이터를 선택적으로 프리페칭(pre-fetching)하는 단계를 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 1 항에 있어서,
상기 캐싱 방침을 조정하는 단계는 상기 데이터 저장 시스템으로부터의 데이터의 프리페칭의 양을 변경하는 단계를 포함하는 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
제 1 항에 있어서,
상기 데이터 저장 시스템은 저장 매체를 포함하는 개별적인 저장 디바이스인 것을 특징으로 하는 데이터 처리 장치에 의해 수행되는 방법.
저장 시스템으로서,
저장 매체;
캐시 디바이스; 및
상기 저장 매체 및 상기 캐시 디바이스와 통신 가능하게 결합되며, 컴퓨터 시스템의 메모리 또는 프로세스와 인터페이스하도록 구성되는 제어기를 포함하며;
상기 제어기는 또한,
상기 저장 시스템과 관련된 어드레스 참조들의 특정된 양(specified quantity)을 수신하고;
상기 어드레스 참조들의 수신되는 특정된 양에 적어도 부분적으로 기초하여, 상기 저장 시스템의 어드레스들에 대한 참조들의 공간적인 분포를 결정하고,
상기 결정된 공간적인 분포와 이전에 결정된 공간적인 분포를 상기 저장 시스템의 공간적인 로컬리티 메트릭(spatial locality metric)으로 결합시키며; 그리고
데이터를 캐싱하는 데에 이용하기 위해 상기 공간적인 로컬리티 메트릭을 상기 저장 매체로부터 상기 캐시 디바이스로 출력하도록 구성되는 것을 특징으로 하는 저장 시스템.
제 9 항에 있어서,
상기 캐시 디바이스는 캐시 메모리를 포함하는 것을 특징으로 하는 저장 시스템.
제 10 항에 있어서,
상기 캐시 디바이스는 디바이스 제어기를 더 포함하는 것을 특징으로 하는 저장 시스템.
제 9 항에 있어서,
상기 공간적인 분포의 결정을 수행하기 위해, 상기 제어기는 또한 상기 공간적인 분포의 이전의 결정과 상기 공간적인 분포의 상기 결정 간의 어드레스 참조들의 임의의 양(random quantity)을 생략하도록 구성되는 것을 특징으로 하는 저장 시스템.
제 9 항에 있어서,
상기 공간적인 로컬리티 메트릭은 상기 결정된 공간적인 분포와 상기 이전에 결정된 공간적인 분포의 가중 합(weighted sum)을 포함하는 것을 특징으로 하는 저장 시스템.
제 9 항에 있어서,
상기 제어기는 또한,
상기 저장 시스템의 어드레스에 대한 참조를 수신하고, 여기서 수신된 어드레스 참조는 상기 저장 시스템 상의 소정의 블록 오프셋(block offset)에 해당하며;
상기 캐시 디바이스 내에서 상기 수신된 어드레스 참조에 대한 캐시 미스(cache miss)를 검출하고;
상기 캐시 미스의 검출에 응답하여, 상기 공간적인 로컬리티 메트릭의 현재 값에 따라 상기 캐시 디바이스에 캐싱하기 위한 상기 저장 시스템의 상기 소정의 블록 오프셋과 관련된 데이터를 선택하도록 구성되는 것을 특징으로 하는 저장 시스템.
제 14 항에 있어서,
상기 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는,
(i) 상기 공간적인 로컬리티 메트릭의 현재 값이 제 1 값과 상기 제 1 값 보다 큰 제 2 값 사이인 경우, 상기 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 특정된 양의 데이터;
(ii) 상기 공간적인 로컬리티 메트릭의 현재 값이 상기 제 2 값 보다 큰 경우, 상기 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 상기 특정된 양 보다 많은 데이터; 및
(iii) 상기 공간적인 로컬리티 메트릭의 현재 값이 상기 제 1 값 미만인 경우, 상기 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 상기 특정된 양 미만의 데이터를 포함하는 것을 특징으로 하는 저장 시스템.
제 15 항에 있어서,
상기 공간적인 로컬리티 메트릭의 현재 값이 상기 제 1 값 미만인 경우, 상기 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는 0인 것을 특징으로 하는 저장 시스템.
제 15 항에 있어서,
상기 공간적인 로컬리티 메트릭의 현재 값이 상기 제 2 값 보다 큰 경우, 상기 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는, 상기 소정의 블록 오프셋 부근의 인접하는 메모리로부터의 상기 특정된 양의 두배의 데이터를 포함하는 것을 특징으로 하는 저장 시스템.
제 14 항에 있어서,
상기 저장 시스템 상에서의 상기 결정된 공간적인 분포는, 상기 어드레스 참조들의 수신되는 특정된 양의 제 1 어드레스 참조의 블록 오프셋으로부터 제 1 거리 내에 있는, 상기 어드레스 참조들의 수신되는 특정된 양의 제 1 부분(fraction)을 포함하는 것을 특징으로 하는 저장 시스템.
제 18 항에 있어서,
상기 저장 시스템 상에서의 상기 결정된 공간적인 분포는, 상기 어드레스 참조들의 수신되는 특정된 양의 상기 제 1 어드레스 참조의 상기 블록 오프셋으로부터 제 2 거리 내에 있는, 상기 어드레스 참조들의 수신되는 특정된 양의 제 2 부분을 포함하고, 상기 제 2 거리는 상기 제 1 거리 보다 더 길며, 이에 따라 상기 결정된 공간적인 분포는 제 1의 더 짧은 거리에 대한 상기 제 1 부분의 비(ratio)를 나타내는 상기 공간 분포의 단범위 컴포넌트(short-range component), 및 제 2의 더 긴 거리에 대한 상기 제 2 부분의 다른 비를 나타내는 상기 공간 분포의 장범위 컴포넌트(long-range component)를 갖고, 상기 공간적인 로컬리티 메트릭은, 상기 공간적인 분포의 단범위 및 장범위 컴포넌트들 각각에 해당하는 단범위 및 장범위 공간적인 로컬리티 메트릭들을 포함하는 것을 특징으로 하는 저장 시스템.
제 19 항에 있어서,
상기 캐시 디바이스에 캐싱하기 위해 선택되는 데이터는,
(i) 상기 단범위 공간적인 로컬리티 메트릭의 현재 값이 상기 장범위 공간적인 로컬리티 메트릭의 현재 값 보다 큰 경우, 상기 소정의 블록 오프셋으로부터 상기 제 1 거리 미만에 위치되는 어드레스들;
(ii) 상기 단범위 및 장범위 공간적인 로컬리티 메트릭들의 현재 값들이 실질적으로 같은 경우, 상기 소정의 블록 오프셋으로부터 상기 제 2 거리 미만에 위치되는 어드레스들; 및
(iii) 상기 단범위 공간적인 로컬리티 메트릭의 현재 값이 상기 장범위 공간적인 로컬리티 메트릭의 현재 값 보다 작은 경우, 상기 소정의 블록 오프셋으로부터 상기 제 2 거리와 제 1 거리 사이에 위치되는 어드레스들에 해당하는 것을 특징으로 하는 저장 시스템.