Geohash 기반의 Geo API 개발.

[jhpark816]

ARCUS에서 GeoHash 기반의 GeoAPI를 개발한다.

참고 자료

• GeoHash wikipedia
  • https://en.wikipedia.org/wiki/Geohash
• Introducing the Geo API in Redis
  • https://cristian.regolo.cc/2015/07/07/introducing-the-geo-api-in-redis.html
• New Geo Features in MongoDB 2.4
  • https://www.mongodb.com/blog/post/new-geo-features-in-mongodb-24

[matteblack9]

위 링크들을 참고해서 생각해본 spec은 다음과 같습니다.
다음과 같이 정의했을 때, 발생하는 문제점이나, 수정 및 추가해야할 사항등이 있을까요?

• Sorted Set Data Structure를 사용하여 구현한다.
• <value>, <longitude>, <latitude> 로 구성된 데이터 집합을 value로 가지는 item을 가진다.

GEO 명령

• [Geo collection 생성: gop create]
  Geo element에 관한 명령은 아래와 같다.

• [Geo element 삽입: gop add]

• [Geo element 변경: gop update]

• [Geo element 삭제: gop delete]

• [Geo element 조회: gop pos]

• [Geo element 간 거리 조회: gop dist]

• [Geo element 근처에 있는 geo element 조회: gop raditem]

• [지정 좌표 근처에 있는 geo element 조회: gop radlocation]

• [Geo hash 조회: gop hash]

gop create (Geo Collection 생성)

Geo collection을 empty 상태로 생성한다.

gop create <key> <attributes> <hashlen> [noreply]\r\n
* <attributes>: <flags> <exptime> <maxcount> [<ovflaction>] [unreadable]

• <key> - 대상 item의 key string
• <attributes> - 설정할 item attributes.
• <hashlen> - 설정할 geo hash의 길이
• noreply - 명시하면, response string을 전달받지 않는다.

gop add (Geo Element 삽입)

Geo collection에 하나의 field, element를 삽입한다.
Geo collection을 생성하면서 <field, value>로 구성된 하나의 element를 삽입할 수도 있다.

gop add <key> <field> <bytes> [create <attributes>] [noreply|pipe]\r\n
[<longitude> <latitude>]\r\n
* <attributes>: <flags> <exptime> <maxcount> [<ovflaction>] [unreadable]

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string
• <bytes> - 삽입할 element의 데이터 길이 (trailing 문자인 "\r\n"을 제외한 길이)
• create <attributes> - 해당 Geo collection 없을 시에 Geo collection 생성 요청.
• noreply or pipe - 명시하면, response string을 전달받지 않는다.
• [<longitude> <latitude>] - 삽입할 경도, 위도

gop update (Geo Element 변경)

Geo collection에서 하나의 field에 대해 element 변경을 수행한다.
현재 다수 field에 대한 변경연산은 제공하지 않는다.

gop update <key> <field> <bytes> [noreply|pipe]\r\n
[<longitude> <latitude>]\r\n

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string
• <bytes> - 변경할 데이터 길이 (trailing 문자인 "\r\n"을 제외한 길이)
• noreply or pipe - 명시하면, response string을 전달받지 않는다.
• [<longitude> <latitude>] - 삽입할 경도, 위도

gop delete (Geo Element 삭제)

Geo collection에서 하나 이상의 field 이름을 주어, 그에 해당하는 element를 삭제한다.

gop delete <key> <field> [drop] [noreply|pipe]\r\n

• <key> - 대상 item의 key string
• drop - field, element 삭제로 인해 empty geo가 될 경우, 그 Geo을 drop할 것인지를 지정한다.
• noreply or pipe - 명시하면, response string을 전달받지 않는다.

gop pos (Geo element에 대한 위도, 경도 조회)

Geo collection에서 하나 이상의 field 이름을 주어, 그에 해당하는 위도 및 경도를 조회한다.

gop pos <key> <field> [delete|drop]\r\n

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string

gop dist (두 Geo element 간의 거리 조회)

