개발 자체의 글보다는 주로 아키텍처에 대한 기사 및 글을 번역하여 작성하고 있습니다.

1. 소개

도시에서 이동할 때 많은 사람들이 Uber 또는 Lyft와 같은 차량 공유 앱을 선택합니다. 실제로 이러한 앱은 경쟁력 있는 가격, 합리적으로 짧은 대기 시간 및 고가용성을 제공하여 단거리 통근을 매우 쉽게 만듭니다. 기술적인 관점에서 이러한 시스템은 가장 가까운 이웃 검색이 어렵기 때문에 매우 흥미롭습니다. 이 기사에서는 Uber/Lyft와 같은 대규모 차량 공유 앱의 디자인을 공유하고 싶습니다.

요구 사항

최신 승차 공유 앱은 승차 매칭 외에도 카풀, 여행 공유, 실시간 채팅과 같은 복잡한 기능을 제공합니다. 이 기사에서는 토론을 간략하게 유지하고 차량 예약이라는 핵심 기능에만 집중하고 싶습니다. 다음은 당사 시스템 의 기능 요구 사항 입니다.

사용자는 차량 서비스를 요청할 수 있으며 가까운 거리에 있는 운전자와 연결되어야 합니다.
사용자는 주변의 모든 드라이버를 볼 수 있습니다(어떤 드라이버를 선택하지는 않지만)
드라이버는 근처 라이더의 요청에 응답/거절할 수 있습니다.
여행이 생성되면 양 당사자는 서로의 실시간 위치를 봅니다.

말할 필요도 없이 시스템은 확장 가능하고 가용성이 높아야 합니다.

트래픽 추정

트래픽에 대해 이야기하기 전에 Uber의 고유한 기능인 데이터 사용량이 로컬임을 살펴보겠습니다. Slack이나 Instagram과 같은 앱과 달리 지역 간 데이터 통신이 거의 필요하지 않습니다. 물리적으로 뉴욕에 있는 경우 런던에서 차량 서비스를 예약할 수 없습니다. 따라서 위치 데이터와 여행은 다른 지역에 걸쳐 복제되지 않습니다(프로필과 같이 자주 액세스하지 않는 데이터는 물론 전역적으로 복제됩니다). 그런 의미에서 글로벌 트래픽에 대한 논의는 지역 트래픽만큼 의미가 없습니다.

시스템에 도달하는 라이드 요청의 양은 앱의 인기도에 따라 다릅니다. 여기에서는 일반화된 솔루션에 대한 상당한 지역 트래픽을 가정합니다.

지역별로 근접성을 기준으로 도시를 그룹화합니다. 미국 전체를 덮으려면 십여 개의 지역이 필요합니다.
한 지역에서 약 100,000명의 활성 드라이버가 있을 것으로 예상합니다.
한 지역에서 약 1백만 명의 활성 사용자가 있을 것으로 예상합니다.
전 세계의 총 사용자 수는 1천만 명입니다.

운전자와 탑승자 모두 경도, 위도 및 추가 메타데이터로 구성된 각 메시지와 함께 위치를 ~5초로 내보낸다고 가정합니다. 또한 라이더는 정기적으로 주변 드라이버(~5초)를 확인하고 때때로 라이드를 요청합니다. 예상할 수 있는 QPS 및 대역폭의 양은 다음과 같습니다.

초당 ~200K 위치 업데이트/쓰기 예상
초당 ~200K 쿼리가 예상되며 최대 트래픽 처리를 위해 두 배로 늘립니다.
각 위치 메시지는 ID(8바이트), 경도 및 위도(16바이트) 및 기타 정보(64바이트)로 구성됩니다. 총 업로드 대역폭은 88MB/s에 불과합니다.

2. 하이레벨 디자인

데이터베이스 디자인

애플리케이션의 액세스 패턴에 따라 사용되는 스키마가 결정됩니다. 데이터베이스에 도달한 요청을 조사해 보겠습니다.

읽기 작업

사용자 ID가 주어지면 해당 프로필을 검색합니다.
사용자 ID가 주어지면 사용자가 완료한 모든 여행 검색
경도와 위도가 주어지면 주변의 모든 운전자에게 쿼리

쓰기 작업

사용자 ID가 주어지면 해당 위치를 업데이트하십시오.
여행 ID가 주어지면 운전자는 요청을 수락/거절할 수 있습니다.

데이터베이스 스키마

액세스 패턴이 주어지면 복잡한 관계 쿼리가 생성되지 않으므로 샤딩된 SQL이 좋은 선택입니다. 강력한 일관성이 어려운 요구 사항이 아닌 경우 Cassandra와 같은 NoSQL 데이터베이스도 여기에서 사용할 수 있습니다.

운전자 프로필 표

그림 1. 운전자 프로필 테이블, 작성자별 그림

라이더 프로필 테이블

그림 2. 라이더 프로필 테이블, 저자별 그림

여행 세부 정보 테이블

그림 3. 여행 내역표, 작가별 그림

