VKontakte 메시지 데이터베이스를 처음부터 다시 작성하고 생존하세요

우리 유저들은 피로도 모르고 서로에게 메시지를 씁니다.

그것은 꽤 많습니다. 모든 사용자의 메시지를 모두 읽으려고 하면 150만년 이상이 걸립니다. 귀하가 상당히 고급 독자이고 각 메시지에 XNUMX초 이상을 소비하지 않는다면 말이죠.

이러한 양의 데이터를 저장하고 액세스하기 위한 논리를 최적으로 구축하는 것이 중요합니다. 그렇지 않으면 그다지 좋지 않은 순간에 모든 것이 곧 잘못될 것이라는 것이 분명해질 수 있습니다.

우리에게 이 순간은 XNUMX년 반 전에 찾아왔습니다. 우리가 어떻게 이 상황에 이르렀고 결국 무슨 일이 일어났는지 순서대로 말씀드리겠습니다.

병력

첫 번째 구현에서 VKontakte 메시지는 PHP 백엔드와 MySQL의 조합에서 작동했습니다. 이는 소규모 학생 웹사이트에 대한 완전히 일반적인 솔루션입니다. 그러나 이 사이트는 통제할 수 없을 정도로 성장했고 자체적으로 데이터 구조의 최적화를 요구하기 시작했습니다.

2009년 말에 최초의 텍스트 엔진 저장소가 작성되었으며 2010년에 메시지가 이곳으로 전송되었습니다.

텍스트 엔진에서 메시지는 일종의 "사서함"인 목록에 저장되었습니다. 이러한 각 목록은 모든 메시지를 소유한 사용자인 uid에 의해 결정됩니다. 메시지에는 대화자 식별자, 텍스트, 첨부 파일 등 일련의 속성이 있습니다. "상자" 내부의 메시지 식별자는 local_id이며 변경되지 않으며 새 메시지에 대해 순차적으로 할당됩니다. "상자"는 독립적이며 엔진 내부에서 서로 동기화되지 않습니다. 상자 간의 통신은 PHP 수준에서 발생합니다. 내부에서 텍스트 엔진의 데이터 구조와 기능을 살펴볼 수 있습니다. 여기에.

이것은 두 사용자 간의 통신에 충분했습니다. 다음에 무슨 일이 일어났는지 추측해 보세요.

2011년 XNUMX월 VKontakte는 여러 참가자와의 대화, 즉 다중 채팅을 도입했습니다. 이들과 협력하기 위해 우리는 두 개의 새로운 클러스터(member-chats 및 chat-members)를 만들었습니다. 첫 번째는 사용자의 채팅에 대한 데이터를 저장하고, 두 번째는 채팅별 사용자에 대한 데이터를 저장합니다. 여기에는 목록 자체 외에도 초대한 사용자 및 해당 사용자가 채팅에 추가된 시간 등이 포함됩니다.

"PHP, 채팅에 메시지를 보내자"라고 사용자가 말합니다.
“자, {username}님.” PHP가 말합니다.

이 계획에는 단점이 있습니다. 동기화는 여전히 PHP의 책임입니다. 대규모 채팅과 동시에 메시지를 보내는 사용자는 위험한 이야기입니다. 텍스트 엔진 인스턴스는 uid에 따라 다르므로 채팅 참가자는 서로 다른 시간에 동일한 메시지를 받을 수 있습니다. 진전이 멈춘다면 이것으로 살 수 있습니다. 그러나 그런 일은 일어나지 않을 것입니다.

2015년 말에 커뮤니티 메시지를 출시했고, 2016년 초에는 이를 위한 API를 출시했습니다. 커뮤니티에 대규모 챗봇이 등장하면서 고른 부하 분산을 잊어버릴 수도 있었습니다.

좋은 봇은 하루에 수백만 개의 메시지를 생성합니다. 아무리 말이 많은 사용자라도 이를 자랑할 수는 없습니다. 이는 그러한 봇이 살았던 텍스트 엔진의 일부 인스턴스가 최대한 어려움을 겪기 시작했음을 의미합니다.

