Google Typeahead 시스템 설계

검색 표시줄→ 사용자가 몇 개의 문자를 입력할 때, 입력한 문자의 처음 10개의 제안을 사용자에게 되돌려 줄 수 있어야 합니다.
제안된 주파수를 표의 최대 값으로 되돌려줍니다.
검색에 World "CA"를 입력합니다.
캘리포니아 주→
고양이→ 20K<- 주파수 개수
소떼→ 25K<- 주파수 개수
낙타.
자동차
택시.
재난적→ 20001<- 주파수 개수
오다
낙타.
낙타.
만약 사용자가 검색 표시줄에서 특정 단어를 검색한다면, 세계가 사전에 있다면, 세계의 주파수 계수를 증가시키고, 사전에서 찾을 수 없으면, 새로운 세계를 사전에 추가합니다
일반적으로 고급 디자인 문제는 4부분으로 구성된다
요구
어림잡다
디테일한 디자인.
모니터링, 경고 및 백업
1. 요구 사항(5-7분):
기능성
10가지 제안을 되돌릴 수 있을 것 같다.
검색된 단어의 빈도를 업데이트합니다.
여기서 우리는 문장이 아니라 단어만 고려한다.(가정)
500밀리초를 더 기다린 다음 다음 다음 결과를 되돌려줍니다.[사용자가 CA를 입력하고 1초를 기다린다고 가정하고 사용자 유형이 나타나면 상위 10개의 결과를 되돌려줍니다.
맞춤법 검사(범위 초과)가 필요하지 않습니다. [맞춤법 검사가 필요할 수 있으므로 고려할 필요가 없습니다.]
사용자 정의 제안(범위 초과)[사용자의 이전 검색 기반]
영역별 검색(범위 초과)
숫자와 자모만 생각하면 된다.
비기능성→ 부탁?엔지니어로서 비기능적인 수요가 나쁜 디자인을 초래하고 사용자의 체험을 방해할 수 있다는 것을 고려하지 않고 어떤 부분을 결정해야 한다.
잠복기→ 약 10ms 낮음 [사용자가 입력하고 10ms 이내에 결과]
활용성→ 고가용성 [가능한 한 빨리 시스템 사용 가능]
일치성→ 즉각적인 요구는 없지만 시스템은 최종적으로 일치해야 한다.
신빙성
시스템은 사용자의 정보를 포착하지 않기 때문에 믿을 만해야 한다.
가장 좋은 건의는 System design online course에서 나온다.
안전층이 이미 자리에 앉았다.[인증 또는 승인]
속도 제한기
2.예상(5-7분):
평가를 시작할 때, 가설을 세워야 하거나, 면접관이 필요하다.
그것은 두 부분으로 구성되어 있다
QPS
용량
가정:
매일 약 1억 개의 단어를 검색한다.
검색된 단어 중 0.001%는 시스템의 새 단어입니다.
QPS(초당 쿼리): 두 부분으로 구성됨
QPS 읽기
QPS 쓰기
QPS[시스템에서 이전 10가지 권장 사항으로 돌아가기] 읽기
100*10^6 (매일)/24*60*60(86400)
10^8/ 10^5
10^3=1000 읽기 QPS*2 (곱셈기) = 2000
QPS 작성[시스템에서 특정 키워드 검색]
읽기와 쓰기 비율은 3:1입니다. [우리가 쓴 책'CA'가 첫 10개의 결과를 준다고 가정하면 대기시간이 500밀리초이고 다시'CAT'를 입력하면 첫 10개의 결과를 되돌려주고 시스템에서 읽은 내용을 다시 쓰기 때문입니다. 따라서 사용자 읽기 요청은 3, 쓰기는 1]
QPS 쓰기→ 초당 600~700회 쓰기
용량 [자원을 저장하기 위해 램이나 디스크나 공간이 얼마나 필요한가]
하루에 100만 번 검색해요.
입선을 신청하다
이야기
빈도
500미터(현재 격언) [영어사전만 고려]
500M*(글자당 평균 7개 크기)*(1자 1바이트)*100바이트→ 이미 나온 단어 [단어마다 공간을 차지한다.]
하루하루→ 500m*0.001→ 매일 5만 개의 새 단어.→ 50K*7*100→ 매일 35K*10^3=35M 신조어
다음해
500M*7*100+35M*365바이트
=35M*10^4+~(1M*10^4)
= 36 * 10^6 * 10 ^ 4/(1024 * 1024 * 1024)
= 연간 360GB의 데이터
3. 세부 설계(30-35분):
API[모든 API 나열]
API 읽기→ 사용자가 결과를 기다리는 중
요청 가져오기
제안 (char[] 접두사 가져오기;
되돌아오다→ 아무것도 없다, 성공/실패
이 시스템은 읽기량이 많은 시스템이므로 가능한 한 빨리 결과를 되돌릴 수 있도록 최적화해야 한다.이전 10가지 제안으로 돌아가기
API 업데이트→ 사용자가 결과를 기다리지 않았습니다.
게시 요청
업데이트 FreqForWord (문자 [])
되돌아오다→ 아무것도 없다, 성공/실패
이 시스템은 읽기량이 많은 시스템이므로 가능한 한 빨리 결과를 되돌려야 한다
사용자가 주파수의 증가를 정말 개의치 않기 때문에 쓰는 속도도 느려질 것이다.→ 쓰기 전에 먼저 읽으세요.
시스템 설계 모델링[설계 및 구성 요소 작성]
시스템에 항상 일부 구성 요소가 존재합니다.
손님: 네.
인증 또는 권한 부여 [부하 평형기 또는 마이크로 시스템 구조 또는 배열층]
웹 서버 [읽기/업데이트 api]
2 로드 밸런서 비즈니스 논리 실행
App server[Cache][suggestion service store sortedData structure training in Python]
데이터베이스
데이터 복제
-> 10가지 권장 사항으로 돌아가기
-> 반환 빈도 검색어
-> 키 값 대신 접두사, 단어 쌍 및 빈도를 저장할 수 있습니다.
-> 더 빠른 읽기
->키 값 저장 [업데이트용 데이터베이스-1], 접두사 및 단어 쌍 및 빈도 저장 [읽기 데이터베이스-2]
-> 오프라인 작업[빈도 및 업데이트 빈도 비교]
-> 한 표는 주파수표이고 다른 표는 접두사표이기 때문에 데이터베이스에 쓰는 데 영향을 주지 않는다.
참조 그림: 1.1
테이블 및 색인 [모든 테이블 나열]
SQL 데이터베이스
Nosql 데이터베이스
표 1(권장 표)
문자열 접두사← 열쇠.
목록 > 10가지 주요 권장 사항
표 2(WordFreq 테이블)
문자열← 열쇠(Pk)
Int64 주파수← 가치관
배율 조정
가로 [리소스의 크기를 변경하는 대신 리소스 추가]
수직이었어
수평 및 수직 축척 조합을 선호
데이터의 분할 및 분할 영역:
거리 기반 탄젠트→ 건의표
A、 B,C….Z→ 26 예
Tier 2 A 부하가 많음
AA-AP,AQ-AZ
날짜 기반 음영처리
매일 너는 하나의 단독 조각을 만들 것이다.[너는 스크롤 창이 있어]
단어
계층 2→ 범위 기반
A-G H-P Q-Z
복제품
일반적으로 운영 디바이스에서 데이터를 읽고 디바이스에서 데이터를 씁니다.
(제안표)→ 최대 5회 복제
(WordFreq 테이블)→ (대가)→ 2차 복제.[두 서버에 동시에 쓰기 가능]
캐시:
캐시는 데이터베이스일 수 있습니다
80-20 규칙
시스템의 80%의 요청은 20%의 데이터를 조회하고 나머지 20%의 요청은 80%의 데이터를 조회한다.
캐시 접두사 20%.
최.→ 캐시 읽기 및 쓰기 최적화
무효
캐시에서 접두사를 제거하는 정책입니다.
부하 균형
여러 계층에 걸쳐 부하를 더 잘 분배하는 데 도움이 된다.
서버/기계 사이의 부하를 균형 있게 하는 순환 정책입니다.
인증(인증 및 승인)
이 설계는 사용자 수준에서 필요하지 않습니다.
4. 모니터링, 경고 및 백업(2~3분):
각 API의 지연 시간을 모니터링하는 데 도움이 됩니다.
API의 성공률 및 실패율 모니터링
API당 QP
캐시를 모니터링합니다.
경계의
→ 요청이 한 시간 동안 x회(1시간, 10분, 20분) 실패하면 실패 경보를 보냅니다.
알림 지연→ 만약 한 창의 총 요청 중 x%의 요청이 t밀리초를 초과해야만 결과를 되돌릴 수 있다.
백업
일부 오류로 인해 손실될 수 있는 데이터를 검색합니다.
백업 관련 제품 지표
백업 실험을 위한 지표를 만듭니다.
Digram:1.1
캐시 설계
우리는 단어를 저장해야 한다. 접두사마다 10개의 조언을 알아야 한다.
응답 반환 지연이 보다 낮아야 합니다.
자동차→ 20k
낙타.→ 30k
소떼→ 1K
택시.→ 4K
모자를 쓰다
만화
바구니
망토→ 100
질문 [java 사용 hashmap 또는python 사용 사전]:
우리는 키를 단어로 저장하고 주파수를 값으로 저장한다.우리는 사전이나 해시투의 모든 세계를 두루 돌아다니며 CA로 시작하는 제안이 10위권 안에 얼마나 많은지 보아야 한다.데이터를 저장하는 데 시간이 필요하고 단어'CA'에 표시할 추가 메모리가 필요합니다.
이 문제를 극복하기 위해 우리는 또 다른 유명한 데이터 구조를 사용했는데, 그것은 많은 단어를 저장했다.
Data Structures online courses: 나무
트리를 trie 구조로 변환

//initialize constant
private static int HEAP_SIZE = 10;
//structure of TrieNode 
Struct TrieNode {
    int freq;
    int arr[26] children;
    priority_queue<pair<int, string>> suggestions; //for storing string with frequency
};

// cat
Pair<Struct TrieNode*, int> insertWordInTrie(struct Trienode * trie, string word, int index, int freqCount){
//node is null
if(trie == null) {
    Struct TrieNode* trieNode = 
        (Struct TrieNode*) malloc(sizeof TrieNode);
    trie = trieNode;
    trie -> freq = 0;
}
//when we reach at end of the world
if(word.size() == index) {
    trie -> freq += freqCount;
    return make_pair(trie, trie -> freq); //return of pair word with frequency
 }
//node is not null

    Pair<Struct TrieNode*, int> childrenWordFreq = 
        insertWordInTrie(
            trie -> children[word[index] - ‘a’], 
            word, 
            index+1);
    trie -> children[word[index] - ‘a’] = childrenWordFreq.first;

    int wordTotalFreq = childrenWordFreq.second;

    (trie->suggestions).insert(make_pair(wordTotalFreq, word));


           //if tree size is a greater than HEAP_SIZE
if((trie->suggestions).size() > HEAP_SIZE) {
    (trie->suggestions).pop();
}
    return make_pair(trie, wordTotalFreq);
}
//Search word in trie
boolean searchWordInTrie(struct Trienode * trie, string word, int index) {
    if(trie == null) {
    return false;
}

if(word.size() == index) {
    return trie -> freq!=0 ? true: false;
}

return searchWordInTrie(trie->children[word[index] - ‘a’], word, index);
}



priority_queue<pair<int, string>> getSuggestions(
            struct Trienode * trie, string prefix, int index) {
     //if trie null
    if(trie == null)
        return null; 
         //return top suggestion
    if(index == prefix.size()) {
        return trie -> suggestions; 
}

    return getSuggestions(trie->children[prefix[index]-’a’], prefix, index+1);

}


//remove all the words below the tree
Struct TrieNode* invalidateCache(string prefix) {
    // Practice
}


//Driver code
int main() {
    TrieNode trie = null;
    trie = insertWordInTrie(trie, “cat”, 0 // string index, 1);

}

``
권장 서비스
Algorithms Online courses
데이터 복제
주파수