Geo collection에서 두 개의 field 이름을 주어, 두 element 사이의 거리를 조회한다.

gop dist <key> <field> <field> <unit>\r\n

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string
• <unit> - 반경의 단위 (m, km, ft, mi)

gop raditem (Geo element 근처에 있는 Geo element 조회)

Geo collection에서 field 이름과 raidus 값을 주어, field에 해당하는 element에서 반경이내의 element를 조회한다.

gop raditem <key> <field> <radius> <unit>\r\n

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string
• <radius> - element로부터 조회할 반경의 거리
• <unit> - 반경의 단위 (m, km, ft, mi)

gop radlocation (입력한 좌표 근처에 있는 Geo element 조회)

Geo collection에서 하나 field이름과 radius

gop radlocation <key> <longitude> <latitude> <radius> <unit>\r\n

• <key> - 대상 item의 key string
• <longitude> - 조회할 location의 경도
• <latitude> - 조회할 location의 위도
• <radius> - location으로부터 조회할 반경의 거리
• <unit> - 반경의 단위 (m, km, ft, mi)

gop hash (Geo element의 해시값 조회)

Geo collection에서 하나 이상의 field 이름을 주어, 그에 해당하는 element를 조회한다.

gop hash <key> <field>\r\n

• <key> - 대상 item의 key string
• <field> - 삽입할 element의 field string

[matteblack9]

redis와 같이 sorted set을 구현하여 Geo API를 구현한다면, Geo를 map, list, set, btree와 같이 하나의 collection으로 보는 관점이 맞을까요?

[jhpark816]

@HarryKim93
최근 바쁜 일로 검토를 못하여 있습니다. 빨리 정리되는 대로 검토 진행하겠습니다.

[jhpark816]

@HarryKim93
우선 의견 차이가 나는 부분에 관해 간단히 의견 남깁니다. (마찬가지로 공부하여 spec 결정하여야 하므로, 최종 spec 결정까지는 시간이 일부 소요될 듯 합니다.)

• ARCUS에는 sorted set collection이 없는 상태이며, 이를 먼저 개발하여야 합니다.
  • 기존 b+tree collection과 set collection 기능을 조합하여 sorted set collection 만들 수 있습니다.
  • 이와 같은 sorted set은 b+tree collection 확장 기능으로 구현하거나 별도 collection으로 구현할 수 있습니다. 전자 방식이 좋을 것 같습니다.
  • 혹시 sorted set을 다른 방식으로 구현할 생각을 가지고 있나요 ?
  • Geo API는 저장/조회 관점에서 sorted set collection을 활용하면 됩니다.
• Geo API 과련하여
  • <field>는 해당 위치(위도,경도)에 있는 관심 사물의 이름을 의미하는 것이죠 ?
  • 아래와 같이 single line command인 것이 나은 것 같습니다. (field 값의 길이가 짧다고 가정).
    • gop add <key> <longitude> <latitude> <field> [create <attributes>] [noreply|pipe]\r\n
  • 만약, field 값의 길이가 길다면, 다음과 같은 2 line command로 처리하여야 합니다.
    • gop add <key> <longitude> <latitude> <bytes> [create <attributes>] [noreply|pipe]\r\n<field>\r\n
  • 주어진 longitude, latitude 기반으로 geohash 값을 얻어, btree에서 bkey 값을 사용할 수 있습니다. (아래 변환이 가능하다고 가정한 것입니다.)
    • <longitude, latitude> => a geohash value
    • a geohash value => <longitude, latitude>
  • btree의 value 정보로 field 값이 들어가게 될 것입니다. 이러한 field 값에 대한 uniqueness 보장과 빠른 exact search를 위해 hash 구조의 색인이 필요할 것입니다. 따라서, sorted set collection이면 됩니다.

확인해 주시고, 다르게 생각하는 부분이 있으면 의견 공유 바랍니다.

[matteblack9]

• 혹시 sorted set을 다른 방식으로 구현할 생각을 가지고 있나요 ?

