2024/07 27

2장. 주변 친구

"주변친구" 기능은 본인 위치 정보 접근 권한을 허락한 사용자에 한해 인근의 친구 목록을 보여주는 시스템이다.근접성 서비스의 경우 사업장 주소는 정적이지만, 주변 친구 위치는 자주 바뀔 수 있다.1단계: 설계 범위 확정기능 요구 사항모바일 앱에서 주변 친구를 확인할 수 있어야 한다.주변 친구 목록에 보이는 각 항목에는 해당 친구까지의 거리, 해당 정보가 마지막으로 갱신된 시각(timestamp)이 함께 표시친구 목록은 몇 초마다 한 번씩 갱신되어야 한다.비기능 요구 사항낮은 지연 시간(low latency): 주변 친구의 위치 변화가 반영되는데 오랜 시간이 걸리면 안된다.안정성: 때로 몇 개 데이터가 유실되는 것 정도는 용인할 수 있다.결과적 일관성(eventual consistency):강한 일관성을 ..

1장. 근접성 서비스 - 2편

※ 내용을 1편(1, 2단계)과 2편(3, 4단계)으로 나눴습니다. ※  근접성 서비스(proximity service)는 음식점, 호텔, 극장, 박물관 등 현재 위치에서 가까운 시설을 찾는데 이용 3단계. 상세 설계시스템 형태 중 일부 더 상세하게 살펴본다. 3.1 데이터베이스의 규모확장성중요한 사업장 테이블과 지리 정보 색인 테이블의 규모 확장성을 살펴본다.1) 사업장 테이블한 서버에 담을 수 없을 수 있다.샤당하기 좋은 후보이다. 사업장 ID를 기준으로 샤딩한다.2) 지리 정보 색인 테이블지오해시 테이블 구성 두 가지 방법방법 1: 지오해시에 연결되는 모든 사장 ID를 JSON 배열로 만들어 같은 열에 저장방법 2: 지오해시에 속한 사업장 ID 각각을 별도 열로 저장 추천: 두 번째(방안 2) 방법..

1장. 근접성 서비스 - 1편

※ 내용을 1편(1, 2단계)과 2편(3, 4단계)으로 나눴습니다. ※   근접성 서비스(proximity service)는 음식점, 호텔, 극장, 박물관 등 현재 위치에서 가까운 시설을 찾는데 이용 1단계: 설계 범위1.1 기능 요구 사항세 가지 핵심 기능사용자의 위치와 검색 반경 정보에 매치되는 사업장 목록을 반환사업장 소유주가 사업장 정보를 추가, 삭제, 갱신할 수 있도록 하되, 그 정보가 검색 결과에 실시간으로 반영될 필요는 없다고 가정고객은 사업장의 상세 정보를 살필 수 있어야 한다.1.2 비기능 요구 사항낮은 응답 지연: 사용자는 주변 사업장을 신속히 검색할 수 있어야 한다.데이터 보호위치 기반 서비스(Location-Based Service, LBS)를 설계할 때는 사용자의 정보 보호 방법을..

[알고리즘] 피보나치 수열의 시간복잡도

