7. UBER // 쏘카 // lyft // 카카오택시

지리적으로 A TO B까지의 운반해야 하는 모든 서비스에 적용 가능하다. ( 배민 / 요기요 등)

여기에서는 우버를 예로 들었다.

 

1. 기능 요구 사항

승차 공유 시스템

• 택시 호출
• 예약 요청이 들어오면 가까운 차들에게 순서대로 승차 요청이 가며 그중 한 명이 요청을 받을 수 있다
• 예상 도착 시간을 알 수 있어야 한다
• 택시 트래킹 (사용 가능한 드라이버를 볼 수 있어야 한다)
• 예상 가격을 알 수 있어야 한다.

번외 기능

• 원하는 운전자를 선택할 수 있어야 한다
• 운전자마다 가격(팁)이 다를수 있다
• 탑승 날짜와 시간을 예약할수 있어야 한다.

 

2. 용량 추정 및 제약

• 3억 명의 고객과 100만 명의 일일 활성 고객, 500,000명의 일일 활성 운전자가 있다고 가정합니다.
• 하루 100만 라이드를 가정합니다.
• 모든 활성 운전자가 3초마다 현재 위치를 통지한다고 가정해 보겠습니다.
• 고객이 승차 요청을 하면 시스템이 실시간으로 운전자에게 연락할 수 있어야 합니다.

 

3. 기본 API 설계

사용자의 호출에 사용자 위치를 포함한 사용자 정보는 Amazon DynamoDB와 같은 key-value로 저장된다. 유저의 데이터는 **지역 분할 인덱스(5.GeoShard)**에 드라이버 검색 대기열에 추가된다.

드라이버 승인 후 사용자에게 최단 거리 계산 및 사용자에게 도착 시간(ETA)을 알려줘야 한다.

 

4. 드라이버 검색

• 사용자의 요청이 얼마나 빠르게 주변의 운전자에게 가는지가 목표이다. (보통 2km 이내의 드라이버를 목표로 한다.)
• 사용자와 운전자의 거리를 어떻게 계산할 것인가?

 

 

4-1 지리 공간 데이터베이스

• 데이터베이스는 확장성이 뛰어나야 한다. 설계 목표는 초당 백만 쓰기 를 처리하는 것입니다. 지역이 계속해서 늘어날 수도 있다.
• 드라이버가 이동할 때 4초마다 업데이트를 보내는 보내 위치 정보를 갱신해야 한다.
• 새로운 지역에서는 모든 시/도에서 모든 드라이버의 위치 및 예상 경로도 추적해야 한다.
• 지구는 구체로 순전히 경도와 위도를 기반으로 요약 및 근사를 수행하는 것은 어렵다.

Uber는 쿼드트리 데이터 구조를 사용하는 Google S2 라이브러리를 사용한다. (s2의 내용은 tinder 편에서 확인 가능) 이 라이브러리는 지도 데이터를 작은 셀(예: 2km)로 나누고 각 셀에 고유한 ID를 부여하며, 이것은 분산 시스템에서 데이터를 분산하고 쉽게 저장하는 매우 쉬운 방법이다.

 

도시에서 반경 2km 이내에 있는 모든 택시를 파악하고 싶다고 가정해 보자. S2 라이브러리를 사용하여 반경 2km의 원을 그릴 수 있으며 특정 원에 있는 ID가 있는 모든 셀을 필터링한다. 이렇게 하면 라이더를 운전자와 쉽게 일치시킬 수 있고 특정 지역에서 사용 가능한 드라이버의 수를 쉽게 찾을 수 있다.

 

 

int64를 사용하면 지구 상의 모든 평방 센티미터를 나타낼 수 있다. Uber는 현재 위치에 따라 3.31km(2) ~ 6.38km(2)인 레벨 12 셀을 사용한다. 각 셀에는 ID가 있으므로 ID가 샤딩 키로 사용된다. 위치가 제공되면 해당 위치의 셀 ID가 결정된다. 셀 ID를 샤드 키로 사용하여 공급 위치가 업데이트된다

 

4-2 일관된 해싱 및 DISCO(GEOshard 아키텍처)

Uber는 사용자와 택시를 연결하기 위해 아키텍처에 Dispatch 시스템(Dispatch Optimization/DISCO)을 가지고 있다. 드라이버는 항상 빠른 속도로 움직이므로 드라이버의 위치는 s2의 cell에서 cell로 이동하는 것을 계속 기록해야 한다.

