대량 데이터 처리 방법 소개

대량 데이터의 처리 방법 소개

적용 범위: 데이터 사전 구현, 데이터의 가중치 판단, 집합의 교차점 찾기 등에 사용할 수 있습니다

기본 원리 및 핵심 사항:

원리는 매우 간단합니다. 비트 배열에는 k개의 독립적인 해시 함수가 있습니다. 해시 함수에 해당하는 값의 비트 배열을 1로 설정합니다. 검색 중에 해시 함수의 해당 비트가 모두 1인 것으로 확인되면 존재한다는 의미임은 물론, 이 과정이 검색을 보장하는 것은 아닙니다. 결과는 100이 맞습니다. 동시에, 삽입된 키워드를 삭제하는 것은 지원되지 않습니다. 왜냐하면 키워드에 해당하는 비트가 다른 키워드에 영향을 미치기 때문입니다. 따라서 간단한 개선 사항은 삭제를 지원하기 위해 비트 배열 대신 카운터 배열을 사용하는 Bloom 필터를 계산하는 것입니다.

또한 더 중요한 문제가 있는데, 입력 요소 수 n을 기준으로 비트 배열 m의 크기와 해시 함수 수를 어떻게 결정하는지입니다. 해시 함수 개수 k=(ln2)*(m/n)일 때 오류율이 가장 작습니다. 오류율이 E보다 크지 않은 경우 n개 요소 집합을 나타내려면 m은 최소한 n*lg(1/E)와 같아야 합니다. 그러나 비트 배열의 절반 이상이 0이어야 하기 때문에 m은 더 커야 합니다. 그러면 m은 gt =nlg(1/E)*lge여야 하며 이는 nlg(1/E)의 약 1.44배입니다(lg는 2가 밑의 로그).

예를 들어 오류율이 0.01이라고 가정하면 m은 n의 약 13배가 되어야 합니다. 따라서 k는 약 8입니다.

여기서 m과 n의 단위가 다르다는 점에 유의하세요. m은 비트의 단위이고, n은 요소 개수(정확하게는 서로 다른 요소의 개수)의 단위입니다. 일반적으로 단일 요소의 길이는 수 비트입니다. 따라서 블룸 필터를 사용하면 일반적으로 메모리가 절약됩니다.

확장:

Bloom 필터는 k(k는 해시 함수의 수) 매핑 비트를 사용하여 집합의 요소를 비트 배열에 매핑하여 요소가 모두 1인지 여부를 나타냅니다. 아니면 컬렉션에 없습니다. CBF(카운팅 ​​블룸 필터)는 비트 배열의 각 비트를 카운터로 확장하여 요소 삭제 작업을 지원합니다. SBF(Spectral Bloom Filter)는 이를 컬렉션 요소의 발생 횟수와 연결합니다. SBF는 요소의 발생 빈도를 대략적으로 나타내기 위해 카운터의 최소값을 사용합니다.

문제 예: 각각 50억 개의 URL을 저장하는 두 개의 파일 A와 B가 있습니다. 각 URL은 64바이트를 차지하고 메모리 제한은 4G입니다. 파일 A와 B***를 찾으세요. . 파일이 3개 또는 심지어 n개라면 어떨까요?

이 질문을 바탕으로 4G=2^32는 약 40억*8, 즉 약 340억 개입니다. 오류율을 0.01로 계산하면 약 650억 비트가 필요합니다. 현재 사용 가능한 것은 340억개로 크게 다르지 않습니다. 이로 인해 오류율이 높아질 수 있습니다. 또한 이러한 URL이 일대일로 대응되면 IP로 변환될 수 있어 훨씬 간단합니다.

2.해싱

적용 범위: 빠른 검색 및 삭제를 위한 기본 데이터 구조, 일반적으로 전체 데이터 양을 메모리에 넣을 수 있습니다.

기본 원리 및 핵심 사항:

문자열, 정수, 순열, 특정 해당 해시 방법에 대한 해시 함수 선택.

충돌 처리의 경우 하나는 지퍼 방식이라고도 알려진 개방형 해싱이고, 다른 하나는 개방형 주소 지정 방식이라고도 알려진 폐쇄형 해싱입니다.

