1장: 근접성 서비스

[minkukjo]

요구사항!

• 근접성 서비스를 디자인해보자.
• 근접성 서비스 예시는 Yelp라고 하는 서비스라고 하는데, 모르겠고 대충 네이버 예약 같은거라고 생각하고 보기 시작함
• 근접성 서비스의 모든 기능을 인터뷰 시간 내에 설계하는 것은 불가능하니, 질문을 던져 설계 범위를 좁혀야 한다.

질문 타임

• 일단 사용자가 범위 지정이 가능한지를 물어보고, 검색 반경 내에 사업장이 충분하지 않으면 범위를 넓힌다고 제안한다.
• 사업장 정보가 변경되면 유저에게 실시간으로 반영되어야하는지 물어본다 ( 아주 중요한 질문임 )
• 지도가 유저를 따라서 실시간으로 화면을 자동 갱신해야할 필요가 있는지도 물어본다 ( 이것 역시 아주 중요한 질문 )

기능 요구 사항

• 사용자 위치(위도 ,경도)를 기반으로 해서 검색 반경 정보에 매치되는 사업장 목록 반환
• 고객은 사업장의 상세 정보를 볼 수 있어야 한다.
• 사업장 소유주가 사업장 정보를 추가/삭제/갱신 할 수 있지만, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다고 가정

비기능 요구사항

• 낮은 응답 지연 (주변 사업장을 신속히 검색할 수 있어야함)
• 데이터 보호 ( GDPR이나CCPA와 같은 사생활 보호 법안을 준수해야한다고 함 )
  • GDPR이 무엇인고 하고 좀 찾아봤는데 유럽 연합 일반 데이터 보호 규칙이라고 한다. https://www.veritas.com/ko/kr/information-center/gdpr
  • CCPA는 캘리포니아주 소비자 개인정보 보호법이라고 한다. https://www.cloudflare.com/ko-kr/learning/privacy/what-is-the-ccpa/
• 고가용성 및 확장성

QPS 계산

• 일 사용 유저가 1억이라고 가정하고 유저가 하루에 5회 검색을 한다고 하면 하루에 발생하는 쿼리는 5억회가 된다.
• 여기서 QPS니까 초를 나눠야하는데 10^5를 나눠버리면 5000이 된다.
• 이렇게 보니 5000 QPS가 엄청나다는 것을 다시 한 번 깨달음!

데이터 모델

• 근접성 서비스의 경우 읽기/쓰기의 비율 중 읽기의 비율이 압도적으로 높다.
• 이럴 경우 저자는 MySQL을 사용하는 것으로 결정했다. ( MySQL은 읽기 성능이 좋은 DB )

시스템 구성

• 위치 기반 서비스
• 사업장 서비스

사업장 검색 알고리즘

• 실제 많은 회사들이 레디스 지오해시나 PostGIS 를 설치한( PostgrSQL ) DB를 사용한다고 한다.

방안 1

• 이를 위해 2차원 검색 ( 원 안의 사업장을 검색) 하는 알고리즘을 떠올릴 수 있는데 이는 좋은 방법이 아니다. ( 질의 자체가 비효율적이라서 테이블 전부를 읽어야함. )
• 방안 1은 구려서 대신 다른 방법을 쓴다.
• 지도를 작은 영역으로 분할해서 고속 검색이 가능하도록 색인을 만드는 방법이 있다. ( 지오해시, 쿼드트리, 구글 S2)

방안 2

• 균등 격자
• 지구를 특정 구획으로 나누는 방법인데, 문제는 인구 밀도나 사업장 밀도는 균등하지 않다는 문제가 있다. ( 뉴욕의 사업장과 대한민국의 시골의 사업장 수를 비교해보아도 말이 안된다. )

방안 3

• 균등해시와 비슷하지만, 지오해시는 2차원 위,경도 데이터를 1차원의 문자열로 변환하고 재귀적으로 세계를 더 작은 격자로 분할해 나간다.
• 지오해시는 해시값이 공통 접두어가 긴 격자들이 서로 더 가깝게 놓이도록 보장해주는데, 이것이 역은 참이 아니다.
• 무슨 말이냐면 충분히 가까운 두 위치가 어떤 공통 접두어를 가지지 않을 수도 있는데 이렇게 되면 접두어 기반 질의를 사용하더라도 주변 모든 사업장을 가져올 수 없게 된다.
• 또 다른 문제는 공통 접두어 길이는 길지만 서로 다른 격자에 놓이는 경우다.
  • 이 경우 가장 간단한 해결책은 현재 격자를 비롯한 인접한 모든 격자의 모든 사업장 정보를 가져오면 된다.
• 표시할 사업장이 충분하지 않은 경우도 간단히 해결이 되는데, 검색 범위를 확대할 때 마다 비트를 지워가면서 검색하면 범위를 점점 넓혀갈 수 있다.

방안4