이러한 데이터베이스 테이블 외에도 자주 업데이트되는 위치 데이터를 보관할 또 다른 고성능 저장소가 필요합니다. 라이브 위치 데이터는 본질적으로 임시적이므로 디스크에 저장하는 것은 의미가 없습니다. 좋은 대안은 Redis 또는 Memcache와 같은 메모리 내 캐시를 사용하는 것입니다.

캐시 스키마

위치 진실 캐시

그림 4. 위치 진실 캐시, 작성자별 그림

이 캐시는 사용자 위치와 관련하여 진실의 근원입니다. 전화 앱은 정확성을 유지하기 위해 정기적인 업데이트를 보냅니다. 사용자의 연결이 끊어지면 해당 기록은 30초 후에 만료됩니다.

드라이버 근접 캐시

그림 5. 드라이버 근접 캐시, 작성자별 그림

근접 캐시는 주변 운전자 검색에 중요합니다. 위치가 주어지면 GeoHash 를 사용하여 위치 키를 계산하고 그리드의 모든 드라이버를 검색할 수 있습니다. 자세한 내용은 세부 정보 섹션에서 설명하겠습니다.

건축물

어떤 데이터를 저장할 것인지 더 명확하게 이해했다면 이제 서비스 지향적인 디자인을 할 때입니다!

알림 서비스 : 백엔드가 클라이언트에 정보를 보내야 할 때마다 알림 서비스를 사용하여 메시지를 전달합니다.
여행 관리 서비스 : 여행 시작 시 모든 당사자의 위치를 모니터링하고 경로를 계획하는 데 필요한 서비스입니다.
승차 매칭 서비스 : 승차 요청을 처리하는 서비스입니다. 운전자 응답(수락 또는 거부)을 기반으로 주변 운전자 및 중매를 찾습니다.
위치 서비스 : 모든 사용자는 이 서비스를 통해 정기적으로 위치를 업데이트해야 합니다.

그림 6. 상위 수준 아키텍처, 작성자별 그림

워크플로

Bob은 Ride Matching 서비스에 라이드 요청을 보내고 드라이버와 짝을 이루기를 희망합니다.
라이더 매칭 서비스는 위치 서비스에 접속하여 동일한 지역에서 사용 가능한 모든 드라이버를 찾습니다.
그런 다음 라이더 매칭 서비스는 순위/필터링을 수행하고 알림 서비스를 통해 선택한 드라이버에게 라이드 요청을 푸시합니다.
드라이버는 요청을 수락/거절할 수 있습니다. 수신되면 라이드 매칭 서비스에서 여행 세부 정보를 여행 관리 서비스로 보냅니다.
여행 관리 서비스는 여행 진행 상황을 모니터링하고 여행에 관련된 모든 당사자에게 드라이버 및 라이더 위치를 방송합니다.

3. 세부사항

고수준 아키텍처 설계는 비교적 간단합니다. 그러나 자세히 살펴보면 여전히 약간의 주름이 있습니다. 예를 들어, 나는 여행 요금, 카풀 등과 같은 기능을 무시했습니다. 이 기사에서는 Uber/Lyft의 기반이 되는 위치 관련 문제에 초점을 맞추고 싶습니다.

3.1 주변 드라이버를 효율적으로 찾는 방법은 무엇입니까?

가장 가까운 이웃 검색은 어려운 문제이며 시스템의 규모는 효율적인 조회를 훨씬 더 어렵게 만듭니다. 라이더와 데이터베이스의 모든 운전자 사이의 거리를 계산하는 대신 GeoHash라는 기술을 사용하여 사용자의 위치를 그림 7의 한 셀에 해당하는 고유 키로 변환하고 검색을 몇 개의 인접한 셀로만 제한할 수 있습니다.

그림 7. GeoHash 위치, PC 크레딧: Movable Type Scripts

그림 7은 키와 위치 셀 간의 일대일 매핑인 GeoHash의 키 속성을 보여줍니다. 따라서 다음 휴리스틱을 사용하여 드라이버를 빠르게 조회할 수 있습니다.

사용자 위치가 주어지면 경도와 위도에서 GeoHash를 계산합니다.
GeoHash 키를 사용하면 8개의 인접 셀에 대한 키를 쉽게 계산할 수 있습니다. ( 이 게시물 참조 )
9개의 키를 모두 사용하여 위치 서비스를 쿼리합니다. 해당 셀에서 드라이버를 검색합니다.

GeoHash의 정확도는 키 길이에 의해 결정됩니다. 키가 길수록 각 셀은 작아집니다.

그림 8. geohash 키 길이 및 셀 크기, 작성자별 그림

어떤 키를 사용하는 것이 좋을까요? 실제로 키 크기는 드라이버와 라이더의 수를 기반으로 반복적으로 결정됩니다. 내 생각에 좋은 출발점은 몇 개의 도시 블록을 포함하기 때문에 크기 6이 될 것입니다.

그림 9. 크기-6 GeoHash는 상당한 양의 적용 범위를 제공합니다(작성자별 그림).