확장:

d-왼쪽 해싱에서 d는 다중을 의미합니다. 먼저 이 문제를 단순화하고 2-왼쪽 해싱을 살펴보겠습니다.

2-왼쪽 해싱은 해시 테이블을 각각 T1과 T2라고 하는 동일한 길이의 두 부분으로 나누고 T1과 T2에 각각 해시 함수 h1과 h2를 장착하는 것을 의미합니다. 새 키를 저장할 때 두 개의 해시 함수를 동시에 사용하여 계산하고 두 개의 주소 h1[key] 및 h2[key]를 얻습니다. 이때 T1의 h1[key] 위치와 T2의 h2[key] 위치를 확인하여 저장된(충돌) 키가 많은 위치를 확인한 후 로드가 적은 위치에 새 키를 저장해야 합니다. 예를 들어 양쪽에 동일한 숫자가 있는 경우, 예를 들어 양쪽 위치가 모두 비어 있거나 키가 양쪽에 모두 저장되어 있으면 새 키가 왼쪽의 T1 하위 테이블에 저장되고 여기서 2-left가 나옵니다. 키를 찾을 때는 두 번 해시하고 동시에 두 위치를 찾아야 합니다.

문제의 예: 1) 대용량 로그 데이터에서 특정 날짜에 바이두에 가장 많이 방문한 IP를 추출합니다.

IP 수는 여전히 최대 2^32개로 제한되어 있으므로 해시를 사용하여 IP를 메모리에 직접 저장한 다음 통계를 수행하는 것을 고려할 수 있습니다.

3.bit-map

적용 범위: 데이터를 빠르게 검색, 결정 및 삭제할 수 있습니다. 일반적으로 데이터 범위는 int의 10배 미만입니다.

기본 원리 및 요점: 비트 배열을 사용하여 8자리 전화번호와 같은 특정 요소의 존재 여부를 나타냅니다.

확장: 블룸 필터는 비트맵의 확장으로 볼 수 있습니다

문제 예:

1) 파일에 일부 전화번호가 포함되어 있고 각 번호는 8자리이며 서로 다른 번호의 개수가 계산되는 것으로 알려져 있습니다.

8비트의 최대 개수는 99 999 999이며 약 99m비트, 약 10m바이트의 메모리가 필요하다.

2) 2억 5천만 개의 정수 중에서 반복되지 않는 정수의 수를 구합니다. 이 2억 5천만 개의 정수를 수용하기에는 메모리 공간이 부족합니다.

비트맵을 확장하고 2비트를 사용하여 숫자를 나타냅니다. 0은 표시되지 않음을 의미하고, 1은 한 번 표시됨을 의미하며, 2는 2번 이상 표시됨을 의미합니다. 또는 이를 표현하기 위해 2비트를 사용하지 않고 이 2비트 맵을 시뮬레이션하고 구현하기 위해 두 개의 비트맵을 사용할 수 있습니다.

4. 힙

적용 범위: n은 대용량 데이터 이전에 크고 n은 상대적으로 작으며 힙을 메모리에 넣을 수 있습니다.

기본 원리 핵심 사항: 최대 힙 처음 n개의 가장 작은 힙을 찾고, 처음 n개의 가장 큰 힙을 찾습니다. 첫 번째 n번째 가장 작은 요소를 찾는 것과 같은 방법으로 현재 요소를 최대 힙의 가장 큰 요소와 비교합니다. 이 요소가 가장 큰 요소보다 작으면 가장 큰 요소를 교체해야 합니다. 이런 방식으로 얻은 최종 n개 요소는 가장 작은 n개입니다. 많은 양의 데이터에 적합하며, n의 크기가 상대적으로 작을 경우 한 번 스캔하면 처음 n개의 요소를 모두 얻을 수 있어 매우 효율적입니다.

확장: 최소 힙과 최대 힙이 결합된 이중 힙을 사용하여 중앙값을 유지할 수 있습니다.

문제 예:

1) 100만 개의 숫자 중 가장 큰 100개의 숫자를 찾으세요.

최소 100개 요소의 힙을 사용하세요.

