코딩펭귄

출처 : http://timroughgarden.org/notes.html

Consistent Hashing

Goal

• hash bucket(node/server)의 add/detach에서 relocate되는 data의 수를 최소화하자.

Algorithm

• data는 x_i, bucket은 b_j라 부른다.
• hash func을 사용하여 h(x_i)와 h(b_j)를 모두 계산한다. 이때 치역이 동일해야 한다. (ex - Z_2^32)
• x_i는 h(x_i)의 우측 중 가장 가까운 h(b_j)값을 가지는 b_j에 assign된다. (Z_2^32가 원형이라고 생각하자.)
• 그러면 relocation되는 data 수의 기대값은 |X| / |B|.

추가 테크닉

• h(b_j)는 self-balancing tree로 유지하자.
• virtual copy를 사용하면 variance를 낮출 수 있다.
• 각 bucket(node/server)의 capacity에 따라 virtual copy의 수를 조절할 수도 있다.

출처 : http://web.stanford.edu/class/cs161/

Universal Hash Family

Preliminaries

• h : M -> Z_n

Goal

• M의 원소 n개를 h에 태울 때, n개의 bucket 각각의 elt 수의 기대값이 2 이하가 되도록 하기.

Definition

• H is a universal hash family if when h is chosen uniformly at random from H, for all (u_i, u_j) with u_i != u_j, P{h \in H}(h(u_i) == h(u_j)) <= 1/n.

설명

• (u_i, u_j)를 뽑아서 h(u_i) == h(u_j)인 확률을 구하는 것에 주목하자.
• u를 먼저 뽑은 다음에, h(u)가 모든 x \in Z_n과 같을 확률을 구하는 게 아니다.
• 각 u가 uniform하게 Z_n에 landing해도 u_i와 u_j 사이에 dependency가 충분히 있을 수 있다.
• 하지만 (u_i, u_j)를 뽑아서 h(u_i) == h(u_j)를 구하면 dependency 없음이 보장된다.
• h_0은 LSB, h_1은 MSB를 리턴하는 함수라고 하고 H = {h_0, h_1} 이라고 하자. 그러면 H는 UHF가 아니다.

UHF의 예시

• f(a, b)(x) = ax + b (mod p) (p >= |M|인 prime)
• h(a, b)(x) = f(a, b, x) (mod n)
• H = {h(a, b) | 1 <= a < p-1, 0 <= b < p (둘 다 정수)}
• 증명 : x, x'을 고정한 다음에 h(x) == h(x')일 확률을 a, b를 옮겨가며 계산하면 된다.

쉘 스크립트

• 변수를 할당하는 방법

value=100             # 값을 할당
files=`ls`            # 명령어의 결과를 할당

• 변수를 사용하는 방법

echo $value
echo ${files}         # $files가 에러가 뜨면 중괄호로 감싸주자
[ -n "$files" ]       # 조건식 안에서는 큰다옴표로 $까지 감싸주자

• 파일을 체크하는 방법

[ -e <filename> ] : <filename>이 존재하면 true
[ -f <filename> ] : <filename>이 dir이거나 dev가 아니라면 true
                    script는 if [ -f <script> ]; then . <script> fi 처럼 사용하는 듯
[ -r <filename> ] : <filename>을 현재 사용자가 읽을 수 있으면 true
                    cat 하기 전에 검사하는 용도로 사용 가능
[ -w <filename> ] : <filename>을 현재 사용자가 쓸 수 있으면 true
[ -x <filename> ] : <filename>을 현재 사용자가 실행시킬 수 있으면 true
                    리눅스 binary의 존재 여부 체크하는 데에 사용 가능

• 정수를 비교하는 방법

[ "$a" -<op> "$b" ]  : op에는 eq, ne, gt, ge, lt, le 등이 있다
(( "$a" <op> "$b" )) : op에는 ==, <, <=, >, >= 등이 있다

• 문자열을 체크하는 방법

