kaonmir
시리즈
SAA
DOP
System Design Interview
Linux
ETC
Share
Sign In
Home
Kaonmir (손성훈)
Copy & Translate
시리즈
SAA
후기
시험 소개 & 꿀팁
Terminology
Region & Availability Zone
Budget
IAM
EC2 - Fundamentals
EC2 - SAA Level
EC2 Storage
ELB & ASG
RDS / Aurora / ElastiCache
S3
CloudFront & Global Accelerator
Route 53
Storage Extras
Decoupling
Container
Serverless
Database
Monitoring, Troubleshooting & Audit
IAM Advanced
Security & Encryption
VPC
Disaster Recovery & Migrations
Ohter Services
기술 백서 총 모음
기술 백서(White paper)
DOP
CodeCommit, CodeBuild, CodeDeploy
CodePipeline, CodeStar, Jenkins
CloudFormation - Fundamentals
CloudFormation - DOP Level
Elastic Beanstalk
Lambda & Step Function & API Gateway
ECS & ECR & OpsWorks
Kinesis
CloudWatch
CloudTrail & X-Ray & ElasticSearch & Tagging
SSM & Config & Service Catalog & Inspector
Other Services
Auto Scaling Group (ASG)
DynamoDB & S3
Multi AZ & Multi Region & Multi Account
AWS Organizations & On-Premise Strategy
Disaster Recovery (DR)
서비스별 기본 배포 전략 비교
CodeDeploy appspec hook
System Design Interview
사용자 수에 따른 규모 확장성
개략적인 규모 추정
시스템 설계 면접 공략법
처리율 제한 장치
안정 해시
키-값 저장소
분산 시스템을 위한 유일 ID 생성기
URL 단축기
웹 크롤러
알림 시스템
뉴스 피드 시스템
채팅 시스템
검색어 자동완성 시스템
유튜브
구글 드라이브
Linux
ETC
AI를 더 잘 쓰기 위한 IT 용어
검색어 자동완성 시스템
요구 사항
빠른 응답 속도 : 100ms 이하
연관성
정렬 : 인기도 같은 순위 모델에 따라 정렬
규모 확장성, 고가용성
규모 추청
Given
DAU = 10,000,000명
사용자당 일일 검색량 = 10 검색
질의
검색 한 번 당 평균 데이터량 = 20B
문자 인코딩 방식 = ASCII(1문자 = 1B)
한 단어 = 5글자, 한 번 검색 = 4단어 = 20바이트
글자 입력마다 요청 전송 = 검색당 20회 질의
질의 중 20%는 신규 검색어
Derived
초당 질의수(QPS) = 10,000,000명 x 10 검색 x 20 글자 / 1 하루
=
2 \times 10^{9} \div (24 \times 3600) \approx
초당 24,000 질의
최대 QPS = QPS x 2 = 48,000
신규 검색 바이트 = 24,000 QPS x 20% = 4.8KB/sec
\approx
0.4GB/day
개략적인 설계안
데이터 수집 서비스 : 사용자의 입력을 수집해 빈도 테이블을 갱신한다.
질의 서비스 : 빈도 테이블을 살펴 자동완성 검색어를 반환한다.
SELECT * FROM frequency_table WHERE query LIKE `prefix%` ORDER BY frequency DESC LIMIT 5
상세 설계
트라이 자료구조
RDBMS 대신 trie(prefix tree)를 사용하여 검색 속도를 향상시킬 것이다.
정의
p : 접두어의 길이 (즉, tree의 depth)
n : 노드 개수
c : 주어진 노드의 자식 노드 수
자동완성 검색어 추출
해당 접두어로 트리를 따라간다.
O(p)
하위 트리를 탐색해 유효 노드(검색 문자열)를 찾는다.
O(c)
유효 노드를 정렬해 인기 있는 검색어 k개를 찾는다.
O(c \cdot \log{c})
한계 극복
k개의 결과를 얻기 위해 트리 전체를 탐색해야 할 수도 있기 때문에
접두어의 최대 길이를 제한하고
인기 검색어를 캐싱한다.
적절한 노드에 하위 트리의 인기 검색어를 캐싱할 수 있다.
공간이 많이 필요하지만 응답속도는 매우 빠르다.
데이터 수집 서비스
질의마다 매번 트라이를 갱신하기에는 비용이 많이 든다. 이 방법보다는 질의를 로그로 남기고 로그를 주기적으로 분석해 트라이를 갱신하는 방법이 효과적이다.
데이터 분석 서비스 로그
: 질의마다 (질의, 시간) 데이터를 로그로 저장한다.
로그 취합 서버
: 로그를 주기적으로 취합한다. 10분에서 일주일까지 비즈니스에 따라 상이하다.
취합 데이터
: 로그를 일주일마다 취합해 (질의, 주차, 빈도) 테이블을 만든다.
트라이 캐시
: 분단 캐시 시스템으로 매주 trie DB의 스냅샷을 떠 갱신한다.
트라이 데이터베이스
Document : MongoDB 같이 트라이를 직렬화해 저장
Key-Value : Redis 같이 해시 테이블 형태로 변환해 저장
질의 최적화 방안
AJAX req
: 페이지를 새로고침하고 필요한 데이터만 벡엔드에서 가져온다.
브라우저 캐싱 : 자동완성 검색어 제안은 실시간으로 바뀌지 않기 때문에 브라우저에 캐싱한다.
cache-control: private, max-age=3600
private
: 공용 캐시에 저장해서는 안된다.
max-age
: 최대 저장 시간, 단위는 초이다.
데이터 샘플링
: N 개의 요청 중 1개만 로깅해 전체 용량을 줄인다.
트라이 연산
트라이 갱신
매주 한 번 갱신, 새로운 트라이를 만들어 기존의 것을 대체한다.
노드를 개별적으로 갱신, 느리다.
검색어 삭제
필터 레이어를 둔다.
저장소 규모 확장
샤딩할 수 있다. (a~m과 j~r)은 다른 서버에 저장
Made with SlashPage