DevSprout/System-Design-Interview-2

3장: 구글맵

Opened this issue · 2 comments

HaeUlNam commented
3장: 구글맵
HaeUlNam commented

  • 경로 탐색 알고리즘은 Djikstra 알고리즘 이나 A* 경로 탐색 알고리즘

    • Node(교차로)와 Edge(도로)로 표현
    • 경로 탐색 알고리즘의 성능은 주어진 그래프 크기에 아주 민감하다. 좋은 성능을 보이려면 그래프를 관리 가능 단위로 분할할 필요가 있다.
    • 지번 수준 정밀도 타일을 가지고 알고리즘을 돌리면 결과를 얻는데 너무 많은 시간이 걸릴 것. 보통 구체성 정도를 상, 중, 하로 구분하여 세 가지 종류의 경로 안내 타일을 준비한다. 알고리즘을 최적화하는 것보다 데이터를 정제하는데 시간을 훨씬 많이 쏟을 것 같음.
      • 상의 경우 지방도 데이터만 둔다.
      • 중은 비교적 큰 관할구를 잇는 간선 도로 데이터만 둔다.
      • 하는 그보다 더 큰 영역을 커버하며, 그런 타일에는 도시와 주를 연결하는 주요 고속도로 데이터만 둔다.
    • 다익스트라 알고리즘: 꼭지점 간의 최단 경로를 찾는 알고리즘. 계산할 다음 노드를 찾는 구현 방식에 따라 시간 복잡도가 달라짐.
      • 순차 탐색을 이용할 시 O(N*N), 우선순위 큐를 사용할시 O(N * LogN)
    • A* 알고리즘: 시작점부터의 코스트뿐만 아니라 현시점에서 목표 지점까지의 추정 코스트도 함께 고려해서 탐색
    • Cost는 어떻게 구할까?

  • 저장소

    • 세계 지도: 지오해싱 기반으로 사진을 준비해둬서 CDN 정적 캐싱할 수 있도록 함.
    • 메타데이터: 각 지도 타일의 메타데이터는 크기가 아주 작아서 무시해도 지장이 없을 정도
    • 도로 정보

  • 서버에서 처리하는 요청

    • 경로 안내 요청
    • 위치 갱신 요청: 클라이언트에 버퍼링해 두었다가 일괄 요청(15초나 30초마다)하면 전송빈도를 줄일 수 있다.
      • 경로를 이탈하는 경우에는 바로 즉시 요청해야 할 것 같음
      • 일괄 요청하는 경우 Jitter value를 고려해야 할 것 같음. ex) client별로 14.5초, 16초

  • 카산드라 Database

    • 사용자 위치 데이터를 저장하려면 엄청난 양의 쓰기 연산을 잘 처리할 수 있으면서 수평적 규모 확장이 가능한 데이터베이스가 필요
    • CAP 정리에 따라 Availability, Partition tolerance를 만족하시는 것은 카산드라이다.

  • TODO) 카산드라에 대해 더 공부해봐야지..

minkukjo commented

끄적끄적

  • 구글맵은 경로 안내, 위치 갱신, 지도 표시가 주요 피쳐
  • 경로탐색 알고리즘
  • 지도에서 위치를 검색할 때는 주로 지오해싱 기법을 사용함
  • 지도 서비스를 위치 안내 서비스와 지도 표시 서비스로 분리한 부분이 인상깊었음 ( MSA! )
    • CDN에서 파일명을 지오해싱 키로 사용하는 것이 특히 흥미로웠는데, 이를 위해 네이밍을 얻는 간단한 알고리즘을 구현한 서비스를 별도로 구성하는 것도 가능하다는 점에서 확실히 확장성있는 설계라고 느낌
  • 사용자 위치데이터처럼 계속해서 바뀌는 정보는 CAP에서 A와 P를 얻기 위해 카산드라를 사용한다는 점에서 매우 인상깊었음
    • NOSQL 늘 제대로 써본적이 없어서 꼭 한 번 경험해보고 싶음..