• 쿼드트리는 격자의 내용이 조건을 만족할 때 까지 2차원 공간을 재귀적으로 사분면 분할을 하는데 흔히 사용되는 자료구조라고 한다. (3차원 공간을 쪼개면 옥트리라고 한다. octa(8)에서 따온 듯 )
• 쿼드트리가 잘 이해가 안되서 직접 구현해봄 -> https://leetcode.com/problems/construct-quad-tree/

"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':

        def dfs(grid, i,j,range):
            if canCompress(grid, i,j, range):
                value = None
                if grid[i][j] == 1:
                    value = 1
                else:
                    value = 0

                return Node(value, True)

            limit = range//2
            result = Node(1, False)
            result.topLeft = dfs(grid,i,j,limit)
            result.topRight = dfs(grid,i,j+limit, limit)
            result.bottomLeft = dfs(grid, i+limit, j, limit)
            result.bottomRight = dfs(grid,i+limit, j+limit, limit)
            return result

        def canCompress(grid, i,j,w):
            for x in range(i, i+w):
                for y in range(j, j+w):
                    if grid[x][y] != grid[i][j]:
                        return False
            return True

• 격자 안에 최대 100개의 사업장이 있다고 가정하면, 말단 노드의 수가 2백만개이고 내부 노드의 수가 0.67백만개 이므로, 2백만 x 832바이트 + 0.67x64바이트 => 1.71GB라는 계산이 나온다고 한다. ( 수학을 잘해야겠구먼.. )
  • 왜 말단 노드는 개당 832바이트(13x64)로 계산하는거지..?
• 물론 실제 면접에선 이렇게 까지 구체적일 필요는 없고, 둬크 트리 인덱스가 메모리를 많이 잡아먹진 않으니까 서버 한 대에 충분히 올릴만 한다는 것을 얘기해주면 된다고 한다.
  • 쿼드트리 연산을 위해 서버를 N대 운용하는 방법도 있음
• 쿼드트리를 갱신하는 것도 중요한 문제일텐데 ( 운영중 추가/삭제될 수 있으니 ) 가장 쉬운 방법은 점진적으로 업데이트 하는 방식이다.
• 물론 이 과정에서 오래된 결과가 반환될 수 는 있지만 일반적으로 그정도 요구사항은 용인될 수 있다고 한다. (과연..?)

방안 5

• 구글 S2는 메모리 기반의 공간 탐색 라이브러리임
• 구글이나 틴더에서 이 알고리즘을 사용중인데, 구현이 복잡하므로 간단히 알아보자.
• 지오펜스라는 가상의 영역을 설정한다고 함. (영역전개..!!)
• 구체적으로 구현에 대한 언급이 없어서 나중에 위치 관련 서비스 개발할 때 좀 더 딥하게 찾아볼 예정

상세 설계

• LBS에서 사업자 정보를 캐싱해두는 방식에서 무효화를 통한 방식을 했던 이유는 아무래도 서비스간 의존을 적게 하여 장애 전파를 막는 것이 가장 큰 목적이었던 것이 아닐까 싶다.

  보고 느낀 점

• 직접 근접 위치 기반 서비스를 만들어보고 싶은 의욕이 생김.
• 이번에 사이드 프로젝트 동아리를 하는데, 가능하다면 이걸 한 번 제안해보고 싶을 정도!

[LOG-INFO]

끄적끄적

• 회사 프로젝트 진행 전에 하는 디자인 리뷰와 비슷한 느낌을 받았다
• GDPR, CCPA와 같은 개인 정보 관련 법안을 고려하는 것은 꽤 어려울 듯
• DB들에서 관련 알고리즘을 지원하는 것은 처음 알았다
  • Geohash - Redis, MongoDB, Lyft(?)
  • Quad Tree - Yext(?)
  • PostgreSQL - PostGIS (extension)

캐시 전략 변경 제안

• p.32에서 제안한 방법들 중
  • 2번 항목의 Cache-Aside 방식은 동의
  • 하지만 사업장 갱신 시 invalidate 보다는 Write through를 함으로써 Cache-Aside 방식보완 가능
  • e.g. Cache-Aside 방식만 사용하면, 동시에 여러 요청이 들어왔는데 캐시가 없을 때 같은 DB 쿼리가 여러번 발생할 수 있다.
    • 이것을 Write-Though로 보완 가능
  • 근데 Write-Through는 캐시에만 저장되고 DB에 저장되지 않는 현상이 발생할 수 있다.
    • 캐시 저장 -> DB 저장이 아닌, DB 저장 -> 캐시 저장 순서로 해야할 듯
  • 단, Write-Through의 단점은 사용하지 않는 캐시인데 캐시에 저장되어 불필요한 캐시 용량 증가로 이어질 수도 있다.

설계 변경 제안

AS-IS design

TO-BE design