5. 이중층 버킷 분할

적용 범위: k번째 최대, 중앙값, 비반복 또는 반복되는 숫자

기본 원리 및 요점: 왜냐하면 요소 범위가 매우 크고 직접 주소 지정 테이블을 사용할 수 없으므로 여러 분할을 통해 범위가 점차 결정되고 최종적으로 허용 가능한 범위 내에 들어갑니다. 여러 번 축소할 수 있으며 이중 레이어는 하나의 예일 뿐입니다.

확장:

문제 예:

1) 2억 5천만 개의 정수 중에서 반복되지 않는 정수의 수를 찾으십시오. 메모리 공간이 부족합니다. 2억 5천만 개의 정수입니다.

비둘기집 원리와 비슷하게 정수의 수는 2^32입니다. 즉, 이 2^32 숫자를 2^8 영역으로 나눌 수 있습니다(예: 단일 파일을 사용하여 영역을 나타냄) ) 그런 다음 데이터를 여러 영역으로 분리한 다음 비트맵을 사용하여 여러 영역을 직접 해결할 수 있습니다.

즉, 디스크 공간만 충분하면 쉽게 해결할 수 있습니다.

2) 중앙값을 찾으려면 5천만 개의 정수가 필요합니다.

이 예는 위의 예보다 더 명확합니다. 먼저 int를 2^16개의 영역으로 나눈 다음 데이터를 읽어 각 영역에 속하는 숫자의 개수를 계산한 다음 통계 결과를 바탕으로 중앙값이 어느 영역에 속하는지 판단하는 동시에 알 수 있습니다. 이 영역의 숫자는 중앙값이 됩니다. 그런 다음 두 번째 스캔에서는 이 영역에 속하는 숫자만 계산합니다.

실제로 int가 아니고 int64라면 이렇게 3번 나누면 허용 가능한 수준으로 줄일 수 있습니다. 즉, 먼저 int64를 2^24개의 영역으로 나눈 다음 해당 영역에서 가장 큰 수를 결정한 다음 해당 영역을 2^20개의 하위 영역으로 나눈 다음 하위 영역에서 가장 큰 수를 결정한 다음 하위 영역에서 숫자를 결정하십시오. 숫자는 2^20이므로 통계에 직접 addr 테이블을 사용할 수 있습니다.

6. 데이터베이스 인덱스

적용 범위: 대용량 데이터의 추가, 삭제, 수정 및 조회

기본 원칙 및 요점: 데이터 디자인 사용 대용량 데이터 분석을 위한 구현 방법 및 추가, 삭제, 수정, 점검 등을 처리합니다.

확장:

문제 예:

7. 반전 인덱스(Inverted index)

적용 범위: 검색 엔진, 키워드 쿼리

기본 원리 및 요점: 역색인이라고 하는 이유는? 전체 텍스트 검색 시 문서 또는 문서 그룹 내 단어의 저장 위치를 ​​매핑하여 저장하는 데 사용되는 색인 방법입니다. .

영어를 예로 들면 다음은 색인을 생성할 텍스트입니다.

T0 = “it is what it is”

T1 = “what is it”

T2 = “바나나입니다”

다음과 같은 역방향 파일 인덱스를 얻을 수 있습니다:

“a”: {2}

"바나나": {2}

"is": {0, 1, 2}

"it": {0, 1, 2}

"what": {0, 1}

검색된 조건 "what", "is" 및 "it"은 세트의 교집합에 해당합니다.

각 문서의 단어 목록을 저장하기 위해 정방향 색인이 개발되었습니다. 정방향 인덱스 쿼리는 각 문서의 순서 있고 빈번한 전체 텍스트 쿼리와 확인 문서의 각 단어에 대한 확인을 만족하는 경우가 많습니다. 정방향 인덱스에서는 문서가 중앙 위치를 차지하고 각 문서는 포함된 일련의 인덱스 항목을 가리킵니다. 즉, 문서는 자신이 담고 있는 단어를 가리키는데, 역색인은 그 단어가 자신을 담고 있는 문서를 가리키는 것을 의미한다. 이러한 역관계를 쉽게 알 수 있다.

확장:

문제 예: 문서 검색 시스템, 일반적인 학술 논문에 대한 키워드 검색과 같이 어떤 문서에 특정 단어가 포함되어 있는지 쿼리합니다.

8. 외부 정렬

적용 범위: 빅데이터 정렬, 중복 제거

기본 원리 및 요점: 외부 정렬, 교체 및 선택의 병합 방법 of 패자 트리 원리, 최적 병합 트리

확장:

문제 예:

1) 1G 크기의 파일이 있는데, 그 안의 각 줄은 다음과 같습니다. 단어 크기는 16바이트를 초과하지 않으며 메모리 제한은 1M입니다. 가장 자주 사용되는 단어 100개를 반환합니다.

이 데이터의 특징은 워드 크기가 16바이트인데 메모리가 1m에 불과해 해싱에는 부족하므로 정렬용으로 사용할 수 있다. 메모리는 입력 버퍼로 사용될 수 있습니다.

9.trie tree

적용 범위: 많은 양의 데이터, 많은 반복, 그러나 작은 데이터 유형을 메모리에 저장할 수 있음

기본 원리 및 핵심 포인트: 구현 방법, 노드 하위 표현

확장: 압축 구현.

문제 예:

1) 10개의 파일이 있으며 각 파일은 1G입니다. 각 파일의 각 줄에는 사용자의 쿼리가 저장되며 각 파일의 쿼리는 중복될 수 있습니다. 쿼리 빈도별로 정렬하라는 메시지가 표시됩니다.

2) 1,000만 개의 문자열 중 일부는 동일(중복)하여 모든 중복을 제거하고 중복 없이 문자열을 유지해야 합니다. 어떻게 설계하고 구현하나요?

3) 인기 검색어 찾기: 검색어 문자열은 총 1,000만개에 달하지만, 반복을 제거하면 발생하지 않습니다. 300만 개 이상, 각각 255바이트 이하.

10. 분산 처리 mapreduce

적용 범위: 많은 양의 데이터이지만 작은 데이터 유형을 메모리에 저장할 수 있습니다.

기본 원칙 및 핵심 사항: 데이터 전송 서로 다른 기계가 데이터를 처리하고 분할하고 결과를 줄이도록 합니다.

확장:

문제 예:

1). MapReduce의 표준 예제 응용 프로그램은

의 출현을 계산하는 프로세스입니다. 문서 집합에 있는 각각의 다른 단어:

void map(String name, String document):

// name: 문서 이름

// document: 문서 내용

문서의 각 단어 w에 대해:

EmitIntermediate(w, 1)

void Reduce(String word, IteratortialCounts):

// 키: 단어

// 값: 집계된 부분 개수 목록

int result = 0;

각 v에 대해 부분 카운트:

result = ParseInt(v);

Emit(result);

여기서 각 문서는 단어로 분할되며 처음에는 각 단어가 계산됩니다.

Map 함수에 의해 "1" 값을 사용하여 단어를 결과 키로 사용합니다. 프레임워크는 동일한 키를 가진 모든 쌍을 모아

동일한 키에 제공합니다. Reduce를 호출하므로 이 함수는 해당 단어의 전체 모양을 찾기 위해 모든 입력 값을 합산하면 됩니다.

2). 컴퓨터라면 이 데이터 배치의 TOP10을 효율적으로 계산하는 방법을 생각해 보세요.

3) ***에는 N개의 머신이 있고, 각 머신에는 N개의 숫자가 있습니다. 각 기계는 최대 O(N) 번호를 저장하고 작동할 수 있습니다. N^2 숫자의 중앙값(중앙값)을 찾는 방법은 무엇입니까?

고전적인 문제 분석

수천만 또는 수십억 개의 데이터(중복 포함), 그 중 상위 N개를 계산합니다. 가장 자주 나타납니다. 데이터는 두 가지 상황으로 나눌 수 있습니다. 즉, 한 번에 메모리로 읽을 수 있는 경우와 한 번에 메모리로 읽을 수 없는 경우입니다.

사용 가능한 아이디어: 트리 트리 힙, 데이터베이스 인덱스, 하위 집합 통계, 해시, 분산 컴퓨팅, 근사 통계, 외부 정렬

