Nothing Special   »   [go: up one dir, main page]

KR20170028825A - 압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색 - Google Patents

압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색 Download PDF

Info

Publication number
KR20170028825A
KR20170028825A KR1020160052404A KR20160052404A KR20170028825A KR 20170028825 A KR20170028825 A KR 20170028825A KR 1020160052404 A KR1020160052404 A KR 1020160052404A KR 20160052404 A KR20160052404 A KR 20160052404A KR 20170028825 A KR20170028825 A KR 20170028825A
Authority
KR
South Korea
Prior art keywords
bits
signature
prefix
value
container
Prior art date
Application number
KR1020160052404A
Other languages
English (en)
Inventor
존 콜그로브
에단 엘 밀러
닐 아마르 바차라자니
펑 왕
Original Assignee
퓨어 스토리지, 아이앤씨.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 퓨어 스토리지, 아이앤씨. filed Critical 퓨어 스토리지, 아이앤씨.
Publication of KR20170028825A publication Critical patent/KR20170028825A/ko

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2255—Hash tables
    • G06F17/3033—
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/13—File access structures, e.g. distributed indices
    • G06F16/134—Distributed indices
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/13—File access structures, e.g. distributed indices
    • G06F16/137—Hash-based
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2272—Management thereof
    • G06F17/30094—
    • G06F17/30097—
    • G06F17/30336—

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법이 제공된다. 방법은, 값을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 나누는 (breaking) 단계를 포함한다. 방법은, 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스에서의 컨테이너를 결정하는 단계를 포함하고, 컨테이너는 컨테이너와 연관된 총 값들에 의해 결정된 프리픽스 비트들에 대응하여 설정된 비트들을 갖는 프리픽스 테이블 및 컨테이너와 연관된 총 값들에 의해 결정된 시그니처 비트들을 포함하는 시그니처 테이블을 포함한다. 방법은, 프리픽스 및 시그니처 테이블들 및 결정된 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하는 단계를 포함한다.

Description