2016년의 메시지 엔진은 채팅 회원 및 회원 채팅 인스턴스 100개, 텍스트 엔진 8000개입니다. 각각 64GB의 메모리를 갖춘 수천 대의 서버에서 호스팅되었습니다. 첫 번째 응급조치로 메모리를 32GB 더 늘렸습니다. 우리는 예측을 추정했습니다. 급격한 변화가 없다면 이 정도면 앞으로 XNUMX년 정도는 충분할 것입니다. 하드웨어를 확보하거나 데이터베이스 자체를 최적화해야 합니다.

아키텍처의 특성상 하드웨어를 여러 개 늘리는 것이 합리적입니다. 즉, 적어도 자동차 수를 두 배로 늘리는 것입니다. 분명히 이것은 다소 비싼 길입니다. 최적화해드리겠습니다.

새로운 개념

새로운 접근 방식의 핵심 본질은 채팅입니다. 채팅에는 이와 관련된 메시지 목록이 있습니다. 사용자에게 채팅 목록이 있습니다.

필요한 최소값은 두 개의 새 데이터베이스입니다.

• 채팅 엔진. 이것은 채팅 벡터의 저장소입니다. 각 채팅에는 이와 관련된 메시지 벡터가 있습니다. 각 메시지에는 텍스트와 채팅 내부의 고유한 메시지 식별자(chat_local_id)가 있습니다.
• 사용자 엔진. 이는 사용자 벡터(사용자에 대한 링크)의 저장소입니다. 각 사용자는 Peer_id 벡터(대화자 - 다른 사용자, 다중 채팅 또는 커뮤니티)와 메시지 벡터를 갖습니다. 각 Peer_id에는 이와 관련된 메시지 벡터가 있습니다. 각 메시지에는 chat_local_id와 해당 사용자의 고유한 메시지 ID(user_local_id)가 있습니다.

새 클러스터는 TCP를 사용하여 서로 통신합니다. 이렇게 하면 요청 순서가 변경되지 않습니다. 요청 자체와 이에 대한 확인은 하드 드라이브에 기록되므로 엔진이 실패하거나 다시 시작된 후 언제든지 대기열 상태를 복원할 수 있습니다. 사용자 엔진과 채팅 엔진은 각각 4개의 샤드이므로 클러스터 간의 요청 대기열은 균등하게 분산됩니다(그러나 실제로는 전혀 없으며 매우 빠르게 작동합니다).

대부분의 경우 데이터베이스에서 디스크 작업은 바이너리 변경 로그(binlog), 정적 스냅샷 및 메모리의 부분 이미지 조합을 기반으로 합니다. 하루 동안의 변경 사항은 binlog에 기록되고, 현재 상태의 스냅샷이 주기적으로 생성됩니다. 스냅샷은 우리의 목적에 최적화된 데이터 구조의 모음입니다. 헤더(이미지의 메타인덱스)와 메타파일 세트로 구성됩니다. 헤더는 RAM에 영구적으로 저장되며 스냅샷에서 데이터를 찾을 위치를 나타냅니다. 각 메타파일에는 단일 사용자와 관련된 데이터와 같이 가까운 시점에 필요할 수 있는 데이터가 포함되어 있습니다. 스냅샷 헤더를 사용하여 데이터베이스를 쿼리하면 필요한 메타파일을 읽은 다음 스냅샷이 생성된 후 발생한 binlog의 변경 사항을 고려합니다. 이 접근 방식의 이점에 대해 자세히 알아볼 수 있습니다. 여기에.

동시에 하드 드라이브 자체의 데이터는 하루에 한 번만 변경됩니다. 모스크바에서는 부하가 최소인 늦은 밤에 변경됩니다. 덕분에(디스크의 구조가 하루 종일 일정하다는 사실을 알고 있음) 벡터를 고정된 크기의 배열로 대체할 수 있으며 이로 인해 메모리가 향상됩니다.

새로운 체계로 메시지를 보내는 것은 다음과 같습니다:

1. PHP 백엔드는 메시지 전송 요청을 통해 사용자 엔진에 접속합니다.
2. user-engine은 요청을 원하는 chat-engine 인스턴스로 프록시하고, 이 인스턴스는 user-engine chat_local_id(이 채팅 내 새 메시지의 고유 식별자)로 반환됩니다. 그런 다음 chat_engine은 채팅의 모든 수신자에게 메시지를 브로드캐스트합니다.
3. user-engine은 chat-engine으로부터 chat_local_id를 받고 user_local_id를 PHP에 반환합니다. 이는 이 사용자의 고유한 메시지 식별자입니다. 이 식별자는 예를 들어 API를 통한 메시지 작업에 사용됩니다.

그러나 실제로 메시지를 보내는 것 외에도 몇 가지 더 중요한 사항을 구현해야 합니다.

• 예를 들어 하위 목록은 대화 목록을 열 때 표시되는 가장 최근 메시지입니다. 읽지 않은 메시지, 태그('중요', '스팸' 등)가 있는 메시지.
• 채팅 엔진에서 메시지 압축
• 사용자 엔진의 메시지 캐싱
• 검색(모든 대화 상자 및 특정 대화 상자 내에서)
• 실시간 업데이트(롱폴링).
• 모바일 클라이언트에서 캐싱을 구현하기 위해 기록을 저장합니다.

모든 하위 목록의 구조는 빠르게 변화하고 있습니다. 그들과 함께 일하기 위해 우리는 나무를 펴다. 이 선택은 때때로 스냅샷의 메시지 전체 세그먼트를 트리 상단에 저장한다는 사실로 설명됩니다. 예를 들어 야간 재인덱싱 후 트리는 하위 목록의 모든 메시지를 포함하는 하나의 상단으로 구성됩니다. Splay 트리를 사용하면 균형 조정에 대해 생각할 필요 없이 이러한 정점의 중앙에 쉽게 삽입할 수 있습니다. 또한 Splay는 불필요한 데이터를 저장하지 않으므로 메모리가 절약됩니다.

메시지에는 많은 양의 정보(주로 텍스트)가 포함되어 있어 압축하는 데 유용합니다. 하나의 개별 메시지라도 정확하게 보관 취소할 수 있는 것이 중요합니다. 메시지를 압축하는 데 사용됩니다. 허프만 알고리즘 예를 들어, 우리는 우리 자신의 경험적 방법을 통해 메시지에서 단어가 "비단어"(공백, 구두점)와 번갈아 사용된다는 것을 알고 있으며 러시아어 기호 사용의 일부 특성도 기억합니다.

채팅보다 사용자 수가 훨씬 적기 때문에 채팅 엔진에 임의 액세스 디스크 요청을 저장하기 위해 메시지를 사용자 엔진에 캐시합니다.

메시지 검색은 사용자 엔진에서 이 사용자의 채팅이 포함된 모든 채팅 엔진 인스턴스에 대한 대각선 쿼리로 구현됩니다. 결과는 사용자 엔진 자체에 결합됩니다.

글쎄, 모든 세부 사항이 고려되었으므로 남은 것은 새로운 계획으로 전환하는 것뿐입니다. 가급적이면 사용자가 눈치 채지 못하는 것입니다.

데이터 마이그레이션

따라서 우리는 사용자별 메시지를 저장하는 텍스트 엔진과 다중 채팅방과 그 안에 있는 사용자에 대한 데이터를 저장하는 두 개의 클러스터 채팅 회원 및 회원 채팅을 보유하고 있습니다. 여기에서 새로운 사용자 엔진과 채팅 엔진으로 이동하는 방법은 무엇입니까?

이전 방식의 회원 채팅은 주로 최적화를 위해 사용되었습니다. 필요한 데이터를 채팅 회원에게 신속하게 전송한 후 더 이상 마이그레이션 프로세스에 참여하지 않았습니다.

채팅 회원을 위한 대기열입니다. 여기에는 100개의 인스턴스가 포함되어 있고 채팅 엔진에는 4개의 인스턴스가 포함되어 있습니다. 데이터를 전송하려면 규정을 준수해야 합니다. 이를 위해 채팅 회원을 동일한 4개 사본으로 나눈 다음 채팅 엔진에서 채팅 회원 binlog 읽기가 활성화되었습니다.