소위 메모리에서 읽을 수 있는지 여부 한 번은 사실 중복을 제거한 후의 데이터 양을 의미해야 합니다. 중복 제거 후 데이터를 메모리에 담을 수 있다면 map, hashmap, trie 등을 통해 해당 데이터에 대한 사전을 생성한 후 직접 통계를 수행할 수 있습니다. 물론 각 데이터의 발생 횟수를 업데이트할 때 힙을 사용하여 발생률이 가장 높은 상위 N개 데이터를 유지할 수 있습니다. 물론 이렇게 하면 유지 관리 시간이 늘어나서 찾는 것만큼 효율적이지 않습니다. 완전한 통계 후 상위 N개 데이터.

데이터가 메모리에 맞지 않는 경우. 한편으로는 이러한 상황에 맞게 위의 사전 방식을 개선할 수 있는지 생각해 볼 수 있는데, 이는 사전을 메모리가 아닌 하드 디스크에 저장하는 방식을 의미할 수 있다. 데이터베이스.

물론 더 좋은 방법이 있는데, 기본적으로 맵리듀스 프로세스인 분산 컴퓨팅을 사용하는 것입니다. 먼저 데이터 값이나 해싱 후 값을 기준으로 데이터를 범위로 나눌 수 있습니다. 데이터(md5)를 여러 머신으로 분할하려면 분할 후 데이터를 한 번에 메모리로 읽어와서 서로 다른 머신이 실제로는 맵인 다양한 수치 범위를 처리하도록 하는 것이 가장 좋습니다. 결과를 얻은 후 각 머신은 가장 많이 발생하는 상위 N개 데이터만 추출한 다음 이를 요약하여 전체 데이터 중에서 가장 많이 발생하는 상위 N개 데이터를 선택하면 됩니다.

실제로 처리를 위해 데이터를 다른 시스템에 직접 배포하고 싶을 수도 있지만 올바른 솔루션을 얻을 수는 없습니다. 하나의 데이터가 다른 시스템에 고르게 분산될 수 있고, 다른 데이터가 하나의 시스템에 완전히 집계되어 동시에 동일한 수의 데이터가 있을 수 있기 때문입니다. 예를 들어, 가장 많이 발생하는 상위 100개 항목을 찾으려면 1000만 개의 데이터를 10개의 시스템에 배포하고 각 시스템에서 가장 많이 발생하는 상위 100개 항목을 찾습니다. 병합 후에는 실제 100번째 항목을 찾는다는 보장이 없습니다. 예를 들어 가장 많이 발생하는 100번째 머신은 10,000개가 있을 수 있지만 10개의 머신으로 나누어져 있으므로 각 머신에는 1,000개만 있습니다. 예를 들어 1,000위 이전의 머신은 모두 하나의 머신에 분산되어 있다고 가정합니다. , 1001개가 있으므로 10,000개가 있는 것을 제거하게 됩니다. 각 머신에서 가장 많이 발생하는 1000개를 선택하여 병합하더라도 1001A가 많이 모일 수 있으므로 여전히 오류가 발생합니다. 개인이 발생합니다. 따라서 데이터는 서로 다른 컴퓨터에 무작위로 배포될 수 없으며 대신 해시된 값에 따라 처리하기 위해 서로 다른 컴퓨터에 매핑되어야 합니다. 그래야 서로 다른 컴퓨터에서 다양한 값을 처리할 수 있습니다.

외부 정렬 방법은 IO를 많이 소모하므로 그다지 효율적이지 않습니다. 위의 분산 방법은 독립형 버전에서도 사용할 수 있습니다. 즉, 전체 데이터를 값 범위에 따라 여러 개의 서로 다른 하위 파일로 나눈 다음 하나씩 처리합니다. 처리가 완료되면 단어와 발생 빈도가 병합됩니다. 실제로 외부 정렬 병합 프로세스를 사용할 수 있습니다.

근사 계산도 고려할 수 있습니다. 즉, 자연어 속성을 결합하고 실제로 사전으로 가장 많이 나타나는 단어만 사용하여 이 척도를 메모리에 저장할 수 있습니다.