ElasticSearch를 버리고 GitHub는 처음부터 검색 엔진을 구축합니다! 2억 개의 코드 창고를 검색하는 방법은 무엇입니까?

2021년 12월 GitHub는 GitHub코드 검색에서 "아무 것도 찾을 수 없음" 문제를 해결하기 위해 기술 미리보기를 출시하고 포괄적인 최적화를 실시했습니다.

지난해 11월 GitHub Universe 개발자 컨퍼런스에서 공식적으로 개발자가 코드를 찾고, 읽고, 탐색하는 문제를 주로 해결하는 공개 베타 버전을 출시했습니다.

컨퍼런스에서 누군가 중요한 질문을 했습니다. 코드 검색 개선의 원리는 무엇인가요?

최근 GitHub는 새 모델의 기술 원리와 시스템 아키텍처를 자세히 설명하는 블로그를 게시했습니다.

GitHub 검색 엔진을 처음부터 구축하세요

간단히 말하면, 새로운 검색 엔진 뒤에는 연구원들이 Rust에서 다시 작성한 바퀴가 있습니다. 이 바퀴는 특별히 코드 검색에 최적화된 코드명 Blackbird입니다.

언뜻 보면 검색 엔진을 처음부터 구축하는 것은 수수께끼 같은 결정처럼 보일 수 있습니다. 처음부터 시작해야 하는 이유는 무엇입니까? 이미 많은 오픈소스 솔루션이 있지 않나요? 왜 새로운 것을 만드는 데 더 이상 에너지를 낭비합니까?

사실 GitHub에서는 검색 문제를 해결하기 위해 기존 솔루션을 사용하려고 노력해 왔지만 안타깝게도 일반 텍스트 검색에 사용되는 제품은 "코드" 검색에 적응하기 어렵습니다. 인덱싱 속도가 너무 느리기 때문에 사용자 경험이 좋지 않고 필요한 서버 수가 많고 운영 비용이 너무 높습니다.

코드 검색에 특별히 적합한 최신 오픈 소스 프로젝트가 있지만 여전히 GitHub만큼 큰 코드 베이스에는 적합하지 않습니다.

위의 관찰을 바탕으로 GitHub 개발자는 세 가지 주요 목표와 결론을 설정했습니다.

1. 사용자는 검색 과정에서 몇 가지 코드 질문을 통해 새로운 경험을 얻을 수 있습니다. 답을 얻기 위해 탐색하고 코드를 읽는 것입니다.

2. 코드 검색과 일반 텍스트 검색에는 많은 차이점이 있습니다.

개발자는 기계가 이해할 수 있도록 코드를 작성하므로 코드 검색 프로세스는 코드의 구조와 상관 관계를 활용해야 하며 사용자는 문장 부호(예: 마침표, 여는 괄호 및 기타 연산자)를 검색할 수 있습니다. 코드 ), 코드에서 단어를 파생시키지 마세요. 쿼리에서 불용어를 제거하거나 검색에 정규식을 사용하지 마세요.

3. GitHub의 규모는 독특한 도전 과제를 제시합니다.

이전 버전의 검색 엔진은 Elasticsearch를 사용했습니다. 처음 배포되었을 때는 GitHub의 모든 코드를 색인화하는 데 몇 달이 걸렸지만(당시 약 800만 개의 코드 저장소가 있었습니다) 지금은 코드 저장소가 있습니다. 그 숫자는 2억 개를 초과했으며 이러한 코드는 고정되어 있지 않습니다. 개발자가 지속적으로 제출하고 코드가 끊임없이 변경되므로 검색 엔진을 구축하는 데 매우 어렵습니다.

현재 베타 버전으로 사용자는 115TB의 코드와 155억 개의 문서가 포함된 약 4,500만 개의 코드 베이스를 검색할 수 있습니다.

결론적으로, 기성품으로는 요구 사항을 충족할 수 없으므로 처음부터 새로 만들어 보세요.

Grep을 사용해 보세요.

검색할 때 흔히 사용하는 도구는 "grep"입니다. 표현식을 입력하면 텍스트에서 일치시킬 수 있으니 그냥 grep을 사용하여 무차별 대입으로 검색 문제를 해결하면 어떨까요?

이 질문에 답하려면 먼저 115TB의 코드를 ripgrep과 일치시키는 데 걸리는 시간을 계산할 수 있습니다.

8코어 Intel CPU가 장착된 시스템에서 ripgrep은 2.769초(~0.6GB/초/코어) 내에 메모리에 캐시된 13GB 파일에 대해 정규식 쿼리를 실행할 수 있습니다.