이제 채팅 엔진은 채팅 회원의 다중 채팅에 대해 알고 있지만 두 명의 대화 상대와의 대화에 대해서는 아직 아무것도 모릅니다. 이러한 대화는 사용자를 참조하여 텍스트 엔진에 위치합니다. 여기에서 우리는 데이터를 "정면"으로 취했습니다. 각 채팅 엔진 인스턴스는 모든 텍스트 엔진 인스턴스에 필요한 대화가 있는지 물었습니다.

훌륭합니다. 채팅 엔진은 다중 채팅이 무엇인지, 어떤 대화가 있는지 알고 있습니다.
각 채팅의 메시지 목록을 만들려면 다중 채팅 채팅의 메시지를 결합해야 합니다. 먼저 chat-engine은 이 채팅의 모든 사용자 메시지를 텍스트 엔진에서 검색합니다. 어떤 경우에는 꽤 많은 수(최대 수억 개)가 있지만 매우 드문 경우를 제외하고 채팅은 RAM에 완전히 들어갑니다. 우리는 정렬되지 않은 메시지를 여러 개의 복사본으로 가지고 있습니다. 결국 메시지는 모두 사용자에 해당하는 서로 다른 텍스트 엔진 인스턴스에서 가져옵니다. 목표는 메시지를 정렬하고 불필요한 공간을 차지하는 복사본을 제거하는 것입니다.

각 메시지에는 보낸 시간과 텍스트가 포함된 타임스탬프가 있습니다. 우리는 정렬에 시간을 사용합니다. 다중 채팅 참가자의 가장 오래된 메시지에 포인터를 배치하고 의도한 복사본의 텍스트에서 해시를 비교하여 타임스탬프를 늘리는 방향으로 이동합니다. 복사본의 해시와 타임스탬프가 동일하다는 것은 논리적이지만 실제로는 항상 그런 것은 아닙니다. 아시다시피 이전 구성표의 동기화는 PHP에 의해 수행되었으며 드물게 동일한 메시지를 보내는 시간이 사용자마다 달랐습니다. 이러한 경우 우리는 일반적으로 XNUMX초 이내에 타임스탬프를 편집할 수 있었습니다. 두 번째 문제는 수신자마다 메시지 순서가 다르다는 것입니다. 그러한 경우, 우리는 사용자마다 다른 주문 옵션을 사용하여 추가 사본을 생성할 수 있도록 허용했습니다.

그 후 멀티챗의 메시지에 대한 데이터가 사용자 엔진으로 전송됩니다. 그리고 가져온 메시지에는 불쾌한 기능이 있습니다. 일반적인 작업에서 엔진에 전달되는 메시지는 user_local_id를 기준으로 엄격하게 오름차순으로 정렬됩니다. 이전 엔진에서 사용자 엔진으로 가져온 메시지는 이 유용한 속성을 잃었습니다. 동시에 테스트의 편의를 위해 신속하게 액세스하고, 해당 항목에서 항목을 찾고, 새 항목을 추가할 수 있어야 합니다.

우리는 가져온 메시지를 저장하기 위해 특별한 데이터 구조를 사용합니다.

크기의 벡터를 나타냅니다. 다들 어디 있어? - 요소의 특별한 순서와 함께 다르며 내림차순으로 정렬됩니다. 인덱스가 있는 각 세그먼트에서 요소가 정렬됩니다. 그러한 구조에서 요소를 검색하는 데는 시간이 걸립니다. 를 통해 이진 검색. 요소 추가는 다음 기간에 걸쳐 상각됩니다. .

그래서 우리는 기존 엔진에서 새 엔진으로 데이터를 전송하는 방법을 알아냈습니다. 하지만 이 과정은 며칠이 걸리며, 이 기간 동안 사용자들이 서로에게 편지를 쓰는 습관을 포기할 가능성은 거의 없습니다. 이 시간 동안 메시지를 잃지 않기 위해 이전 클러스터와 새 클러스터를 모두 사용하는 작업 방식으로 전환합니다.