기존에는 RB-Tree를 사용해서 구현하려했는데, geohash 특성상 말씀하신대로 b+tree collection으로 하는 것이 여러 geo 값 스캔시 overhead가 더 적고, radius 연산 시 더 효율적일 것 같습니다.

• <field>는 해당 위치(위도,경도)에 있는 관심 사물의 이름을 의미하는 것이죠 ?

네 맞습니다.

• 아래와 같이 single line command인 것이 나은 것 같습니다. (field 값의 길이가 짧다고 가정).

  • gop add <key> <longitude> <latitude> <field> [create <attributes>] [noreply|pipe]\r\n

• 만약, field 값의 길이가 길다면, 다음과 같은 2 line command로 처리하여야 합니다.

  • gop add <key> <longitude> <latitude> <bytes> [create <attributes>] [noreply|pipe]\r\n<field>\r\n

field 값의 길이를 제한하여, 위의 명령어로 통일하는 것은 어떨까요?

• 주어진 longitude, latitude 기반으로 geohash 값을 얻어, btree에서 bkey 값을 사용할 수 있습니다. (아래 변환이 가능하다고 가정한 것입니다.)

  • <longitude, latitude> => a geohash value
  • a geohash value => <longitude, latitude>

• btree의 value 정보로 field 값이 들어가게 될 것입니다. 이러한 field 값에 대한 uniqueness 보장과 빠른 exact search를 위해 hash 구조의 색인이 필요할 것입니다. 따라서, sorted set collection이면 됩니다.

기존 b+collection의 확장기능으로 sorted set을 구현하는 방법으로 생각해보겠습니다.
다만, 말씀하신대로 최종 spec 결정을 위해서 세부적인 고려해야할 사항(geo-hash 길이를 collection별로 다르게 할 것인지 혹은 통일할 것인지, unit은 어떤 단위까지 포함하는지 등)에 대하여 조금 더 고민해보겠습니다.

[jhpark816]

@HarryKim93
의견 감사하고, 추가 의견 드립니다.

• <field>가 해당 위치에 해당하는 사물의 이름이라면, <name> 용어로 변경하면 좋을 것 같습니다.
• <name> 길이는 짧을 것으로 예상하므로, 현재로는 1 line command로 통일하는 것이 좋겠습니다.
  • 참고로, 2 line command는 어떤 주어진 값의 길이가 긴 경우에 parsing 및 memory usage 최적화를 위해 사용합니다.
    해당 command에 주어진 값들의 길이가 모두 짧다면 1 line command가 단순하고 처리 overhead도 커지지 않습니다.
• geohash 52bit이면 1m 거리 단위의 위치 표현이 가능하다고 들었습니다.
  • 그러면, 8bytes unsigned integer 타입의 bkey를 사용하면 됩니다.
  • 개별 collection item 별로 geohash 길이를 다르게 하는 것이 좋은 지는 추가 고려 대상이 될 것 같습니다.
• 응용에 제공하는 collection 유형과 collection의 저장 유형이 기존에는 1-to-1 mapping 이었는 데,
  이번에 geohash를 위해 b+tree 구조를 사용한다면 아래와 같이 N-to-1 mapping이 만들어 집니다.
  따라서, b+tree 구조를 여러 collection에서 활용할 수 있도록, 모듈화를 잘 해야 할 것 같습니다.
  • 응용에 제공하는 b+tree collection : 저장 유형은 b+tree 구조
  • 응용에 제공하는 sorted set collection: 저장 유형은 b+tree 구조 (향후 제공 예정)
  • 응용에 제공하는 geohash collection: 저장 유형은 b+tree 구조
• 참고 사항으로, 기존 items 모듈에 kv, collection 포함한 여러 기능이 있다 보니, 코드 복잡성 및 관리 부담이 생깁니다.
  따라서, 최근에 이러한 기능들을 별도 파일로 분리하는 작업을 시작하였으며, 1~2주 내에 분리될 것이므로 이를 고려해 주기 바랍니다.

[jhpark816]

@HarryKim93
추가 의견입니다.