앞서 우리는 S2 라이브러리가 맵을 고유 ID를 가진 작은 셀로 나누는 것에 대해 알아보았다. s2 ID는 DISCO에서 샤딩 키로 사용된다. 드라이버는 사용자로부터 요청을 받으면 셀 ID를 샤드 키로 사용하여 위치가 업데이트된다. 이 작은 셀의 책임은 여러 지역에 있는 다른 서버로 나누어진다(일관된 해싱).

예를 들어, 우리는 6개의 다른 지역에 있는 6개의 다른 서버(각 서버에 2개의 셀)에 12개의 작은 셀의 책임을 할당할 수 있다.

DISCO는 일관된 해싱된 GEOshard를 검색하는 서버이다.

• DISCO가 위치 근처에서 공급을 찾아야 하는 경우 라이더가 있는 위치를 중심으로 서클의 커버리지가 계산된다. 원 영역의 셀 ID를 사용하여 모든 관련 샤드에 연결하여 공급 데이터를 반환한다.
• 원하는 만큼 효율적이지 않고 팬아웃이 상대적으로 저렴하기 때문에 쓰기 로드는 항상 노드를 추가하여 확장할 수 있어야 한다. 읽기 로드는 레플리카를 사용하여 확장된다. 더 많은 읽기 용량이 필요한 경우 레플리카 노드를 늘릴 수 있다.
• 제한 사항은 셀 크기가 레벨 12 크기로 고정되어 있다. 셀 크기가 작을수록 쿼리에 대한 팬아웃(아웃풋 크기)이 커짐에 따라 절충점이 있다.

 

 

 

 

• Supply는 GPS 위치 데이터를 기반으로 DISCO 서버에 요청을 보낸다. 그 후, 시스템은 ring(CEOshard)에서 요구에 충족되는 드라이버를 찾는다.
• 그런 다음 드라이버 목록이 ETA로 전송되어 승객과 드라이버 사이의 거리를 지리적으로 거리가 아닌 도로 시스템으로 계산한다
• 분류된 ETA는 다시 공급 시스템으로 보내져 운전자에게 제공된다

새로 추가된 도시의 트래픽을 처리해야 하는 경우 서버 수를 늘리고 새로 추가된 도시 셀 ID의 책임을 이 서버에 할당할 수 있다.(일관된 해싱에서의 서버를 늘리면 해시값은 그대로 유지가 가능하다)

 

5. 지도 영역 정의

새로운 지역에서 새로운 작업을 시작하기 전에 Uber는 새로운 지역을 지도 기술 스택에 온보딩 해야 한다. 이 지도 영역에서 A, B, AB 및 C 등급으로 레이블이 지정된 다양한 하위 영역을 정의한다

A 등급: 이 소구역은 도심과 통근 지역을 담당. Uber 트래픽의 약 90%가 이 하위 지역에서 처리되므로 하위 지역 A에 대한 최고 품질의 지도를 구축하는 것이 중요하다

B 등급: 이 하위 지역은 Uber 고객이 덜 이동하고 인구가 적은 시골 및 교외 지역을 포함

AB 등급: A 등급과 B 등급 소지역의 조합

C 등급: 다양한 Uber 지역을 연결하는 고속도로 및 외각도로를 포함

 

6. 지도를 구축하는 방법

Uber는 타사 지도 서비스 제공업체를 사용하여 애플리케이션에서 지도를 구축한다. 이전 Uber는 Mapbox 서비스를 사용했지만 나중에 Uber는 위치를 추적하고 ETA를 계산하기 위해 Google Maps API로 전환했다.

1. 추적 범위: 추적 범위는 누락된 도로 세그먼트 또는 잘못된 도로 형상을 찾는다. 추적 범위 계산은 두 가지 입력을 기반으로 한다. 테스트 중인 지도 데이터와 특정 기간 동안 찍은 모든 Uber 차량의 과거 GPS 추적이다. 지도에 GPS 추적을 포함하여 도로 세그먼트와 비교하고 일치시킨다. GPS 추적에서 누락된 도로 구간(도로가 표시되지 않음)을 찾으면 결함을 수정하기 위한 몇 가지 조치를 취한다.

2. 선호 액세스(픽업) 지점 정확도: Uber에서 택시를 예약할 때 애플리케이션에서 픽업 지점을 얻는다. 픽업 지점은 Uber에서 특히 공항, 대학 캠퍼스, 경기장, 공장 또는 회사와 같은 대규모 장소에서는 사용자의 이동에 따라 경로가 다시 갱신되어야 하는 매우 중요한 매트릭스이다. 실제 위치와 운전자가 사용하는 모든 승하차 지점 간의 거리를 계산한다.