압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색{MEMORY-EFFICIENT STORAGE AND SEARCHING IN HASH TABLES USING COMPRESSED INDEXES}
해시 테이블들은 키들을 값들에 매핑하고, 종종 데이터 구조들 및 룩업 테이블들의 다른 타입들 보다 그렇게 행하는데 더 효율적이다. 해시 테이블들은 데이터베이스 인덱싱, 데이터 듀플리케이션, 및 다량의 데이터 및 키-값 쌍들을 수반하는 태스크들을 위한 광범위한 사용을 발견한다. 하지만, 큰 해시 테이블들을 통한 탐색은 시간 소모적이고 집중적인 프로세서 사이클일 수 있다. 큰 해시 테이블들은 로컬 메모리 또는 DRAM (동적 랜덤 액세스 메모리) 에서 유지하기에 너무 커서, 더 크거나 조밀하지만 더 느린 메모리 액세스에서 더 큰 해시 테이블들을 유지하는 것을 필요로 하며, 이는 그 후 해시 테이블을 통한 탐색을 위해 필요한 시간의 양을 증가시킨다.
실시형태들이 발생하는 것은 이 컨택스트 내에서 이다.
일부 실시형태들에서, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법이 제공된다. 방법은, 값을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 나누는 (breaking) 단계를 포함한다. 방법은, 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스에서의 컨테이너를 결정하는 단계를 포함하고, 컨테이너는 컨테이너와 연관된 총 (aggregate) 값들에 의해 결정된 프리픽스 비트들에 대응하여 설정된 비트들을 갖는 프리픽스 테이블 및 컨테이너와 연관된 값들을 총 값들에 의해 결정된 시그니처 비트들을 포함하는 시그니처 테이블을 포함한다. 방법은, 프리픽스 및 시그니처 테이블들 및 결정된 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하는 단계를 포함한다.
일부 실시형태들에서, 유형의 비일시적 컴퓨터 판독가능 매체는, 프로세서에 의해 실행될 때, 프로세서로 하여금, 방법을 수행하게 하는 명령들을 갖는다. 방법은 값의 비트들을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 분리하는 단계를 포함한다. 방법은 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스를 사용하는 컨테이너를 결정하는 단계를 포함하고, 컨테이너는 컨테이너와 연관된 총 값들에 의해 결정된 프리픽스 비트들에 따라 설정된 비트들을 갖는 프리픽스 테이블 및 컨테이너와 연관된 총 값들에 의해 결정된 시그니처 비트들을 포함하는 시그니처 테이블을 포함한다. 방법은 프리픽스 및 시그니처 테이블들 및 결정된 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하는 단계를 포함한다.
일부 실시형태들에서, 컴퓨팅, 통신 또는 스토리지 시스템이 제공된다. 이 시스템은 값을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 나누고, 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스를 사용하여 컨테이너를 결정하도록 구성된 하나 이상의 프로세서들을 포함한다. 컨테이너는 컨테이너와 연관된 총 값들에 의해 결정된 프리픽스 비트들에 따라 비트들을 갖는 프리픽스 테이블 및 컨테이너와 연관된 값들을 총 값들에 의해 결정된 시그니처 비트들을 포함하는 시그니처 테이블을 포함한다. 프로세서는 프리픽스 및 시그니처 테이블들 및 결정된 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하도록 구성되고, 하나 이상의 프로세서들은 값이 해시 테이블에 저장되는지를 결정한다.
실시형태들의 다른 양태들 및 이점들은, 기재된 실시형태들의 원리들을, 예시로서 도시하는 첨부 도면들과 함께 취해지는 다음의 상세한 설명으로부터 명백해질 것이다.
기재된 실시형태들 및 그 이점들은 첨부 도면들과 함께 취해진 다음의 기재를 참조하여 최상으로 이해될 수도 있다. 이들 도면들은 기재된 실시형태들의 사상 및 범위로부터 벗어나지 않으면서 당업자에 의해 기재된 실시형태들에 대해 이루어질 수도 있는 상세 및 형태에서의 임의의 변경들을 조금도 제한하지 않는다.
도 1 은 일부 실시형태들에 따라, 데이터 스토리지에서의 데이터를 순차적으로 가리키는, 해시 피라미드에서의 해시 테이블들을 요약하기 위한 요약 테이블들을 사용한 스토리지 시스템을 나타내는 시스템 액션 및 블록 다이어그램이다.
도 2 는 일부 실시형태들에 따라, 키/값 쌍들을 포함하는 키들, 해시 함수, 분류된 해시 값들, 및 엔트리들을 갖는 일 예의 해시 테이블을 도시한다.
도 3 은 일부 실시형태들에 따라, 각각이 도 2 의 해시 테이블로부터 다중 해시 값들을 인코딩하는, 버킷들을 갖는 요약 테이블을 도시한다.
도 4 는 일부 실시형태들에 따라, 도 3 의 요약 테이블을 사용하는, 압축된 인덱스들을 사용한 결정론적 탐색을 위한 방법의 플로우 다이어그램이다.
도 5 는 본 명세서에 기재된 실시형태들을 구현할 수도 있는 예시적인 컴퓨팅 디바이스를 나타내는 도시이다.
본 명세서에 기재된 다양한 시스템 실시형태들은 압축된 인덱스를 사용하여 효율적이고 결정론적 탐색을 위해, 해시 테이블에 대응하는 요약 테이블을 사용한다. 다양한 실시형태들은 메모리에 캐시될 수 있는 해시 테이블들의 다중 레벨들, 및 유사한 유연성을 갖는 다중 요약 테이블들을 사용한다. 해시 테이블로부터의 다중 해시 값들은, 대응 요약 테이블의 각각의 버킷으로 인코딩된다. 요약 테이블은, 해시 테이블의 해시 값들에 기초하여 구성되고, 그 후 관심의 해시 값을 탐색하기 위해 사용된다. 본 명세서에 기재된 메커니즘들 및 기법들은 해시 테이블들을 사용하는 다양한 시스템들에 있어서 컴퓨팅 효율성을 개선하고 탐색 시간 레이턴시를 감소시킨다. 데이터 스토리지 환경에서 데이터를 위치시키기 위해 요약 테이블(들) 및 해시 테이블(들) 을 사용하기 위한 예들이 제공되며, 이들에 대한 추가적인 사용들은 본 명세서에서의 교시들에 따라, 데이터 스토리지 환경들의 외부를 포함하여, 용이하게 창안된다.
도 1 은 데이터 스토리지 (118) 에서 데이터를 순차적으로 가리키는, 해시 피라미드 (116) 의 해시 테이블들 (120) 을 요약하기 위한 요약 테이블들 (114) 을 사용하는 스토리지 시스템 (102) 을 나타내는 시스템 액션 및 블록 다이어그램이다. 예시의 스토리지 시스템 (102) 은 하나 이상의 프로세서들 (104) 및 로컬 메모리 (108), 메타데이터 섹션 (110), 및 데이터 섹션 (112) 로 분할된 메모리 (106) 를 갖는다. 이러한 스토리지 시스템 (102) 및/또는 메모리 조직화에 대한 변형들이 쉽게 창안된다. 다른 컴퓨팅 디바이스들이 본 명세서에 기재된 실시형태들을 통합할 수도 있기 때문에 실시형태들은 스토리지 시스템들에 제한되지 않는다는 것을 알아야 한다. 로컬 메모리 (108) 는 일부 실시형태들에서 DRAM (동적 랜덤 액세스 메모리) 를 사용하여 구현될 수 있다. 메모리 (106) 의 데이터 섹션 (112) 은 스토리지 메모리로서 구현될 수도 있다. 메모리 (106) 는 요약 테이블들 (114), 해시 피라미드 (116) 및 데이터 스토리지 (118) 를 포함하도록 다양한 방식들로 조직화될 수 있다. 이러한 예는 제한되도록 의미되지 않기 때문에 다른 방식들로 대응하는 변형들이 창안될 수 있지만, 요약 테이블들 (114) 은, 예를 들어 일 대 일 기반으로 해시 테이블들 (120) 에 대응한다. 일부 실시형태들은 단일 요약 테이블 및 단일 해시 테이블 (120) 을 갖고, 일부 실시형태들은 다중 요약 테이블들 (114) 및 다중 해시 테이블들 (120) 을 가지며, 일부 실시형태들은 요약 테이블들 (114) 의 다중 레벨들과 해시 테이블들 (120) 의 다중 레벨들 및 해시 피라미드 (116) 등을 갖는다.
도 2 는 키들 (202), 해시 함수 (210), 분류된 해시 값들 (206), 및 키/값 쌍들 (214) 를 포함하는 엔트리들 (212) 을 갖는, 일 예의 해시 테이블 (120) 을 도시한다. 해시 테이블들 (120) 은 컴퓨팅, 통신 및 데이터 관리에 있어서 많은 목적들을 위해 사용되며, 다음의 예들은 몇몇 실시형태들을 도시하며, 더 많은 실시형태들이 쉽게 창안된다. 키 (202) 는 사람, 사업 또는 디바이스의 명칭, 사람, 사업 또는 건물의 주소, 데이터 또는 디바이스의 논리 어드레스, 데이터 또는 디바이스의 물리 어드레스, 포인터 등일 수 있고, 각각의 키 (202) 는 키 (202) 성질에 대해 적절한 키 값 (204) 을 갖는다. 키/값 쌍 (214) 은 사람이 살고 있는 주소와 연관된 사람의 명칭, 사람의 전화 번호 또는 사람의 사회 보장 번호, 그 후 이진 ASCII (American Standard Code for Information Interchange) 을 유지하는 데이터의 물리 어드레스와 연관된 데이터의 논리 어드레스 또는 데이터 그 자체의 다른 코드 값, 다른 레벨의 어드레스와 연관된 일 레벨의 어드레스 디바이스 명칭 및 디바이스 식별자 (예를 들어 숫자 또는 영숫자 스트링) 등일 수 있으며, 각각의 키/값 쌍 (214) 은 키/값 쌍 (214) 의 성질에 대해 적절한 해시 테이블에서의 엔트리 (212) 를 갖는다. 일부 실시형태들에서, 해시 값들 (206) 은 그 후 분류되고, 대응 엔트리 값들 (208) 로 해시 테이블 (120) 에 배치된다. 대안의 실시형태들에서, 해시 테이블 (120) 은 키의 해시 값 (206) 에 대응하는 위치들에 키들을 하나씩 부가함으로써 구성된다. 해시 테이블을 사용하기 위해서, 관심의 키 (202) 는 해시 값 (206) 을 생성하기 위해 해시 함수 (210) 에 의해 평가되는, 키 값 (204) 을 제출한다. 해시 값 (206) 은 분류된 해시 값들 (206) 에 있어서 해시 테이블에서 검색되고, 이것은 대응 엔트리 값 (208) 과 연관된다. 엔트리 값 (208) 은 원하는 키/값 쌍 (214) 을 포함한다.
도 3 은, 각각이 도 2 의 해시 테이블 (120) 로부터 다중 해시 값들 (206) 을 인코딩하는 버킷들 (310) 을 갖는 요약 테이블 (320) 을 도시한다. 요약 테이블 (320) 을 구성하기 위해서, 대응 해시 테이블 (120) 의 각각의 해시 값 (206) 은 다중 비트 필드들 (302 304, 306) 로 분해된다. 이들 비트 필드들 (302, 304, 306) 은 다양한 실시형태들에 있어서 재배열될 수 있고 다양한 사이즈들 (즉 비트들의 수들) 을 가질 수 있다. 해시 값 (206) 의 버킷 어드레스 필드 (302) 는 버킷 (310) 을 가리키는, 버킷 어드레스 값으로서 해석되는 다중 비트들을 갖는다. 즉, 버킷 어드레스 필드 (302) 는 요약 테이블 (320) 에서 버킷 (310) 의 어드레스로서 작용한다. 버킷 어드레스 필드 및 연관된 값은 일부 실시형태들에서 해시 값 (206) 의 최대 유의 비트들 (MSB) 로부터 취해진다는 것을 알아야 한다. 각각의 버킷 (310) 은, 그 각각의 버킷 어드레스 필드들 (302) 에서 동일한 비트 값들 (즉, 버킷 어드레스 값) 을 갖는 많은 해시 값들 (206) 을 유지하거나, 나타내거나 또는 인덱싱할 수 있다.
해시 값 (206) 의 프리픽스 필드 (304) 는 버킷 어드레스 값에 의해 가리킨 버킷 (310) 의 프리픽스 테이블 (314) 에서 비트들을 설정하는, 프리픽스 값으로서 해석되는 다중 비트들을 갖는다. 예를 들어, 프리픽스 값이 숫자 N 인 경우, 프리픽스 테이블 (314) 에서 N 번째 비트가 설정될 것이다. 추가 실시형태에서, 이 비트는 대신 클리어된다. 프리픽스 필드 (304) 에서 2 의 비트들의 수의 거듭 제곱과 동등한 프리픽스 테이블 (314) 에서의 비트들의 수가 있어야 한다는 결론이 나온다. 예를 들어, 프리픽스 필드 (304) 에서 8 개의 비트들이 있는 경우, 프리픽스 테이블 (314) 에서 2 백 56 개 (2 의 8 거듭제곱) 가 있어야 한다.
해시 값 (206) 의 시그니처 필드 (306) 는 시그니처로서 해석되고, 시그니처 필드 (318) 에 배치되는 다중 비트들을 갖는다. 버킷 (310) 의 사이즈 (즉, 비트들의 총 수) 에 의존하여, 시그니처 필드 (306) 는 프리픽스 필드 (304) 및 버킷 어드레스 필드 (302) 의 비트들이 해시 값 (206) 에서 스트립된 후에 남겨진 해시 값 (206) 의 모든 비트들을 포함할 수 있다. 일부 실시형태들에서, 절단 (truncation) 필드 (308) 에서의 비트들은 제거될 수 있고 시그니처 값으로서 나머지 비트들이 사용되었다. 시그니처 값들은 해시 테이블 (120) 의 분류된 해시 값들 (206) 과 동일한 순서 또는 시퀀스로 시그니처 테이블 (318) 에 배치된다. 예를 들어, 버킷 (310) 에서 나타낼 최하위 어드레싱된 해시 값 (206) 의 시그니처 값은 시그니처 테이블 (318) 에서 최좌측에 배치된다. 후속 어드레싱된 해시 값들 (206) 의 후속 시그니처 값들은 시그니처 테이블 (318) 에 있어서 좌측에서 우측으로의 후속 위치들에 배치된다. 일부 실시형태들에서, 이것은 반전될 수 있으며, 즉 우측으로부터 시작하여 좌측으로 진행할 수 있다.
버킷 (310) 의 트랜지트 테이블 (316) 은 버킷 (310) 의 해시 값들 (206) 의 시퀀스를 나타낸다. 일부 실시형태들에 있어서 시그니처 테이블 (318) 에서 나타낼 수 있는 해시 값들의 최대 수만큼 많은 비트들이 트랜지트 테이블 (316) 에 있을 수 있다. 이것은 일 예에 있어서 시그니처 테이블 (318) 에 의해 수용된 시그니처 값들의 최대 수와 동일한 수의 비트들일 수 있다. 트랜지트 테이블 (316) 은 이렇게 크지 않아야 하고 일부 실시형태들에 있어서 트랜지트 테이블 (316) 이 값들의 더 적거나 큰 수들에 대해 동적으로 수축 또는 성장할 수 있다는 것을 알아야 한다. 버킷 (310) 에서 나타낸 최하위 어드레싱된 해시 값 (206) 에 대응하는 트랜지트 테이블 (316) 의 최대 유의 비트로 시작하면, 이 비트가 1 의 값으로 자동으로 설정된다. 각각의 적은 유의 비트는 다음 상위 어드레싱된 해시 값 (206) 이 이전 해시 값 (206) 과 동일한 프리픽스 값을 갖는 경우 0 의 값으로 설정되고, 다음 상위 어드레싱된 해시 값 (206) 이 이전 해시 값 (206) 과 상이한 프리픽스 값을 갖는 경우 1 의 값으로 설정된다. 일부 실시형태들에 있어서, 버킷에서의 최상위 엔트리에 대응하는 비트는 항상 1 로 설정된다. 이들 값들은 반전될 수도 있고 (1 에 대해 0 그리고 0 에 대해 1 로 교환) LSB 에 대해 MSB 로 또는 MSB 에 대해 LSB 로 채워질 수도 있으며, 추가적인 변형들이 창안될 수도 있다.
버킷 (310) 으로 인코딩하는 샘플 및 해시 값들 (206) 의 일 예의 세트는 상술한 메커니즘들 및 프로세스들의 실시형태를 도시한다. 16 진법으로 나타내는, 다음의 6 개의 엔트리들 (예를 들어, 특정 해시 테이블 (120) 로부터의 6 개의 해시 값들 (206)) 을 인코딩하는 것이 요망된다고 추정하며, 여기서 B=16, P=4, 그리고 S=8. 이들은 실제 구현을 위한 최적의 파라미터들일 수도 있고 아닐 수도 있지만, 이들은 일 예로서 제공되고 제한되도록 의미되지 않는다.
54FE3618
54FD0831
54FE4884
54FEC01D
54FE3257
54FE4882
이들 해시 값들 (206) 은 모두 동일한 버킷에 있는데, 이는 최상위 16 비트들 (B=16) 또는 4 개의 16 진 숫자들 (예를 들어, 54FE) 이 버킷을 선택하기 위해 사용되기 때문이다. 다음, 최소 유의 4 개의 비트들이 절단되고, 단지 B+P+S=28 비트들만이 유지된다. 리스트는 하기에 나타낸 바와 같이 계수적으로 분류된다.
54FE083
54FE325
54FE361
54FE488
54FEC01
그 후, 시스템은 버킷 (310) 에 대한 프리픽스 값들의 요약을 만들어 낸다. 이 경우, 해시 값들 (206) 의 프리픽스 필드 (304) (P = 4 비트, B 비트들의 우측으로) 는 0, 3 (2 배), 4 및 C 의 (예를 들어, 리스트에서 상부로부터 아래로) 프리픽스 값들을 가져서, 시스템은 프리픽스 테이블 (최우측 또는 마지막의 최소 유의 비트를 가짐) 에 있어서 16 외의, 대응 비트들을 설정한다. 이것은 프리픽스 테이블 (314) 에 대해 다음을 산출한다.
Prefix_table = 0001 0000 0001 1001
이것은 16 비트 워드에서 설정된 제 4 비트, 제 3 비트, 및 제 0 비트를 나타낸다.
시스템은 엔트리 0 (즉, 0 번째 엔트리 또는 초기 엔트리) 이 아닌 엔트리 1 로 시작하는 버킷 (310) 의 트랜지트 테이블 (316) 을 설정하는데, 이는 엔트리 0 에 대한 비트는 자동으로 프리픽스 테이블에서의 제 1 엔트리 (최소 유의 비트 (LSB) 또는 최우측 비트) 이기 때문이다. 엔트리 1 (즉, 제 1 엔트리) 는 엔트리 0 으로부터 프리픽스 값을 변화시키기 때문에, 설정된 비트 (1) 는 새로운 프리픽스가 이 값에 대해 사용되는 것을 표시한다. 제 2 엔트리는 제 1 엔트리로부터 프리픽스 값들을 변화시키지 않아서 (예를 들어, 양자 모두가 숫자 3 을 가짐), 클리어된 비트 (0) 는 동일한 프리픽스가 이 값을 위해 사용되는 것을 표시한다. 제 3 엔트리는 제 2 엔트리로부터 프리픽스 값들을 변화시키고 (예를 들어, 숫자 3 에서 숫자 4 로), 설정된 비트 (1) 은 새로운 프리픽스가 이 값을 위해 사용되는 것을 표시한다. 제 5 엔트리는 제 4 엔트리로부터 프리픽스 값들을 변화시키고 (예를 들어, 숫자 4 에서 숫자 C 로), 설정된 비트 (1) 는 새로운 프리픽스가 이 값에 대해 사용되는 것을 표시한다. 트랜지트 테이블 (316) 에 대한 결과의 트랜지트 비트들은 하기에 나타낸다.
11101
일부 실시형태들에서, 단지 5 개의 비트들만이 저장되어야 하는데, 이는 제 4 의 "1" 비트가 버킷 (310) 에 더 이상 엔트리가 없다는 것을 표시하기 때문이다. 트랜지트 테이블 (316) 에서 각각의 1 은 프리픽스 테이블에서 1 을 "소비" 하고, 제 1 의 1 은 버킷 (310) 의 시작에 의해 소비된다고 고려한다. 이것은, 프리픽스 테이블에 w 비트들이 있는 경우, 제 w 의 "1" 비트가 트랜지트 테이블 (316) 의 끝에 대응하는 것을 의미한다. 이것은 또한 버킷 (310) 에서 엔트리들의 수를 저장하는 것이 필요하지 않다는 것을 의미한다. 일부 실시형태들은 비트들을 카운트하기 위해 내재성들 (intrinsics) 을 사용하여 이러한 동작을 수행한다. 이 예는 예시적인 것이고 제한하도록 의미되지 않기 때문에, 일부 실시형태들은 트랜지트 테이블 (316) 에서 1들 및 0들을 플립한다. 부가적으로, 일부 실시형태들은 MSB 로부터 LSB 로 비트들을 배치한다.
시그니처 비트들의 수는 버킷 (310) 에서 (해시 값들 (206) 을 나타내는) 엔트리들의 수로 분할된 시그니처 테이블 (316) 에 할당된 비트들의 수로 결정되어, 필요한 경우 이동 (take the floor) 한다. 일부 실시형태들에서, 시그니처 비트들의 수는 버킷 포맷에 의해 고정될 수 있다. 위의 예에서, 시그니처들 (즉, 해시 값들 (206) 의 시그니처 필드 (306) 로부터의 시그니처 값들) 은 하기에 나타낸 바와 같다.
83 25 61 88 01
일부 실시형태들은 버킷 (310) 에서 버킷 포맷 필드 (312) 를 갖는 한편, 다른 것들은 버킷 포맷 필드를 생략하고 특정 요약 테이블에 대해 고정된 포맷을 사용한다. 이 포맷은 해시 피라미드 (116)(도 1) 에서의 해시 테이블들 (120) 의 레벨들 및/또는 요약 테이블들 사이에서 상이할 수 있다. 버킷 포맷 필드 (312) 를 갖는 실시형태들에 있어서, 이들 비트들은 프리픽스 테이블의 사이즈를 표시한다. 위의 예에서, 3 개의 테이블 사이즈가 있을 수 있다: 16 비트, 32 비트, 및 64 비트. 이것은 2 개의 비트들에서 인코딩되고 버킷 포맷 필드에 저장될 수 있으며, 하나의 코딩은 "64+" 를 표시하도록 남겨지는데, 이것은 64 비트 프리픽스 테이블을 갖는 오버플로우된 버킷을 의미한다. 최상위 인코딩된 값 후의 임의의 값이 존재할 수도 있지만 테이블에서 인코딩되지 않을 수도 있다. 이것은 부가적인 포지티브 오류들을 유도할 수도 있지만 마지막 엔트리의 상부 위의 어드레스 공간에만 비례한다는 것을 알아야 한다. 추가적인 실시형태에서, "64+" 는 최대 위 그리고 최소 아래의 값들이 잠재적인 매치들인 것을 표시한다.
위의 예들은 해시 테이블 (120) 그 자체에서 값들의 오프셋들을 포함하지 않는다. 하나의 전체 오프셋이 일부 실시형태들에서 다중 버킷들을 커버할 수도 있다. 이 값으로부터의 오프셋을 포함하는 작은 (예를 들어, 3-4 비트들) 필드 및 1024 버킷들에 대해 하나의 오프셋을 갖는 것과 같은, 이것에 대한 변형들이 창안될 수 있다. 이것은 실제 해시 테이블 (120) 에 대한 위치 정보가, 예를 들어 버킷 당 몇 비트 이하로 작을 수도 있다는 것을 의미한다.
프리픽스 테이블 (314) 및 트랜지트 테이블 (316) 에 관한 위의 기재 및 위의 예로부터, 프리픽스 값, 즉 해시 값 (206) 의 프리픽스 필드 (304) 에서의 비트들이 프리픽스 테이블 (314) 및 트랜지트 테이블 (316) 의 조합으로부터 추론될 수 있다는 것을 알 수 있다. 따라서, 버킷 (310) 또는 요약 테이블 (320) 의 임의의 다른 부분에서 명시적으로 프리픽스 값을 저장할 필요가 없다.
도 1 내지 도 3 을 다시 참조하면, 예를 들어 levelDB (키에 의해 저장된 데이터를 갖는 키-값 스토어) 에서, 블룸 필터 (Bloom filer) 의 사용과 상이한 본 실시형태에서의 압축된 인덱스들을 사용 및 요약 테이블 (320) 의 2 개의 중요한 양태들이 있다. 블룸 필터는 확률론적 필터이고, 이는 멤버십의 가능도를 표시할 수 있지만 멤버가 블룸 필터에 명확히 존재하는 것을 표시할 수 없다. 따라서, 블룸 필터는 포지티브 멤버십에 관하여 결정론적이지 않다. 버킷 어드레스 값, 프리픽스 값 및 시그니처 값, 즉 버킷 어드레스 필드 (302), 프리픽스 필드 (304), 및 시그니처 필드 (306) 의 비트들을 매칭하는 버킷 (310) 에 대한 요약 테이블 (320) 에서의 탐색을 고려한다. 블룸 필터와 대조적으로, 요약 테이블 (320) 의 제 1 양태는, 그러한 탐색이 그러한 버킷 (310) 을 발견하는 경우, 이것은 해시 테이블 (120) 에 명확히 엔트리가 있다는 것을 표시하며, 이들은 해시 값 (206) 에서의 비트들과 정확히 동일하다. 따라서, 요약 테이블 (320) 에 의한 탐색은 해시 테이블 (120) 에서의 엔트리의 존재에 관하여 결정론적인 반면, 블룸 필터는 결정론적이지 않다. 게다가, 시그니처 값이 해시 값 (206) 의 나머지 비트들 모두를 사용하는 실시형태들이 있으며, 즉 요약 테이블 (320) 을 구성하기 위해 사용될 때, 해시 값 (206) 으로부터 절단되는 비트들이 없고 절단 필드 (308) 가 없다. 따라서, 해시 값 (206) 을 매칭 (즉, 함유 또는 포함) 하는 요약 테이블 (320) 에 있어서 버킷 (310) 의 포지티브 발견은 전체 해시 값 (206) 이 대응 해시 테이블 (120) 에 명확히 있다는 것을 표시한다. 블룸 필터는 이러한 기능을 달성할 수 없다.
압축된 인덱스들의 사용 및 요약 테이블 (120) 의 제 2 양태는, 요약 테이블 (320) 이 대응 해시 테이블 (120) 에서 엔트리들의 로컬리티 (locality) 를 갖거나 보존하는 것이다. 블룸 필터는, 멤버가 존재할 가능성이 있는 표시하더라도 (그렇게 결정론적으로는 아님), 해시 테이블에서 멤버를 발견하는 곳을 표시할 수 없다. 대조적으로, 요약 테이블 (320) 은 해시 값 (206) 을 발견하는 곳을 대략적으로 표시할 수 있다. 예를 들어, 요약 테이블 (320) 이, 키 (202) 가 버킷 (320) 에 있다고 표시하는 것을 가정한다 (예를 들어, 이는 키 (202) 의 해시 값 (206) 을 사용한 탐색이 매칭 버킷 (310) 을 찾게 되기 때문이다). 시그니처 테이블 (318) 및 트랜지트 테이블 (316) 의 양자는 버킷에서의 엔트리들의 근접도를 표시하고, 이것은 대응 해시 테이블 (120) 에서의 엔트리들의 근접도에 대응한다. 해시들은 해시 테이블 (120) 에서와 동일한 순서로, 요약 테이블 (320) 에서 그리고 시그니처 테이블 (318) 에서 저장된다. 시그니처 테이블 (318) 및 트랜지트 테이블 (316) 은 해시 테이블 (120) 에서의 해시 값들 (206) 의 로컬리티에 관하여 힌트들을 제공한다. 따라서, 버킷 (310) 은 해시 값들 (206) 의 로컬리티를 인코딩하며, 이 로컬리티는 해시 테이블 (120) 에서 보기 위한 곳을 표시한다.
도 1 내지 도 3 을 계속 참조하면, 해시 피라미드 (116) 에서의 해시 테이블들 (120), 및 대응 요약 테이블들 (114) 의 다중 레벨들의 일 양태는 스토리지 시스템 (102) 에서의 메모리 (106) 의 타입들 또는 다른 적절한 컴퓨팅 디바이스에 있어서 데이터 구조들의 유연한 관리를 위해 제공된다. 시스템은, 빠른 (예를 들어, 몇 분 마다) 곳부터 느리거나 드믄 (예를 들어, 일들, 주들, 달들 이상) 곳일 수 있는, 다양한 간격들로 해시 테이블들 (120) 및 대응 요약 테이블들 (114) 을 만들어 낼 수 있고, 메모리 (106) 의 메타데이터 섹션 (110) 에 대응 해시 테이블들 (120) 을 저장 또는 캐싱하면서, 로컬 메모리 (106) 의 내부 또는 외부로 하나 이상의 요약 테이블들 (114) 을 이동할 수 있다. 예를 들어, 현재 및 잦은 사용에서의 최근 해시 테이블 (120), 또는 해시 테이블들의 수개의 레벨들은 메타데이터 섹션 (110) 으로 이동될 수 있는 한편, 대응 요약 테이블들 (114) 은 로컬 메모리 (108) 에 있고, 해시 피라미드 (116) 의 더 깊은 레벨들에서 다른 덜 빈번하게 사용된 해시 테이블들은 오프-라인 또는 스토리지 시스템 (102) 의 다른 곳에 저장된다. 해시 피라미드 (116) 의 레벨들 및 덜 빈번하게 사용된 해시 테이블들에 대한 요약 테이블들 (114) 은 메타데이터 섹션 (110) 에 저장될 수 있고, 필요할 때 또는 요구에 기초하여 로컬 메모리 (108) 에 이동되거나 캐시될 수 있다. 메모리의 다양한 타입들 (예를 들어, 상이한 메모리 타입들, 사이즈들, 비용들 및/또는 액세스 속도들) 을 갖는 다양한 배열들 및 해시 테이블들 (120) 및 해시 피라미드 (116) 의 다양한 레벨들 및 대응 요약 테이블들 (114) 이 구현의 구체적인 것들에 따라 쉽게 창안된다.
추가적인 예에서, 듀플리케이션 (예를 들어, 백업 런에서 또는 백업 런 후에) 을 수행하는 시스템은 로컬 메모리 (108) 에서의 최근 듀플리케이션 런에 대응하는 하나 이상의 요약 테이블들 (114), 및 메타데이터 섹션 (110) 에서의 대응 해시 테이블들을 유지할 수 있다. 이전의 요약들 및 대응 해시 테이블들 (120) 은 스토리지 시스템 (102) 에서의 다른 곳에서 유지될 수 있다. 백업 런으로부터의 복원이 요청되는 경우, 적절한 요약 테이블들 (114) 및 해시 테이블들 (120) 이 스토리지 시스템 (102) 의 외부 또는 내부의 다른 위치들로부터 스토리지 시스템 (102) 내부로 이동될 수 있다. 일부 실시형태들에서, 스토리지 시스템 (102) 은 해시 피라미드 (116) 에서 해시 테이블들 (120) 을 가지며, 최신 해시 테이블들 (120) 의 하나 이상에 대응하는, 하나 이상의 요약 테이블들 (114) 을 로컬 메모리 (108) 에서 유지한다. 추가적인 시나리오들 및 대응 할당들이, 본 명세서에서의 교시들에 따라, 해시 테이블들 (120) 및 요약 테이블들 (114) 의 다양한 사용들을 위해 쉽게 창안된다.
도 4 는 도 3 의 요약 테이블을 사용하는, 압축된 인덱스들을 사용한 결정론적 탐색을 위한 방법의 플로우 다이어그램이다. 방법은 다양한 컴퓨팅, 통신 또는 스토리지 시스템들에서 실시될 수 있고, 그의 하나 이상의 프로세서들에 의해 실시될 수 있다. 도 4 의 플로우 다이어그램은 +64 경우를 생략하지만, 요약에서의 최대 값 위 및/또는 최소 값 아래의 값들이 해시 테이블에서 탐색되어야 하는 변형이 본 명세서에 기재된 실시형태들과 통합될 수도 있다. 액션 (402) 에서, 해시 테이블이 생성된다. 액션 (404) 에서, 대응 요약 테이블은 해시 테이블의 해시 값들에 기초하여 생성된다. 요약 테이블은 포맷을 가지며 도 3 을 참조하여 개시된 방식 또는 그 변형들로 구성된다. 액션 (406) 에서, 결정론적 탐색이 요약 테이블에서의 해시 값에 대해 수행된다. 이것은 도 3 을 참조하여 위에서 기재된 바와 같이, 해시 값의 비트 필드들에 기초한다. 결정 액션 (408) 에서, 해시 값의 버킷 어드레스 비트들, 프리픽스 비트들, 및 시그니처 피트들이 요약 테이블에서의 버킷에서 명확히 발견되는지 여부가 결정된다. 대답이 아니오 이면, 이들 비트들은 요약 테이블에서의 임의의 버킷에서 발견되지 않고, 액션 (410) 으로 브랜치들을 플로우하며, 해시 값에 대한 어떠한 탐색도 해시 테이블에서 수행되지 않는다. 버킷의 발견이 없는 것은 해시 값이 해시 테이블에 있지 않다는 명확한 대답이라는 것을 알아야 한다. 대답이 예 이면, 이들 비트들이 요약 테이블에서의 버킷에서 명확히 발견되고, 액션 (412) 로 플로우가 진행하며, 해시 값에 대한 탐색이 해시 테이블에서 수행된다. 버킷의 발견은 버킷 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들의 해시 값이 해시 테이블에 있다는 명확한 대답이다.
위의 방법에 대한 변형에 있어서, 하나의 접근법은 다음의 액션들을 수행할 수도 있다:
1. 버킷을 검색;
2. 설정된 프리픽스 비트를 구함. 프리픽스 비트가 설정되지 않으면, 종료: 버킷에 없음;
3. 프리픽스 비트가 설정되면 위에 기재된 바와 같이 프리픽스 및 트랜지트 테이블을 사용하여 엔트리들을 카운트;
4. 시그니처 비트들의 사이즈를 결정; 그리고
5. 해시 값의 시그니처 비트들에 대해 시그니처 테이블에서의 엔트리들을 비교.
여기에 설명된 방법들은 통상적인 범용 컴퓨터 시스템과 같은 디지털 프로세싱 시스템으로 수행될 수도 있음을 알아야 한다. 하나의 기능만을 수행하도록 설계 또는 프로그래밍된 특수 목적 컴퓨터들이 대안에서 이용될 수도 있다. 도 5 은 본 명세서에 기재된 실시형태들을 구현할 수도 있는 예시적인 컴퓨팅 디바이스를 나타내는 도시이다. 도 5 의 컴퓨팅 디바이스는 일부 실시형태들에 따라 압축된 인덱스들 및 요약 테이블을 사용한 결정론적 탐색을 위한 기능의 실시형태들을 수행하는데 이용될 수도 있다. 컴퓨팅 디바이스는 중앙 프로세싱 유닛 (CPU)(501) 을 포함하고 이 유닛은 버스 (505) 를 통하여 메모리 (503) 및 대용량 스토리지 디바이스 (507) 에 커플링된다. 대용량 스토리지 디바이스 (507) 는 일부 실시형태들에서, 원격이거나 또는 국부적일 수 있는 고정 디스크 드라이브 또는 플로피 디스크 드라이브와 같은 영구적인 데이터 스토리지 디바이스를 나타낸다. 일부 실시형태들에서, 대용량 스토리지 디바이스 (507) 는 백업 스토리지를 구현할 수 있다. 메모리 (503) 는 판독 전용 메모리, 랜덤 액세스 메모리 등을 포함할 수도 있다. 일부 실시형태들에서, 컴퓨팅 디바이스 상에 상주하는 애플리케이션들은 메모리 (503) 또는 대용량 스토리지 디바이스 (507) 와 같은 컴퓨터 판독가능 매체 상에 저장되거나 또는 매체를 통하여 액세스될 수도 있다. 애플리케이션들은 또한 컴퓨팅 디바이스의 네트워크 모뎀 또는 다른 네트워크 인터페이스를 통하여 변조되어 액세스되는 변조된 전자 신호들의 형태로 될 수도 있다. 일부 실시형태들에서, CPU (501) 가 범용 프로세서, 특수 목적 프로세서, 또는 특수 프로그래밍된 로직 디바이스에서 구현될 수도 있음을 알아야 한다.
디스플레이 (511) 는 버스 (505) 를 통하여 CPU (501), 메모리 (503) 및 대용량 스토리지 디바이스 (507) 와 통신한다. 디스플레이 (511) 는 본 명세서에 기재된 시스템과 연관된 임의의 가시화 툴들 또는 리포트들을 디스플레이하도록 구성된다. 입력/출력 디바이스 (509) 는 CPU (501) 에 커맨드 선택들에서의 정보를 통신하기 위하여 버스 (505) 에 커플링된다. 외부 디바이스들로부터 그리고 외부 디바이스들로의 데이터는 입력/출력 디바이스 (509) 를 통하여 통신될 수도 있다. CPU (501) 는 도 1 내지 도 4 를 참조하여 설명된 기능을 실시하도록 본 명세서에 기재된 기능을 실행하도록 정의될 수도 있다. 일부 실시형태들에서, 이러한 기능성을 구현하는 코드는 CPU (501) 와 같은 프로세서에 의한 실행을 위하여 메모리 (503) 또는 대용량 스토리지 디바이스 (507) 내에 저장될 수도 있다. 컴퓨팅 디바이스 상의 오퍼레이팅 시스템은 MS-DOSTM, MS-WINDOWSTM, OS/2TM, UNIXTM, LINUXTM, 또는 다른 알려진 오퍼레이팅 시스템들일 수도 있다. 본 명세서에 기재된 실시형태들은 또한, 물리 컴퓨팅 리소스들로 구현되는 가시화된 컴퓨팅 시스템과 함께 통합될 수도 있음을 알아야 한다.
상세한 예시적인 실시형태들이 본 명세서에 개시된다. 그러나, 본 명세서에 개시된 특정 기능적인 세부사항들은 실시형태들을 설명하는 목적을 나타내는 것에 불과하다. 그러나, 실시형태들은 많은 대안의 형태들로 구현될 수도 있고, 본 명세서에 기술된 실시형태들만으로 제한되는 것으로 간주되지 않아야 한다.
용어 제 1, 제 2 등은 여러 단계들, 또는 계산들을 설명하는데 본 명세서에서 이용될 수도 있지만, 이들 단계들 또는 계산들은 이들 용어로 제한되지 않아야 함을 이해해야 한다. 이들 용어들은 하나의 단계 또는 계산을 다른 것과 구분하기 위해서만 이용된다. 예를 들어, 본 개시물의 범위를 벗어남이 없이, 제 1 계산은 제 2 계산으로 지칭될 수도 있고, 유사하게, 제 2 단계는 제 1 단계로 지칭될 수도 있다. 본 명세서에서 사용되는 바와 같이, 용어 "및/또는" 및 "/" 기호는 연관되어 나열된 항목들 중 하나 이상의 임의의 그리고 모든 조합들을 포함한다.
본 명세서에서 사용된 바와 같이, 단수 형태들 "하나 (a)", "한 (an)" 및 "그 (the)"는, 문맥상 그렇지 않다고 명확하게 나타내지 않는 한, 복수의 형태들도 포함하는 것으로 의도된다. 용어 "포함한다", "포함하는", 구비한다" 및/또는 "구비하는" 은, 본 명세서에서 사용될 때, 언급된 피처들, 정수들, 단계들, 동작들, 엘리먼트들, 및/또는 컴포넌트들을 특정하지만, 하나 이상의 다른 피처들, 정수들, 단계들, 동작들, 엘리먼트들, 컴포넌트들, 및/또는 이들의 그룹들의 존재 또는 추가를 배제하는 것은 아님이 더 이해될 것이다. 따라서, 본 명세서에서 사용된 전문 용어는 특정 구체 예를 설명하려는 목적이며, 제한하려는 의도는 아니다.
또한, 일부 대안의 구현 예들에서, 언급된 기능들/동작들은 도면들에 표기된 순서 외로 발생할 수도 있음을 주지해야 한다. 예를 들어, 연속하여 도시된 2 개의 도면들은 실제로 실질적으로 동시에 실행될 수도 있거나, 또는 수반되는 기능/동작들에 의존하여 역순으로 종종 실행될 수도 있다.
위의 실시형태들을 유념하여 보면, 실시형태들은 컴퓨터 시스템들에 저장된 데이터를 수반하는 여러 컴퓨터 구현 동작들을 채용할 수도 있음을 이해해야 한다. 이들 동작들은 물리적 양들의 물리적 조작을 필요로 하는 것이다. 통상적으로, 필수적이진 않지만, 이러한 양들은 정보를 나타내는 전자적 신호들로서 저장, 전송, 병합, 비교 또는 그렇지 않으면 조작될 수 있는 전자적 신호 또는 자기적 신호의 형태를 취할 수도 있다. 또한, 수행된 조작들은 생산, 식별, 결정 또는 비교와 같은 용어를 지칭한다. 실시형태들의 부분을 형성하는 본 명세서에 기재된 동작들 중 임의의 것은 유용한 머신 동작들이다. 실시형태들은 또한 이들 동작들을 수행하기 위한 장치 또는 디바이스에 관한 것이다. 장치는 필요한 목적으로 특수하게 구성되거나 또는 장치는 컴퓨터에 저장된 컴퓨터 프로그램에 의해 선택적으로 활성화되거나 또는 구성된 범용 컴퓨터일 수 있다. 특히, 여러 범용 머신들은 본 명세서에 개시된 교시들에 따라 기록된 컴퓨터 프로그램들과 함께 이용될 수 있거나 또는 보다 특수화된 장치가 필요한 동작들을 수행하도록 구성하는 것이 보다 편리할 수도 있다.
모듈, 애플리케이션, 계층, 에이전트 또는 다른 메소드 동작가능 엔티티는 하드웨어, 펌웨어, 또는 프로세서 실행 소프트웨어 또는 이들의 조합으로서 구현될 수 있다. 소프트웨어 기반 실시형태가 본 명세서에 개시되는 경우 소프트웨어는 제어기와 같은 물리적 머신에서 구현될 수 있음을 알아야 한다. 예를 들어, 제어기는 제 1 모듈 및 제 2 모듈을 포함할 수 있다. 제어기는 예를 들어, 방법, 애플리케이션, 계층 또는 에이전트의 여러 액션들을 수행하도록 구성될 수 있다.
실시형태들은 또한 비일시적 컴퓨터 판독가능 매체 상에 컴퓨터 판독가능 코드로서 구현될 수 있다. 컴퓨터 판독가능 매체는 컴퓨터 시스템에 의해 이후에 판독될 수 있는 데이터를 저장할 수 있는 임의의 데이터 스토리지 디바이스이다. 컴퓨터 판독가능 매체의 예들은 하드 드라이브들, 네트워크 연결 스토리지 (NAS), 판독전용 메모리, 랜덤 액세스 메모리, CD-ROM들, CD-R들, CD-RW들, 자기 테이프들, 및 다른 광학 및 비광학 데이터 스토리지 디바이스들을 포함한다. 컴퓨터 판독가능 매체는 또한, 컴퓨터 판독가능 코드가 분산된 방식으로 저장 및 실행되도록 네트워크 커플링된 컴퓨터 시스템에 걸쳐 분산될 수 있다. 본 명세서에 기재된 실시형태들은 핸드 헬드 디바이스들, 테블릿들, 마이크로프로세서 시스템들, 마이크로프로세서 기반 또는 프로그래밍 컨슈머 전자 장치들, 미니컴퓨터들, 메인프레임 컴퓨터들 등을 포함한 여러 컴퓨터 시스템 구성들로 실시될 수도 있다. 실시형태들은 또한, 작업들이 유선 기반 또는 무선 네트워크를 통하여 링크되는 원격 프로세싱 디바이스들에 의해 수행되는 분산형 컴퓨팅 환경들에서 실시될 수 있다.
방법 동작들이 특정 순서로 설명되었지만, 다른 동작들이 설명된 동작들 사이에 수행될 수도 있고, 설명된 동작들은 이들이 약간 상이한 시간에 발생하도록 조정될 수도 있거나 또는 설명된 동작들이 프로세싱과 연관된 여러 간격들에서 프로세싱 동작들의 발생을 허용하는 시스템에 분산될 수도 있음을 이해해야 한다.
여러 실시형태들에서, 본 명세서에 기재된 설명된 방법들 및 메커니즘들의 하나 이상의 부분들은 클라우드 컴퓨팅 환경의 부분을 형성할 수도 있다. 이러한 실시형태들에서, 리소스들은 하나 이상의 여러 모델들에 따라 서비스들로서 인터넷을 통하여 제공될 수도 있다. 이러한 모델들은 IaaS (Infrastructure as a Service), PaaS (Platform as a Service), 및 SaaS (Software as a Service) 를 포함할 수도 있다. IaaS 에서, 컴퓨터 인프라스트럭처는 서비스로서 전달된다. 이러한 경우에, 컴퓨팅 장비는 일반적으로 서비스 제공자에 의해 소유 및 동작된다. PaaS 모델에서, 소프트웨어 솔루션들을 개발하기 위해 개발자들에 의해 이용된 소프트웨어 툴들 및 기초가 되는 장비는 서비스로서 제공되어 서비스 제공자에 의해 호스트될 수도 있다. SaaS 는 통상적으로 요구시 서비스로서 서비스 제공자 라이센싱 소프트웨어를 포함한다. 서비스 제공자는 소프트웨어를 호스트할 수도 있거나, 또는 소프트웨어를 주어진 기간 동안에 고객에 배치할 수도 있다. 위의 모델들 중 다수의 조합들이 가능성있게 고려된다.
여러 유닛들, 회로들, 또는 다른 컴포넌트들이 작업 또는 작업들을 수행"하도록 구성되는" 것으로서 기술 또는 청구될 수도 있다. 이러한 문맥에서, 어구 "하도록 구성되는" 은 유닛들/회로들/컴포넌트들이 동작 동안에 작업 또는 작업들을 수행하는 구조 (예를 들어, 회로) 를 포함하고 있음을 나타냄으로써 구조를 함축하는데 이용된다. 이로써, 유닛/회로/컴포넌트는 특정된 유닛/회로/컴포넌트가 현재 동작하는 않는 (예를 들어, 온이 아닌) 경우에도 작업을 수행하도록 구성하는 것이라 말할 수 있다. "하도록 구성되는" 언어로 이용되는 유닛들/회로들/컴포넌트들은 하드웨어, 예를 들어, 회로들, 동작을 구현하도록 실행가능한 메모리 저장 프로그램 명령들 등을 포함한다. 유닛/회로/컴포넌트가 하나 이상의 작업들을 수행 "하도록 구성되는" 것임을 인용하는 것은 유닛/회로/컴포넌트에 대해 35 U.S.C. 112, 제 6 패러그래프를 언급하는 것으로 명시적으로 의도되지 않는다. 추가로, "하도록 구성되는" 은 발행시 작업(들)을 수행할 수 있는 방식으로 동작하는 소프트웨어 및/또는 펌웨어 (예를 들어, FPGA 또는 범용 프로세서 실행 소프트웨어) 에 의해 조작되는 일반 구조 (예를 들어, 일반 회로) 를 포함할 수 있다. "하도록 구성되는" 은 또한 하나 이상의 작업들을 구현 또는 수행하도록 적응된 디바이스들 (예를 들어, 집적 회로들) 을 제조하는 제조 프로세스 (예를 들어, 반도체 제조 설비) 를 적응시키는 것을 포함할 수도 있다.
상술한 설명은 설명을 목적으로 특정 실시형태들을 참조로 설명되었다. 그러나, 예시적인 위의 논의들은 개시된 정확한 형태들로 본 발명을 제한하거나 배타적이 되도록 의도되지 않는다. 많은 변경들 및 변형들이 위의 교시들의 관점에서 가능하다. 실시형태들은 실시형태들의 원리들 및 그 실제적인 애플리케이션들을 가장 잘 설명하기 위하여 선택되고 설명되었으며, 이에 의해 당해 기술 분야의 당업자는 고려되는 특정 이용에 적합화될 수도 있는 실시형태들 및 여러 변형예들을 최상으로 이용할 수도 있다. 따라서, 본 실시형태들은 제한적인 것이 아니라 예시적인 것으로서 고려될 것이며, 본 발명은 본 명세서에서 주어진 세부사항들에 제한되지 않고, 첨부된 특허청구범위의 범위와 그 등가의 범위 내에서 수정될 수도 있다.