데이터는 채팅 회원과 사용자 엔진에 기록됩니다(이전 체계에 따른 일반 작동에서는 텍스트 엔진이 아님). user-engine은 요청을 chat-engine으로 프록시합니다. 여기서 동작은 이 채팅이 이미 병합되었는지 여부에 따라 달라집니다. 채팅이 아직 병합되지 않은 경우 채팅 엔진은 메시지를 자체적으로 작성하지 않으며 해당 처리는 텍스트 엔진에서만 발생합니다. 채팅이 이미 chat-engine에 병합된 경우 chat_local_id를 user-engine에 반환하고 모든 수신자에게 메시지를 보냅니다. user-engine은 모든 데이터를 텍스트 엔진으로 프록시합니다. 따라서 어떤 일이 발생하면 항상 롤백하여 기존 엔진에 현재 데이터를 모두 보관할 수 있습니다. text-engine은 user-engine이 저장하고 백엔드로 반환하는 user_local_id를 반환합니다.

결과적으로 전환 프로세스는 다음과 같습니다. 빈 사용자 엔진과 채팅 엔진 클러스터를 연결합니다. chat-engine은 전체 chat-members binlog를 읽은 다음 위에서 설명한 구성표에 따라 프록시를 시작합니다. 이전 데이터를 전송하고 두 개의 동기화된 클러스터(이전 클러스터와 새 클러스터)를 얻습니다. 남은 것은 읽기를 텍스트 엔진에서 사용자 엔진으로 전환하고 프록싱을 비활성화하는 것입니다.

조사 결과

새로운 접근 방식 덕분에 엔진의 모든 성능 지표가 개선되었으며 데이터 일관성 문제가 해결되었습니다. 이제 우리는 메시지에 새로운 기능을 신속하게 구현할 수 있습니다. (그리고 이미 이 작업을 시작했습니다. 최대 채팅 참가자 수를 늘리고, 전달된 메시지에 대한 검색을 구현하고, 고정된 메시지를 실행하고, 사용자당 총 메시지 수에 대한 제한을 높였습니다.) .

논리의 변화는 정말 엄청납니다. 그리고 이것이 항상 거대한 팀과 수많은 코드 라인에 의한 수년 간의 개발을 의미하는 것은 아니라는 점에 주목하고 싶습니다. 메시지 압축을 위한 Huffman, Splay 트리 및 가져온 메시지의 구조와 같은 모든 추가 스토리와 함께 채팅 엔진 및 사용자 엔진은 20줄 미만의 코드입니다. 그리고 단 3개월 만에 10명의 개발자가 작성했습니다. 모든 세 개발자 - 세계 챔피언 스포츠 프로그래밍에서).

또한 서버 수를 두 배로 늘리는 대신 서버 수를 절반으로 줄였습니다. 이제 사용자 엔진과 채팅 엔진은 500개의 물리적 시스템에 존재하는 반면 새로운 체계는 로드할 수 있는 여유 공간이 큽니다. 우리는 장비 비용을 많이 절약했습니다. 연간 운영 비용으로 약 5만 달러 + 750만 달러를 절약했습니다.

우리는 가장 복잡하고 대규모의 문제에 대한 최상의 솔루션을 찾기 위해 노력합니다. 우리는 그런 개발자를 많이 보유하고 있습니다. 이것이 바로 우리가 데이터베이스 부서에서 재능 있는 개발자를 찾는 이유입니다. 이러한 문제를 해결하는 방법을 좋아하고 알고 있으며 알고리즘과 데이터 구조에 대한 탁월한 지식을 갖고 있다면 팀에 합류하도록 초대합니다. 우리에게 연락하세요 HR자세한 내용은

이 이야기가 귀하에 관한 이야기가 아니더라도 우리는 추천을 중요하게 생각한다는 점을 참고하시기 바랍니다. 친구에게 이야기해 보세요 개발자 공석, 그가 수습 기간을 성공적으로 마치면 100 루블의 보너스를 받게됩니다.

출처 : habr.com