이러한 셀 중 하나에 들어갈 수 있는 운전자와 라이더의 최대 수에는 물리적 제한이 있습니다. 그림 5로 돌아가서 각 셀은 Redis의 Driver Proximity 캐시에 있는 항목이 됩니다.

Redis가 이 수준의 트래픽을 처리할 수 있는지 궁금할 수 있습니다. 해당 지역에 1백만 명의 활성 라이더가 있는 경우 클러스터에 도달하는 요청 수는 약 200K 쓰기/초(각 사용자가 위치 업데이트 ~5초) 및 2백만 읽기/초(각 사용자가 9개의 Redis 키 ~5초 읽기)입니다.

그림 10. 단일 Redis 노드 용량, PC by Redis.com

32개의 스레드가 있는 단일 AWS c5.18xlarge 노드로도 시스템이 트래픽을 처리할 수 있습니다. 실제로 수십 대의 컴퓨터에 작업 부하를 분산하고 ~1억 수준의 RPS 용량을 달성할 수 있습니다.

메모리 제한은 어떻습니까? 크기 6 지오해시를 사용하면 캐시에 잠재적으로 32⁶ ~=100억 개의 키가 있습니다. 그러나 빈 키가 제거 되면 이 양의 키에 도달하지 않습니다 (그림 5). 실제로 캐시 항목의 수는 각 자동차가 하나의 셀에만 있을 수 있기 때문에 자동차 수에 의해 제한됩니다! 따라서 메모리는 병목 현상이 아닙니다.

3.2 위치 업데이트

Redis에서 위치 서비스를 호스팅할 수 있는 가능성을 확신했기를 바랍니다. 이제 사용자가 위치를 업데이트하는 방법을 살펴보겠습니다.

캐시에는 두 개의 테이블이 있습니다. 위치 진리표와 드라이버 근접성 테이블입니다. 위치 진리표의 사용법은 간단합니다. 사용자의 모바일 앱은 5초마다 위치 서비스에 사용자 ID와 위치를 보냅니다. 사용자의 정확한 위치가 필요할 때마다 시스템은 사용자 ID로 이 테이블을 쿼리할 수 있습니다.

근접 테이블은 본질적으로 더 흥미 롭습니다. 운전자는 차 안에서 이리저리 움직입니다. 즉, 종종 한 셀을 다른 셀로 건너게 됩니다. 백엔드가 드라이버로부터 업데이트를 수신할 때 과거에 어떤 셀이었는지 알 수 없습니다. 따라서 오래된 셀에서 드라이버를 제거하기가 어렵습니다. 그 의미는 분명합니다. 오래된 데이터로 인해 동일한 드라이버가 여러 셀에 나타날 수 있습니다.

그림 11. Redis의 오래된 레코드, 작성자별 그림

이 문제를 해결하기 위해 각 레코드에 타임스탬프를 도입할 수 있습니다. 타임스탬프를 사용하면 오래된 위치 데이터를 쉽게 필터링할 수 있습니다. 실제로 Redis의 정렬된 집합 데이터 구조는 이러한 기능을 달성하는 효율적인 방법입니다.

운전자의 위치 외에도 차종, 운행상황(무임, 승차) 등의 정보를 캐시에 보관할 수 있습니다. 추가 정보를 이용하면 데이터베이스(차량 정보 및 운행 상황 조회)로의 왕복을 건너뛰어 빠른 라이드 매칭이 가능합니다.

3.3 여행 기록

우리 시스템의 또 다른 중요한 기능은 여행 기록입니다. 완료된 여행의 경우 운전자가 이동한 경로를 저장하고 클라이언트가 검토할 수 있도록 하려고 합니다.

이 기능을 구현하는 방법에는 여러 가지가 있습니다. 가장 간단한 방법은 운전자가 자신의 위치와 여행 상태를 보고하도록 하는 것입니다. 위치 서비스는 영구 저장을 위해 데이터베이스에 여행 중 상태의 모든 위치 업데이트를 일괄적으로 기록합니다 .

클라이언트 앱에 의존하는 것은 위험합니다. 여행 중에 클라이언트 앱이 모든 로컬 데이터를 잃으면 어떻게 됩니까? 재부팅하기 전에 드라이버의 상태를 알 수 없습니다. 실패에서 복구하려면 클라이언트 앱이 데이터베이스에 완료되지 않은 여행이 있는지 확인하고 드라이버와 상태를 확인해야 합니다.

그림 11. 장애 복구, 작성자별 수치

4. 요약

이 기사에서는 Uber/Lyft와 같은 차량 공유 앱의 기초를 설계했습니다. 특히 근접 검색을 구현하는 방법을 자세히 살펴보았습니다. 면접에서 완벽한 답은 없다는 것을 명심하십시오. 모든 솔루션에는 결함이 있습니다. 우리의 임무는 주어진 가정과 제약 조건에서 충분히 잘 작동하는 디자인을 찾는 것입니다.

https://towardsdatascience.com/ace-the-system-design-interview-uber-lyft-7e4c212734b3

Uber/Lyft의 Ace 시스템 설계