• update는 초기 버전에서는 제외하도록 하시죠. delete & insert로 처리가 가능하기 때문입니다.
• raditem, radlocation 연산에서 가까운 순서 or 먼 순서대로 정렬하는 옵션이 추가되면 좋겠습니다.
• Geo API를 제공한다면, dist, radius 외에 어떤 기능들을 제공하면 좋은가요 ?
• geohash <=> coordinates 간의 변환은 자유롭게 수행할 수 있나요 ?

[matteblack9]

• Geo API를 제공한다면, dist, radius 외에 어떤 기능들을 제공하면 좋은가요 ?

현재 명시된 기능 (pos, dist, radius) 외에는 지금 생각이 나지 않습니다. 이것도 한번 고민해보도록 하겠습니다.

• geohash <=> coordinates 간의 변환은 자유롭게 수행할 수 있나요 ?

네. 자유롭게 수행이 가능합니다. Geohash의 경우에는
Z-order curve(morton number)기법으로 위도 및 경도를 interleave 한 뒤, base32문자와 1:1 대응시키는 방법으로 해싱을 합니다.

https://en.wikipedia.org/wiki/Z-order_curve

Z-order curve와 base32를 사용해서 해싱했을 경우,
반대로만 연산을 하면 되기때문에
geohash <=> coordinates 간의 변환은 자유롭습니다.

Redis 코드를 통해서 예시로 보여드리자면
Encode를

static inline uint64_t interleave64(uint32_t xlo, uint32_t ylo) {
    static const uint64_t B[] = {0x5555555555555555ULL, 0x3333333333333333ULL,
                                 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
                                 0x0000FFFF0000FFFFULL};
    static const unsigned int S[] = {1, 2, 4, 8, 16};

    uint64_t x = xlo;
    uint64_t y = ylo;

    x = (x | (x << S[4])) & B[4];
    y = (y | (y << S[4])) & B[4];

    x = (x | (x << S[3])) & B[3];
    y = (y | (y << S[3])) & B[3];

    x = (x | (x << S[2])) & B[2];
    y = (y | (y << S[2])) & B[2];

    x = (x | (x << S[1])) & B[1];
    y = (y | (y << S[1])) & B[1];

    x = (x | (x << S[0])) & B[0];
    y = (y | (y << S[0])) & B[0];

    return x | (y << 1);
}

하고 있고(interleave 후 4bit씩 base32의 값과 1:1대응 시켜 만든 문자열이 해시값)

geohash에서 coordinate 변환 경우에는(decode)

static inline uint64_t deinterleave64(uint64_t interleaved) {
    static const uint64_t B[] = {0x5555555555555555ULL, 0x3333333333333333ULL,
                                 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
                                 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL};
    static const unsigned int S[] = {0, 1, 2, 4, 8, 16};

    uint64_t x = interleaved;
    uint64_t y = interleaved >> 1;

    x = (x | (x >> S[0])) & B[0];
    y = (y | (y >> S[0])) & B[0];

    x = (x | (x >> S[1])) & B[1];
    y = (y | (y >> S[1])) & B[1];

    x = (x | (x >> S[2])) & B[2];
    y = (y | (y >> S[2])) & B[2];

    x = (x | (x >> S[3])) & B[3];
    y = (y | (y >> S[3])) & B[3];

    x = (x | (x >> S[4])) & B[4];
    y = (y | (y >> S[4])) & B[4];

    x = (x | (x >> S[5])) & B[5];
    y = (y | (y >> S[5])) & B[5];

    return x | (y << 32);
}

처럼 해싱된 값에대해 Z-curve 기법을 반대로 사용하여 위도와 경도를 구할 수 있습니다.
따라서, encode decode를 자유롭게 할 수 있습니다.

[jhpark816]

@HarryKim93 변환 방식을 알려주어서 감사합니다.