Claims (20)

  1. 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법으로서,
    상기 값을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 나누는 (breaking) 단계;
    상기 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스에서의 컨테이너를 결정하는 단계로서, 상기 컨테이너는 상기 컨테이너와 연관된 총 (aggregate) 값들에 의해 결정된 상기 프리픽스 비트들에 대응하여 설정된 비트들을 갖는 프리픽스 테이블 및 상기 컨테이너와 연관된 상기 총 값들에 의해 결정된 상기 시그니처 비트들을 포함하는 시그니처 테이블을 포함하는, 상기 컨테이너를 결정하는 단계; 및
    상기 프리픽스 및 시그니처 테이블들 및 결정된 상기 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하는 단계를 포함하는, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  2. 제 1 항에 있어서,
    상기 결과는 상기 값이 상기 해시 테이블에 포함되지 않는다는 결정인, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  3. 제 1 항에 있어서,
    각각의 컨테이너는, 상기 시그니처 테이블로부터의 시그니처 비트들의 대응 세트가 상기 시그니처 테이블로부터의 시그니처 비트들의 이전 세트와 동일한 프리픽스를 갖는지 여부를 표시하는 트랜지트 (transit) 테이블을 갖는, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  4. 제 1 항에 있어서,
    상기 방법은, 트랜지트 테이블, 프리픽스 테이블, 및 시그니처 테이블을 사용하여 상기 값이 상기 해시 테이블에 포함되는지 여부를 결정하는, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  5. 제 1 항에 있어서,
    탐색되고 있는 상기 값은 상기 해시 테이블에 저장된 키의 전부인, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  6. 제 1 항에 있어서,
    상기 결과를 결정하는 단계는, 원하는 값이 발견되게 되는 상기 해시 테이블에서의 대략적인 위치를 표시하는, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  7. 제 1 항에 있어서,
    상기 압축된 인덱스를 사용하여 상기 컨테이너를 결정하는 단계는,
    컨테이너를 식별하는 단계;
    식별된 상기 컨테이너의 프리픽스 테이블이 상기 값의 상기 프리픽스 비트들에 따라 설정된 비트를 갖는지 여부를 결정하는 단계; 및
    상기 식별된 컨테이너의 상기 시그니처 테이블이 상기 값으로부터 상기 시그니처 비트들을 갖는지 여부를 결정하는 단계를 포함하는, 해시 테이블에 값이 저장되는지를 결정하기 위한 프로세서 기반 방법.
  8. 프로세서에 의해 실행될 때, 상기 프로세서로 하여금, 방법을 수행하게 하는 명령들을 갖는, 유형의 비일시적 컴퓨터 판독가능 매체로서,
    상기 방법은,
    값의 비트들을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 분리하는 단계;
    상기 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스를 사용하는 컨테이너를 결정하는 단계로서, 상기 컨테이너는 상기 컨테이너와 연관된 총 값들에 의해 결정된 상기 프리픽스 비트들에 따라 설정된 비트들을 갖는 프리픽스 테이블 및 상기 컨테이너와 연관된 상기 총 값들에 의해 결정된 상기 시그니처 비트들을 포함하는 시그니처 테이블을 포함하는, 상기 컨테이너를 결정하는 단계; 및
    상기 프리픽스 및 시그니처 테이블들 및 결정된 상기 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하는 단계를 포함하는, 유형의 비일시적 컴퓨터 판독가능 매체.
  9. 제 8 항에 있어서,
    상기 결과를 결정하는 단계는 상기 값이 상기 해시 테이블에 포함되지 않음을 결정하는 단계를 포함하는, 유형의 비일시적 컴퓨터 판독가능 매체.
  10. 제 8 항에 있어서,
    각각의 컨테이너는, 상기 시그니처 테이블로부터의 시그니처 비트들의 대응 세트가 상기 시그니처 테이블로부터의 시그니처 비트들의 이전 세트와 동일한 프리픽스를 갖는지 여부를 표시하는 트랜지트 테이블을 갖는, 유형의 비일시적 컴퓨터 판독가능 매체.
  11. 제 8 항에 있어서,
    트랜지트 테이블, 프리픽스 테이블, 및 시그니처 테이블은 상기 값이 해시 테이블에 포함되는지 여부를 결정하기 위해 사용되는, 유형의 비일시적 컴퓨터 판독가능 매체.
  12. 제 8 항에 있어서,
    상기 값은 해시 테이블에 저장된 키의 전부인, 유형의 비일시적 컴퓨터 판독가능 매체.
  13. 제 8 항에 있어서,
    상기 값으로의 상기 컨테이너의 매치는,
    컨테이너를 식별하는 단계;
    상기 값의 상기 프리픽스 비트들에 따라 상기 컨테이너의 상기 프리픽스 테이블에서 설정된 비트를 발견하는 단계; 및
    상기 컨테이너의 상기 시그니처 테이블에서 상기 값의 상기 시그니처 비트들을 발견하는 단계를 포함하는, 유형의 비일시적 컴퓨터 판독가능 매체.
  14. 제 8 항에 있어서,
    상기 컨테이너는 복수의 컨테이너들의 트랜지트 테이블들로 해시 테이블의 해시 값들의 로컬리티 (locality) 를 인코딩하는 것을 포함하는 요약 테이블에서의 상기 복수의 컨테이너들 중 하나인, 유형의 비일시적 컴퓨터 판독가능 매체.
  15. 컴퓨팅, 통신 또는 스토리지 시스템으로서,
    하나 이상의 프로세서들을 포함하고,
    상기 하나 이상의 프로세서들은,
    값을 어드레스 비트들, 프리픽스 비트들 및 시그니처 비트들로 나누고,
    상기 어드레스 비트들에 의해 특정된 어드레스에서 압축된 인덱스를 사용하여 컨테이너를 결정하는 것으로서, 상기 컨테이너는 상기 컨테이너와 연관된 총 값들에 의해 결정된 상기 프리픽스 비트들에 따라 비트들을 갖는 프리픽스 테이블 및 상기 컨테이너와 연관된 상기 총 값들에 의해 결정된 상기 시그니처 비트들을 포함하는 시그니처 테이블을 포함하는, 상기 컨테이너를 결정하며, 그리고
    상기 프리픽스 및 시그니처 테이블들 및 결정된 상기 프리픽스 및 시그니처 비트들의 함수에 기초하여 결과를 결정하도록 구성되고,
    상기 하나 이상의 프로세서들은 상기 값이 해시 테이블에 저장되는지를 결정하는, 컴퓨팅, 통신 또는 스토리지 시스템.
  16. 제 15 항에 있어서,
    상기 결과는 상기 값이 상기 해시 테이블에 포함되지 않는다는 결정인, 컴퓨팅, 통신 또는 스토리지 시스템.
  17. 제 15 항에 있어서,
    상기 하나 이상의 프로세서들이, 복수의 컨테이너들을 갖는 요약 테이블을 생성하도록 구성되는 것을 더 포함하고,
    각각의 컨테이너는, 상기 시그니처 테이블로부터의 시그니처 비트들의 대응 세트가 상기 시그니처 테이블로부터의 시그니처 비트들의 이전 세트와 동일한 프리픽스를 갖는지 여부를 표시하는 트랜지트 테이블을 갖는, 컴퓨팅, 통신 또는 스토리지 시스템.
  18. 제 15 항에 있어서,
    상기 하나 이상의 프로세서들은, 트랜지트 테이블, 프리픽스 테이블, 및 시그니처 테이블을 사용하여 상기 값이 상기 해시 테이블에 포함되는지 여부를 결정하는, 컴퓨팅, 통신 또는 스토리지 시스템.
  19. 제 15 항에 있어서,
    탐색되고 있는 상기 값은 상기 해시 테이블에 저장된 키의 전부인, 컴퓨팅, 통신 또는 스토리지 시스템.
  20. 제 15 항에 있어서,
    상기 결과를 결정하는 것은, 원하는 값이 발견되는 상기 해시 테이블에서의 대략적인 위치를 표시하는, 컴퓨팅, 통신 또는 스토리지 시스템.