기존 알고리즘O(2^n)매 번 함수가 호출 될 때마다 또 두 번씩 호출 된다.F(n, r) { if (n  기존 알고리즘 + 메모이제이션O(n)메모이제이션을 통해 n을 두 번 호출 안하게 된다.F(n, r) { if (n 0) return r[n]; ⭐ return r[n] = F(n-1, r) + F(n-2, r);} 변형된 피보나치 수열 풀이코드O(n2^n)으로 계산은 틀렸다.2^n을 n번 반복하는 것으로 때문에 착각할 수 있다.allF은 1부터 n까지의 모든 피보나치 수를 계산하고 출력  F(1): O(2^1)F(2): O(2^2)F(3): O(2^3)...F(n): O(2^n)O(2^1 + 2^2 + 2^3 + ... + 2^n-1 + 2^n)= 2^n - 2 + 2^n= 2 *..

15장. 구글 드라이브 설계

구글 드라이브는 파일 저장 및 동기화 서비스로, 문서, 사진, 비디오, 기타 파일을 클라우드에 보관할 수 있다.해당 파일은 어떤 단말에서도 이용 가능하고 공유도 쉽게한다. 1단계 설계 범위 확정기능 설계파일 추가-> 가장 쉬운 방법은 파일을 구글 드라이브 안으로 떨구는 것파일 다운로드여러 단말에 파일 동기화. -> 하나의 단말에서 파일을 추가하면 다른 단말에도 자동으로 동기화파일 갱신 이력 조회파일 공유파일이 편집된거나 삭제되거나 새롭게 공유되었을 때 알림 표시논의 대상 제외구글 문서 편집 및 협업 기능비기능 설계안전성: 저장소 시스템에서 안전성이 가장 중요빠른 동기화 속도: 파일 동기화에 오랜 시간이 걸리면 사용자는 인내심을 잃는다.네트워크 대역폭: 네트워크 대역폭을 불필요하게 많이 소모규모 확작성: ..

[알고리즘] 빅오(Big-O) 표기법

What is Big-O?알고리즘의 실제 실행 시간을 표기하는 것보다는 데이터 또는 사용자의 증가율에 따라 알고리즘의 성능을 예측하는 것이 목표Mathematical notation that describes algorithm efficiencyTime & Space complexityDescribes the growth rate of algorithms용어 정리n, m: 함수의 매개변수로 입력의 크기를 의미할 때 사용.  O(1) - const time인자로 받는 데이터의 크기 상관없이 일관되게 0의 위치에 있는 값을 확인F(int[] n) { return (n[0] == 0)? true:false;}  O(n) - 선형 시간(linear time)인자로 n개의 데이터를 받으면 n번 루프(loop)를 ..

14장.유튜브 설계

1단계 설계 범위 확정요구사항빠른 비디오 업로드원활한 비디오 재생재생 품질 선택 기능낮은 인프라 비용높은 가용성과 규모 확장성 그리고 안정성지원 클라이언트: 모바일 앱, 웹 브라우저 그리고 스마트 TV 개략적 규모 추정일간 능동 사용자 수는 5백만사용자 한 명은 하루에 평균 5개의 비디오를 시청10%의 사용자가 하루에 비디오 한 개 업로드비디오 평균 크기는 300MB비디오 저장을 위해 매일 새로 요구되는 저장 용량 = 5백만 * 10% * 300MB = 150TBCDN 비용CDN에서 나가는 데이터의 양에 따라 과금한다.해당 비용을 줄이는 방향으로 설계 진행 2단계 개략적 설계안기존 클라우드 서비스를 이용해도 좋다.주어진 시간 안에 적절한 기술을 골라 설계를 마치는 것이 중요하다.BLOB 저장소나 CDN을..

13장. 검색어 자동완성 시스템

웹 사이트 검색 창에 단어를 입력하다 보면 입력중인 글자에 맞는 검색어가 자동을 완성된다.이런 기능을 보통 검색어 자동완성이라고 부른다.1단계 설계 범위 확정요구사항빠른 응답 속도: 사용자가 검색어를 입력함에 따라 자동완성 검색어도 충분히 빨리 표시되어야 한다.연관성: 자동완성 되어 출력되는 검색어는 사용자가 입력한 단어와 연관된 것이어야 한다.정렬: 시스템의 계산 결과는 인기도 등의 순위 모델에 의해 정렬되어 있어야 한다.규모 확장성: 시스템은 많은 트랙픽을 감당할 수 있도록 확장 가능해야 한다.고가용성: 시스템의 일부 장애가 발생해도 시스템은 계속 사용 가능해야한다. 개략적 규모측정일간 능동 사용자(DAU)는 천 만명으로 가정평균적으로 한 사용자는 매일 10건의 검색을 수행질의할 떄마다 평균적으로 2..

12장. 채팅 시스템 설계

1단계 설계 범위 확정응답지연이 낮은 일대일 채팅 기능최대 100명까지 참여할 수 있는 그룹 채팅 기능사용자의 접속상태 표시 기능다양한 단말 지원, 하나의 계정으로 여러 단말에 동시 접속 지원푸시 알림 2단계 개략적 설계안 먼저, 채팅을 시작하려는 클라이언트는 네트워크 통신 프로토콜을 사용하여 서비스에 접속한다.대부분의 클라이언트/서버 애플리케이션에서 요청을 보내는 것은 클라이언트(사용자)이다.메세지 송신 클라이언트가 수신  클라이언트에게 전달할 메세지를 채팅 서브시에 보낼 때, HTTP 프로토콜을 사용한다.채팅 서비스와의 접속에는 keep-alive 헤더를 사용하면 효율적이다.=> 클라이언트와 서버 사이의 연결이 끊지 않고 계속 유지할 수 있다.=> TCP 접속 과정에서 발생하는 핸드 쉐이크 횟수도 줄..