1개 캐시 노드에서 point 기반의 위치 정보를 저장하고 dist, radius 연산을 수행하는 것은 대략 정리/이해가 된 것 같습니다.
추가적으로 정리해야 할 사항은 관심 있는 point 기반의 위치 데이터가 아주 많아서 여러 캐시 노드에 분산 저장할 경우,
이를 어떤 기준으로 분산시키고, 어떻게 dist, radius 연산을 처리할 것인가 입니다.
이에 대하여 어떤 의견이 있다면, 공유하여 주면 좋겠습니다.

[matteblack9]

@jhpark816

추가적인 의견입니다.

• 추가적으로 radmin, radmax와 같은 연산도 추가하면 어떨까요?
  (radius내에서 가장 가까운 위치 or 가장 먼 위치의 item반환)

• Btree기반이 아닌 skiplist를 사용한 geo collection도 고려하면 좋을 것 같습니다.
  https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf
  https://en.wikipedia.org/wiki/Skip_list

 btree의 경우,
 캐시 친화적이며, 기존에 구현이 되어 있는 코드가 있고, 순서를 유지하고,
log(n) 시간을 보장할 수 있지만
 삽입/삭제 연산 시 생기는 rebalancing으로 인해, 다소 작지 않은 overhead가 생깁니다.

 skiplist의 경우, 최근에 고안된 자료구조이며
 현재 memSQL, Redis, skipDB 등
최근의 인메모리 데이터베이스들은 이 자료구조를 사용하는 것으로 보입니다.
 구현이 btree에 간단하고, log(n)의 가까운 시간 보장, 순서 유지 등
btree와 거의 동일한 기능을 하면서
 rebalancing에 의한 overhead가 없다는 장점이 있습니다.
 다만, skiplist는 리스트를 여러개 사용하는 구조라, btree에 비해 캐시 미스 발생에 의한 overhead가 높다는 단점이 있지만,  이는
 http://ticki.github.io/blog/skip-lists-done-right/
 에 설명된 Unrolled lists으로 보완이 가능할 것으로 보입니다.

추가적으로 정리해야 할 사항은 관심 있는 point 기반의 위치
데이터가 아주 많아서 여러 캐시 노드에 분산 저장할 경우,
이를 어떤 기준으로 분산시키고,

• 현재 arcus는 client에서 key기반의 hash ring으로 캐시 노드에 분산 저장하는데, geo들의 값이 모두 unique하기 때문에 field를 기준으로 분산시켜도 되지 않을까요?

어떻게 dist, radius 연산을 처리할 것인가

• dist의 경우는 geohash<=> coordinate 연산의 자유로우므로, 입력 item의 coordinate, target item의 coordinate를 구하면 두 점사이의 거리를 구하는 것처럼 쉽게 구할 수 있을 것 같습니다.

• radius의 경우 조금 더 까다로울 것 같은데, geohash는 가까이 있는 point들일 수록
  서로 접두사가 같은 것이 많다는 점을 이용한다면,

아래 표에 나와있는대로, geohash 길이에 따른 오차를 이용하면 될 것 같습니다.
강남역의 coordinate정보를 geohash 변환한 wydm6d3c의 경우를 예로 들면,

geohash 길이가 8로 설정되어 있는 조건에서

• 강남역으로부터 15m거리의 point들을 구한다고 했을 때,
  강남역으로부터 동,서,남,북, 북동, 북서, 남동, 남서의 geohash값을 구한 다음
  (위도와 경도의 2진수 값을 각각 +-1을 해주면 구할 수 있음)
  강남역, 동,서,남,북, 북동, 북서, 남동, 남서의 접두사와 8자리까지 똑같은 point들에 대해 dist가 radius이하인 point들만 포함시킨 집합을 return하는 방법입니다.
  (밑의 빨간색 네모칸들)

• 강남역으로부터 50m거리의 point들을 구한다고 했을 때,
  geohash의 길이 8에서의 lng 오차가 +-17m이기 때문에,
  강남역의 geohash에서 7번째까지의 값 wydm6d3c만 사용합니다.
  (15m의 경우 8번째까지의 값 모두 사용)
  길이 7의 geohash에 대한, 동, 서, 남, 북, 북동, 북서, 남동, 남서의 geohash값을 구한 다음, 강남역, 동,서,남,북, 북동, 북서, 남동, 남서의 접두사와 7자리까지 똑같은 point들에 대해radius이하 여부를 확인하여 조건을 만족시키는 집합을 return 합니다.
  (밑의 파란색 네모칸들)