KR1020160052404A 2015-09-04 2016-04-28 압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색 KR20170028825A (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US201514846566A 2015-09-04 2015-09-04
US14/846,566 2015-09-04

Publications (1)

Publication Number Publication Date
KR20170028825A true KR20170028825A (ko) 2017-03-14

Family

ID=58460238

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020160052404A KR20170028825A (ko) 2015-09-04 2016-04-28 압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색

Country Status (2)

Country Link
US (1) US11249999B2 (ko)
KR (1) KR20170028825A (ko)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN112868042A (zh) * 2018-09-11 2021-05-28 维萨国际服务协会 使用共享散列图进行欺诈管理的系统、方法和计算机程序产品
US11048623B2 (en) 2018-02-06 2021-06-29 Samsung Electronics Co., Ltd. Memory controller including mapping tables to efficiently process an iteration command and a method of operating the same

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10977315B2 (en) * 2019-03-01 2021-04-13 Cyborg Inc. System and method for statistics-based pattern searching of compressed data and encrypted data
US11520738B2 (en) * 2019-09-20 2022-12-06 Samsung Electronics Co., Ltd. Internal key hash directory in table
US11502957B2 (en) * 2020-05-14 2022-11-15 Mellanox Technologies, Ltd. Avoiding markers for longest prefix match based on binary search tree algorithm
US11423028B2 (en) * 2020-08-21 2022-08-23 Cyborg Inc. System and method for encrypted search using hash vectorization models
US11461301B2 (en) 2020-09-13 2022-10-04 International Business Machines Corporation Database index optimization
US12117984B1 (en) * 2023-06-02 2024-10-15 Black Cape Inc. Systems and methods for event tracking
US11797508B1 (en) * 2023-06-02 2023-10-24 Black Cape Inc. Systems and methods for geospatial correlation

Family Cites Families (176)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5208813A (en) 1990-10-23 1993-05-04 Array Technology Corporation On-line reconstruction of a failed redundant array system
US5403639A (en) 1992-09-02 1995-04-04 Storage Technology Corporation File server having snapshot application data groups
DE9310582U1 (de) 1993-07-15 1993-09-23 Paul Hettich GmbH & Co, 32278 Kirchlengern Rasteinrichtung fuer schubkaesten o.dgl.
US6412045B1 (en) 1995-05-23 2002-06-25 Lsi Logic Corporation Method for transferring data from a host computer to a storage media using selectable caching strategies
US5832529A (en) 1996-10-11 1998-11-03 Sun Microsystems, Inc. Methods, apparatus, and product for distributed garbage collection
US5940838A (en) 1997-07-11 1999-08-17 International Business Machines Corporation Parallel file system and method anticipating cache usage patterns
US6038639A (en) 1997-09-09 2000-03-14 Storage Technology Corporation Data file storage management system for snapshot copy operations
US6286056B1 (en) 1998-06-26 2001-09-04 Seagate Technology Llc Data storage device with small computer system interface providing persistent reservations
US6799283B1 (en) 1998-12-04 2004-09-28 Matsushita Electric Industrial Co., Ltd. Disk array device
JP2000181803A (ja) 1998-12-18 2000-06-30 Fujitsu Ltd 鍵管理機能付電子データ保管装置および電子データ保管方法
US6834298B1 (en) 1999-09-21 2004-12-21 Siemens Information And Communication Networks, Inc. System and method for network auto-discovery and configuration
US6804755B2 (en) 2000-06-19 2004-10-12 Storage Technology Corporation Apparatus and method for performing an instant copy of data based on a dynamically changeable virtual mapping scheme
US6912537B2 (en) 2000-06-20 2005-06-28 Storage Technology Corporation Dynamically changeable virtual mapping scheme
US6804703B1 (en) 2000-06-22 2004-10-12 International Business Machines Corporation System and method for establishing persistent reserves to nonvolatile storage in a clustered computer environment
JP2002108573A (ja) 2000-09-28 2002-04-12 Nec Corp ディスクアレイ装置、そのエラー制御方法、ならびにその制御プログラムを記録した記録媒体
US6954881B1 (en) 2000-10-13 2005-10-11 International Business Machines Corporation Method and apparatus for providing multi-path I/O in non-concurrent clustering environment using SCSI-3 persistent reserve
US6757769B1 (en) 2000-11-28 2004-06-29 Emc Corporation Cooperative lock override procedure
US6718448B1 (en) 2000-11-28 2004-04-06 Emc Corporation Queued locking of a shared resource using multimodal lock types
US6850938B1 (en) 2001-02-08 2005-02-01 Cisco Technology, Inc. Method and apparatus providing optimistic locking of shared computer resources
EP1370945B1 (en) 2001-02-13 2010-09-08 Candera, Inc. Failover processing in a storage system
US6986015B2 (en) 2001-12-10 2006-01-10 Incipient, Inc. Fast path caching
US6973549B1 (en) 2001-12-10 2005-12-06 Incipient, Inc. Locking technique for control and synchronization
US8103754B1 (en) 2002-05-02 2012-01-24 Hewlett-Packard Development Company, L.P. Reserving a shared volume in a multiple node data storage system
US7260628B2 (en) 2002-09-06 2007-08-21 Hitachi, Ltd. Event notification in storage networks
EP1547342B1 (en) * 2002-09-12 2014-07-23 International Business Machines Corporation A method and apparatus for deep packet processing
US7216164B1 (en) 2002-10-09 2007-05-08 Cisco Technology, Inc. Methods and apparatus for determining the performance of a server
US7028218B2 (en) 2002-12-02 2006-04-11 Emc Corporation Redundant multi-processor and logical processor configuration for a file server
US20070162954A1 (en) 2003-04-07 2007-07-12 Pela Peter L Network security system based on physical location
US7272674B1 (en) 2003-06-30 2007-09-18 Veritas Operating Corporation System and method for storage device active path coordination among hosts
US7424498B1 (en) 2003-06-30 2008-09-09 Data Domain, Inc. Probabilistic summary data structure based encoding for garbage collection
US7865485B2 (en) 2003-09-23 2011-01-04 Emc Corporation Multi-threaded write interface and methods for increasing the single file read and write throughput of a file server
JP4426262B2 (ja) 2003-11-26 2010-03-03 株式会社日立製作所 ディスクアレイ装置及びディスクアレイ装置の障害回避方法
US8560747B1 (en) 2007-02-16 2013-10-15 Vmware, Inc. Associating heartbeat data with access to shared resources of a computer system
JP4456909B2 (ja) 2004-03-29 2010-04-28 株式会社日立製作所 バックアップ方法、ストレージシステム及びそのプログラム
JP2005293774A (ja) 2004-04-02 2005-10-20 Hitachi Global Storage Technologies Netherlands Bv ディスク装置の制御方法
US7424482B2 (en) 2004-04-26 2008-09-09 Storwize Inc. Method and system for compression of data for block mode access storage
US7139907B2 (en) 2004-04-29 2006-11-21 International Business Machines Corporation Method and apparatus for implementing distributed SCSI devices using enhanced adapter reservations
US7313636B2 (en) 2004-06-15 2007-12-25 Lsi Corporation Methods and structure for supporting persistent reservations in a multiple-path storage environment
US20060074940A1 (en) 2004-10-05 2006-04-06 International Business Machines Corporation Dynamic management of node clusters to enable data sharing
US7363444B2 (en) 2005-01-10 2008-04-22 Hewlett-Packard Development Company, L.P. Method for taking snapshots of data
US7685136B2 (en) * 2005-01-12 2010-03-23 International Business Machines Corporation Method, system and program product for managing document summary information
US7913300B1 (en) 2005-04-08 2011-03-22 Netapp, Inc. Centralized role-based access control for storage servers
US7577802B1 (en) 2005-04-18 2009-08-18 Netapp, Inc. Accessing a reservable device by transiently clearing a persistent reservation on the device in multi-host system
US8200887B2 (en) 2007-03-29 2012-06-12 Violin Memory, Inc. Memory management system and method
WO2006123416A1 (ja) 2005-05-19 2006-11-23 Fujitsu Limited ディスク故障復旧方法及びディスクアレイ装置
US8364845B2 (en) 2005-05-19 2013-01-29 Wyse Technology Inc. Method and system for thin client configuration
US7933936B2 (en) 2005-06-10 2011-04-26 Network Appliance, Inc. Method and system for automatic management of storage space
US7979613B2 (en) 2005-07-15 2011-07-12 International Business Machines Corporation Performance of a storage system
JP2007087036A (ja) 2005-09-21 2007-04-05 Hitachi Ltd スナップショット維持装置及び方法
JP4662548B2 (ja) 2005-09-27 2011-03-30 株式会社日立製作所 スナップショット管理装置及び方法並びにストレージシステム
ITVA20050061A1 (it) 2005-11-08 2007-05-09 St Microelectronics Srl Metodo di gestione di un dispositivo di memoria non volatile e relativa memoria
JP4684864B2 (ja) 2005-11-16 2011-05-18 株式会社日立製作所 記憶装置システム及び記憶制御方法
JP2007199953A (ja) 2006-01-25 2007-08-09 Fujitsu Ltd ディスクアレイ装置およびディスクアレイ制御方法
JP4927408B2 (ja) 2006-01-25 2012-05-09 株式会社日立製作所 記憶システム及びそのデータ復元方法
US7743197B2 (en) 2006-05-11 2010-06-22 Emulex Design & Manufacturing Corporation System and method for virtualizing PCIe devices
JP2007233903A (ja) 2006-03-03 2007-09-13 Hitachi Ltd 記憶制御装置及び記憶制御装置のデータ回復方法
US8832247B2 (en) 2006-03-24 2014-09-09 Blue Coat Systems, Inc. Methods and systems for caching content at multiple levels
US20080034167A1 (en) 2006-08-03 2008-02-07 Cisco Technology, Inc. Processing a SCSI reserve in a network implementing network-based virtualization
US7987438B2 (en) 2006-08-10 2011-07-26 International Business Machines Corporation Structure for initializing expansion adapters installed in a computer system having similar expansion adapters
US7555599B2 (en) 2006-09-06 2009-06-30 International Business Machines Corporation System and method of mirrored RAID array write management
US7475215B2 (en) 2006-09-08 2009-01-06 Lsi Corporation Identification of uncommitted memory blocks during an initialization procedure
US7827218B1 (en) * 2006-11-18 2010-11-02 X-Engines, Inc. Deterministic lookup using hashed key in a multi-stride compressed trie structure
WO2008065695A1 (fr) 2006-11-27 2008-06-05 Fujitsu Limited Programme de gestion de serveur, programme de gestion de serveur de messagerie, système de gestion de serveur et procédé de gestion de serveur
US7949847B2 (en) 2006-11-29 2011-05-24 Hitachi, Ltd. Storage extent allocation method for thin provisioning storage
US8694712B2 (en) 2006-12-05 2014-04-08 Microsoft Corporation Reduction of operational costs of virtual TLBs
US20080155191A1 (en) 2006-12-21 2008-06-26 Anderson Robert J Systems and methods for providing heterogeneous storage systems
US8370562B2 (en) 2007-02-25 2013-02-05 Sandisk Il Ltd. Interruptible cache flushing in flash memory systems
US9632870B2 (en) 2007-03-29 2017-04-25 Violin Memory, Inc. Memory system with multiple striping of raid groups and method for performing the same
JP4529990B2 (ja) 2007-03-30 2010-08-25 ブラザー工業株式会社 画像処理プログラム及び画像処理装置
JP4900811B2 (ja) 2007-03-30 2012-03-21 株式会社日立製作所 記憶システムおよび記憶制御方法
US7958303B2 (en) 2007-04-27 2011-06-07 Gary Stephen Shuster Flexible data storage system
US8086652B1 (en) 2007-04-27 2011-12-27 Netapp, Inc. Storage system-based hole punching for reclaiming unused space from a data container
US7991942B2 (en) 2007-05-09 2011-08-02 Stmicroelectronics S.R.L. Memory block compaction method, circuit, and system in storage devices based on flash memories
KR101059302B1 (ko) 2007-05-30 2011-08-24 후지쯔 가부시끼가이샤 화상 암호화 장치, 화상 암호화 방법, 및 기록 매체
US7765426B2 (en) 2007-06-07 2010-07-27 Micron Technology, Inc. Emerging bad block detection
US8874854B2 (en) 2007-07-30 2014-10-28 International Business Machines Corporation Method for selectively enabling and disabling read caching in a storage subsystem
US7941598B2 (en) 2007-08-08 2011-05-10 Hitachi, Ltd. Method and apparatus for capacity on demand dynamic chunk allocation
US8495111B1 (en) * 2007-09-28 2013-07-23 Symantec Corporation System and method of hierarchical space management for storage systems
US7970994B2 (en) 2008-03-04 2011-06-28 International Business Machines Corporation High performance disk array rebuild
US8352540B2 (en) 2008-03-06 2013-01-08 International Business Machines Corporation Distinguishing data streams to enhance data storage efficiency
US7873619B1 (en) 2008-03-31 2011-01-18 Emc Corporation Managing metadata
US8621241B1 (en) 2008-04-25 2013-12-31 Netapp, Inc. Storage and recovery of cryptographic key identifiers
US8117464B1 (en) 2008-04-30 2012-02-14 Netapp, Inc. Sub-volume level security for deduplicated data
US9678879B2 (en) 2008-05-29 2017-06-13 Red Hat, Inc. Set partitioning for encoding file system allocation metadata
US8468320B1 (en) * 2008-06-30 2013-06-18 Symantec Operating Corporation Scalability of data deduplication through the use of a locality table
US8296547B2 (en) 2008-08-27 2012-10-23 International Business Machines Corporation Loading entries into a TLB in hardware via indirect TLB entries
US20100057673A1 (en) 2008-09-04 2010-03-04 Boris Savov Reusable mapping rules for data to data transformation
US20100077205A1 (en) 2008-09-19 2010-03-25 Ekstrom Joseph J System and Method for Cipher E-Mail Protection
US8756369B2 (en) 2008-09-26 2014-06-17 Netapp, Inc. Priority command queues for low latency solid state drives
US7814149B1 (en) * 2008-09-29 2010-10-12 Symantec Operating Corporation Client side data deduplication
US7910688B2 (en) 2008-10-22 2011-03-22 Evonik Stockhausen Inc. Recycling superabsorbent polymer fines
US9047330B2 (en) * 2008-10-27 2015-06-02 Ianywhere Solutions, Inc. Index compression in databases
JP4399021B1 (ja) 2008-10-29 2010-01-13 株式会社東芝 ディスクアレイ制御装置および記憶装置
US7945733B2 (en) 2008-12-12 2011-05-17 Lsi Corporation Hierarchical storage management (HSM) for redundant array of independent disks (RAID)
US8200922B2 (en) 2008-12-17 2012-06-12 Netapp, Inc. Storage system snapshot assisted by SSD technology
US20110258362A1 (en) 2008-12-19 2011-10-20 Mclaren Moray Redundant data storage for uniform read latency
US8312204B2 (en) 2009-01-23 2012-11-13 Seagate Technology Llc System and method for wear leveling in a data storage device
JP4869368B2 (ja) 2009-03-12 2012-02-08 株式会社東芝 ストレージ装置及び仮想化装置
US7941584B2 (en) 2009-03-26 2011-05-10 Arm Limited Data processing apparatus and method for performing hazard detection
US8205065B2 (en) 2009-03-30 2012-06-19 Exar Corporation System and method for data deduplication
US8560787B2 (en) 2009-03-30 2013-10-15 International Business Machines Corporation Incremental backup of source to target storage volume
TWI397009B (zh) 2009-04-30 2013-05-21 Inventec Corp 基本輸入輸出系統的資料處理裝置
US8180955B2 (en) 2009-05-06 2012-05-15 Via Telecom, Inc. Computing systems and methods for managing flash memory device
EP2302638B1 (fr) 2009-09-21 2013-04-17 STMicroelectronics (Rousset) SAS Procédé d'écriture et de lecture de données dans une mémoire non volatile, au moyen de métadonnées
US8510569B2 (en) 2009-12-16 2013-08-13 Intel Corporation Providing integrity verification and attestation in a hidden execution environment
US9134918B2 (en) 2009-12-31 2015-09-15 Sandisk Technologies Inc. Physical compression of data with flat or systematic pattern
US8452932B2 (en) 2010-01-06 2013-05-28 Storsimple, Inc. System and method for efficiently creating off-site data volume back-ups
US9059851B2 (en) 2010-02-23 2015-06-16 Salesforce.Com, Inc. Method and computer program product for order preserving symbol based encryption
JP4892072B2 (ja) 2010-03-24 2012-03-07 株式会社東芝 ホスト装置と連携して重複データを排除するストレージ装置、同ストレージ装置を備えたストレージシステム、及び同システムにおける重複排除方法
US8301811B1 (en) 2010-03-30 2012-10-30 Emc Corporation Techniques for performing online data migration while effectively migrating SCSI reservations between source and target arrays
US8738970B2 (en) 2010-07-23 2014-05-27 Salesforce.Com, Inc. Generating performance alerts
US8713268B2 (en) 2010-08-05 2014-04-29 Ut-Battelle, Llc Coordinated garbage collection for raid array of solid state disks
US8589625B2 (en) 2010-09-15 2013-11-19 Pure Storage, Inc. Scheduling of reconstructive I/O read operations in a storage environment
US8468318B2 (en) 2010-09-15 2013-06-18 Pure Storage Inc. Scheduling of I/O writes in a storage environment
US8775868B2 (en) 2010-09-28 2014-07-08 Pure Storage, Inc. Adaptive RAID for an SSD environment
US20120090035A1 (en) * 2010-10-12 2012-04-12 Synergetics Incorporated System and Tool for Logistics Data Management on Secured Smart Mobile Devices
US20120117029A1 (en) 2010-11-08 2012-05-10 Stephen Gold Backup policies for using different storage tiers
US9639543B2 (en) 2010-12-28 2017-05-02 Microsoft Technology Licensing, Llc Adaptive index for data deduplication
US8966184B2 (en) 2011-01-31 2015-02-24 Intelligent Intellectual Property Holdings 2, LLC. Apparatus, system, and method for managing eviction of data
US9563555B2 (en) 2011-03-18 2017-02-07 Sandisk Technologies Llc Systems and methods for storage allocation
US8595267B2 (en) 2011-06-27 2013-11-26 Amazon Technologies, Inc. System and method for implementing a scalable data storage service
US8751463B1 (en) 2011-06-30 2014-06-10 Emc Corporation Capacity forecasting for a deduplicating storage system
US8527544B1 (en) 2011-08-11 2013-09-03 Pure Storage Inc. Garbage collection in a storage system
US8806160B2 (en) 2011-08-16 2014-08-12 Pure Storage, Inc. Mapping in a storage system
US8793467B2 (en) 2011-09-30 2014-07-29 Pure Storage, Inc. Variable length encoding in a storage system
US8788788B2 (en) 2011-08-11 2014-07-22 Pure Storage, Inc. Logical sector mapping in a flash storage array
JP5768587B2 (ja) 2011-08-17 2015-08-26 富士通株式会社 ストレージシステム、ストレージ制御装置およびストレージ制御方法
US8700875B1 (en) 2011-09-20 2014-04-15 Netapp, Inc. Cluster view for storage devices
WO2013046273A1 (en) 2011-09-29 2013-04-04 Hitachi, Ltd. Reservation of volumes having a copy pair relationship
JP5735654B2 (ja) 2011-10-06 2015-06-17 株式会社日立製作所 格納データの重複排除方法、格納データの重複排除装置、及び重複排除プログラム
US8825605B2 (en) 2011-10-11 2014-09-02 Netapp, Inc. Deduplication aware scheduling of requests to access data blocks
US8918579B2 (en) 2012-02-06 2014-12-23 Sandisk Technologies Inc. Storage device and method for selective data compression
US9519647B2 (en) 2012-04-17 2016-12-13 Sandisk Technologies Llc Data expiry in a non-volatile device
US9075710B2 (en) 2012-04-17 2015-07-07 SanDisk Technologies, Inc. Non-volatile key-value store
US8996881B2 (en) 2012-04-23 2015-03-31 International Business Machines Corporation Preserving redundancy in data deduplication systems by encryption
US8793466B2 (en) 2012-04-27 2014-07-29 Netapp, Inc. Efficient data object storage and retrieval
US9645177B2 (en) 2012-05-04 2017-05-09 Seagate Technology Llc Retention-drift-history-based non-volatile memory read threshold optimization
US8874850B1 (en) 2012-05-10 2014-10-28 Netapp, Inc. Hierarchically tagged cache
US20130318314A1 (en) 2012-05-25 2013-11-28 Red Hat, Inc. Managing copies of data on multiple nodes using a data controller node to avoid transaction deadlock
US9501546B2 (en) 2012-06-18 2016-11-22 Actifio, Inc. System and method for quick-linking user interface jobs across services based on system implementation information
US8959305B1 (en) 2012-06-29 2015-02-17 Emc Corporation Space reclamation with virtually provisioned devices
US8838691B2 (en) * 2012-06-29 2014-09-16 International Business Machines Corporation Data de-duplication in service oriented architecture and web services environment
US9063937B2 (en) 2012-07-31 2015-06-23 Hewlett-Packard Development Company, L.P. Storage array reservation forwarding
US9489293B2 (en) 2012-08-17 2016-11-08 Netapp, Inc. Techniques for opportunistic data storage
US9176822B2 (en) 2012-08-31 2015-11-03 Cleversafe, Inc. Adjusting dispersed storage error encoding parameters
JP5954081B2 (ja) 2012-09-26 2016-07-20 富士通株式会社 ストレージ制御装置、ストレージ制御方法、およびストレージ制御プログラム
US9348757B2 (en) 2012-10-08 2016-05-24 International Business Machines Corporation System supporting multiple partitions with differing translation formats
WO2014076743A1 (en) 2012-11-19 2014-05-22 Hitachi, Ltd. Storage system
US9348840B2 (en) 2012-12-14 2016-05-24 Intel Corporation Adaptive data striping and replication across multiple storage clouds for high availability and performance
US9063967B2 (en) 2013-01-10 2015-06-23 Pure Storage, Inc. Performing copies in a storage system
US9886346B2 (en) 2013-01-11 2018-02-06 Commvault Systems, Inc. Single snapshot for multiple agents
US9652376B2 (en) 2013-01-28 2017-05-16 Radian Memory Systems, Inc. Cooperative flash memory control
US8751763B1 (en) * 2013-03-13 2014-06-10 Nimbus Data Systems, Inc. Low-overhead deduplication within a block-based data storage
US9335932B2 (en) 2013-03-15 2016-05-10 Bracket Computing, Inc. Storage unit selection for virtualized storage units
US9471500B2 (en) * 2013-04-12 2016-10-18 Nec Corporation Bucketized multi-index low-memory data structures
US9519575B2 (en) 2013-04-25 2016-12-13 Sandisk Technologies Llc Conditional iteration for a non-volatile device
US9430412B2 (en) 2013-06-26 2016-08-30 Cnex Labs, Inc. NVM express controller for remote access of memory and I/O over Ethernet-type networks
US9785545B2 (en) 2013-07-15 2017-10-10 Cnex Labs, Inc. Method and apparatus for providing dual memory access to non-volatile memory
US10263770B2 (en) 2013-11-06 2019-04-16 Pure Storage, Inc. Data protection in a storage system using external secrets
US9516016B2 (en) 2013-11-11 2016-12-06 Pure Storage, Inc. Storage array password management
JP6233086B2 (ja) 2014-02-20 2017-11-22 富士通株式会社 ストレージ制御装置，ストレージシステム及び制御プログラム
US9798596B2 (en) 2014-02-27 2017-10-24 Commvault Systems, Inc. Automatic alert escalation for an information management system
US10656864B2 (en) 2014-03-20 2020-05-19 Pure Storage, Inc. Data replication within a flash storage array
US9361469B2 (en) 2014-03-26 2016-06-07 Amazon Technologies, Inc. Electronic communication with secure screen sharing of sensitive information
US9513820B1 (en) 2014-04-07 2016-12-06 Pure Storage, Inc. Dynamically controlling temporary compromise on data redundancy
US9294567B2 (en) 2014-05-02 2016-03-22 Cavium, Inc. Systems and methods for enabling access to extensible storage devices over a network as local storage via NVME controller
US9501245B2 (en) 2014-05-02 2016-11-22 Cavium, Inc. Systems and methods for NVMe controller virtualization to support multiple virtual machines running on a host
US9563509B2 (en) 2014-07-15 2017-02-07 Nimble Storage, Inc. Methods and systems for storing data in a redundant manner on a plurality of storage units of a storage system
US9489132B2 (en) 2014-10-07 2016-11-08 Pure Storage, Inc. Utilizing unmapped and unknown states in a replicated storage system
US10430282B2 (en) 2014-10-07 2019-10-01 Pure Storage, Inc. Optimizing replication by distinguishing user and system write activity
US9917776B2 (en) * 2014-10-16 2018-03-13 Cisco Technology, Inc. Hash-based address matching
US9565269B2 (en) 2014-11-04 2017-02-07 Pavilion Data Systems, Inc. Non-volatile memory express over ethernet
US9552248B2 (en) 2014-12-11 2017-01-24 Pure Storage, Inc. Cloud alert to replica
US9654397B2 (en) * 2015-03-13 2017-05-16 Mediatek Inc. Method for looking up data in hash tables and associated network device
US10235097B2 (en) 2015-07-21 2019-03-19 Samsung Electronics Co., Ltd. Area and performance optimized namespace sharing method in virtualized PCIE based SSD controller
US20170123676A1 (en) 2015-11-04 2017-05-04 HGST Netherlands B.V. Reference Block Aggregating into a Reference Set for Deduplication in Memory Management

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11048623B2 (en) 2018-02-06 2021-06-29 Samsung Electronics Co., Ltd. Memory controller including mapping tables to efficiently process an iteration command and a method of operating the same
CN112868042A (zh) * 2018-09-11 2021-05-28 维萨国际服务协会 使用共享散列图进行欺诈管理的系统、方法和计算机程序产品
US11797998B2 (en) 2018-09-11 2023-10-24 Visa International Service Association System, method, and computer program product for fraud management with a shared hash map
CN112868042B (zh) * 2018-09-11 2024-01-23 维萨国际服务协会 使用共享散列图进行欺诈管理的系统、方法和计算机程序产品

Also Published As

Publication number Publication date
US20190095490A1 (en) 2019-03-28
US11249999B2 (en) 2022-02-15

Similar Documents

Publication Publication Date Title
KR20170028825A (ko) 압축된 인덱스들을 사용한 해시 테이블들에서의 메모리 효율적인 스토리지 및 탐색
US10936556B2 (en) Generating a schema of a Not-only-Structured-Query-Language database
CN111247518B (zh) 用于数据库分片的方法和系统
US10552378B2 (en) Dividing a dataset into sub-datasets having a subset of values of an attribute of the dataset
US10915532B2 (en) Supporting a join operation against multiple NoSQL databases
CN110263043A (zh) 数据存储方法、数据查询方法、装置及存储介质
WO2013097546A1 (en) Assisting query and querying
US9886783B2 (en) Indexing and querying spatial graphs
US11475151B2 (en) Security policy management for database
WO2022121172A1 (zh) 文本纠错方法、装置、电子设备及计算机可读存储介质
TW202046142A (zh) 向量字串搜尋指令
US11409724B2 (en) Hashed balanced tree data structure
US9875275B2 (en) Efficient state change support for hierarchical data models in a virtualized system
JP7488798B2 (ja) 大きなデータをより小さな表現に変換する、およびより小さな表現を当初の大きなデータに戻して再変換するためのシステムおよび方法
CN105930104A (zh) 数据存储方法和装置
WO2024078122A1 (zh) 数据库表扫描的方法、装置以及设备
CN110362404B (zh) 一种基于sql的资源分配方法、装置和电子设备
US11042578B2 (en) Multigram index for database query
CN116842012A (zh) 一种Redis集群的分片存储方法、装置、设备及存储介质
CN111125090A (zh) 数据存取方法及装置
US10691828B2 (en) Method for securing access to a relation
US11435926B2 (en) Method, device, and computer program product for managing storage system
US11177824B2 (en) Dictionary embedded expansion procedure
CN112445800A (zh) 一种数据流水号的生成方法、系统及电子设备
US20190197138A1 (en) Data shuffling with hierarchical tuple spaces