그런 다음 최단 거리(가장 가까운 픽업 지점)를 계산하고 해당 위치에 핀을 지도의 기본 액세스 지점으로 설정한다. 라이더가 지도 핀으로 표시된 위치를 요청하면 지도가 운전자를 원하는 액세스 포인트로 안내한다. 계산은 제안된 선호 액세스 포인트의 신선도와 정확성을 보장하기 위해 최신 실제 픽업 및 하차 위치로 계속된다.

 

7. 드라이버 추적

모든 택시는 웹 애플리케이션 게이트웨이/방화벽, 로드 밸런서를 필요에 따라 다른 장소, 데이터베이스 및 DISCO에서 사용되는 Kafka REST API로 전송하여 최신 드라이버 위치를 유지한다. 서로 다른 해시된 셀 인덱스가 할당된 링에 서로 다른 서버에 저장된다.  이러한 서버는 Ring Pop이라는 아키텍처에 있으며 새 서버가 추가되거나 서버가 중단될 때 부하가 균등하게 분산됩니다. (일관된 해싱)

 

 

이러한 서버는 Ring Pop(일관된 해싱)이라는 아키텍처에 있으며 새 서버가 추가되거나 서버가 중단될 때 부하가 균등하게 분산된다. Ringpop은 분산 응용 프로그램에 협력과 조정을 제공하는 라이브러리이다.  프로토콜 위에 일관된 해시 링을 유지하고 라우팅 편의로 요청 전달을 제공하며 확장 가능하고 내결함성이 있는 방식으로 애플리케이션을 분할하는 데 사용할 수 있습니다.

 

8. ETA (최단 거리 계산)

라이더의 위치에서 반경 2~3km 떨어진 원 안에서 S2 라이브러리를 사용하여 사용 가능한 모든 드라이버를 나열한 다음 ETA를 확인해야 한다. 여기서 우리는 최단 거리( Euclidean Distance )를 사용할 수 있다. 그러나  A에서 B로 직접 선을 그릴 수는 없다. 거리와 도로는 다르기 때문이다. 연결된 도로를 통해 최단 거리를 계산해야 한다.

 

 

• Geospatial에서 답변을 받은 후 드라이버의 순위를 매긴다. 우선순위에 신경 써야 하는 옵션들은 다음과 같다
  • 추가 운전을 줄어야 한다. (거리가 최단 거리여야 한다) 추가 비용이 발생할 수 있다.
  • 대기 시간을 줄여야 한다.  드라이버 / 유저는 가능한 한 조금 기다려야 합니다.

ETA는 도로 시스템(지리학적이 아님)을 기반으로 계산되며 ETA 계산과 관련된 많은 요소(예: 교통량이 많거나 도로 건설)가 있을 수 있다.  사용자 위치에서 택시를 요청하면 앱은 운행/휴무 중인 택시를 식별할 뿐만 아니라 승차를 마치려는 택시도 포함해야 한다. 탑승을 마치려는 택시 중 하나가 사용자로부터 멀리 떨어진 택시보다 수요에 더 가까울 수 있다. 도로 위의 많은 우버 차량이 4초마다 GPS 위치를 전송하므로 교통량을 예측하기 위해 운전자 앱의 GPS 위치 데이터를 사용할 수 있다.

ETA를 계산하기 위해 전체 도로망을 그래프로 나타낼 수 있다. AI 시뮬레이션 알고리즘이나 간단한 Dijkstra 알고리즘을 사용하여 이 그래프에서 최적의 경로를 찾을 수 있다. 이 그래프에서 노드는 교차로(사용 가능한 택시)를 나타내고 가장자리는 도로 세그먼트를 나타낸다. 우리는 가장자리 가중치를 통해 도로 세그먼트 거리 또는 이동 시간을 나타낸다. 또한 일방통행 도로, 회전 비용, 회전 제한 및 속도 제한과 같은 몇 가지 추가 요소를 그래프에서 표현하고 모델링한다

데이터 구조가 결정되면 라우팅 알고리즘 중 하나인 Dijkstra의 검색 알고리즘을 사용하여 최적의 경로를 찾을 수 있다. 더 빠른 성능을 위해서는 축소 계층 구조를 기반으로 하는 OSRM(Open Source Routing Machine)도 사용해야 한다. 축소 계층 구조를 기반으로 하는 시스템은 라우팅 그래프를 사전 처리하여 경로를 계산하는 데 몇 밀리 초가 걸린다.

 