그러므로 radius 값에 따라서,
위와 같은 연산들을 해준다면 radius 기능을 구현할 수 있지 않을까합니다.

[jhpark816]

@HarryKim93
의견입니다.

• radmin, radmax는 radius 기능의 부분 집합에 해당되므로, radius 기능만 제공하죠.
  • radius 명령에 정렬 기준(ASC, DESC)과 조회 개수(count)를 추가할 것이므로,
  • 정렬 기준을 달리하고 count = 1이면, radmin, radmax를 구할 수 있게 됩니다.
• 제공 연산은 pos, dist, radius 만으로 한정하시죠.
• 저장 구조는 skip list로 합시다.
  • skip list 구현체를 모듈화하고, geohash collection에서 이용하도록 합시다.
  • skip list 구현체는 필요하다면 다른 collection(예, list)에서도 이용할 수 있을 것입니다.
• 분산 저장에 대한 질문은 하나의 geohash collection에 아주 많은(예, 1천만건) 위치 정보를 저장해야 할 경우, 이에 대한 분산 저장과 처리에 관한 질문이었습니다.
  • 응용에게 big sized geohash collection을 제공할 경우, 1개의 물리적인 geohash collection(저장소에 실제로 저장되는 collection)으로 저장하는 것은 좋지 않다고 봅니다.
    • ARCUS 내부에서 N개의 물리적인 geohash collection으로 분산 저장하고 N개의 물리적인 geohash collection에 대해 dist, radisu 연산을 처리하는 것이 좋다고 봅니다.
  • 분산 저장된 geohash collection에 대해 dist나 radius 연산을 잘 처리하기 위해서는 field 기준이 아니라 geohash 값 기준으로 분산되어야 한다고 봅니다. geohash 특성을 잘 이용하여 잘 분산하면, 연산 처리도 최적화할 수 있습니다.
    • 이는 결국 가급적 1개 cache node에서 처리되도록 하기 위함입니다.
    • 예를 들어, dist 연산의 두 위치가 서로 다른 geohash collection에 저장되어 있다면, client에서 두 위치 정보를 가져와서 client 단에서 dist 연산을 수행해야 할 것입니다.
    • dist 연산의 두 위치가 1개 geohash collection에 저장되어 있다면, 그 collection을 가진 cache node에서 dist 처리하고 최종 결과만 client가 받아오면 됩니다.
  • 다른 방안으로, 이러한 분산 저장과 처리를 응용에게 넘기는 방안도 있습니다. 하지만, ARCUS가 처리해 주는 방안이 있으면 좋을 듯 합니다.
    • 이 경우, 응용에서 여러 geohash collection을 만들어 처리할 수 있습니다.
    • 예를 들어, 전국의 레스토랑의 위치 정보를 1개 geohash collection으로 저장하지 않고
      서울, 대전, 부산 등의 지역별로 별도의 geohash collection을 생성하여 저장하는 방법이 있습니다.
  • 이러한 분산 저장과 처리에 대해선, 시간을 가지면서 고민해 보시죠.
• geohash 값을 저장하기 위해, 8 바이트를 사용하면 충분하다고 생각합니다.
  • 향후 radius 연산 처리 시에 "100m 이내"와 같은 조건을 검사하려면, geohash collection에 저장할 위치(경도, 위도)의 정밀도 정보가 geohash collection의 메타 정보로 보관되어야 할 것입니다.
  • 입력되는 위치 정보가 해당 정밀도를 가지지 않으면 잘못된 결과가 나오게 될 것입니다. 입력되는 위치 정보가 해당 정밀도에 부합하는 지를 검사할 방법은 없겠죠 ?
• 참고 사항.
  • items 모듈을 분리하는 작업이 최근에 진행되고 있습니다.
  • 이를 감안하여 진행해 주시면 됩니다.