[ -n "$var" ] : var이 not null이면 true
[ -z "$var" ] : var이 null이면 true
echo "$var" | grep <substr> > /dev/null : var 안에 <substr>이 있으면 true
[ "$var" -eq *<substr>* ] : 상동

• 복합 비교

[ cond1 -a cond2 ] : [[ cond1 && cond2 ]] 와 동일
[ cond1 -o cond2 ] : [[ cond1 || cond2 ]] 와 동일

정규표현식

• 반복 횟수

x?     : 0 or 1회
x*     : 0회 이상
x+     : 1회 이상
x{n}   : n회
x{n,}  : n회 이상
x{n,m} : n회 이상 m회 이하

• escape 문자들

\d : 숫자
\D : !숫자

\s : 공백
\S : !공백

\t : 탭

\w : 알파벳+숫자+_
\W : !(알파벳+숫자+_)

• class들

[:alnum:] : 알파벳+숫자
[:alpha:] : 알파벳
[:digit:] : 숫자

[:upper:] : 대문자
[:lower:] : 소문자

[:blank:] : 탭 & 공백

LRU

• 로직은 생략
• repeated pattern size > cache size이면 느려짐.

TLRU

• Time-aware LRU
• network 환경에서 less popular & small life data를 빨리 replace한다.
• TTU(time to use) 값은 처음에 content publisher가 정해주며, cache에서는 내부 함수로 재가공한 결과값을 사용한다.
• cache 관리자에게 더 많은 권한이 부여됨.

PLRU

• bit로 tree를 만들고 0이면 왼쪽, 1이면 오른쪽을 타도록 한다. leaf node = cache entry
• insert/replace 모두 tree를 따라서 도착한 leaf entry에 행해진다. 이때 지나간 모든 branch bit를 flip해준다.
• almost always LRU처럼 동작하며, LRU에 비해 miss ratio 조금 높고, latency 조금 높고, power usage 조금 낮고, overhead (특히 space) 낮다.

NRU

• entry별로 modified bit, referenced bit가 존재한다. modified/referenced일 때 bit가 켜진다.
• timer가 주기적으로 작동하며 모든 referenced bit을 꺼준다.
• Replacement가 필요하면, mod && ref > !mod && ref > mod && !ref > !mod && !ref 순으로 priority를 정한 뒤, priority가 가장 낮은 non-empty 그룹에서 random하게 하나를 evict한다.

MRU

• Most recently used.
• random access와 repeated large dataset access에서 LRU보다 효율적이다.

LFU

• 로직은 생략
• LRU의 단점을 개선할 수 있지만 expensive하다.

LRU-k

• approximate LFU 알고리즘
• 각 page의 k-th most recent access가 가장 오래된 걸 replace. k=1이면 그냥 LRU.
• LRU에 비해 time locality에서 상당히 이득을 본다.
• https://www.cs.cmu.edu/~christos/courses/721-resources/p297-o_neil.pdf

LRU-2Q

• approximate LFU 알고리즘. queue 2개로 작동하며 access가 O(1)에 이뤄진다. LRU-2에 가까운 성능을 보임.
• 처음에는 A1 queue에 들어가며, 두 번째로 ref되면 Am queue에 들어간다.
• 빈 자리가 없으면 A1 queue의 사이즈가 thres 이상이면 A1에서 otherwise Am에서 하나 빼고, A1 head에 넣는다.
• https://pdfs.semanticscholar.org/d62d/e5f995164fff50f5ce61c0113f6bc9f04225.pdf

LFRU

• Least frequent recently used. 네트워크 환경에서 사용됨.
• privileged partition(LRU)과 unprivileged partition(ALFU)를 사용한다.
• p.p.에서 replacement가 필요하면, evict 대상을 빼서 u.p.에 넣고, u.p.에서 하나를 빼서 p.p.에 넣어준다.
• ALFU에서 locally popular content들을 걸러내 LRU에 올려주는 방식.

출처

• https://en.wikipedia.org/wiki/Cache_replacement_policies
• https://en.wikipedia.org/wiki/Page_replacement_algorithm