간단히 계산해 보면 현재의 대용량 데이터에는 이 방법이 적합하지 않다는 것을 알 수 있습니다. 코드 검색 프로그램이 32개의 서버 클러스터에서 실행된다고 가정하면 115TB의 코드를 모두 입력하더라도 각 시스템에는 64개의 코어가 있습니다. 메모리와 모든 것이 원활하게 실행됩니다. "하나의" 쿼리를 실행하는 데 약 96초가 소요되며 다른 사용자는 대기열에 있어야 하며 이는 QPS가 0.01인 경우에만 사용할 수 있음을 의미합니다. .grep

무차별 대입은 작동하지 않으므로 먼저 인덱스만 구축하면 됩니다.

검색 인덱스(serach index)

해당 정보를 인덱스 형태로 미리 계산한 후에야 쿼리 시 검색 엔진이 빠르게 응답할 수 있습니다. 간단히 말해서 인덱스는 키-값 매핑입니다. 반전된 인덱스(inverted index), 키는 키워드, 값은 해당 단어가 나타나는 문서 ID의 정렬된 목록입니다.

코드 검색 작업에서 연구원들은 특수한 유형의 역 인덱스, 즉 ngram 인덱스를 사용했습니다.

ngram은 길이가 n인 문자 시퀀스입니다. 예를 들어 n = 3(trigams)은 키의 최대 길이가 3만 될 수 있음을 의미합니다. 키가 더 긴 경우 길이에 따라 잘라야 합니다. 3, lim, imi, mit 및 its로 구분됩니다.

다음 질문은 어떻게 하면 상대적으로 합리적이게 만들 수 있느냐는 것입니다. 소요 시간 내에 인덱스 구축을 완료하세요.

연구원들은 Git이 Content-Addressed Hashing을 사용하고 실제로 GitHub에 중복된 콘텐츠가 꽤 많다는 것을 관찰하고, 연구원들은 인덱스를 구축하기 위해 다음과 같은 두 가지 방법을 제안했습니다.

1. Git Blob 개체 ID의 샤드는 샤드 간에 문서를 균등하게 배포하고 중복을 피하는 동시에 필요에 따라 언제든지 샤드 수를 확장할 수 있는 좋은 방법을 제공합니다.

2. 인덱스를 트리로 모델링하고 차등 인코딩(델타 인코딩)을 사용하여 크롤링 횟수를 줄이고 인덱스의 메타데이터를 최적화합니다. 여기서 메타데이터에는 문서가 나타나는 위치 목록이 포함됩니다( 경로, 분기 및 리포지토리) 및 이러한 개체에 대한 정보(리포지토리 이름, 소유자, 가시성 등). 일부 인기 있는 리포지토리의 경우 메타데이터의 양이 상당히 클 수 있습니다.

GitHub는 쿼리 결과가 제출된 코드와 일치하도록 유지하는 시스템도 설계했습니다.

팀 구성원이 코드를 푸시하는 동안 사용자가 코드 베이스를 검색하면 시스템이 해당 문서를 완전히 처리할 때까지 새로 커밋된 문서가 검색 결과에 포함되어서는 안 됩니다. Blackbird는 커밋 쿼리 일관성을 핵심 부분으로 만듭니다. 그 디자인.

Blackbird

다음은 Blackbird 검색 엔진의 아키텍처 다이어그램입니다.

먼저 Kafka는 인덱스의 내용을 지정하는 이벤트를 제공한 다음 코드에서 기호를 다시 추출하는 서비스를 포함하여 Git과 상호 작용할 수 있는 수많은 크롤러 프로그램이 있습니다. Kafka를 사용하여 각 샤드를 인덱싱하고 대상 문서를 얻습니다.

시스템은 "git push"와 같은 이벤트에만 응답하여 변경 사항 및 유사한 이벤트를 가져오지만 처음으로 모든 코드 기반을 수집하려면 몇 가지 추가 작업이 필요합니다.

이 시스템의 주요 기능은 증분 인코딩을 최대한 활용하기 위해 초기 수집 순서를 최적화하는 것입니다.

GitHub는 새로운 확률적 데이터 구조를 사용하여 코드 베이스의 유사성을 표현하며, 수집 순서는 코드 베이스 유사성 그래프의 최소 신장 트리를 수평 순차 순회하여 계산됩니다.