• 나라면 dependency 분리를 위해 LBS에서 사업장 정보 Redis를 바로 호출하지 않도록 분리할 것 같다
  • Read 작업은 LBS에서 사업장 정보 서비스의 API 호출을 통해 실행될 듯
  • 쓰기 작업은 각 서비스간 쓰기 API Request 또는 Event를 통해 전달할 듯 (여기서도 dependency 분리를 위해 Event가 나을 듯 하다)
  • 이렇게 까지 분리하는 이유는 dependency 때문이다.
  • 사업장 정보 Redis를 다른 곳들에서 사용한다면, 사업장 정보 서비스에서 데이터 구조를 변경할 때 큰 제약사항이 된다.
    • 데이터 구조 변경 시 사업장 정보 Redis에 접근하는 모든 서비스를 찾아서 데이터 구조 변경 가능 여부 확인 요청해야함.

• 장점
  • dependency를 분리할 수 있기 때문에 유지보수성 증가
• 단점
  • 한 Hop이 추가되기 때문에
  • latency가 증가하고,
  • Business Service load 증가할 수 있음
  • 각 서비스간 장애가 전파될 수 있음

추가 변경 제안

• 그리고 DB들에서 알고리즘을 지원하고 있으니, LBS를 직접 구축하는 대신 DB 기능들을 사용할 듯
  • Q. 근데 캐시도 추가하려면 geo-hash를 알아야 하는데 DB 내부에 저장된 geo-hash를 조회할 수도 있겠지?
  • Q. Rebalancing 시 변경된 geo-hash도 조회할 수 있겠지? -> 캐시 refresh해야 함
  • 성능, 유지 비용도 고려하긴 해야할 듯

TODO: 필터링 기능도 보완할 것 없나 생각해보자

[MinJunKweon]

끄적끄적

• 저번에 설렁설렁봐서 대충 본 부분이 너무 많았음
• Write를 redis에 하지 않고 Primary DB에 작업후 redis로 sync 하는 부분이 좀 생소했음
  • 희찬님 말씀대로 write through 하는게 좋지 않나?
• S2 알고리즘은 다음에 한번 다시봐도 좋을듯

[HaeUlNam]

• 주변 사업장 검색 알고리즘
  • 방안 1 - 2차원 검색: 계산으로 위해서 Table full scan을 해야 함으로 효율적이지 않음
  • 방안 2- 균등 격자: 모든 곳을 균등한 작은 격자로 나누면 단순하다. 다만, 이 경우 데이터 분포가 전혀 균등하지 않다
  • 방안 3 - 지오 해시(GeoHash): 2차원의 위도 경도 데이터를 1차원의 문자열로 변환한다. 재귀적으로 반복
    • 위도 범위 [-90, 0]은 0, 위도 범위 [0, 90]은 1, 경도 범위 [-180, 0]은 0에 대응, 경도 범위 [0, 180]은 1에 대응. 이 기준으로 사분면으로 나누면, 시계 방향으로 01/11/10/00가 된다.
    • 이 절차를 원하는 정밀도를 얻을 때까지 반복. 최적 정밀도는 사용자가 지정한 반경으로 그린 원을 덮는 최소 크기 격자를 만드는 지오해시 길이를 구해야 함.
  • 방안 4 - 쿼드 트리: 격자의 내용이 특정 기준을 만족할때까지 2차원 공간을 재귀적으로 사분면 분할하는데 사용되는 자료구조. 트리를 Balanced하게 만드는 것도 관건.
    • 락을 이용해서 실시간으로 갱신하는 게 더 좋아보임. 한꺼번에 업데이트하는 경우 SnapShot 버전을 바꾸는 식으로 하는 경우가 있는데, 서버에 부하가 클 것 같음.
• Geo Hash Redis
  • Redis Geohash는 Sorted Set기반으로 동작한다
  • GEOADD: O(log(N)). N은 Sorted Set item의 수
  • GEOSEARCH: O(N + log(M)). N은 grid-aligned bounding box area 근처에 shape 안에 있는 element의 수. M은 shape 안에 있는 element의 수
    • BYRADIUS: 원형
    • BYBOX: 직사각형

GEOADD places 127.064053 37.508645 "Park Hyatt Seoul"
GEOADD places 127.060896 37.508899 "Grand InterContinental Seoul Parnas"
GEOADD places 127.926644 37.525339 "Conrad Seoul"
GEOADD places 126.929140 37.525198 "Fairmont Ambassador Seoul"

GEOADD places XX 126.926667 37.525250 "Conrad Seoul"
GEOSEARCH places FROMLONLAT 126.9243 37.5217 BYRADIUS 1 km

GEOSEARCH - 여의도역 기준으로 호텔 검색 결과

Reference

• https://medium.com/groupon-eng/scaling-millions-of-geospatial-queries-per-minute-using-redis-7c05bcf6b4db
• https://www.alibabacloud.com/blog/apsaradb-for-redis-6-2-enhanced-geographic-location-features_597588
• https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/SkipList.html#