번외 생각해야 할 시나리오.

- 현재 운행 중인 드라이버가 더 멀리 떨어져 있는 현재 대기 드라이버보다 고객에게 더 적합할 수 있다. 드라이버를 선택하면 고객 대기 시간이 최소화되고 드라이버에 대한 추가 운전 시간이 최소화됩니다.

- 운전자가 고객 근처에서 온라인 상태가 되었지만 다른 운전자가 이미 더 먼 곳에서 파견된 경우 파견 결정을 변경할 방법이 없다.

- 근처에 이제 막 새로운 차량을 공유할 의사가 있는 드라이버가 있다. 새롭게 갱신이 필요하다.

 

10. 데이터베이스

• 데이터베이스는 수평적으로 확장 가능해야 한다. 더 많은 서버를 추가하여 선형적으로 용량을 추가할 수 있다.
• 4초마다 한 번씩 택시가 GPS 위치를 보내고 해당 위치가 데이터베이스에서 업데이트되기 때문에 많은 읽기 및 쓰기를 처리할 수 있어야 한다
• 어떤 작업을 수행하든(스토리지 확장, 백업, 새 노드가 추가될 때 등) 고가용성이어야 한다

이전 Uber는 RDBMS PostgreSQL 데이터베이스를 사용했지만 확장성 문제로 인해 uber는 다양한 데이터베이스로 전환했다. Uber는 MySQL 데이터베이스 위에 구축된 NoSQL 데이터베이스(스키마 없음)를 사용한다

• 캐싱과 queue을 위한 Redis사용. 일부는 Twemproxy를 사용(캐싱 계층의 확장성 제공).
• Uber는 스키마리스(MySQL 위에 자체적으로 구축), Riak 및 Cassandra를 사용. Schemaless는 장기 데이터 저장을 위한 것. Riak과 Cassandra는 고가용성, 저지연 요구 사항을 충족
• Uber는 많은 MySQL 인스턴스를 오케스트레이션하는 자체 분산 열 저장소를 구축

 

11. 기타 구성 요소

• 웹 소켓 - 양방향으로 웹 소켓을 통해 메시지를 보내고 받을 수 있는 비동기 및 이벤트 기반 프레임워크이다. 빠른 응답을 위해 요즘 HTTP/2와 함께 gRCP를 사용하는 것이 일반적인 대안이 되고 있다.
• 우버에서는 TChannel이라는 자체 RPC 메커니즘을 사용한다.
  • Twitter의 Finagle에서 영감을 받은 양방향 요청/응답 프로토콜
  • TChannel(우버에서 만든 RPC에 사용되는 네트워킹 프로토콜)은 HTTP보다 20배 빠르다.
  • 중개자가 전체 페이로드를 이해하지 않고도 매우 쉽게 전달 결정을 내릴 수 있도록 고성능 전달 경로를 원했다
  • 헤드 오브 라인 차단이 없도록 적절한 파이프라이닝을 원했으며 요청과 응답은 언제든지 어느 방향으로든 보낼 수 있어야 한다.
  • 페이로드 체크섬 및 모든 요청은 시스템을 통과할 때 추적 가능해야 한다
  • Uber는 HTTP와 Json 사용하지 않는다.  Thrift over TChannel로 이동하고 있다.
  • ringpop은 TChannel 기반 영구 연결을 통해 애플리케이션 트래픽을 팬 아웃하거나 전달하는 데 사용되며  TChannel은 서비스 간 대화에도 사용된다

 

기타 참고사항

GRPC 대 MQTT 대 Websockets를 통한 데이터 스트리밍

 

우버 전체 아키텍처

참고

https://www.youtube.com/watch?v=J3DY3Te3A_A&ab_channel=SuccessinTechSuccessinTech

https://www.youtube.com/watch?v=umWABit-wbk

https://www.youtube.com/watch?v=Tp8kpMe-ZKw&ab_channel=codeKarle

https://techtakshila.com/system-design-interview/chapter-3/

https://www.youtube.com/watch?v=8zWQYCMgVOI&ab_channel=SaralSaxena

https://www.geeksforgeeks.org/system-design-of-uber-app-uber-system-architecture/

https://medium.com/nerd-for-tech/uber-architecture-and-system-design-e8ac26690dfc

http://highscalability.com/blog/2015/9/14/how-uber-scales-their-real-time-market-platform.html

https://medium.com/@narengowda/uber-system-design-8b2bc95e2cfe