[이 게시물은 다음에도 표시됩니다. Dustin의 깃허브 블로그].
이 문제는 가끔씩 발생하는 문제입니다. 
동안. 저는 일반적으로 합리적이라고 생각되는 방법을 설명하지만, 다음과 같이 설명한 적은 없는 것 같습니다. 꽤 충분합니다. 사람들은 복잡하거나 느리다고 생각하는 경향이 있습니다. 저는 여기서 그 문제를 해결하려고 노력할 것입니다.
제약 조건
충분한 애플리케이션에 유용하게 사용할 수 있도록 다음과 같은 가정 하에 작업하겠습니다:
- 서버로의 왕복 이동을 최소화해야 합니다.
- O(1) 추가(현재 크기와 새로 들어오는 항목 모두에 대해)
- O(1) 제거(현재 크기와 제거 중인 항목 모두에 대해)
- O(1) 가져오기
- 잠금 및 대기 무료
- 간편한 사용
- 이해하기 쉬운
- 명시적인 유지 관리가 필요하지 않습니다.
그리고 당연히 웹 스케일이어야 합니다!
재료
개념은 간단하며 원자성이 보장되는 세 가지 멤캐시드 연산을 사용합니다.
인덱스는 다음을 사용하여 생성됩니다. 추가. 이것은 매우 당연한 일입니다.
항목을 추가하거나 제거해야 할 때마다 다음을 사용합니다. 추가. 이 기능을 사용하려면 양수 또는 음수 항목을 나타내는 방식으로 항목을 인코딩해야 합니다. 간단한 샘플 인코딩을 만들었습니다. +키 의 추가를 나타내기 위해 키 를 세트에 추가하고 -키 의 제거를 나타내기 위해 키 를 설정합니다. 그런 다음 공백을 사용하여 여러 항목을 구분합니다.
예시: +a +b +c -b 는 {a, c}. 물론 순서는 중요합니다.
멤버가 자주 왔다 갔다 하는 세트는 압축해야 할 수도 있습니다. 이를 위해 집합을 다시 인코딩하고 cas 를 추가하여 다른 클라이언트를 밟지 않고 다시 추가할 수 있도록 합니다.
안내해 드립니다
이 예제에서는 파이썬을 사용하고 있습니다. 이상적으로는 클라이언트에서 구현하면 모든 것이 정상적으로 작동합니다.
먼저 인코더와 디코더가 필요합니다. 사실 이 부분이 가장 어려운 부분이며, 알고 보면 정말 사소한 부분입니다.
인코더
세트 내에서 가장 기본적인 데이터 표현부터 시작합니다.
def encodeSet(키, op=‘+’):
"""키 집합을 인코딩하여 집합을 수정합니다.
>>> encodeSet(['a', 'b', 'c'])
'+a +b +c '
“””
반환 ”.join(OP + K + ‘ ‘ 에 대한 k in 키)
이것은 코드보다는 문서에 가깝지만 꽤 명확합니다. 대신 JPEG 세트를 원한다면 공백으로 구분하는 대신 길이와 본문으로 간단한 바이너리 인코딩을 만들면 됩니다.
세트 수정
수정은 추가와 제거의 유일한 차이점은 인코딩 연산이라는 점뿐입니다. 두 경우 모두 동일한 코드를 작성할 수 있기 때문에 유용합니다.
def 수정(mc, 인덱스 이름, op, 키):
인코딩 = encodeSet(키, op)
시도:
mc.추가(인덱스 이름, 인코딩)
예외 키 오류:
# 추가할 수 없는 경우 세트에 추가합니다,
# 인덱스를 생성하려고 하므로 그렇게 하세요.
만약 op == ‘+’:
mc.추가(인덱스 이름, 인코딩)
def 추가(mc, 인덱스 이름, *키):
"""주어진 세트에 주어진 키를 추가합니다."""
수정(mc, 인덱스 이름, ‘+’, 키)
def 제거(mc, 인덱스 이름, *키):
"""주어진 세트에서 주어진 키를 제거합니다."""
수정(mc, 인덱스 이름, ‘-‘, 키)
다음과 같은 부작용을 허용합니다. 추가 를 사용하여 인덱스가 없는 경우 생성합니다.
실제 애플리케이션에서는 0이 아닌 확률로 추가 항목이 누락되어 실패하고 바로 뒤에 오는 추가 는 경쟁 조건으로 인해 실패할 수 있습니다. 여기서 다루기 위해 코드를 작성하지는 않았지만 꽤 간단합니다. 중요한 경우 둘 다 실패하는 한 전체 수정 메서드를 반복하면 됩니다. 두 번 이상 실패하도록 해야 합니다.
디코더
데이터를 사용하려면 데이터를 디코딩해야 하므로 위의 인코더가 수행하는 작업(추가 및 제거를 위한 추가 포함)을 역으로 수행할 수 있는 빠른 디코더를 조합해 보겠습니다.
def decodeSet(데이터):
"""캐시에서 세트 임플로 항목을 디코딩합니다.
더러움 표시기(다짐 힌트)와 집합을 반환합니다.
>>> decodeSet('+a +b +c -b -x')
(2, set(['a', 'c']))
“””
키 = set()
더러움 = 0
에 대한 k in 데이터.분할():
op, 키 = k[0], k[1:]
만약 op == ‘+’:
키를 입력합니다.추가(키)
elif op == ‘-‘:
키를 입력합니다.폐기(키)
더러움 += 1
반환 더러움, 키
가장 복잡한 부분입니다.
항목 검색하기
이제 데이터를 인코딩, 설정 및 수정할 수 있으므로 검색은 매우 간단합니다. 기본 패스는 다음과 같습니다:
def 항목(mc, 인덱스 이름):
"""집합에서 현재 값을 검색합니다."""
플래그, cas, 데이터 = mc.get(인덱스 이름)
더러움, 키 = decodeSet(데이터)
반환 키
여기까지입니다. 하지만 지금이 압축을 하기에 아주 좋은 시기입니다. 더러움 는 세트에 얼마나 많은 제거 토큰이 있는지 측정합니다. 토큰이 너무 많으면 제거합니다.
다음과 같은 상황을 상상해 보세요. 더러움_임계값 숫자를 설정하여 자동 압축을 수행할 위치를 결정합니다. 이보다 더 많은 더티가 있으면 검색 시 압축합니다(단일 가져오기를 단일 가져오기와 단일 CAS.
이 사용 사례의 경우 실제로는 CAS 대부분의 경우 성공하기 때문에 그냥 실행하고 잊어버립니다. 안전하지만(즉, 데이터가 파괴되지 않음) 작동이 보장되지는 않습니다.
따라서 다음은 수정된 항목 함수를 조건부로 압축합니다:
def 항목(mc, 인덱스 이름, forceCompaction=False):
"""집합에서 현재 값을 검색합니다.
이 경우 압축을 요청하거나 인코딩이
너무 더럽습니다."""
플래그, casid, 데이터 = mc.get(인덱스 이름)
더러움, 키 = decodeSet(데이터)
만약 forceCompaction 또는 더러움 > dirtiness_threshold:
압축 = encodeSet(키)
mc.cas(인덱스 이름, casid, 압축)
반환 키
이제 끝났습니다.
요약
최악의 경우 세트에 추가왕복 2회(세트가 존재하지 않아 생성해야 하지만 이를 알 필요는 없는 경우).
세트에 일반 추가: 추가되는 멤버 수에 관계없이 왕복 1회. (항목을 일괄적으로 올바르게 추가하거나 제거하기 위해 현재 값을 검색할 필요도 없으며, 모든 항목을 다시 전송할 필요도 없습니다).
최악의 사례 검색왕복 2회(압축이 부작용인 경우).
일반 검색: 왕복 1회(키 하나만 가져오기).
주의 사항
세트의 수는 대략 무제한이지만, 이 구현을 사용하는 단일 세트의 실제 크기는 제한이 있습니다. 매우 큰 세트(예: 4,000개 이상의 250바이트 항목)가 필요한 경우 여러 키(따라서 여러 서버)에 걸쳐 세트를 '샤드'하는 것은 간단합니다.
이 구현에서는 읽기 시 압축이 수행되므로 수정은 매우 많이 하지만 읽기는 거의 하지 않는 경우에는 이 코드에 적합하지 않을 수 있습니다. 이 경우 저는 무작위 쓰기에서 압축을 시작합니다(최악의 경우 추가/제거가 한 번이면 될 것을 세 홉 정도 걸리게 만듭니다).
