[PostgreSQL] simplehash

dynahash의 단점(indirect function call)을 개선(실행할 코드가 컴파일 시점에 결정됨)한 hash table

---

commit b30d3ea824c (2016)

• dynahash.c 의 성능이 몇몇 use-case들에서 충분하지 못했다.
  • 충돌을 회피하기 위해 사용되는 chaining으로 인해 cache가 비효율적으로 사용되었다. chaining으로 연결된 element들은 논리적으로는 인접하지만 실제로 메모리 상에서는 연속하지 못하기 때문이다.
  • dynahash의 element size는 런타임에 결정되기 때문에 offset 계산의 비용이 높았다.
  • hash와 element 비교가 indirect function call방식으로 진행되어 pipeline stall이 발생했다.

• 이러한 문제점을 해결하려면 hash table이 컴파일 타임에 결정되어야 한다. 하지만 C에는 C++의 template처럼 컴파일 시점에 코드를 결정하는 방법을 제공하지 않는다. 그래서 약간 우아하지 못한 방법으로 구현했다. macro-templatized 헤더 파일을 사용해서 코드(prefix에 따른 함수와 타입)를 컴파일 시점에 생성한다.
• tidbitmap.c와 execGrouping.c에 simplehash를 사용하고 bitmap scan과 hash aggregation 등이 대부분의 시간을 차지하는 쿼리 에서 성능이 100% 이상 개선되는 것을 측정했다.
  • tidbitmap.c - bitmap scan
  • execGrouping.c - hash aggregation 등
• 뿐만 아니라 다른 use-case(예를 들면 catcache.c)에서도 이 simplehash는 유용할 수 있다.
• 이 해시테이블 설계는 linear open-addressing을 변형한 것이다. 단순 open-addressing 방법의 가장 큰 단점은 clustering으로 인해 lookup 시간의 편차가 매우 크다는 점과 삭제 연산에서 부가적인 표시(tombstone)를 매우 많이 남긴다는 점이다. 이런 문제를 해결하기 위해 robin hood hasing을 변형해서 적용했다.

• Robin hood hashing은 삽입할 element를 최적의 bucket에서 먼 곳에 삽입해야(poor element가 될 것 같은) 할 경우 최적의 bucket에 가까운 element들(rich element)을 최적의 bucket 근처로 옮기는 방식으로 chaining 길이를 최적화한다. 이것이 삽입 연산을 느리게 만들지만, 평균 lookup 시간이 매우 크게 개선되고 성능을 유지하면서 fill factor를 높게 유지할 수 있다.
• To avoid tombstones - which normally solve the issue that a deleted node's presence is relevant to determine whether a lookup needs to continue looking or is done - buckets following a deleted element are shifted backwards, unless they're empty or already at their optimal position.

• 이번에 도입한 simplehash의 구현을 다음과 같이 개선할 수 있다
  • 탐색하는 동안 거리를 종료의 기준으로 사용하는 것이다. 이것은 일반적으로 좋은 생각이지만, 몇몇 상황에서 overhead가 큰것을 확인할 수 있어서 그렇게 하지는 않았다.
  • 비어있는 상태를 hash값으로 통합하여 hash값 저장을 강제하는 것이다. 몇몇 상황에 대해 이 방법은 메모리 밀도를 높이고 instruction 몇 개를 제거할 수 있다.
  • fill factor를 조절하는 방법. 단, 매우 조심스럽게 선택해야 한다.
  • hashtable의 maximum size를 설정 가능하도록 변경해서 매우 큰 테이블들을 저장할 수 있도록 변경하는 것이다. 그렇게 하기 위해서는 64bit 해시값이 더 일반적으로 사용되어야 한다.

Introduction

• 이 파일(simplehash.h)을 include하면 매크로에 의해 사용자가 정의한 타입에 대해 template화된 open-addressing 해시테이블 구현이 생성된다.
• 단, 성능이나 메모리 공간에 예민하지 않은 타입에 대한 해시테이블 구현을 생성하는 것은 가치가 없다.
• dynahash에 비해 simplehash는 다음과 같은 장점을 가진다.
  • structure size를 미리 알고 있는 템플릿화된 코드가 생성되고 간점 함수 호출이 없어진다. 이러한 특징으로 인해 크기가 작은 entry들에 대해 성능(speed)이 크게 향상된다.
  • Open addressing 방식은 dynahash의 chained hashtable보다 CPU 캐시를 잘 활용한다.
  • 매크로로 생성된 코드의 인터페이스는 type-safe하고 dynahash보다 사용하기 쉽다. 대신 설정(setup)이 복잡하다.
  • MemoryContext 또는 다른 allocator에서 메모리를 할당받는다.
  • 별도의 memory context를 관리하지 않아 memory context를 유지하는데 필요한 ovearhead가 없다.