최적화된 수집 순서에 따라 델타 트리의 구성 프로세스는 각 코드 베이스를 상위 코드 베이스와 구별하는 것입니다. 이는 또한 시스템이 현재 코드 베이스에 고유한 blob만 크롤링하면 된다는 것을 의미합니다. 포함 Git에서 Blob 콘텐츠를 가져오고 이를 구문 분석하여 기호를 추출하고 인덱스에 대한 입력으로 사용될 문서를 만듭니다.

그런 다음 이 파일을 다른 Kafka 주제에 게시하세요. 이 주제는 데이터가 샤드 간에 분할되는 곳이기도 합니다. 각 샤드는 주제의 Kafka 파티션을 사용합니다.

Kafka를 사용하면 인덱싱과 크롤링을 분리할 수 있으며 Kafka에서 메시지를 정렬하면 쿼리 결과의 일관성을 유지할 수도 있습니다.

인덱서 샤드는 이러한 문서를 찾아 인덱스를 구축합니다. 콘텐츠, 기호 및 경로를 토큰화하여 ngram 인덱스 및 기타 유용한 인덱스(언어, 소유자, 코드 베이스 등)를 구성하고 결과를 디스크에 플러시합니다.

마지막으로 샤드를 압축하고 더 작은 인덱스를 더 큰 인덱스로 축소하면 쿼리가 더 효율적이고 이동이 더 쉬워집니다.

쿼리 수명주기

인덱스를 사용하면 시스템을 통한 쿼리 추적이 간단해집니다. 각 쿼리는 "/arguments?/org:rails lang:Ruby"로 작성할 수 있는 정규식입니다. Rails 조직에서 Ruby 언어로 작성한 코드입니다.

GitHub.com과 샤드 사이에는 사용자 쿼리 수신 조정, 검색 클러스터의 각 호스트에 대한 요청 분산, 마지막으로 Redis를 사용하여 디스크 관리를 담당하는 서비스도 있습니다. 공간(할당량)을 확보하고 일부 액세스 제어 데이터를 캐시합니다.

프런트엔드는 사용자 쿼리를 받아 Blackbird에 전달합니다. Blackbird는 쿼리를 추상 구문 트리로 구문 분석하고 이를 표준 언어 ID로 다시 작성하며 추가 절에 권한 및 범위에 태그를 지정합니다.

다음 단계는 n개의 동시 요청을 보내는 것입니다. 즉, 검색 클러스터의 각 샤드에 하나씩 시스템에 설정된 샤딩 전략은 클러스터의 각 샤드에 쿼리 요청을 보내는 것입니다.

그런 다음 각 개별 샤드에 대한 쿼리를 일부 변환하여 인덱스에서 정보를 찾습니다. ㅋㅋㅋ , 용어 강조 표시 및 페이징을 통해 결과를 페이지에 표시할 수 있습니다.

실제 사용 시 단일 샤드의 p99 응답 시간은 약 100ms입니다. 그러나 응답 집계, 권한 확인, 구문 강조 등의 이유로 총 응답 시간은 더 길어집니다.

쿼리는 인덱스 서버에서 100밀리초 동안 하나의 CPU 코어를 차지하므로 64코어 호스트의 상한은 초당 약 640개의 쿼리입니다. grep 방식(0.01 QPS)과 비교하면 이 방식은 상당히 빠르다고 할 수 있다.

요약

전체 시스템 아키텍처를 소개한 후 문제의 규모를 다시 검토할 수 있습니다.

GitHub의 수집 파이프라인은 초당 약 120,000개의 문서를 게시할 수 있으므로 155억 개의 문서를 모두 처리하는 데 약 36시간이 소요됩니다. 그러나 델타 인덱싱을 사용하면 크롤링해야 하는 문서 수를 50% 이상 줄일 수 있습니다. 전체 코퍼스를 다시 색인화하는 전체 프로세스는 약 18시간이 소요됩니다.

초기 콘텐츠 용량이 115TB였는데, 중복 콘텐츠를 삭제하고 증분 인덱싱을 적용한 결과 콘텐츠 용량이 약 28TB로 줄었습니다.

그리고 인덱스 자체는 25TB에 불과합니다. 여기에는 모든 인덱스(ngram 포함)뿐만 아니라 모든 고유 콘텐츠의 압축 복사본도 포함됩니다. 이는 콘텐츠를 포함한 총 인덱스 크기가 원본의 약 4분의 1에 불과하다는 것을 의미합니다. 데이터 크기 1!

위 내용은 ElasticSearch를 버리고 GitHub는 처음부터 검색 엔진을 구축합니다! 2억 개의 코드 창고를 검색하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!