Usage

• 특정 use case에 필요한 hash-table과 함수 코드를 생성하기 위해서는 이 파일을 simplehash.h를 include하기 전에 몇몇 매크로들이 #define되어야 한다. 이 파일에서는 해당 매크로들을 #undef하여 이후에 새로운 타입에 대한 simplehash api가 생성될 수 있다.
• 정의해줘야 하는 매크로(parameter)들은 다음과 같다.
  • SH_PREFIX - 생성되는 모든 symbol에 붙일 접두사. 예를 들어 접두사를 'foo'로 설정하면 생성되는 해시테이블 구조체는 foo_hash, 함수는 foo_insert, foo_lookup등이 된다.
  • SH_ELEMENT_TYPE - 원소의 타입
  • SH_KEY_TYPE - 해시테이블의 키 타입
  • SH_DECLARE[on/off] - 정의하면 함수의 프로토타입과 타입 선언을 생성한다.
  • SH_DEFINE[on/off] - 정의하면 함수 정의를 생성한다.
  • SH_SCOPE - 함수의 scope(extern, static inline 등)를 지정한다.
  • SH_RAW_ALLOCATOR - 정의하면 전역 공간의 메모리 컨텍스트를 참조하지 않고 이 allocator에서 공간을 할당한다. 이 allocator는 반드시 반환한 공간을 0으로 초기화해야 한다.
  • SH_DEFINE이 정의된 경우 아래의 매크로를 정의할 수 있다.
    • SH_KEY - 해시 키를 가지는 SH_ELEMENT_TYPE 속 원소의 이름
    • SH_EQUAL(table, a, b) - table key 두 개를 비교한다.
    • SH_HASH_KEY(table, key) - 키에 대한 해시값을 계산한다.
    • SH_STORE_HASH[on/off] - 정의되면 해시값을 원소에 저장한다.
    • SH_GET_HASH(tb, a) - 해시값을 저장하는 필드를 반환한다.
• element 타입에는 status 필드가 있어야 한다. 이 필드에는 SH_STATUS enum 값을 저장할 수 있어야 한다.
• 실제 사용 예시는 tidbitmap.c와 execnodes.h/execGrouping.c에서 볼 수 있다.

SH_TYPE

/* type definitions */
typedef struct SH_TYPE
{
    /*
     * 데이터 또는 bucket array 크기.
     * 크기가 UINT32_MAX인 해시테이블의 크기까지 저장하기 위해 64비트를 사용한다.
     * 해시테이블에 저장된 원소 개수는 SH_MAX_FILLFACTOR보다 작다.
     */
    uint64      size;

    /* how many elements have valid contents */
    /* element중 유효한(삭제되지 않은) 데이터의 개수 */
    uint32      members;

    /* bucket과 크기 계산을 위한 mask. */
    uint32      sizemask;

    /* 이 값을 넘으면 해시테이블의 크기를 늘린다. */
    uint32      grow_threshold;

    /* hash buckets */
    SH_ELEMENT_TYPE *data;

#ifndef SH_RAW_ALLOCATOR
    /* 메모리 할당에 사용할 메모리 컨텍스트 */
    MemoryContext ctx;
#endif

    /* 사용자가 정의하는 데이터. 콜백함수에 전달하는 용도로 사용할 수 있다. */
    void       *private_data;
}           SH_TYPE;

SH_STATUS SH_ITERATOR

/* element의 상태를 나타낸다 */
typedef enum SH_STATUS
{
    SH_STATUS_EMPTY = 0x00,
    SH_STATUS_IN_USE = 0x01
} SH_STATUS;

typedef struct SH_ITERATOR
{
    uint32      cur;            /* 현재 원소의 인덱스 */
    uint32      end;
    bool        done;           /* iterator가 끝났는지를 나타낸다 */
}           SH_ITERATOR;

SH_COMPUTE_SIZE

/*
 * Compute allocation size for hashtable. Result can be passed to
 * SH_UPDATE_PARAMETERS.
 */
static inline uint64
SH_COMPUTE_SIZE(uint64 newsize)
{
    uint64      size;

    /* supporting zero sized hashes would complicate matters */
    size = Max(newsize, 2);

    /* round up size to the next power of 2, that's how bucketing works */
    size = pg_nextpower2_64(size);
    Assert(size <= SH_MAX_SIZE);

    /*
     * Verify that allocation of ->data is possible on this platform, without
     * overflowing Size.
     */
    if (unlikely((((uint64) sizeof(SH_ELEMENT_TYPE)) * size) >= SIZE_MAX / 2))
        sh_error("hash table too large");

    return size;
}

references

• PostgreSQL github repository
• src/include/lib/simplehash.h

---