command, address version number, stream number, label, 개수, passphrase, hash값의 앞의 몇자리를 0x00으로 할 것인가, nonce trials per byte, payload length extra bytes
현재 최신 address version number는 4
nonce trials per byte는 현재 320이 최소, payload length exxtra bytes는 현재 1400이 최소
command: createChan, joinChan, createRandomAddress, createDeterministicAddress, getDeterministicAddress
address 만들기
1. 32bytes random으로 private signing key와 private encryption key를 만든다.
2. Elliptic Curve DSA 알고리즘 사용하여 public key 생성한다. 64bytes가 만들어진다.
3. 앞에서 생성된 두개(signing과 encryption)의 public key를 앞뒤로 붙인후(public signing key + public encryption key) sha512에 의한 hash를 구한다.
4. 구해진 digest를 가지고 ripemd160에 의한 hash를 구한다.
5. ripe.digest의 앞자리(1 or 2)가 0x00일 때까지 반복한다.(address의 크기를 줄이기 위한 작업)
6. address version number의 인코딩 + stream number의 인코딩 + ripe.digest
7. verify를 위해 앞의 값에 sha512를 두번 적용한 후 앞의 4bytes를 checksum으로 사용한다.
8. (6에서의 값의 hex + 7에서의 checksum의 hex) 를 integer로 변경한다.
9. integer를 base58로 인코딩한다.
10. 앞에 BitMessage를 의미하는 BM-를 덧붙인다.
양의 정수 인코딩하기
1. 253보다 작으면 big endian unsigned char
2. 253에서 65535(2^16)사이이면 (>B, 253) + >H unsigned short
3. 65536에서 2^32사이이면 (>B, 254) + >I unsigned int
4. 2^32에서 2^64사이이면 (>B, 255) + >Q unsigned long long
5. 2^64보다 큰 수는 없다.
Wallet Import Format
1. 0x80 + private key
2. sha256을 두번 적용한 hash를 구한다.
3. hash된 결과의 앞 4bytes를 checksum으로 사용한다.
4. 1의 끝에 checksum을 추가한다.
5. base58로 인코딩한다.
signature 계산
expires time + object type + address version number + stream number + tag + 0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes
위의 내용을 private signing key로 sign한 것이 signature이다.
encrypted 계산
0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes + signature의 length + signature
위의 내용을 address의 double hash의 앞 32bytes로 암호화 한다.
실제 다른 node에 전달되는 값은 아래와 같다.
payload = POW에 의해 계산된 nonce + expires time + object type + address version number + stream number + tag + encrypted
inventoryhash: payload에 sha512를 두번 적용한 hash의 앞 32bytes
inventoryhash -> object type, stream number, payload, expires time, tag)
2015년 6월 17일 수요일
2015년 6월 10일 수요일
쉽게 배우는 알고리즘 9장 요약
Chapter 9. 그래프 알고리즘
1. 그래프
그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
정점(Vertex): 대상이나 개체
간선(Edge): 이들간의 관계
사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
G = (V, E)
로 표시한다.
2. 그래프의 표현
2.1 인접행렬을 이용한 방법
그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.
행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.
2.2 인접리스트를 이용한 방법
각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.
단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.
3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)
3.1 BFS
루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.
// G: 그래프
// s: 시작정점
BFS(G, s)
{
// s를 제외한 모든 정점을 NO로 표시한다.
for each v in V -{s} {
visited[v] = NO;
}
visited[s] = Yes;
enqueue(Q,s);
while (Q가 비어 있지 않으면) {
u = dequeue(Q);
for each v in L(u) // 정점 u의 인접 리스트
if (visited[v] == NO) {
visited[v] = YES;
enqueue(Q,v);
}
}
}
}
3.2 DFS
루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.
DFS(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
aDFS(v)
}
}
}
aDFS(v)
{
visited[v] = YES;
for each x in L(v) { // L(v): 정점 v의 인접리스트
if (visited[x] == NO) {
aDFS(x);
}
}
}
4. 최소신장트리(Minimum Spanning Tree)
간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.
4.1 프림 알고리즘
집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.
// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
S는 공집합
// 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + [u]; // 집합 S에 u를 포함시킨다.
for each v in L(u) { // L(u): u의 인접 정점 집합
if (v in V-S && w(u,v) < d[v]) {
d[v] = w(u,v);
tree[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
4.2 크루스칼 알고리즘
싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.
Kruskal(G)
{
T는 공집합
단 하나의 정점만으로 이루어진 n개의 집합을 초기화한다.
모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
while (T의 간선수 < n - 1) {
A에서 최소비용의 간선(u,v)를 제거한다.
if (정점 u와 v가 다른 집합에 속함) {
T = T + (u,v);
정점 u와 v가 속한 두 집합을 하나로 합친다.;
}
}
}
5. 위상 정렬
싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.
topologicalSort(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
DFS-TS(v);
}
}
}
DFS-TS(v)
{
visited[v] = YES;
for each x in L(v) {
if (visited[x] == NO) {
DFS-TS(x);
}
}
연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}
6. 최단경로
6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
S는 공집합
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + {u};
for each v in L(u) {
if (v in V-S && d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)
BellmanFord(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
for (int i=0; i<V; i++) {
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
// 음의 싸이클 존재여부 확인
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
output "해없음"
}
}
}
6.3 모든쌍 최단경로 알고리즘
d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리
d.k(ij) = w(ij) if k=0
min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1
FloydWarshall(G)
{
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d(ij) = w(ij);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
}
}
}
}
6.4 싸이클이 없는 그래프의 최단경로
DAG-ShortestPath(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
G의 정점들을 위상정렬한다.
for each u in V { // 위상정렬 순서대로
for each v in L(u) {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
7. 강연결요소
유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.
// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
1. 그래프
그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
정점(Vertex): 대상이나 개체
간선(Edge): 이들간의 관계
사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
G = (V, E)
로 표시한다.
2. 그래프의 표현
2.1 인접행렬을 이용한 방법
그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.
행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.
2.2 인접리스트를 이용한 방법
각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.
단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.
3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)
3.1 BFS
루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.
// G: 그래프
// s: 시작정점
BFS(G, s)
{
// s를 제외한 모든 정점을 NO로 표시한다.
for each v in V -{s} {
visited[v] = NO;
}
visited[s] = Yes;
enqueue(Q,s);
while (Q가 비어 있지 않으면) {
u = dequeue(Q);
for each v in L(u) // 정점 u의 인접 리스트
if (visited[v] == NO) {
visited[v] = YES;
enqueue(Q,v);
}
}
}
}
3.2 DFS
루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.
DFS(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
aDFS(v)
}
}
}
aDFS(v)
{
visited[v] = YES;
for each x in L(v) { // L(v): 정점 v의 인접리스트
if (visited[x] == NO) {
aDFS(x);
}
}
}
4. 최소신장트리(Minimum Spanning Tree)
간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.
4.1 프림 알고리즘
집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.
// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
S는 공집합
// 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + [u]; // 집합 S에 u를 포함시킨다.
for each v in L(u) { // L(u): u의 인접 정점 집합
if (v in V-S && w(u,v) < d[v]) {
d[v] = w(u,v);
tree[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
4.2 크루스칼 알고리즘
싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.
Kruskal(G)
{
T는 공집합
단 하나의 정점만으로 이루어진 n개의 집합을 초기화한다.
모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
while (T의 간선수 < n - 1) {
A에서 최소비용의 간선(u,v)를 제거한다.
if (정점 u와 v가 다른 집합에 속함) {
T = T + (u,v);
정점 u와 v가 속한 두 집합을 하나로 합친다.;
}
}
}
5. 위상 정렬
싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.
topologicalSort(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
DFS-TS(v);
}
}
}
DFS-TS(v)
{
visited[v] = YES;
for each x in L(v) {
if (visited[x] == NO) {
DFS-TS(x);
}
}
연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}
6. 최단경로
6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
S는 공집합
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + {u};
for each v in L(u) {
if (v in V-S && d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)
BellmanFord(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
for (int i=0; i<V; i++) {
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
// 음의 싸이클 존재여부 확인
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
output "해없음"
}
}
}
6.3 모든쌍 최단경로 알고리즘
d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리
d.k(ij) = w(ij) if k=0
min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1
FloydWarshall(G)
{
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d(ij) = w(ij);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
}
}
}
}
6.4 싸이클이 없는 그래프의 최단경로
DAG-ShortestPath(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
G의 정점들을 위상정렬한다.
for each u in V { // 위상정렬 순서대로
for each v in L(u) {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
7. 강연결요소
유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.
// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
쉽게 배우는 알고리즘 8장 요약
Chapter. 8 동적 프로그래밍
1. 어떤 문제를 동적 프로그래밍으로 푸는가
동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다.
다음의 두 성질을 갖고 있는 문제에 대해 동적 프로그래밍이 적합하다.
a. 최적 부분구조를 이룬다.
b. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.
2. 행렬 경로 문제
nxn행렬의 죄상단에서 시작해 한 칸씩 이동해 우하단까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동상의 규칙은 아래와 같다.
- 오른쪽이나 아래쪽으로만 이동할 수 있다.
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.
c(i,j)를 원소 (i,j)에 이르는 최고점수라하고, m(i,j)는 행렬의 원소(i,j)의 값이라 하면 아래와 같이 문제를 해결할 수 있다.
c(i,j) = m(1,1) if i=j=1
m(1,j) + c(1,j-1) if i=1, j>1
m(i,1) + c(i-1,1) if i>1, j=1
m(i,j) + max(c(i,j-1), c(i-1,j)) if i>1, j>1
3. 조약돌 놓기 문제
3xn 테이블의 각 칸에 숫자가 쓰여 있다. 테이블의 칸들 중 일부에 제한조건을 만족하는 방법으로 조약돌을 놓아 조약돌이 놓인 곳에 있는 수의 합을 최대로 하는 방법을 구하는 문제이다. 제한 조건은 다음과 같다.
- 가로나 세로로 인접한 두 칸에 동시에 조약돌이 놓일 수 없다.
- 각 열에는 하나 이상의 조약돌을 놓는다.
임의의 열에 조약돌을 놓을 수 있는 방법은 총 4가지다 -> 패턴에 대한 내용은 책 확인
이를 기준으로 아래와 같이 문제를 해결할 수 있다.
c(i,p): i열이 패턴p로 놓일 때의 최고 점수
w(ip): i열이 패턴p로 놓일 때 i열에 돌이 놓인 곳의 점수 합
c(i,p) = w(i,p) if i=1
max(c(i-1,q)) + w(i,p) if i>1, q는 p와 양립하는 패턴
4. 행렬 곱셈 순서 문제
n개의 행렬이 주어지고 이들의 곱을 계산하려 한다. 행렬은 결합법칙이 성립하므로 어떤 순서로 두개씩 짝지어 계산해도 결과는 동일하다.
c(i,j): 행렬 A(i), ..., A(j)의 곱 A(i), ... A(j)를 계산하는 최소 비용
A(i): p(i-1)Xp(i) 행렬
c(i,j) = 0 if i=j
min(c(i,k) + c(k+1,j) + p(i-1)p(k)p(j)) if i<j, i<=k<=j-1
5. 최장 공통 부분순서(LCS)
두 문자열 X(m)과 Y(n)에 대해 두 문자열에 공통적으로 존재하는 가장 긴 부분순서를 구한다.
c(i,j)를 문자열 X(i)와 Y(i)의 LCS의 길이라 하면 점화식은 다음과 같다.
c(i,j) = 0 if i=0, j=0
c(i-1,j-1) + 1 if i,j>0 and x(i)=y(j)
max(c(i-1,j),c(i,j-1)) if i,j>0 and x(i)!=y(j)
쉽게 배우는 알고리즘 7장 요약
7장 상호배타적 집합의 처리
1. 연결 리스트를 이용한 집합의 처리
1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
* Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
* Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
* Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.
1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조
2. 트리를 이용한 집합의 처리
2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.
2.2 연산의 효율을 높이는 방법
2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.
2.2.3 효율성
책 참조
1. 연결 리스트를 이용한 집합의 처리
1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
* Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
* Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
* Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.
1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조
2. 트리를 이용한 집합의 처리
2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.
2.2 연산의 효율을 높이는 방법
2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.
2.2.3 효율성
책 참조
쉽게 배우는 알고리즘 6장 요약
6장 해시 테이블
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.
1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.
2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.
2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.
2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
* x에 A를 곱한 다음 소수부만 취한다.
* 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
* h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안
3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.
3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.
3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.
3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.
3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
* h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
* f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
* m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.
3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.
4. 검색 시간 분석
책 참조
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.
1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.
2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.
2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.
2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
* x에 A를 곱한 다음 소수부만 취한다.
* 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
* h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안
3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.
3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.
3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.
3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.
3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
* h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
* f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
* m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.
3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.
4. 검색 시간 분석
책 참조
쉽게 배우는 알고리즘 5장 요약
1. 이진 검색 트리
1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.
1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.
1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.
1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.
2. 레드블랙트리
- 균형잡인 이진검색트리
2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.
2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
- s가 레드인경우
p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
- s가 블랙인 경우
x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
- 오른쪽 자식인 경우
p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
- 왼쪽 자식인 경우
p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결
왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.
새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.
2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방
- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.
- p가 레드이고 s가 블랙인 경우
- p가 블랙인 경우
c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
- x의 부모노드 : p
- p의 다른 자식 노드 : s
- s의 자식 노드: l과 r
각각의 경우를 살펴보자.
2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.
a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.
b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.
c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동
2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.
a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작
b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.
c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.
d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동
3. B-트리
3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
3.2 검색
이진검색트리에서의 검색과 같다.
3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.
3.4 삭제
a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.
4. KD-트리
4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.
4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.
4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.
4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거
b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.
c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.
5 KDB-트리
5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.
5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.
5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.
6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조
7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.
1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.
1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.
1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.
2. 레드블랙트리
- 균형잡인 이진검색트리
2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.
2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
- s가 레드인경우
p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
- s가 블랙인 경우
x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
- 오른쪽 자식인 경우
p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
- 왼쪽 자식인 경우
p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결
왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.
새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.
2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방
- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.
- p가 레드이고 s가 블랙인 경우
- p가 블랙인 경우
c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
- x의 부모노드 : p
- p의 다른 자식 노드 : s
- s의 자식 노드: l과 r
각각의 경우를 살펴보자.
2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.
a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.
b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.
c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동
2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.
a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작
b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.
c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.
d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동
3. B-트리
3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
3.2 검색
이진검색트리에서의 검색과 같다.
3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.
3.4 삭제
a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.
4. KD-트리
4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.
4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.
4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.
4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거
b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.
c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.
5 KDB-트리
5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.
5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.
5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.
6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조
7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
쉽게 배우는 알고리즘 3장 요약
3장 정렬
1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.
2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.
3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.
4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.
5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤
6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.
- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.
- 힙으로 만드는 방법
* 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
* 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.
7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용
8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.
9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs
1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.
2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.
3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.
4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.
5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤
6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.
- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.
- 힙으로 만드는 방법
* 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
* 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.
7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용
8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.
9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs
쉽게 배우는 알고리즘 2장 요약
2장. 점화식과 점근적 복잡도 분석
1. 점화식의 이해
점화식: 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법
-> 등차수열, factorial, 피보나치 수열
예)
재귀적 관계를 이용해 알고리즘의 수행시간을 점화식으로 표현할 수 있다.
병합정렬의 경우 "T(n) = 2T(n/2) + 후처리시간"으로 표현할 수 있다.
2. 점화식의 점근적 분석 방법
a. 반복 대치
T(n)을 T(n-1)로 대치하고 T(n-1)을 T(n-2)로 대치하고 계속해서 T(n-2), T(n-3), ..., T(1)까지 반복해서 대치해가는 것과 같은 방식을 사용해 점근적 복잡도를 구한다.
b. 추정후 증명
식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옮음을 귀납적으로 증명하는 방법
c. 마스터 정리
a>=1, b>1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^(log a over b) = h(n)이라 할 때 T(n)의 점근적 복잡도는 아래와 같다.
- 어떤 양의 상수 e에 대하여 f(n)/h(n) = O(1/(n^e))이면, T(n) = Theta(h(n))이다.
- 어떤 양의 상수 e에 대하여 f(n)/h(n) = Omega(n^e)이고, 어떤 상수 c(<1)와 충분히 큰 모든 n에 대해 af(n/b) <= cf(n)이면 T(n) = Theta(f(n))이다.
- f(n)/h(n) = Theta(1)이면 T(n) = Theta(h(n)log n)이다.
쉽게 배우는 알고리즘 1장 요약
1장. 알고리즘 설계와 분석의 기초
1. 몇가지 기초 사항들
알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식
2. 점근적 표기
a. Theta 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨
b. Oh 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨
c. Omega 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨
3. 점근적 표기의 엄밀한 정의
a. Oh 표기법
Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한
b. Omega 표기법
Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한
c. Theta 표기법
Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합
d. Little Oh 표기법
o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용
e. Little Omega 표기법
w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용
1. 몇가지 기초 사항들
알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식
2. 점근적 표기
a. Theta 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨
b. Oh 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨
c. Omega 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨
3. 점근적 표기의 엄밀한 정의
a. Oh 표기법
Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한
b. Omega 표기법
Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한
c. Theta 표기법
Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합
d. Little Oh 표기법
o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용
e. Little Omega 표기법
w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용
Why should I have written ZeroMQ in C, not C++에의 요약
http://www.250bpm.com/blog:4
처음 ZeroMQ개발시 C++를 선택한 이유
1. data structures and algorithms(STL)의 라이브러리가 언어에 포함되어 있음
2. OOP가 가지는 장점
3. C에서는 virtual function을 사용하기 복잡하다.
4. block의 끝에서 descructor가 자동으로 호출된다.
절대 죽지 않아야 하는 ZeroMQ에게 있어서 error handling은 매우매우 중요하다. 그런데, C++의 exception은 에러를 발생시키는 지점과 에러를 처리하는 지점이 다르게 되어 있다. 이점이 undefined behaviour를 발생시키지 않아야 하는 ZeroMQ에게 있어서 좋지 않다. C처럼 에러의 발생과 처리가 한군데에서 이루어 지는 것이 좋다.
이것때문에 C++에서 exception을 사용하지 않는 형태로 ZeroMQ를 구현하였다.
그러나 여전히 문제는 남아있다. object의 initialization과 termination시에 문제가 발생한다. constructor는 return값이 없으므로 에러를 처리하려면 exception을 발생시켜야 한다. exception을 사용하지 않기로 했으므로 이를 에러를 발생시키지 않는 constructor와 에러가 발생할 수 있는 init함수로 분리하였다. 그러다보니 state의 문제가 발생한다.(semi-initialized) 이것은 descturtor의 경우도 마찬가지다. 에러가 어디서 일어나느냐에 따라 다양한 state가 있을 수 있기 때문에 이에 대한 처리는 매우 복잡해진다. C를 사용하면 이 문제가 매우 간단해진다.
C++은 undefined behaviour 보다는 빠른 개발이 더 필요한 환경에 적합한 것으로 생각된다. 시스템 프로그래밍은 C가 여전히 최고다.
처음 ZeroMQ개발시 C++를 선택한 이유
1. data structures and algorithms(STL)의 라이브러리가 언어에 포함되어 있음
2. OOP가 가지는 장점
3. C에서는 virtual function을 사용하기 복잡하다.
4. block의 끝에서 descructor가 자동으로 호출된다.
절대 죽지 않아야 하는 ZeroMQ에게 있어서 error handling은 매우매우 중요하다. 그런데, C++의 exception은 에러를 발생시키는 지점과 에러를 처리하는 지점이 다르게 되어 있다. 이점이 undefined behaviour를 발생시키지 않아야 하는 ZeroMQ에게 있어서 좋지 않다. C처럼 에러의 발생과 처리가 한군데에서 이루어 지는 것이 좋다.
이것때문에 C++에서 exception을 사용하지 않는 형태로 ZeroMQ를 구현하였다.
그러나 여전히 문제는 남아있다. object의 initialization과 termination시에 문제가 발생한다. constructor는 return값이 없으므로 에러를 처리하려면 exception을 발생시켜야 한다. exception을 사용하지 않기로 했으므로 이를 에러를 발생시키지 않는 constructor와 에러가 발생할 수 있는 init함수로 분리하였다. 그러다보니 state의 문제가 발생한다.(semi-initialized) 이것은 descturtor의 경우도 마찬가지다. 에러가 어디서 일어나느냐에 따라 다양한 state가 있을 수 있기 때문에 이에 대한 처리는 매우 복잡해진다. C를 사용하면 이 문제가 매우 간단해진다.
C++은 undefined behaviour 보다는 빠른 개발이 더 필요한 환경에 적합한 것으로 생각된다. 시스템 프로그래밍은 C가 여전히 최고다.
AOSA의 내용중 ZeroMQ에 대한 내용 요약
http://www.aosabook.org/en/zeromq.html
ZeroMQ는 messaging system이다. 처음에는 엄청 빠른 messaging system을 만드는 것으로 시작하였다. 그래서 처음 1년은 벤치마킹 방법을 고안하고 가능한한 효율적인 아키텍쳐를 만드는데 주력하였다. 2년째에는 distributed application을 만들고 임의의 message pattern이나 다양한 전송 방법이나 여러 language binding을 지원하는데 초점을 맞추었다. 3년째에는 사용성을 향상시키고 배우기 쉽도록 만드는데 주력하였다.
ZeroMQ는 messaging server가 아닌 library다.
ZeroMQ는 messaging system이다. 처음에는 엄청 빠른 messaging system을 만드는 것으로 시작하였다. 그래서 처음 1년은 벤치마킹 방법을 고안하고 가능한한 효율적인 아키텍쳐를 만드는데 주력하였다. 2년째에는 distributed application을 만들고 임의의 message pattern이나 다양한 전송 방법이나 여러 language binding을 지원하는데 초점을 맞추었다. 3년째에는 사용성을 향상시키고 배우기 쉽도록 만드는데 주력하였다.
1. Application vs Library
ZeroMQ는 messaging server가 아닌 library다.
퍼포먼스의 측면에서 볼 때 중간에 서버가 있으면 네트워크를 두번 타게 되는 단점이 생기고 이 서버가 bottleneck의 원인이 될 수 있다.
두번째로 생각해 볼 수 있는 것은 large-scale deployment이다. deployment가 여러 회사에 걸쳐 있게 되면 각각의 회사들은 다른 회사에 서버가 있기를 원하지 않을 것이다. 그러다보니 각각의 회사에 서버가 있게 되고 이것은 관리라든지의 어려움이 생기게 된다. 이것을 해결하려면 각각의 컴포넌트가 별도로 동작하게 하는 완전한 분산 아키텍쳐가 필요하게 된다. 결국 messaging library이다.
ZeroMQ는 서버없이 메시징을 어떻게 할 수 있을까에서 시작하였다. 이에대한 결론이 library이다.
이 아키텍쳐가 더 효율적이고 더 유연하다는 것을 그동안 증명할 수 있었다.
의도하지 않았던 결론중의 하나는 라이브러리 모델이 제품의 사용성을 향상시켰다는 것이다. 사용자들은 서버를 설치하고 운용하지 않아도 된다는 것에 많은 점수를 주었다.
배운점: 처음 프로젝트를 시작할 때 가능하다면 라이브러리의 형태로 만드는 것을 고려해라.
2. Global State
라이브러리에 전역변수는 좋지 않다. 라이브러리는 한 프로세스내에서도 여러번 로드될 수 있는데 이렇다 하더라도 전역변수는 하나만 있게 된다. 그러면 서로 다른 두 군데서 라이브러리의 전역변수는 사용하려고 하면 race condition이나 실패같은 상황이 발생 할 수 있다.
이 무제를 해결하기 위해 ZeroMQ는 전역변수를 사용하지 않는다. 따라서, ZeroMQ를 사용하는 사용자가 필요한 전역변수를 만들어서 사용해야 한다. 이것은 context라고 부르는데 전역변수를 가지고 있는 하나의 object라고 말할 수 있다. 만약 두 군데서 라이브러리를 사용하고 각자 자신의 context를 가지고 사용한다면 서로서로 상대방의 context의 존재를 모를 것이다.
배운점: 라이브러리에서 전역변수를 사용하지 말아라.
3. Performance
메시지 시스템의 속도는 throughput과 latency로 이야기 할 수 있다: throughput - 주어진 시간에 얼마나 많은 메시지가 지나 갈 수 있는가, latency - 메시지가 도착하는데 얼마의 시간이 걸리는가.
여기서 중요하게 이해하고 있어야 하는 점이 있다. latency는 A에서 B로 도착하는 데 각각의 메시지가 걸리는 시간을 의미하는 것이고 throughput은 A에서의 throughput, B에서의 throughput으로 표현되는 것이라는 것이다.
배운점: 직면한 문제를 명확하게 이해하라.
4. Critical Path
아래의 세가지가 퍼포먼스에 중요한 역할을 한다.
- Number of memory allocations
- Number of system calls
- Concurrency model
하지만, 모든 memory allocation이나 system call이 중요하지는 않다. 메시징 시스템에서는주어진 시간동안 A에서 B로 얼마나 많은 메시지를 전달할 수 있느냐가 중요하다. 또한 한 메시지를 얼마의 시간만에 전달할 수 있느냐도 중요할 수 있다.
매우 자주 사용되는 코드의 부분을 critical path라 부르는데 이 부분이 최적화에 초점이 맞추어져야 하는 부분이다.
배운점: critical path에 있지 않은 부분을 최적화하려 하지 마라.
5. Allocating Memory
message allocation과 message copying을 잘 조절하는 것이 퍼포먼스에 중요하다. 작은 메시지는 copy를 하는 것이 낫고, 큰 메시지는 allocation을 하는 것이 낫다.
ZeroMQ는 handle이라고 하는 것을 사용하는데 작은 메시지의 경우는 handle에 데이터를 저장하고 큰 메시지의 경우는 데이터에 대한 포인터만을 저장한다.
배운점: 퍼포먼스를 생각할 때 한가지만을 생각하지 마라. 각각의 경우(작은 메시지와 큰 메시지)에 다른 해결책이 있을 수 있다.
6. Batching
4개의 메시지를 각각 따로 보낸다면 전체 네트워크 스택을 4번 타야하기 때문에 좋지 않다. 이런 경우 여러 메시지를 한번(batching)에 보낼 수 있다면 좋을 것이다(throughput의 향상). 하지만, 반대로 이것은 latency가 나쁘게 된다.
ZeroMQ는 다음의 방법을 사용한다. 메시지가 많지 않고 네트워크 스택의 bandwidth를 넘지 않으면 latency를 향상시키기 위해 batching을 사용하지 않는다. 네트워크 스택의 bandwidth를 넘으면 메시지를 큐에 저장한다. 이러한 상황에서는 batching을 사용한다.
배운점: throughput을 향상시키기 위해 제일 위의 레이어에서만(아래의 레이어에서의 batching은 의미없다) batching을 사용한다. 메시지가 쌓이는 경우만 batch를 사용한다.
7. Architecture Overview
사용자는 여러 peer와 통신할 수 있는 socket이라는 것으로 ZeroMQ와 통신한다.
socket object가 사용자의 쓰레드에 있고 이 외에 ZeroMQ는 통신의 비동기를 다루기 위해 여러개의 worker 쓰레드를 만든다.(네트워크로부터 데이터 읽기, 메시지 큐에 넣기, 접속 연결 허락하기 등)
worker 쓰레드에는 여러 object가 있는데 이들은 하나의 parent를 가진다. 이 parent는 다른 쓰레드에 있을 수 있다. 대부분의 object의 parent는 socket이다. object의 parent의 parent가 socket인 경우도 있다. 따라서 socket을 시작으로 하는 tree가 생기게 된다. object는 자신의 children이 사라져야(shut down) 자신도 사라질 수 있기 때문에 이에 tree를 이용한다.
message passing에 관련이 있는 object와 관련이 없는 object로 해서 두 종류의 비동기 object가 있다. message passing에 관련이 없는 object는 주로 connection management와 관련이 있다. 예를 들어 TCP listener object는 접속하려는 TCP 연결을 기다리고 각각의 새 연결에 engine/session object를 만든다. 비슷하게 TCP connector object는 TCP peer에의 연결을 시도하고 이것이 성공하면 연결을 관리하는 engine/session object를 만든다. 연결이 실패하면 다시 연결하기를 시도한다.
message passing에 관련이 있는 object는 data transfer를 다루는 object들이다. 이 object들은 두 부분으로 구성되어 있다. session object는 ZeroMQ socket과 통신을 하고 engine object는 네트워크 부분과 통신을 한다. session object는 한 종류만 있지만 engine object는 여러 type(TCP engines, IPC engines, PGM engines등)이 있다. 추가도 가능하게 되어 있다.
session은 socket과 message를 교환한다. message를 전달하는 것은 양방향으로 되어 있고 각각은 pipe object에 의해 다루어진다. 각각의 pipe는 쓰레드들 사이에 메시지를 빠르게 전달하는데 최적화된 lock-free 큐이다.
마지막으로, 모든 socket과 모든 비동기 object들에 의해 사용이 가능하고 global state를 저장하고 있는 context object가 있다.
8. Concurrency Model
멀티코어를 잘 이용하는 것은 ZeroMQ의 요건중의 하나다. 다시 말하면 코어가 증가하면 throughput이 증가하는 것을 의미한다.
전통적인 방법(critical sections, semaphores등)으로 여러 쓰레드를 사용하는 것은 성능을 향상시키지 않는다. 여러 쓰레드를 사용하면 코어가 여러개라도 하나의 쓰레드를 사용하는 것보다 느릴 수 있다.
ZeroMQ는 actor model이라 불리는 다른 모델을 사용한다. 쓰레드들 간의 통신에 쓰레드들 사이에 전달하는 비동기 메시지를 사용하는 것이다.
한 코어당 하나의 worker thread만을 사용한다. TCP engine 같은 각각의 내부 ZeroMQ object들은 특정한 worker thread에 연결되어 있다. 따라서 critical section이나 mutex나 semaphore같은 것을 사용할 필요가 없게 된다. 또한 이 object들은 CPU 코어 사이를 이동할 필요가 없게 되기 때문에 cache pollution을 피할 수 있게 된다.
이 방법은 기존의 멀티 쓰레딩의 문제를 사라지게 한다. 하지만 여전히 많은 object들 사이에 worker thread를 공유할 필요가 있다. 이벤트의 임의의 시퀀스를 다루어야 하고 object가 CPU를 오래 사용하면 안되도록 해야 하기 때문에 하나의 이벤트 루프를 사용하기 보다는 event-driven 방식으로 object를 관리하는 스케줄러가 필요하다는 것을 의미한다.
전체 시스템은 완전히 비동기적이어야 한다. blocking을 사용하는 object가 없어야 한다. blocking을 어떤 하나의 object가 사용하면 같은 worker thread를 공유하는 다른 쓰레드가 block될 수 있기 때문이다. 모든 object는 명백히든 내부적으로든 state machine이어야 한다. 동시에 실행중인 수백, 수천개의 state machine사이에 가능한 모든 통신을 다룰 수 있어야 한다. 특히 중요한것이 shutdown process이다.
완전히 비동기적인 시스템에서의 shutdown은 매우 복잡한 작업이다. 이 부분이 ZeroMQ에서 가장 복잡한 부분이다.버그 트래커를 보면 30-50%정도가 shutdown에 관련되어 있다.
배운점: 진짜로 performance와 scalibility를 고려한다면 actor model를 고려해보라.
9. Lock-Free Algorithms
lock-free algorithm은 커널이 제공하는 mutex나 semaphore를 사용하지 않고 쓰레드간에 통신을 하기 위한 방법이다. atomic compare-and-swap(CAS)같은 CPU의 기능을 사용해서 동기화를 한다. 이것은 하드웨어 레벨에서 lock이 이루어지기 때문에 진짜로 lock-free이지는 않다.
ZeroMQ는 pipe object에서 lock-free queue를 사용해서 user thread와 worker thread사이의 메시지를 전달한다. ZeroMQ가 lock-free queue를 사용하는 두가지 흥미로운 측면이 있다.
첫째로, 각각의 queue는 하나의 write thread와 하나의 reader thread를 가진다. 1:N 통신이 필요하면 여러 queue가 만들어진다. 이렇게 하면 writer들이나 reader들에의 동기화를 신경쓸 필요가 없어지기 때문에 매우 효율적이 된다.
둘째로, lock-free algorithm이 효율적이기는 하지만 여전히 우리가 원하는 만큼의 성능을 주지는 않았다.
이것을 향상시키기 위해 사용한 방법이 batching이다. 10개의 메시지가 있다고 하자. 이 메시지들을 하나씩 queue에 넣기 보다는 10개를 모은 후 한번에 queue에 저장하는 것이 낫다.
같은 방법을 reader쪽에도 적용할 수 있다. 메시지를 하나씩 읽기보다는 이 메시지들을 reader thread만이 읽을 수있는 queue의 특정영역(pre-read buffer)에 두고 reader thread가 한번에 읽을 수 있게 한다.
배운점: lock-free algorithm은 사용하기도 어렵고, 구현하기에도 문제 많고 디버깅하기도 좋지 않다. 가능하다면 기존의 가능한 방법을 사용하자. 너무 lock-free algorithm에 의존하지 말아라.
10. API
user interface는 제품에서 매우 중요한 부분이다. 라이브러리에서는 API가 될 것이다.
ZeroMQ의 초기 API는 exchange와 queue에 AMQP의 model을 따라 만들었다. 이것을 다시 처음부터 만들 때 BSD Socket API를 따라 만들었다. 이전에는 전문가가 사용하는 제품이었다면 이후부터는 누구든지 쉽게 사용할 수 있는 제품이 되었다. 커뮤니티는 10배로 커졌고 20개 이상의 언어의 바인딩이 만들어졌다.
배운점: 만들고자 하는 것을 알고 그에 맞는 UI를 만들어라.
BSD Socket API가 오래되었지만 많은 사람들이 알고 있고 쓰고 있는 것이기 때문에 ZeroMQ의 API를 배우기가 쉬워졌다. 또한 TCP, UDP, file, pipe같은 기존의 것과 같은 API를 사용하기 때문에 이것들과 같은 데서 사용될 수도 있고 기존의 것에 ZeroMQ를 쉽게 추가할 수도 있다. 그리고 BSD Socket API가 오래 사용되었다는 것은 이것이 좋은 디자인으로 만들어졌다고 말할 수 있는 것이다. 이것을 따른다는 것은 우리의 API도 좋은 디자인을 따라간다고 할 수 있다.
배운점: 제품을 만들 때 관련 제품을 살펴보라. 어떤 제품이 실패했고 어떤 제품이 성공했는지를 보고 배워라. 배울 수 있는 모든 것(idea, API, framework등)은 다 배워라.
11. Messaging Patterns
메시징 시스템에서 가장 중요한 문제는 사용자가 어떤 메시지를 어디로 보낼 것인지를 정하는 방법을 어떻게 사용자에게 제공할 것인가 하는 것이다. 이에는 두가지 접근법이 있다.
첫째로는 "do one thing and do it well"이라는 유닉스 철학을 따르는 것이다. 이것이 의미하는 바는 문제를 제한된 영역으로 제한하여 해결해야 하는 문제를 해결하는 것이다. 이것의 예로는 MQTT가 있다.
두번째로는 일반성에 초점을 맞추어 강력하고 구성이 가능한 시스템을 만드는 것이다. AMQP가 이것의 예이다. 이 모델은 어떤 routing algorithm도 정의할 수 있게 해주는 수단을 사용자에게 제공한다.
ZeroMQ는 첫번째 모델을 따른다. 첫번째 모델은 누구나 쉽게 사용할 수 있지만 두번째는 전문가정도는 되어야 사용이 가능한다.
특정 문제에 맞는 해결을 하는 것이 일반적인 해결을 하는 것보다 낫기는 하지만 그래도 사용자에게 다양한 기능을 제공하는 것이 좋다. 이 모순을 어떻게 해결할 수 있을까?
아래의 두단계로 해결할 수 있다.
1. 특정한 문제 영역을 다루기 위한 레이어를 정의한다.(transport, routing, presentation등)
2. 서로 관련이 없는 각 레이어의 구현을 만든다.
인터넷 스택에서 transport layer를 예로 들어보자. IP layer위에 다양한 서비스(TCP, UDP, SCTP등)가 존재한다. 이들은 서로 연관을 맺지 않는다. 따라서 쉽게 새로운 서비스를 추가할 수 있고 기존의 것을 제거할 수도 있다.
같은 원리가 messaging pattern에도 적용된다. messaging pattern은 transport layer위로 scalibility layer라 불리는 layer를 구성한다. 각각의 messaging pattern은 이 레이어의 구현이다. publish/subscribe나 request/reply는 서로 연관없이 동작한다.
배운점: 복잡하고 다양한 측면을 가지는 문제를 해결하고자 할 때 하나의 일반적인 해결책이 최선이 아닐 수 있다. 대신에 문제 영역을 잘 추상화하고 각각의 레이어에 다양한 구현을 제공한다.
12. Conclusion
이 문서는 시스템적인 측면에서 large-scale distributed system을 만들면서의 우리의 경험을 이야기한다.
2. Global State
라이브러리에 전역변수는 좋지 않다. 라이브러리는 한 프로세스내에서도 여러번 로드될 수 있는데 이렇다 하더라도 전역변수는 하나만 있게 된다. 그러면 서로 다른 두 군데서 라이브러리의 전역변수는 사용하려고 하면 race condition이나 실패같은 상황이 발생 할 수 있다.
이 무제를 해결하기 위해 ZeroMQ는 전역변수를 사용하지 않는다. 따라서, ZeroMQ를 사용하는 사용자가 필요한 전역변수를 만들어서 사용해야 한다. 이것은 context라고 부르는데 전역변수를 가지고 있는 하나의 object라고 말할 수 있다. 만약 두 군데서 라이브러리를 사용하고 각자 자신의 context를 가지고 사용한다면 서로서로 상대방의 context의 존재를 모를 것이다.
배운점: 라이브러리에서 전역변수를 사용하지 말아라.
3. Performance
메시지 시스템의 속도는 throughput과 latency로 이야기 할 수 있다: throughput - 주어진 시간에 얼마나 많은 메시지가 지나 갈 수 있는가, latency - 메시지가 도착하는데 얼마의 시간이 걸리는가.
여기서 중요하게 이해하고 있어야 하는 점이 있다. latency는 A에서 B로 도착하는 데 각각의 메시지가 걸리는 시간을 의미하는 것이고 throughput은 A에서의 throughput, B에서의 throughput으로 표현되는 것이라는 것이다.
배운점: 직면한 문제를 명확하게 이해하라.
4. Critical Path
아래의 세가지가 퍼포먼스에 중요한 역할을 한다.
- Number of memory allocations
- Number of system calls
- Concurrency model
하지만, 모든 memory allocation이나 system call이 중요하지는 않다. 메시징 시스템에서는주어진 시간동안 A에서 B로 얼마나 많은 메시지를 전달할 수 있느냐가 중요하다. 또한 한 메시지를 얼마의 시간만에 전달할 수 있느냐도 중요할 수 있다.
매우 자주 사용되는 코드의 부분을 critical path라 부르는데 이 부분이 최적화에 초점이 맞추어져야 하는 부분이다.
배운점: critical path에 있지 않은 부분을 최적화하려 하지 마라.
5. Allocating Memory
message allocation과 message copying을 잘 조절하는 것이 퍼포먼스에 중요하다. 작은 메시지는 copy를 하는 것이 낫고, 큰 메시지는 allocation을 하는 것이 낫다.
ZeroMQ는 handle이라고 하는 것을 사용하는데 작은 메시지의 경우는 handle에 데이터를 저장하고 큰 메시지의 경우는 데이터에 대한 포인터만을 저장한다.
배운점: 퍼포먼스를 생각할 때 한가지만을 생각하지 마라. 각각의 경우(작은 메시지와 큰 메시지)에 다른 해결책이 있을 수 있다.
6. Batching
4개의 메시지를 각각 따로 보낸다면 전체 네트워크 스택을 4번 타야하기 때문에 좋지 않다. 이런 경우 여러 메시지를 한번(batching)에 보낼 수 있다면 좋을 것이다(throughput의 향상). 하지만, 반대로 이것은 latency가 나쁘게 된다.
ZeroMQ는 다음의 방법을 사용한다. 메시지가 많지 않고 네트워크 스택의 bandwidth를 넘지 않으면 latency를 향상시키기 위해 batching을 사용하지 않는다. 네트워크 스택의 bandwidth를 넘으면 메시지를 큐에 저장한다. 이러한 상황에서는 batching을 사용한다.
배운점: throughput을 향상시키기 위해 제일 위의 레이어에서만(아래의 레이어에서의 batching은 의미없다) batching을 사용한다. 메시지가 쌓이는 경우만 batch를 사용한다.
7. Architecture Overview
사용자는 여러 peer와 통신할 수 있는 socket이라는 것으로 ZeroMQ와 통신한다.
socket object가 사용자의 쓰레드에 있고 이 외에 ZeroMQ는 통신의 비동기를 다루기 위해 여러개의 worker 쓰레드를 만든다.(네트워크로부터 데이터 읽기, 메시지 큐에 넣기, 접속 연결 허락하기 등)
worker 쓰레드에는 여러 object가 있는데 이들은 하나의 parent를 가진다. 이 parent는 다른 쓰레드에 있을 수 있다. 대부분의 object의 parent는 socket이다. object의 parent의 parent가 socket인 경우도 있다. 따라서 socket을 시작으로 하는 tree가 생기게 된다. object는 자신의 children이 사라져야(shut down) 자신도 사라질 수 있기 때문에 이에 tree를 이용한다.
message passing에 관련이 있는 object와 관련이 없는 object로 해서 두 종류의 비동기 object가 있다. message passing에 관련이 없는 object는 주로 connection management와 관련이 있다. 예를 들어 TCP listener object는 접속하려는 TCP 연결을 기다리고 각각의 새 연결에 engine/session object를 만든다. 비슷하게 TCP connector object는 TCP peer에의 연결을 시도하고 이것이 성공하면 연결을 관리하는 engine/session object를 만든다. 연결이 실패하면 다시 연결하기를 시도한다.
message passing에 관련이 있는 object는 data transfer를 다루는 object들이다. 이 object들은 두 부분으로 구성되어 있다. session object는 ZeroMQ socket과 통신을 하고 engine object는 네트워크 부분과 통신을 한다. session object는 한 종류만 있지만 engine object는 여러 type(TCP engines, IPC engines, PGM engines등)이 있다. 추가도 가능하게 되어 있다.
session은 socket과 message를 교환한다. message를 전달하는 것은 양방향으로 되어 있고 각각은 pipe object에 의해 다루어진다. 각각의 pipe는 쓰레드들 사이에 메시지를 빠르게 전달하는데 최적화된 lock-free 큐이다.
마지막으로, 모든 socket과 모든 비동기 object들에 의해 사용이 가능하고 global state를 저장하고 있는 context object가 있다.
8. Concurrency Model
멀티코어를 잘 이용하는 것은 ZeroMQ의 요건중의 하나다. 다시 말하면 코어가 증가하면 throughput이 증가하는 것을 의미한다.
전통적인 방법(critical sections, semaphores등)으로 여러 쓰레드를 사용하는 것은 성능을 향상시키지 않는다. 여러 쓰레드를 사용하면 코어가 여러개라도 하나의 쓰레드를 사용하는 것보다 느릴 수 있다.
ZeroMQ는 actor model이라 불리는 다른 모델을 사용한다. 쓰레드들 간의 통신에 쓰레드들 사이에 전달하는 비동기 메시지를 사용하는 것이다.
한 코어당 하나의 worker thread만을 사용한다. TCP engine 같은 각각의 내부 ZeroMQ object들은 특정한 worker thread에 연결되어 있다. 따라서 critical section이나 mutex나 semaphore같은 것을 사용할 필요가 없게 된다. 또한 이 object들은 CPU 코어 사이를 이동할 필요가 없게 되기 때문에 cache pollution을 피할 수 있게 된다.
이 방법은 기존의 멀티 쓰레딩의 문제를 사라지게 한다. 하지만 여전히 많은 object들 사이에 worker thread를 공유할 필요가 있다. 이벤트의 임의의 시퀀스를 다루어야 하고 object가 CPU를 오래 사용하면 안되도록 해야 하기 때문에 하나의 이벤트 루프를 사용하기 보다는 event-driven 방식으로 object를 관리하는 스케줄러가 필요하다는 것을 의미한다.
전체 시스템은 완전히 비동기적이어야 한다. blocking을 사용하는 object가 없어야 한다. blocking을 어떤 하나의 object가 사용하면 같은 worker thread를 공유하는 다른 쓰레드가 block될 수 있기 때문이다. 모든 object는 명백히든 내부적으로든 state machine이어야 한다. 동시에 실행중인 수백, 수천개의 state machine사이에 가능한 모든 통신을 다룰 수 있어야 한다. 특히 중요한것이 shutdown process이다.
완전히 비동기적인 시스템에서의 shutdown은 매우 복잡한 작업이다. 이 부분이 ZeroMQ에서 가장 복잡한 부분이다.버그 트래커를 보면 30-50%정도가 shutdown에 관련되어 있다.
배운점: 진짜로 performance와 scalibility를 고려한다면 actor model를 고려해보라.
9. Lock-Free Algorithms
lock-free algorithm은 커널이 제공하는 mutex나 semaphore를 사용하지 않고 쓰레드간에 통신을 하기 위한 방법이다. atomic compare-and-swap(CAS)같은 CPU의 기능을 사용해서 동기화를 한다. 이것은 하드웨어 레벨에서 lock이 이루어지기 때문에 진짜로 lock-free이지는 않다.
ZeroMQ는 pipe object에서 lock-free queue를 사용해서 user thread와 worker thread사이의 메시지를 전달한다. ZeroMQ가 lock-free queue를 사용하는 두가지 흥미로운 측면이 있다.
첫째로, 각각의 queue는 하나의 write thread와 하나의 reader thread를 가진다. 1:N 통신이 필요하면 여러 queue가 만들어진다. 이렇게 하면 writer들이나 reader들에의 동기화를 신경쓸 필요가 없어지기 때문에 매우 효율적이 된다.
둘째로, lock-free algorithm이 효율적이기는 하지만 여전히 우리가 원하는 만큼의 성능을 주지는 않았다.
이것을 향상시키기 위해 사용한 방법이 batching이다. 10개의 메시지가 있다고 하자. 이 메시지들을 하나씩 queue에 넣기 보다는 10개를 모은 후 한번에 queue에 저장하는 것이 낫다.
같은 방법을 reader쪽에도 적용할 수 있다. 메시지를 하나씩 읽기보다는 이 메시지들을 reader thread만이 읽을 수있는 queue의 특정영역(pre-read buffer)에 두고 reader thread가 한번에 읽을 수 있게 한다.
배운점: lock-free algorithm은 사용하기도 어렵고, 구현하기에도 문제 많고 디버깅하기도 좋지 않다. 가능하다면 기존의 가능한 방법을 사용하자. 너무 lock-free algorithm에 의존하지 말아라.
10. API
user interface는 제품에서 매우 중요한 부분이다. 라이브러리에서는 API가 될 것이다.
ZeroMQ의 초기 API는 exchange와 queue에 AMQP의 model을 따라 만들었다. 이것을 다시 처음부터 만들 때 BSD Socket API를 따라 만들었다. 이전에는 전문가가 사용하는 제품이었다면 이후부터는 누구든지 쉽게 사용할 수 있는 제품이 되었다. 커뮤니티는 10배로 커졌고 20개 이상의 언어의 바인딩이 만들어졌다.
배운점: 만들고자 하는 것을 알고 그에 맞는 UI를 만들어라.
BSD Socket API가 오래되었지만 많은 사람들이 알고 있고 쓰고 있는 것이기 때문에 ZeroMQ의 API를 배우기가 쉬워졌다. 또한 TCP, UDP, file, pipe같은 기존의 것과 같은 API를 사용하기 때문에 이것들과 같은 데서 사용될 수도 있고 기존의 것에 ZeroMQ를 쉽게 추가할 수도 있다. 그리고 BSD Socket API가 오래 사용되었다는 것은 이것이 좋은 디자인으로 만들어졌다고 말할 수 있는 것이다. 이것을 따른다는 것은 우리의 API도 좋은 디자인을 따라간다고 할 수 있다.
배운점: 제품을 만들 때 관련 제품을 살펴보라. 어떤 제품이 실패했고 어떤 제품이 성공했는지를 보고 배워라. 배울 수 있는 모든 것(idea, API, framework등)은 다 배워라.
11. Messaging Patterns
메시징 시스템에서 가장 중요한 문제는 사용자가 어떤 메시지를 어디로 보낼 것인지를 정하는 방법을 어떻게 사용자에게 제공할 것인가 하는 것이다. 이에는 두가지 접근법이 있다.
첫째로는 "do one thing and do it well"이라는 유닉스 철학을 따르는 것이다. 이것이 의미하는 바는 문제를 제한된 영역으로 제한하여 해결해야 하는 문제를 해결하는 것이다. 이것의 예로는 MQTT가 있다.
두번째로는 일반성에 초점을 맞추어 강력하고 구성이 가능한 시스템을 만드는 것이다. AMQP가 이것의 예이다. 이 모델은 어떤 routing algorithm도 정의할 수 있게 해주는 수단을 사용자에게 제공한다.
ZeroMQ는 첫번째 모델을 따른다. 첫번째 모델은 누구나 쉽게 사용할 수 있지만 두번째는 전문가정도는 되어야 사용이 가능한다.
특정 문제에 맞는 해결을 하는 것이 일반적인 해결을 하는 것보다 낫기는 하지만 그래도 사용자에게 다양한 기능을 제공하는 것이 좋다. 이 모순을 어떻게 해결할 수 있을까?
아래의 두단계로 해결할 수 있다.
1. 특정한 문제 영역을 다루기 위한 레이어를 정의한다.(transport, routing, presentation등)
2. 서로 관련이 없는 각 레이어의 구현을 만든다.
인터넷 스택에서 transport layer를 예로 들어보자. IP layer위에 다양한 서비스(TCP, UDP, SCTP등)가 존재한다. 이들은 서로 연관을 맺지 않는다. 따라서 쉽게 새로운 서비스를 추가할 수 있고 기존의 것을 제거할 수도 있다.
같은 원리가 messaging pattern에도 적용된다. messaging pattern은 transport layer위로 scalibility layer라 불리는 layer를 구성한다. 각각의 messaging pattern은 이 레이어의 구현이다. publish/subscribe나 request/reply는 서로 연관없이 동작한다.
배운점: 복잡하고 다양한 측면을 가지는 문제를 해결하고자 할 때 하나의 일반적인 해결책이 최선이 아닐 수 있다. 대신에 문제 영역을 잘 추상화하고 각각의 레이어에 다양한 구현을 제공한다.
12. Conclusion
이 문서는 시스템적인 측면에서 large-scale distributed system을 만들면서의 우리의 경험을 이야기한다.
Linux Performance and Tuning Guidelines 초간단 요약
- 병목점 찾기
1 시스템 파악
2 시스템 백업
3 시스템의 성능 모니터링하고 분석
4 문제가 있는 병목점을 정한 후 원인 찾기
5 한번에 하나씩 시도하며 병목점 문제 해결
6 시스템의 성능이 만족스러울 때까지 3으로 돌아가 반복
- CPU performance tuning
ps -ef로 확인하여 불필요한 프로그램이 돌고 있으면 cron을 써서 중요하지 않은 시간에 돌도록 변경
CPU를 많이 쓰나 중요하지 않은 프로세스는 priority를 조정(top, renice)
SMP 머신의 경우 프로세스가 여러 프로세서에서 돌지 않도록 해준다(taskset)
실행중인 애플리케이션에 따라 CPU를 증설하는 것보다는 더 빠른 CPU로 바꾸어 주는 것이 나을 수 있다.
최신 driver나 firmware를 사용한다.
- Memory performance tuning
bigpages, hugetlb, shared memory를 사용해서 swap space를 튜닝
page의 사이즈를 늘리거나 줄이기
active와 inactive memory를 다루는 방법을 향상시키기
page-out rate를 조절하기
서버에서 각각의 유저가 사용가능한 리소스 제한하기
불필요한 서비스 중단하기
메모리 늘리기
- Disk performance tuning
workload가 sequential 때문이라면 더 빠른 disk controller를 설치한다. workload가 random 때문이라면 drive를 추가한다.
RADI환경에서는 disk drive를 추가한다. 하드웨어 RAID를 사용한다.
striping없는 logical volume을 사용하는 것보다 striping있는 logical volume을 사용하는 것을 고려해라.
네트워크상의 다른 시스템으로 프로세싱 넘기기 - Offload processing to another system in the network (users, applications, or services).
더 많은 램을 추가하기
- Network performance tuning
네트워크 카드의 설정이 router와 switch 설정과 잘 맞는지 확인(frame size)
subnet 조작하기
더 빠른 네트워크 카드 사용하기
적절한 IPv4 TCP 커널 파라메터 튜닝하기
네트워크 카드 바꾸고 성능 측정하기
네트워크 카드를 추가하고 바인딩하기
- Changing kernel parameters
kernel parameter에 대한 정보는 /proc(or /proc/sys)에 저장된다.
sysctl 사용
예: > sysctl /proc/sys/kernel/kernel.shmmax
reboot후 설정 사라짐. /etc/sysctl.conf에 위 내용 넣어두면 계속 적용
- Tuning the processor subsystem
프로세스의 priority를 변경 - renice
CPU affinity
프로세스를 특정 CPU에서만 돌도록 하기
irq 19를 3번째 CPU에 할당
> echo 03 > /proc/irq/19/smp_affinity
SMT(symmetric multi-threading)시스템에서는 물리 CPU가 인터럽트를 처리하도록 하기
NUMA(Non-Uniform Memory Architecture) 시스템
NUMA지원이 없는 애플리케이션이 병목점이 될 수 있다. numastat(numactl 패키지)로 확인
- Tuning the vm subsystem
swap 설정
메모리 페이지 스왑하기 - /proc/sys/vm/swappiness(값을 크게하면 swap이 더 잘 일어나게 된다.)
pdflush daemon이 얼마나 자주 flush를 하는지 설정 - /proc/sys/vm/dirty_background_ratio(값을 크게하면 flush가 더 잘 일어나게 된다.)
애플리케이션에 의해 만들어진 dirty page를 디스크로 flush하는 비율 설정 - /proc/sys/vm/dirt_ratio(file system cache의 비율 설정)
Swap partition
보통의 스왑 파티션은 물리 메모리의 두배
스왑 파티션을 여러개 만드는 것이 성능을 향상시킬 수 있다.
순차적 사용, 여러개 동시에 사용
스왑 파티션은 가장 빠른 드라이브에 설정한다.
HugeTLBfs
TLB(Translation Lookaside Buffer)의 크기를 늘린다. - /proc/sys/vm/nr_hugepages
TLB - a small cache used for storing virtual-to-physical mapping information
/proc/meminfo로 hugetlb page의 정보를 볼 수 있다.
- Tuning the disk subsystem
Hardware 고려사항
disk I/O가 중요한 시스템: file, print, database server
disk I/O가 중요하지 않은 시스템: email, web server
RAID로 엮은(software and hardware RAID) drive를 통해 성능을 향상 시킬 수 있다.
파티션 나누기
보안을 향상시킨다.
data integrity를 향상시킨다.
새로운 인스톨이나 업그레이드 시 다른 파티션에 영향을 주지 않을 수 있다.
효율적인 백업 가능
I/O elevator
elevator 선택하기
Synchronous file system access
anticipatory elevator - least throughput and the highest latency
CFQ, NOOP, deadline은 비슷하게 좋으나 I/O 사이즈가 16kb가 넘어가면 CFQ와 NOOP가 좋음
Complex disk subsystems
NOOP elevator
Database systems
seek-oriented 특성때문에 deadline elevator가 좋다.
Virtual machines
virtualization layer가 필요한 작업을 한다.
CPU bound applications
NOOP elevator
Simple ATA or SATA disk subsystems
anticipatory elevator
nr_requests
> echo 64 > /sys/block/sdb/queue/nr_requests
disk subsystem과 I/O 특성에 따라 다르게 해줄 필요가 있다.
nr_requests의 값 별로 I/O 사이즈에 따른 throughput 측정
read_ahead_kb
> echo 64 > /sys/block/<disk_subsystem>/queue/read_ahead_kb
large streaming read의 경우 read ahead buffer의 크기를 증가시키면 성능 향상이 올 수 있다.
random I/O operation의 경우는 별로 효과가 없을 것이다.
file system 선택하기
적은 I/O request의 경우 ReiserFS가 적합하고 매우 큰 파일 시스템과 매우 큰 I/O 사이즈에서는 XFS와 JFS가 좋다. Ext3는 좋은 multiprocessor scalability를 제공하면서 적은 I/O request에 적합하기 때문에 이들의 중간점이라 볼 수 있다.
JFS, XFS: high-end data warehouses, scientific workloads, large SMP servers, or streaming media servers
ReiserFS, Ext3: file, web, mail
Ext2는 synchronous file system acccess시 좋음. data integrity보다 성능이 우선시 되는 경우 선택한다. asynchronous file system의 경우는 ReiserFS가 Ext3보다 좋다.
I/O priority
CFQ I/O elevator에서 제공하는 process에 priority를 할당하는 기능
ionice를 사용
idle, best-effort, real time
Access time updates
linux file system이 저장하는 파일의 시간정보를 저장하지 않음으로서 성능향상을 줄 수 있다.
Journaling mode 선택하기
mode 변경방법
> mount -o data=writeback /dev/sdb1 /mnt/mountpoint
또는 /etc/fstab에서 변경가능
/dev/sdb1 /testfs ext3 defaults,data=writeback 0 0
data=journal
file data와 metadata를 저널링한다.
data=ordered(default)
metadata만 저널링한다.
data=writeback
특별히 적은 I/O사이즈의 경우 Ext3의 성능을 향상시킨다.
I/O 사이즈가 증가하면 writeback의 효과는 줄어든다.
write의 경우 성능향상이 있고 read의 경우 별 효과가 없다.
Block sizes
작은 파일을 많이 다룬다면 작은 block size가 좋다.
많은 파일을 많이 다룬다면 큰 block size가 좋다.
하지만 여러 벤치마크를 보면 block size의 변경으로 실제 성능향상을 보기는 쉽지 않다. 그러므로 디폴트인 4K로 두는 것이 일반적으로 좋다.
hardware RAID가 사용되는 경우 array의 stripe size가 성능에 매우 큰 영향을 미친다.
- Tuning the network subsystem
네트워크 트래픽
netstat, tcpdump, ethereal을 사용하여 정보 획득
고려사항:
Transaction throughput requirements (peak, average)
Data transfer throughput requirements (peak, average)
Latency requirements
Transfer data size
Proportion of send and receive
Frequency of connection establishment and close or number of concurrent connections
Protocol (TCP, UDP, and application protocol such as HTTP, SMTP, LDAP, and so on)
speed and duplexing
NIC의 속도 확인
네트워크 컴포넌트(switch or hub)와 NIC의 관계 확인
MTU size
Maximum Transmission Units
> ifconfig eth0 mtu 9000 up
모든 네트워크가 큰 MTU를 지원하지는 않는다.
Network buffer 증가시키기
memory resources
초기 TCP memory
/proc/sys/net/ipv4/tcp_mem
receive socket memory
/proc/sys/net/core/rmem_default
/proc/sys/net/core/rmem_max
send socket memory
/proc/sys/net/core/wmem_default
/proc/sys/net/core/wmem_max
option memory buffer
/proc/sys/net/core/optmem_max
window size 조정
BDP(bandwidth delay product)로 최적의 window size 값을 알아올 수 있다.
BDP = Bandwidth(bytes/sec) * Delay(or round trip time)(sec)
tcpdump로 변경 내용 확인
TCP/IP tuning
IP와 ICMP tuning
spoofing attack 막기
> sysctl -w net.ipv4.conf.eth0.accept_source_route=0
> sysctl -w net.ipv4.conf.lo.accept_source_route=0
> sysctl -w net.ipv4.conf.default.accept_source_route=0
> sysctl -w net.ipv4.conf.all.accept_source_route=0
지정된 머신이 아닌 곳에서의 redirect 막기
> sysctl -w net.ipv4.conf.eth0.secure_redirects=1
> sysctl -w net.ipv4.conf.lo.secure_redirects=1
> sysctl -w net.ipv4.conf.default.secure_redirects=1
> sysctl -w net.ipv4.conf.all.secure_redirects=1
ICMP redirect 막기
> sysctl -w net.ipv4.conf.eth0.accept_redirects=0
> sysctl -w net.ipv4.conf.lo.accept_redirects=0
> sysctl -w net.ipv4.conf.default.accept_redirects=0
> sysctl -w net.ipv4.conf.all.accept_redirects=0
router가 아닌 경우 redirect 보내지 않기
> sysctl -w net.ipv4.conf.eth0.send_redirects=0
> sysctl -w net.ipv4.conf.lo.send_redirects=0
> sysctl -w net.ipv4.conf.default.send_redirects=0
> sysctl -w net.ipv4.conf.all.send_redirects=0
broadcast ping과 smurf 공격 무시하기
> sysctl -w net.ipv4.icmp_echo_ignore_broadcasts=1
icmp 패킷이나 ping 무시하기
> sysctl -w net.ipv4.cimp_echo_ignore_all=1
router에 의한 invalid response 무시하기
> sysctl -w net.ipv4.icmp_ignore_bogus_error_responses=1
IP fragment를 합치는데 사용되는 메모리 설정
> sysctl -w net.ipv4.ipfrag_low_thresh=262144
> sysctl -w net.ipv4.ipfrag_high_thresh=393216
TCP tuning
TIME_WAIT socket 다시 사용하기
> sysctl -w net.ipv4.tcp_tw_reuse=1
> sysctl -w net.ipv4.tcp_tw_recycle=1
tcp_fin_timeout 값 줄이기
FIN-WAIT-2에서 소켓을 가지고 있는 시간
> sysctl -w net.ipv4.tcp_fin_timeout=30
동작중이지 않은 소켓 연결 끊는 시간 줄이기
> sysctl -w net.ipv4.tcp_keepalive_time=1800
backlog connections queue값 올리기
> sysctl -w net.ipv4.tcp_max_syn_backlog=4096
TCP SYN cookies는 필요할 때만 키기
> sysctl -w net.ipv4.tcp_syncookies=1
커널이 CONFIG_SYNCOOKIES로 컴파일되어야 함
Dos와 DDos를 막아주기는 하지만 성능에 영향을 미침
TCP options tuning
selective acknowledgment 막기
> sysctl -w net.ipv4.tcp_sack=0
> sysctl -w net.ipv4.tcp_dsack=0
TCP timestamp 막기
> sysctl -w net.ipv4.tcp_timestamps=0
backend system의 경우 굳이 time stamp 필요없음
window scaling 막기
> sysctl -w net.ipv4.tcp_window_scaling=0
high network load에서는 window scaling이 좋지 않음
Netfilter
packet filtering capability와 network security를 향상시키지만 예측가능하지 않은 행동을 유발할 수 있다.
영향을 끼치는 요인
Number of rules
Order of rules
Complexity of rules
Connection tracking level (depends on protocols)
Netfilter kernel parameter configuration
Offload configuration
ethtool 사용
> ethtool -k eth0
packet queue의 크기 늘리기
/proc/sys/net/core/netdev_max_backlog
transmit queue length 늘리기
> ifconfig eth1 txqueuelen 2000
large, homogeneous data transfer를 수행하는 high-speed 연결에 적합
인터럽트 줄이기
network interface의 인터럽트를 물리 CPU에 할당하면 성능 향상을 얻을 수 있다.
interrupt number 알아내기
> ifconfig eth1
인터럽트의 CPU affinity 설정하기
> echo 02 > /proc/irq/169/smp_affinity
- sysctl tutorial
http://www.frozentux.net/ipsysctl-tutorial/ipsysctl-tutorial.html
- 참고
https://access.redhat.com/knowledge/docs/en-US/Red_Hat_Enterprise_Linux/6/html/Performance_Tuning_Guide/index.html
Flask - Quickstart 요약
- 가장 간단한 웹앱을 만들어 보자.
# hello.py
위와 같이 입력하고 command line에서 아래와 같이 입력한다.
> python hello.py
브라우저에서 http://127.0.0.1:5000에 접속하면 'Hello World!'를 볼 수 있다.
접속 URL을 컴퓨터의 ip로 바꾸고 싶으면 app.run부분을 아래와 같이 바꾸면 된다.
=> app.run(host='0.0.0.0')
디버그 모드를 키고 싶으면 아래와 같이 한다.
=> app.run(debug=True)
'/'의 요청시 hello_world() 함수가 호출되는 것은 @app.route에 의해 이루어진다.
위에서처럼 고정된 URL이 아닌 필요에 따라 변하는 URL의 경우 매칭시키고 싶으면 아래와 같이 하면 URL에서 <username> 부분이 함수의 username 파라메터로 넘어온다.
@app.route('/<username>')
def show_user_profile(username):
return 'User %s' % username
들어오는 값을 아래와 같이 변환해 줄 수도 있다.
@app.route('/<int:post_id>')
def show_post(post_id):
return 'Post %d' % post_id
변환해주는 값에는 아래의 3가지가 있다.
int : 정수로 변환
float: 실수로 변환
path: 마지막 '/'도 포함하는 path
- routing rule
* 마지막에 '/'가 있는 경우:
예) '/projects/'
'/projects'로 요청하면 flask는 '/projects/'로 redirect한다.
* 마지막에 '/'가 없는 경우:
예) '/projects'
'/projects/'로 요청하면 없는 페이지로 에러 발생
지금까지는 url을 함수로 매핑시켜주는 @app.route를 살펴봤다. 반대도 가능할까? url_for()를 사용하면 된다. 첫번째 파라메터는 함수의 이름이고 두번째부터는 URL에서의 변경부분이다. 없는 두번째 파라메터는 query parameter가 된다.
url_for('hello_world') => /
url_for('username', username='soo') => /username/soo
url_for('username', query='soo') => /username?query=soo
- HTTP method에 대한 처리
@app.route('/', methods=['GET', 'POST'])
def login():
if request.method == 'POST':
do_post_job()
else:
do_get_job()
디폴트는 GET이다.
- static 파일은 패키지에 static 디렉토리를 만들어서 거기에 넣어두면 /static으로 접근가능하다.
* static/style.css라는 파일이 있으면 아래와 같이 접근 가능
url_for('static', filename='style.css')
- flask는 Jinja2 템플릿 엔진을 사용한다. 물론 원하면 다른 엔진을 사용해도 된다.
패키지 안에 templates 디렉토리를 만들고 html 파일을 넣어둔다.
코드에서는 아래와 같이 접근 가능하다.
templates/hello.html 이 있는 경우
hello.html은 아래와 같을 것이다.
html에서의 name은 render_template에 name argument로 넘겨준 값이 사용된다.
- 클라이언트가 보낸 데이타에 대한 처리를 위해 flask는 request object를 사용한다.
- URL에서 query parameter(?key=value)에 대한 처리는 아래와 같이 한다.
request.args.get('key', '')
- 파일 업로드하기
HTML form에서 enctype="multipart/form-data"로 해주어야 함
업로드된 파일은 메모리나 임시 디렉토리에 저장되므로 save()함수를 사용하여 원하는 위치에 저장한다.
클라이언트쪽에서 사용했던 파일 이름을 알고 싶으면 f.filename을 사용하면 된다. 또는 좀 더 확실하게 알고 싶으면 secure_filename(f.filename)을 사용한다.
- Cookies
* 쿠키 읽기
request.cookies를 사용
* 쿠키 저장하기
response object의 set_cookie()함수를 사용
- redirect하고 싶으면 redirect()함수를, 바로 종료하고 싶으면 abort()함수를 사용한다.
- 에러 페이지를 커스터마이즈하고 싶으면 app.errorhandler를 사용한다.
- Response object
a. 정상적인 response object가 함수로부터 리턴하면 이것이 바로 넘어간다.
b. string이 함수로부터 리턴하면 response object를 만들고 이것의 data로 string을 넘긴다.
c. tuple을 넘길 수 있는데 다음과 같은 형태가 되어야 한다. (response, status, headers)
d. 앞의 세 종류가 아니면 리턴 값을 response object로 변환한다.
- Session
session object를 통해 값을 가져오고 저장하고를 할 수 있다. session에는 아래의 예에서 처럼 secret key가 필요하다.
- 로그가 필요하면 app.logger를 사용한다.
- 구글 앱 엔진에 flask를 사용한 앱을 올리고 싶으면 아래의 내용 참조하라.
https://github.com/kamalgill/flask-appengine-template
# hello.py
위와 같이 입력하고 command line에서 아래와 같이 입력한다.
> python hello.py
브라우저에서 http://127.0.0.1:5000에 접속하면 'Hello World!'를 볼 수 있다.
접속 URL을 컴퓨터의 ip로 바꾸고 싶으면 app.run부분을 아래와 같이 바꾸면 된다.
=> app.run(host='0.0.0.0')
디버그 모드를 키고 싶으면 아래와 같이 한다.
=> app.run(debug=True)
'/'의 요청시 hello_world() 함수가 호출되는 것은 @app.route에 의해 이루어진다.
위에서처럼 고정된 URL이 아닌 필요에 따라 변하는 URL의 경우 매칭시키고 싶으면 아래와 같이 하면 URL에서 <username> 부분이 함수의 username 파라메터로 넘어온다.
@app.route('/<username>')
def show_user_profile(username):
return 'User %s' % username
들어오는 값을 아래와 같이 변환해 줄 수도 있다.
@app.route('/<int:post_id>')
def show_post(post_id):
return 'Post %d' % post_id
변환해주는 값에는 아래의 3가지가 있다.
int : 정수로 변환
float: 실수로 변환
path: 마지막 '/'도 포함하는 path
- routing rule
* 마지막에 '/'가 있는 경우:
예) '/projects/'
'/projects'로 요청하면 flask는 '/projects/'로 redirect한다.
* 마지막에 '/'가 없는 경우:
예) '/projects'
'/projects/'로 요청하면 없는 페이지로 에러 발생
지금까지는 url을 함수로 매핑시켜주는 @app.route를 살펴봤다. 반대도 가능할까? url_for()를 사용하면 된다. 첫번째 파라메터는 함수의 이름이고 두번째부터는 URL에서의 변경부분이다. 없는 두번째 파라메터는 query parameter가 된다.
url_for('hello_world') => /
url_for('username', username='soo') => /username/soo
url_for('username', query='soo') => /username?query=soo
- HTTP method에 대한 처리
@app.route('/', methods=['GET', 'POST'])
def login():
if request.method == 'POST':
do_post_job()
else:
do_get_job()
디폴트는 GET이다.
- static 파일은 패키지에 static 디렉토리를 만들어서 거기에 넣어두면 /static으로 접근가능하다.
* static/style.css라는 파일이 있으면 아래와 같이 접근 가능
url_for('static', filename='style.css')
- flask는 Jinja2 템플릿 엔진을 사용한다. 물론 원하면 다른 엔진을 사용해도 된다.
패키지 안에 templates 디렉토리를 만들고 html 파일을 넣어둔다.
코드에서는 아래와 같이 접근 가능하다.
templates/hello.html 이 있는 경우
hello.html은 아래와 같을 것이다.
html에서의 name은 render_template에 name argument로 넘겨준 값이 사용된다.
- 클라이언트가 보낸 데이타에 대한 처리를 위해 flask는 request object를 사용한다.
- URL에서 query parameter(?key=value)에 대한 처리는 아래와 같이 한다.
request.args.get('key', '')
- 파일 업로드하기
HTML form에서 enctype="multipart/form-data"로 해주어야 함
업로드된 파일은 메모리나 임시 디렉토리에 저장되므로 save()함수를 사용하여 원하는 위치에 저장한다.
클라이언트쪽에서 사용했던 파일 이름을 알고 싶으면 f.filename을 사용하면 된다. 또는 좀 더 확실하게 알고 싶으면 secure_filename(f.filename)을 사용한다.
- Cookies
* 쿠키 읽기
request.cookies를 사용
* 쿠키 저장하기
response object의 set_cookie()함수를 사용
- redirect하고 싶으면 redirect()함수를, 바로 종료하고 싶으면 abort()함수를 사용한다.
- 에러 페이지를 커스터마이즈하고 싶으면 app.errorhandler를 사용한다.
- Response object
a. 정상적인 response object가 함수로부터 리턴하면 이것이 바로 넘어간다.
b. string이 함수로부터 리턴하면 response object를 만들고 이것의 data로 string을 넘긴다.
c. tuple을 넘길 수 있는데 다음과 같은 형태가 되어야 한다. (response, status, headers)
d. 앞의 세 종류가 아니면 리턴 값을 response object로 변환한다.
- Session
session object를 통해 값을 가져오고 저장하고를 할 수 있다. session에는 아래의 예에서 처럼 secret key가 필요하다.
- 로그가 필요하면 app.logger를 사용한다.
- 구글 앱 엔진에 flask를 사용한 앱을 올리고 싶으면 아래의 내용 참조하라.
https://github.com/kamalgill/flask-appengine-template
The Little Redis Book 요약
Chapter 1 - The Basics
a. Databases
Redis도 database의 개념을 가지고 있다. 처음에는 database 0로 시작한다. 이 database를 다른 것으로 바꾸고 싶으면 select 명령어를 사용한다. select 1을 입력하면 1번 database로 옮겨갈 것이다. 돌아가고 싶으면 select 0를 입력하면 된다.
b. Commands, Keys and Values
Redis를 잘 사용하려면 key와 value의 개념을 파악하고 있는 것이 중요하다. key는 data를 구별해주는 것이고 value는 key와 관련있는 실제 data이다. Redis는 value를 byte array로 다루기 때문에 value가 어떤 값이던지 상관하지 않는다.
아래의 명령어를 입력해보자.
> set users:leto "{name: leto, planet: dune, likes: [spice]}"
user:leto를 key로, 2번째 파라메터를 value로 저장하라는 명령어이다. key에서의 ':'는 Redis의 입장에서는 아무런 의미도 없다. 우리가 봤을 때 leto라는 이름의 user라는 것을 짐작할 수 있게 해주는 key일 뿐이다. value를 가져오는 명령어는 아래와 같다.
> get user:leto
c. Querying
key로 value를 찾을 수 있지만 value를 가지고 무언가를 할 수는 없다. value를 가지고 문언가를 하는 것(예: dune이라는 planet에 살고 있는 유저 찾기)은 Redis의 용도가 아니다.
d. Memory and Persistence
Redis는 in-memory persistent store이다. 기본적으로 Redis는 적당한 수 이상으로 key가 변할 때(예: key가 9번보다 적게 변하면 15분마다 disk에 저장하기) disk에 database를 복제한다. 또는 append mode로 동작하여 key가 변할 때마다 append-only file에 업데이트를 할 수도 있다.
e. Putting It Together
query limitation과 data structure와 memory에 data 저장하기 때문에 Redis는 무척이나 빠르다. 따라서 DB를 쓸 때 db에 접속량을 줄이기 위해 고민하는 것 같은 것을 할 필요가 없다.
Redis는 만능이 아니다. 필요한 용도에 적합하게 사용해야 한다.
Chapter 2 - The Data Structures
a. Strings
위에서 String을 저장하는 set를 살펴봤다. 다른 명령어들도 있다.
> strlen users:leto
> getrange users:leto 27 40
> append users:leto " OVER 9000!!"
strlen은 key의 value의 길이(length)를 가져오고 getrange는 value의 지정한 영역(range)을 가져온다. append는 기존의 value에 새 value를 더한다. 물론 지금 설명한 명령어들은 string의 경우에 의미가 있을 것이다.
> incr stats:page:about
> incr stats:page:about
> incrby ratings:video:12333 5
> incrby ratings:video:12333 3
incr은 value의 값을 1 증가시키고 decr은 1 감소시킨다. incrby는 지정한 수만큼 증가시키고 decrby는 지정한 수만큼 감소시킨다. users:leto에 incr을 적용하면 에러가 발생할 것이다. 각자 setbit과 getbit도 한번 살펴보자.
b. Hashes
key와 value 사이에 field라는 것을 두어 field를 가지고 value를 처리한다.
> hset users:goku powerlevel 9000
> hget users:goku powerlevel
hset은 key로 field와 value를 설정한다. hget으로 key에서의 field의 value를 얻어온다.
>hmset users:goku race saiyan age 737
>hmget users:goku race powerlevel
>hgetall users:goku
>hkeys users:goku
>hdel users:goku age
hmset은 한번에 여러 field를 설정할 수 있도록 해주고 hmget은 한번에 여러 field를 가져올 수 있게 해준다. hgetall은 한번에 모든 field와 이의 value를 가져오고, hkeys는 모든 field를 list로 보여준다. hdel은 지정한 field를 지운다.
이처럼 hash를 통해 좀 더 세밀한 처리를 할 수 있게 된다.
c. Lists
List는 주어진 key로 value의 배열을 처리할 수 있게 해준다.
> lpush newusers goku
>ltrim newusers 0 50
lpush는 value를 list에 더하고 ltrim은 range 사이의 value만을 유지하게 한다. ltrim은 O(N) operation을 가지는 명령어(여기서 N은 제거하는 value의 수이다.)이기 때문에 위의 두 명령어를 항상 같이 실행 함으로서 O(1)로 유지할 수 있게 된다.
d. Sets
중복되지 않는 value를 저장하고 이와 관련한 명령어들을 제공한다.
> sadd friends:leto ghanima paul chani jessica
> sadd friends:duncan paul jessica alia
> sismember friends:leto jessica
> sismember friends:leto vladimir
value가 key의 멤버인지 아닌지 알려주는 sismember는 O(1) operation이므로 매우 효율적이다.
> sinter friends:leto friends:duncan
> sinterstore friends:leto_duncan friends:leto friends:duncan
sinter는 두 key가 같이 가지고 있는 value를 알려준다. sinterstore는 sinter의 결과를 바로 새 key에 저장한다.
중복되는 value가 없는 집합에서 value의 특정한 집합을 찾거나 지정하는데 Set은 유용하다.
e. Sorted Sets
score를 가지는 set이라 할 수 있다.
> zadd friends:duncan 70 ghanima 95 paul 95 chani 75 jessica 1 vladimir
score가 90 이상인 친구를 찾고 싶으면 아래와 같이 한다.
> zcount friends:duncan 90 100
chani의 rank를 알고 싶으면 아래와 같이 한다.
> zrevrank friends:duncan chani
Chapter 3 - Leveraging Data Structures
a. Big O Notation
다수의 Redis 명령어는 O(1)이다. zadd는 O(log(N))이다. ltrim은 O(N)이지만 N이 전체 item의 수가 아니라 제거할 아이템의 수이므로 앞에서 설명했듯이 사용하면 O(1)이 된다. zremrangebyscore는 O(log(N) + M)이다.(N은 set할 element의 수이고 M은 제거할 element의 수이다.) sort는 O(N + M*log(M))이다. 이러한 내용을 인지하고 가능한 한 느린 명령어를 사용하지 않는 방향으로 해야 한다.
b. Pseudo Multi Key Queries
email과 id로 유저의 정보를 찾기 위해 아래처럼 저장하는 것은 좋지 않다.
> set users:leto@dune.gov "{id: 9001, email: 'leto@dune.gov', ... }"
> set users:9001 "{id: 9001, email: 'leto@dune.gov', ... }"
hash를 사용하면 중복을 제거할 수 있다.
> set users:9001 "{id: 9001, email: 'leto@dune.gov', ... }"
> hset user:lookup:email leto@dune.gov 9001
c. References and Indexes
앞에서 한 value가 다른 value를 reference하는 것을 봤다. 만약에 reference하고 있는 것이 바뀌면 어떻하지? Redis는 이에 대한 간편한 해결책이 없다. 수동으로 관리를 해야한다.
> sadd friends:leto ghanima paul chani jessica
> sadd friends_of:chani leto paul
d. Round Trips and Pipelining
Redis는 mget이나 sadd 같은 여러 value를 한번에 전달하는 명령어를 통해 round trip를 줄일 수 있게 해준다.
보통은 클라이언트가 한 명령을 Redis에 보내고 나면 reply를 기다린다. 하지만, Redis는 여러 명령을 먼저 보내고 나중에 response를 받는 pipelining을 지원한다. Ruby같은 경우 pipelined 함수를 통해 pipelining을 할 수 있다.
e. Transactions
여러 명령어를 atomic하게 동작시키고 싶을 때가 있다. 아래와 같이 한다.
> multi
> hincrby groups:1percent balance -9000000000
> hincrby groups:99percent balance 9000000000
> exec
지정한 key를 watch하고 있다가 그 key가 변하면 transaction을 할 수 있다. 그냥 multi와 exec만을 쓰면 모든 명령어가 한번에 실행되 버리기 때문에 이와 같은 상황에 쓸 수 없다.
redis.watch('powerlevel')
current = redis.get('powerlevel')
redis.multi()
redis.set('powerlevel', current + 1)
redis.exec()
f. Keys Anti-Pattern
keys 명령어는 pattern을 인식한다. 하지만, 이 명령어는 매우 느리다.
> keys bug:1233:*
따라서 위처럼 1233에 관련된 value를 찾고 싶은 경우 위처럼 해서 모든 key를 뒤지게 하는 것보다는 아예 처음에 저장할 때 아래처럼 하는 것이 좋은 선택이다.
> hset bugs:1233 1 "{id:1, account:1233, subject: '...'}"
> hset bugs:1233 2 "{id:1, account:1233, subject: '...'}"
Chapter 4 - Beyond The Data Structures
a. Expiration
key에 expiration을 지정할 수 있다. expire할 앞으로의 시간(second)이나 날짜(timestamp since Jan 1, 1970)를 준다.
> expire pages:about 30
> expire pages:about 1356933600
첫번째는 30초 후 key를 지우고 두번째는 2012년 12월 31일 아침 12시에 key를 지운다. ttl은 남아있는 시간을 알려주고 persist는 expiration을 제거한다. setex는 value를 set하면서 바로 expiration time도 지정한다.
> setex pages:about 30 '<h1>about us</h1>'
b. Publication and Subscriptions
> subscribe warnings
> publish warnings "it's over 9000!"
subscribe를 통해 channel에 가입하고 publish를 통해 channel에 메시지를 보낼 수 있다.
c. Monitor and Slow Log
monitor 명령어를 통해 Redis에 전달되는 모든 명령어를 모니터할 수 있다. slowlog 명령어를 통해 지정한 시간 이상이 걸리는 명령어를 log할 수 있다.
모든 명령어를 log하려면 아래와 같이 한다.
> config set slowlog-log-slower-than 0
아래의 모든 log를 보고 최근 10개의 log만 보고 log의 개수를 보는 명령이다.
> slowlog get
> slowlog get 10
> slowlog len
d. Sort
list, set or sorted set을 sort한다.
> rpush users:leto:guesses 5 9 10 2 4 10 19 2
> sort users:leto:guesses
> sadd friends:ghanima leto paul chani jessica alia duncan
> sort friends:ghanima limit 0 3 desc alpha
위의 명령은 descending order로 lexicographically 소트한 후 지정한 위치의 element를 리턴하는 명령이다.
> sadd watch:leto 12339 1382 338 9338
> set severity:12339 3
> set severity:1382 2
> set severity:338 5
> set severity:9338 4
> sort watch:leto by severity:* desc
위의 명령에서 *은 pattern에 의해 watch:leto의 value로 치환 되고 이 친환된 key의 value에 따라 sort가 된다.
Chapter 5 - Lua Scripting
a. Why?
전형적인 stored procedure를 쓰는 것이나 Lua script를 쓰는 것이나 편하지 않은 것은 똑같다. 하지만 Lua script를 잘 쓰면 성능을 향상 시킬 수 있고 코드도 간단해진다.
b. Eval
eval 명령어는 Lua script를 string으로 하는 파라메터를 받는다.
c. Script Management
eval로 실행되는 script를 매번 보내는 것은 좋은 선택이 아니다. Redis는 script를 cache하는 script load 명령을 제공한다.
redis = Redis.new
script_key = redis.script(:load, "THE_SCRIPT") // script의 sha1 digest를 리턴
redis.evalsha(script_key, ['friends:leto'], ['m'])
아래와 같은 명령어도 있다.
script kill - 실행중인 script 중단시키기
script flush - cache되어 있는 모든 script 제거하기
script exists - script가 cache에 이미 있는지 확인하기
d. Libraries
다양한 유용한 라이브러리들이 있다. table.lib, string.lib, math.ib, cjson.lib등이 있다.
e. Atomic
Redis는 single-threaded이므로 Lua script는 중간에 인터럽트 되지 않는다.
f. Administration
lua-time-limit 명령으로 Lua script가 얼마나 오래 실행될 수 있는지를 지정할 수 있다. 기본은 5초이고 보통의 Lua script는 milisecond 단위로 실행되기 때문에 이것은 꽤 긴 시간이다.
Chapter 6 - Administration
a. Configuration
redis.conf 파일을 통해 설정을 지정할 수 있다.
> config get *log*
위의 명령으로 모든 log가 들어가는 명령을 확인 할 수 있다.
b. Authentication
redis.conf 파일에 requirepass 명령으로 password를 지정할 수 있다. 이 값이 지정되면 클라이언트는 auth password 명령으로 인증해야 한다.
심각한 위험을 초래할 수 있는 명령어는 rename 할 수도 있다.
> rename-command CONFIG 5ec4db16...
> rename-command FLUSHALL 10412850...
c. Size Limitations
Redis는 수십억개의 data를 저장할 수 있다.
d. Replication
master에 data를 저장하면 하나 이상의 slave에 master의 내용을 up-to-date 한다. slave로 띄우려면 configuration 파일에 slaveof를 지정하거나 slaveof 명령을 사용한다.
Redis는 automated failover를 지원하지 않는다.
e. Backups
기본적으로 Redis는 dump.rdb라는 파일에 snapshot을 저장한다. snapshot을 뜨거나 append-only file에 저장하는 것을 하지 않고 slave에 저장하는 것을 선택할 수도 있다. 이것은 master에 부하를 줄여주는 장점이 있다.
f. Scaling and Redis Cluster
몇몇의 명령어들은 부하가 심할 수 있으므로 slave를 통한 replication은 부하를 줄여 줄 수 있다. key들을 여러 Redis instance에 분산 배치하는 것도 좋은 방법이다(consistent-hashing algorithm).
Redis Cluster는 현재 작업중에 있다.
a. Databases
Redis도 database의 개념을 가지고 있다. 처음에는 database 0로 시작한다. 이 database를 다른 것으로 바꾸고 싶으면 select 명령어를 사용한다. select 1을 입력하면 1번 database로 옮겨갈 것이다. 돌아가고 싶으면 select 0를 입력하면 된다.
b. Commands, Keys and Values
Redis를 잘 사용하려면 key와 value의 개념을 파악하고 있는 것이 중요하다. key는 data를 구별해주는 것이고 value는 key와 관련있는 실제 data이다. Redis는 value를 byte array로 다루기 때문에 value가 어떤 값이던지 상관하지 않는다.
아래의 명령어를 입력해보자.
> set users:leto "{name: leto, planet: dune, likes: [spice]}"
user:leto를 key로, 2번째 파라메터를 value로 저장하라는 명령어이다. key에서의 ':'는 Redis의 입장에서는 아무런 의미도 없다. 우리가 봤을 때 leto라는 이름의 user라는 것을 짐작할 수 있게 해주는 key일 뿐이다. value를 가져오는 명령어는 아래와 같다.
> get user:leto
c. Querying
key로 value를 찾을 수 있지만 value를 가지고 무언가를 할 수는 없다. value를 가지고 문언가를 하는 것(예: dune이라는 planet에 살고 있는 유저 찾기)은 Redis의 용도가 아니다.
d. Memory and Persistence
Redis는 in-memory persistent store이다. 기본적으로 Redis는 적당한 수 이상으로 key가 변할 때(예: key가 9번보다 적게 변하면 15분마다 disk에 저장하기) disk에 database를 복제한다. 또는 append mode로 동작하여 key가 변할 때마다 append-only file에 업데이트를 할 수도 있다.
e. Putting It Together
query limitation과 data structure와 memory에 data 저장하기 때문에 Redis는 무척이나 빠르다. 따라서 DB를 쓸 때 db에 접속량을 줄이기 위해 고민하는 것 같은 것을 할 필요가 없다.
Redis는 만능이 아니다. 필요한 용도에 적합하게 사용해야 한다.
Chapter 2 - The Data Structures
a. Strings
위에서 String을 저장하는 set를 살펴봤다. 다른 명령어들도 있다.
> strlen users:leto
> getrange users:leto 27 40
> append users:leto " OVER 9000!!"
strlen은 key의 value의 길이(length)를 가져오고 getrange는 value의 지정한 영역(range)을 가져온다. append는 기존의 value에 새 value를 더한다. 물론 지금 설명한 명령어들은 string의 경우에 의미가 있을 것이다.
> incr stats:page:about
> incr stats:page:about
> incrby ratings:video:12333 5
> incrby ratings:video:12333 3
incr은 value의 값을 1 증가시키고 decr은 1 감소시킨다. incrby는 지정한 수만큼 증가시키고 decrby는 지정한 수만큼 감소시킨다. users:leto에 incr을 적용하면 에러가 발생할 것이다. 각자 setbit과 getbit도 한번 살펴보자.
b. Hashes
key와 value 사이에 field라는 것을 두어 field를 가지고 value를 처리한다.
> hset users:goku powerlevel 9000
> hget users:goku powerlevel
hset은 key로 field와 value를 설정한다. hget으로 key에서의 field의 value를 얻어온다.
>hmset users:goku race saiyan age 737
>hmget users:goku race powerlevel
>hgetall users:goku
>hkeys users:goku
>hdel users:goku age
hmset은 한번에 여러 field를 설정할 수 있도록 해주고 hmget은 한번에 여러 field를 가져올 수 있게 해준다. hgetall은 한번에 모든 field와 이의 value를 가져오고, hkeys는 모든 field를 list로 보여준다. hdel은 지정한 field를 지운다.
이처럼 hash를 통해 좀 더 세밀한 처리를 할 수 있게 된다.
c. Lists
List는 주어진 key로 value의 배열을 처리할 수 있게 해준다.
> lpush newusers goku
>ltrim newusers 0 50
lpush는 value를 list에 더하고 ltrim은 range 사이의 value만을 유지하게 한다. ltrim은 O(N) operation을 가지는 명령어(여기서 N은 제거하는 value의 수이다.)이기 때문에 위의 두 명령어를 항상 같이 실행 함으로서 O(1)로 유지할 수 있게 된다.
d. Sets
중복되지 않는 value를 저장하고 이와 관련한 명령어들을 제공한다.
> sadd friends:leto ghanima paul chani jessica
> sadd friends:duncan paul jessica alia
> sismember friends:leto jessica
> sismember friends:leto vladimir
value가 key의 멤버인지 아닌지 알려주는 sismember는 O(1) operation이므로 매우 효율적이다.
> sinter friends:leto friends:duncan
> sinterstore friends:leto_duncan friends:leto friends:duncan
sinter는 두 key가 같이 가지고 있는 value를 알려준다. sinterstore는 sinter의 결과를 바로 새 key에 저장한다.
중복되는 value가 없는 집합에서 value의 특정한 집합을 찾거나 지정하는데 Set은 유용하다.
e. Sorted Sets
score를 가지는 set이라 할 수 있다.
> zadd friends:duncan 70 ghanima 95 paul 95 chani 75 jessica 1 vladimir
score가 90 이상인 친구를 찾고 싶으면 아래와 같이 한다.
> zcount friends:duncan 90 100
chani의 rank를 알고 싶으면 아래와 같이 한다.
> zrevrank friends:duncan chani
Chapter 3 - Leveraging Data Structures
a. Big O Notation
다수의 Redis 명령어는 O(1)이다. zadd는 O(log(N))이다. ltrim은 O(N)이지만 N이 전체 item의 수가 아니라 제거할 아이템의 수이므로 앞에서 설명했듯이 사용하면 O(1)이 된다. zremrangebyscore는 O(log(N) + M)이다.(N은 set할 element의 수이고 M은 제거할 element의 수이다.) sort는 O(N + M*log(M))이다. 이러한 내용을 인지하고 가능한 한 느린 명령어를 사용하지 않는 방향으로 해야 한다.
b. Pseudo Multi Key Queries
email과 id로 유저의 정보를 찾기 위해 아래처럼 저장하는 것은 좋지 않다.
> set users:leto@dune.gov "{id: 9001, email: 'leto@dune.gov', ... }"
> set users:9001 "{id: 9001, email: 'leto@dune.gov', ... }"
hash를 사용하면 중복을 제거할 수 있다.
> set users:9001 "{id: 9001, email: 'leto@dune.gov', ... }"
> hset user:lookup:email leto@dune.gov 9001
c. References and Indexes
앞에서 한 value가 다른 value를 reference하는 것을 봤다. 만약에 reference하고 있는 것이 바뀌면 어떻하지? Redis는 이에 대한 간편한 해결책이 없다. 수동으로 관리를 해야한다.
> sadd friends:leto ghanima paul chani jessica
> sadd friends_of:chani leto paul
d. Round Trips and Pipelining
Redis는 mget이나 sadd 같은 여러 value를 한번에 전달하는 명령어를 통해 round trip를 줄일 수 있게 해준다.
보통은 클라이언트가 한 명령을 Redis에 보내고 나면 reply를 기다린다. 하지만, Redis는 여러 명령을 먼저 보내고 나중에 response를 받는 pipelining을 지원한다. Ruby같은 경우 pipelined 함수를 통해 pipelining을 할 수 있다.
e. Transactions
여러 명령어를 atomic하게 동작시키고 싶을 때가 있다. 아래와 같이 한다.
> multi
> hincrby groups:1percent balance -9000000000
> hincrby groups:99percent balance 9000000000
> exec
지정한 key를 watch하고 있다가 그 key가 변하면 transaction을 할 수 있다. 그냥 multi와 exec만을 쓰면 모든 명령어가 한번에 실행되 버리기 때문에 이와 같은 상황에 쓸 수 없다.
redis.watch('powerlevel')
current = redis.get('powerlevel')
redis.multi()
redis.set('powerlevel', current + 1)
redis.exec()
f. Keys Anti-Pattern
keys 명령어는 pattern을 인식한다. 하지만, 이 명령어는 매우 느리다.
> keys bug:1233:*
따라서 위처럼 1233에 관련된 value를 찾고 싶은 경우 위처럼 해서 모든 key를 뒤지게 하는 것보다는 아예 처음에 저장할 때 아래처럼 하는 것이 좋은 선택이다.
> hset bugs:1233 1 "{id:1, account:1233, subject: '...'}"
> hset bugs:1233 2 "{id:1, account:1233, subject: '...'}"
Chapter 4 - Beyond The Data Structures
a. Expiration
key에 expiration을 지정할 수 있다. expire할 앞으로의 시간(second)이나 날짜(timestamp since Jan 1, 1970)를 준다.
> expire pages:about 30
> expire pages:about 1356933600
첫번째는 30초 후 key를 지우고 두번째는 2012년 12월 31일 아침 12시에 key를 지운다. ttl은 남아있는 시간을 알려주고 persist는 expiration을 제거한다. setex는 value를 set하면서 바로 expiration time도 지정한다.
> setex pages:about 30 '<h1>about us</h1>'
b. Publication and Subscriptions
> subscribe warnings
> publish warnings "it's over 9000!"
subscribe를 통해 channel에 가입하고 publish를 통해 channel에 메시지를 보낼 수 있다.
c. Monitor and Slow Log
monitor 명령어를 통해 Redis에 전달되는 모든 명령어를 모니터할 수 있다. slowlog 명령어를 통해 지정한 시간 이상이 걸리는 명령어를 log할 수 있다.
모든 명령어를 log하려면 아래와 같이 한다.
> config set slowlog-log-slower-than 0
아래의 모든 log를 보고 최근 10개의 log만 보고 log의 개수를 보는 명령이다.
> slowlog get
> slowlog get 10
> slowlog len
d. Sort
list, set or sorted set을 sort한다.
> rpush users:leto:guesses 5 9 10 2 4 10 19 2
> sort users:leto:guesses
> sadd friends:ghanima leto paul chani jessica alia duncan
> sort friends:ghanima limit 0 3 desc alpha
위의 명령은 descending order로 lexicographically 소트한 후 지정한 위치의 element를 리턴하는 명령이다.
> sadd watch:leto 12339 1382 338 9338
> set severity:12339 3
> set severity:1382 2
> set severity:338 5
> set severity:9338 4
> sort watch:leto by severity:* desc
위의 명령에서 *은 pattern에 의해 watch:leto의 value로 치환 되고 이 친환된 key의 value에 따라 sort가 된다.
Chapter 5 - Lua Scripting
a. Why?
전형적인 stored procedure를 쓰는 것이나 Lua script를 쓰는 것이나 편하지 않은 것은 똑같다. 하지만 Lua script를 잘 쓰면 성능을 향상 시킬 수 있고 코드도 간단해진다.
b. Eval
eval 명령어는 Lua script를 string으로 하는 파라메터를 받는다.
c. Script Management
eval로 실행되는 script를 매번 보내는 것은 좋은 선택이 아니다. Redis는 script를 cache하는 script load 명령을 제공한다.
redis = Redis.new
script_key = redis.script(:load, "THE_SCRIPT") // script의 sha1 digest를 리턴
redis.evalsha(script_key, ['friends:leto'], ['m'])
아래와 같은 명령어도 있다.
script kill - 실행중인 script 중단시키기
script flush - cache되어 있는 모든 script 제거하기
script exists - script가 cache에 이미 있는지 확인하기
d. Libraries
다양한 유용한 라이브러리들이 있다. table.lib, string.lib, math.ib, cjson.lib등이 있다.
e. Atomic
Redis는 single-threaded이므로 Lua script는 중간에 인터럽트 되지 않는다.
f. Administration
lua-time-limit 명령으로 Lua script가 얼마나 오래 실행될 수 있는지를 지정할 수 있다. 기본은 5초이고 보통의 Lua script는 milisecond 단위로 실행되기 때문에 이것은 꽤 긴 시간이다.
Chapter 6 - Administration
a. Configuration
redis.conf 파일을 통해 설정을 지정할 수 있다.
> config get *log*
위의 명령으로 모든 log가 들어가는 명령을 확인 할 수 있다.
b. Authentication
redis.conf 파일에 requirepass 명령으로 password를 지정할 수 있다. 이 값이 지정되면 클라이언트는 auth password 명령으로 인증해야 한다.
심각한 위험을 초래할 수 있는 명령어는 rename 할 수도 있다.
> rename-command CONFIG 5ec4db16...
> rename-command FLUSHALL 10412850...
c. Size Limitations
Redis는 수십억개의 data를 저장할 수 있다.
d. Replication
master에 data를 저장하면 하나 이상의 slave에 master의 내용을 up-to-date 한다. slave로 띄우려면 configuration 파일에 slaveof를 지정하거나 slaveof 명령을 사용한다.
Redis는 automated failover를 지원하지 않는다.
e. Backups
기본적으로 Redis는 dump.rdb라는 파일에 snapshot을 저장한다. snapshot을 뜨거나 append-only file에 저장하는 것을 하지 않고 slave에 저장하는 것을 선택할 수도 있다. 이것은 master에 부하를 줄여주는 장점이 있다.
f. Scaling and Redis Cluster
몇몇의 명령어들은 부하가 심할 수 있으므로 slave를 통한 replication은 부하를 줄여 줄 수 있다. key들을 여러 Redis instance에 분산 배치하는 것도 좋은 방법이다(consistent-hashing algorithm).
Redis Cluster는 현재 작업중에 있다.
Redis command 분석 - 2
* INCR key
Time complexity O(1)
key에 저장된 value의 값을 1 증가시킨다.
- incrCommand in t_string.c
a. incrDecrCommand(c, 1);
b. 정수값의 경우 shared.integers[value]로 미리 만들어 놓은 object를 value로 사용
* DECR key
Time complexity O(1)
key에 저장된 value의 값을 1 감소시킨다.
- decrCommand in t_string.c
a. incrDecrCommand(c, -1);
* MGET key [key ...]
Time complexity O(N)
key에 맞는 값을 찾아서 리턴. 없으면 nil을 리턴. 다수의 key를 설정하므로 multi bulk리턴
* RPUSH key value [value ...]
Time complexity O(1)
기존에 저장된 value의 끝(tail)에 value를 추가. 기존에 저장된 value가 list가 아니면 에러 리턴. key가 없으면 ziplist를 새로 만듦.
ZIPLIST와 LINKEDLIST에 사용 가능
* LPUSH key value [value ...]
Time complexity O(1)
기존에 저장된 value의 처음(head)에 value를 추가. 기존에 저장된 value가 list가 아니면 에러 리턴. key가 없으면 ziplist를 새로 만듦.
ZIPLIST와 LINKEDLIST에 사용 가능
* RPUSHX key value
Time complexity O(1)
key가 있고 list인 경우에만 끝에 value를 추가.
* LPUSHX key value
Time complexity O(1)
key가 있고 list인 경우에만 처음에 value를 추가.
* LINSERT key BEFORE|AFTER pivot value
Time complexity O(N)
value를 pivot의 이전(BEFORE)이나 뒤(AFTER)에 추가.
pivot의 encoding값이 REDIS_ENCODING_RAW이어야 함. 기존에 저장된 value들이 ZIPLIST이고 새로 저장할 value의 크기가 list_max_ziplist_value를 넘으면 LINKEDLIST로 컨버전. pivot은 앞에서부터 뒤로 loop를 돌며 찾는다.
저장한 후 value가 ZIPLIST이고 리스트의 크기가 list_max_ziplist_entries보다 크면 LINKEDLIST로 컨버전한다.
* RPOP key
Time complexity O(1)
list에서 마지막 값을 제거한다.
* LPOP key
Time complexity O(1)
list에서 처음 값을 제거한다.
* BRPOP key [key ...] timeout
Time complexity O(1)
처음으로 비어있지 않은 list의 마지막 값을 제거한다.
주어진 모든 key가 비어 있으면 timeout만큼 block된다. 하지만, MULTI/EXEC안에서 이 명령어가 실행된 것이면 바로 "*-1\r\n"을 리턴한다.
block은 리턴을 하지 않아 버리는 것이다. 그럼으로서 client는 무한정 기다리게 된다. 서버는 serverCron에서 확인하여 지정한 timeout이 지나고 나면 리턴을 한다.
* BRPOPLPUSH source destination timeout
Time complexity O(1)
* BLPOP key [key ...] timeout
Time complexity O(1)
처음으로 비어있지 않은 list의 처음 값을 제거한다.
주어진 모든 key가 비어 있으면 timeout만큼 block된다. 하지만, MULTI/EXEC안에서 이 명령어가 실행된 것이면 바로 "*-1\r\n"을 리턴한다.
Time complexity O(1)
key에 저장된 value의 값을 1 증가시킨다.
- incrCommand in t_string.c
a. incrDecrCommand(c, 1);
b. 정수값의 경우 shared.integers[value]로 미리 만들어 놓은 object를 value로 사용
* DECR key
Time complexity O(1)
key에 저장된 value의 값을 1 감소시킨다.
- decrCommand in t_string.c
a. incrDecrCommand(c, -1);
* MGET key [key ...]
Time complexity O(N)
key에 맞는 값을 찾아서 리턴. 없으면 nil을 리턴. 다수의 key를 설정하므로 multi bulk리턴
* RPUSH key value [value ...]
Time complexity O(1)
기존에 저장된 value의 끝(tail)에 value를 추가. 기존에 저장된 value가 list가 아니면 에러 리턴. key가 없으면 ziplist를 새로 만듦.
ZIPLIST와 LINKEDLIST에 사용 가능
* LPUSH key value [value ...]
Time complexity O(1)
기존에 저장된 value의 처음(head)에 value를 추가. 기존에 저장된 value가 list가 아니면 에러 리턴. key가 없으면 ziplist를 새로 만듦.
ZIPLIST와 LINKEDLIST에 사용 가능
* RPUSHX key value
Time complexity O(1)
key가 있고 list인 경우에만 끝에 value를 추가.
* LPUSHX key value
Time complexity O(1)
key가 있고 list인 경우에만 처음에 value를 추가.
* LINSERT key BEFORE|AFTER pivot value
Time complexity O(N)
value를 pivot의 이전(BEFORE)이나 뒤(AFTER)에 추가.
pivot의 encoding값이 REDIS_ENCODING_RAW이어야 함. 기존에 저장된 value들이 ZIPLIST이고 새로 저장할 value의 크기가 list_max_ziplist_value를 넘으면 LINKEDLIST로 컨버전. pivot은 앞에서부터 뒤로 loop를 돌며 찾는다.
저장한 후 value가 ZIPLIST이고 리스트의 크기가 list_max_ziplist_entries보다 크면 LINKEDLIST로 컨버전한다.
* RPOP key
Time complexity O(1)
list에서 마지막 값을 제거한다.
* LPOP key
Time complexity O(1)
list에서 처음 값을 제거한다.
* BRPOP key [key ...] timeout
Time complexity O(1)
처음으로 비어있지 않은 list의 마지막 값을 제거한다.
주어진 모든 key가 비어 있으면 timeout만큼 block된다. 하지만, MULTI/EXEC안에서 이 명령어가 실행된 것이면 바로 "*-1\r\n"을 리턴한다.
block은 리턴을 하지 않아 버리는 것이다. 그럼으로서 client는 무한정 기다리게 된다. 서버는 serverCron에서 확인하여 지정한 timeout이 지나고 나면 리턴을 한다.
* BRPOPLPUSH source destination timeout
Time complexity O(1)
* BLPOP key [key ...] timeout
Time complexity O(1)
처음으로 비어있지 않은 list의 처음 값을 제거한다.
주어진 모든 key가 비어 있으면 timeout만큼 block된다. 하지만, MULTI/EXEC안에서 이 명령어가 실행된 것이면 바로 "*-1\r\n"을 리턴한다.
Redis command 분석 - 1
* GET key
Time complexity: O(1)
key의 값(value) 얻어오기. key가 없으면 nil을 리턴
GET은 string만을 다루기 때문에 key의 값이 string이 아니면 에러가 리턴됨
- getCommand in t_string.c
a. db로부터 key를 찾는다.
b. key가 있으면 access time을 업데이트
c. key가 없으면 "$-1\r\n"을 client에 보낸다.
d. 찾은 key의 type이 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에 보낸다.
e. 리턴할 value의 크기를 prefix로 해주고(예: "$2344\r\n") 뒤에 value를 붙인 후 client에게 보낸다.(예: value가 Hello인 경우 - "$5\r\nHello\r\n")
- value의 크기가 32보다 작은 경우는 자주 사용되므로 미리 shared.bulkhdr[]에 보낼 값을 만들어 놓고 사용함
shared.bulkhdr[j] = createObject(REDIS_STRING, sdscatprintf(sdsempty(), "$%d\r\n", j));
* SET key value
Time complexity: O(1)
string인 value를 key로 하여 저장. key가 이미 있으면 그 값의 타입이 무었인지에 상관없이 덮어쓴다.
- setCommand in t_string.c
a. 공간 절약을 위해 string이 숫자이면 숫자로 변환한다.
b. db에 key/value를 무조건 설정한다.(없으면 add, 있으면 overwrite)
c. expire가 설정되어 있으면 delete
d. 이 key를 watch하고 있는 client가 있으면 이 client의 flags값에 REDIS_DIRTY_CAS를 더함으로서 그 client에서의 exec가 실패하도록 해준다.
e. 항상 "+OK\r\n"을 client에게 보낸다.(set은 실패하지 않음)
* SETNX key value
Time complexity: O(1)
key가 없을 경우만 key/value를 저장한다.
- setnxCommand in t_string.c
a. key가 없을 경우는 SET과 같다.
b. key가 있을 경우 ":0\\r\n"을 key가 없을 경우는 ":1\r\n"을 client에게 보낸다.
* SETEX key seconds value
Time complexity: O(1)
주어진 시간에 timeout하는 key/value 저장
아래의 두 명령을 MULTI/EXEC block 안에서 실행하는 것과 같은 명령
SET key value
EXPIRE key seconds
- setexCommand in t_string.c
위의 SET 명령어에 더하여 expire에 관련된 부분만 추가해줌
a. seconds를 milliseconds로 바꾼다.
b. db의 expires로부터 key를 찾는다.(없으면 추가)
c. key의 value를 milliseconds로 바꾸어준다.
* PSETEX key milliseconds value
Time complexity: O(1)
expire time을 millisecond로 설정한다는 것만 제외하고는 setex와 같은 명령어
* APPEND key value
Time complexity: O(1)
key가 이미 있고 string이라면 string의 끝에 value를 더한다. 없으면 key를 만들어서 value를 넣는다.
- appendCommand in t_string.c
a. key를 찾는다.
b. 없으면 key를 만들어 value를 저장한다.
c. key가 있으면 type을 확인하여 type이 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에게 보낸다.
d. append할 경우 string의 size가 512MB를 넘으면 "string exceeds maximum allowed size (512MB)"를 client에게 보낸다.
e. object가 shared이거나 encoded이면 value를 copy한 후 key의 value에 덮어쓴다.
f. key의 value가 바뀌었으므로 watch하고 있는 client에 signal을 날린다.
* STRLEN key
Time complexity: O(1)
key에 저장된 value의 size를 리턴한다. key가 string이 아니면 에러를 리턴한다.
- strlenCommand in t_string.c
a. key가 없으면 ":0\r\n"을 client에게 보낸다.
b. key가 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에게 보낸다.
c. value의 크기를 client에게 보낸다.
* DEL key [key ...]
Time complexity: O(1)
지정한 키를 지운다. key가 없으면 무시한다.
- delCommand in db.c
a. argument로 지정한 key들을 지운다.
b. 지정한 key를 watch하고 있는 client에게 알린다.
c. 지운 key의 수를 client에게 보낸다.
* EXISTS key
Time complexity: O(1)
key가 존재하는지 확인한다.
- existsCommand in db.c
a. key가 존재하는지 확인한다.
b. 있으면 ":1\r\n"을 client에게 보낸다.
c. 없으면 ":0\r\n"을 client에게 보낸다.
* SETBIT key offset value
Time complexity: O(1)
key에 저장된 value의 offset위치의 bit를 set(1) 또는 clear(0)한다.
- setbitCommand in bitops.c
a. offset의 값을 가져온다. 512MB이하여야 한다. 아닐경우 "-ERR bit offset is not an integer or out of range\r\n"를 리턴한다.
b. value의 값을 가져온다. LONG_MIN과 LONG_MAX사이여야 한다. 아닐 경우 "-ERR bit is not an integer or out of range\r\n"를 client에게 보낸다.
c. offset이 0이나 1이 아니면 "-ERR bit is not an integer or out of range\r\n"를 client에게 보낸다.
d. key를 찾는다.
e. key가 없으면 empty string을 새로 만든다.
f. key가 있으면 type이 string인지 확인한다. 그리고 나서 key가 shared 또는 encoded이면 copy를 하여 기존의 다른 값이 변하지 않도록 한다.
g. string의 크기가 offset만큼 크지 않으면 offset 설정이 가능하도록 string의 크기를 증가시킨다. 이때 추가되는 부분의 bit값은 0으로 한다.
h. offset 부분의 값을 value로 바꾼다.(key의 값이 바뀌므로 watch중인 client에 signal을 보낸다.)
i. 값을 바꾼 bit의 원래 값을 client에게 보낸다.
* GETBIT key offset
Time complexity: O(1)
key에 저장된 value의 offset 위치의 값을 리턴한다.
- getbitCommand in bitops.c
a. offset 값이 정상적인지 확인한다.
b. key가 없으면 ":0\r\n"을 client에게 보낸다. type이 string이 아니면 에러를 리턴한다.
c. key가 있으면 offset 위치의 값을 client에게 보낸다.(":1\\r\n" or ":0\r\n")
d. offset의 위치가 key의 string 크기를 벗어나면 0으로 가정하고 값을 리턴한다.
* SETRANGE key offset value
Time complexity: O(1)
string의 부분을 변경한다.
- setrangeCommand in t_string.c
a. offset값을 가져온다. 값이 0보다 작으면 "-ERR offset is out of range\r\n"을 client에게 보낸다.
b. key를 찾는다.
c. key가 없는 경우 다음의 순서로 진행한다.
c-1. value의 크기가 0이면 ":0\r\n"을 client에게 보낸다.
c-2. offset + value의 크기가 최대 크기를 넘으면 에러를 리턴한다.
c-3. key에 빈 스트링을 넣는다.
d. key가 있는 경우
d-1. key의 타입이 string인지 확인한다.
d-2. value의 크기가 0이면 저장되어 있는 key의 value의 크기를 리턴한다.
d-3. offset + value의 크기가 최대 크기를 넘으면 에러를 리턴한다.
d-4. object가 shared이거나 encoded이면 object를 복사한다.
e. value의 크기가 0보다 크면 key의 value의 offset위치의 값을 변경한다. 이때 offset위치가 저장되어 있는 value의 크기보다 크면 0(zero byte)을 붙여서 값 변경이 가능하도록 해준다.
f. 변경된 value의 크기를 리턴한다.
* GETRANGE key start end
Time complexity: O(N)
string의 지정한 부분의 값을 가져온다. 음수의 start와 end는 뒤에서 부터를 의미한다. 이전 버전에서는 SUBSTR이었다.(코드에 남아있으므로 사용은 가능하다.)
- getrangeCommand in t_string.c
a. key가 없으면 "$0\r\n\r\n"를 리턴한다.
b. start가 음수인 경우 뒤에서 부터 value에서의 실제 위치를 계산했을 때 value의 0 index보다 더 작게 가면 0으로 설정한다.
c. end가 음수인 경우 뒤에서 부터 value에서의 실제 위치를 계산했을 때 value의 0 index보다 작으면 0으로 설정한다.
d. end가 value의 크기보다 크면 값을 value의 크기로 조정한다.
c. end보다 start가 더 크면 "$0\r\n\r\n"를 리턴한다.
Time complexity: O(1)
key의 값(value) 얻어오기. key가 없으면 nil을 리턴
GET은 string만을 다루기 때문에 key의 값이 string이 아니면 에러가 리턴됨
- getCommand in t_string.c
a. db로부터 key를 찾는다.
b. key가 있으면 access time을 업데이트
c. key가 없으면 "$-1\r\n"을 client에 보낸다.
d. 찾은 key의 type이 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에 보낸다.
e. 리턴할 value의 크기를 prefix로 해주고(예: "$2344\r\n") 뒤에 value를 붙인 후 client에게 보낸다.(예: value가 Hello인 경우 - "$5\r\nHello\r\n")
- value의 크기가 32보다 작은 경우는 자주 사용되므로 미리 shared.bulkhdr[]에 보낼 값을 만들어 놓고 사용함
shared.bulkhdr[j] = createObject(REDIS_STRING, sdscatprintf(sdsempty(), "$%d\r\n", j));
* SET key value
Time complexity: O(1)
string인 value를 key로 하여 저장. key가 이미 있으면 그 값의 타입이 무었인지에 상관없이 덮어쓴다.
- setCommand in t_string.c
a. 공간 절약을 위해 string이 숫자이면 숫자로 변환한다.
b. db에 key/value를 무조건 설정한다.(없으면 add, 있으면 overwrite)
c. expire가 설정되어 있으면 delete
d. 이 key를 watch하고 있는 client가 있으면 이 client의 flags값에 REDIS_DIRTY_CAS를 더함으로서 그 client에서의 exec가 실패하도록 해준다.
e. 항상 "+OK\r\n"을 client에게 보낸다.(set은 실패하지 않음)
* SETNX key value
Time complexity: O(1)
key가 없을 경우만 key/value를 저장한다.
- setnxCommand in t_string.c
a. key가 없을 경우는 SET과 같다.
b. key가 있을 경우 ":0\\r\n"을 key가 없을 경우는 ":1\r\n"을 client에게 보낸다.
* SETEX key seconds value
Time complexity: O(1)
주어진 시간에 timeout하는 key/value 저장
아래의 두 명령을 MULTI/EXEC block 안에서 실행하는 것과 같은 명령
SET key value
EXPIRE key seconds
- setexCommand in t_string.c
위의 SET 명령어에 더하여 expire에 관련된 부분만 추가해줌
a. seconds를 milliseconds로 바꾼다.
b. db의 expires로부터 key를 찾는다.(없으면 추가)
c. key의 value를 milliseconds로 바꾸어준다.
* PSETEX key milliseconds value
Time complexity: O(1)
expire time을 millisecond로 설정한다는 것만 제외하고는 setex와 같은 명령어
* APPEND key value
Time complexity: O(1)
key가 이미 있고 string이라면 string의 끝에 value를 더한다. 없으면 key를 만들어서 value를 넣는다.
- appendCommand in t_string.c
a. key를 찾는다.
b. 없으면 key를 만들어 value를 저장한다.
c. key가 있으면 type을 확인하여 type이 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에게 보낸다.
d. append할 경우 string의 size가 512MB를 넘으면 "string exceeds maximum allowed size (512MB)"를 client에게 보낸다.
e. object가 shared이거나 encoded이면 value를 copy한 후 key의 value에 덮어쓴다.
f. key의 value가 바뀌었으므로 watch하고 있는 client에 signal을 날린다.
* STRLEN key
Time complexity: O(1)
key에 저장된 value의 size를 리턴한다. key가 string이 아니면 에러를 리턴한다.
- strlenCommand in t_string.c
a. key가 없으면 ":0\r\n"을 client에게 보낸다.
b. key가 string이 아니면 "-ERR Operation against a key holding the wrong kind of value\r\n"을 client에게 보낸다.
c. value의 크기를 client에게 보낸다.
* DEL key [key ...]
Time complexity: O(1)
지정한 키를 지운다. key가 없으면 무시한다.
- delCommand in db.c
a. argument로 지정한 key들을 지운다.
b. 지정한 key를 watch하고 있는 client에게 알린다.
c. 지운 key의 수를 client에게 보낸다.
* EXISTS key
Time complexity: O(1)
key가 존재하는지 확인한다.
- existsCommand in db.c
a. key가 존재하는지 확인한다.
b. 있으면 ":1\r\n"을 client에게 보낸다.
c. 없으면 ":0\r\n"을 client에게 보낸다.
* SETBIT key offset value
Time complexity: O(1)
key에 저장된 value의 offset위치의 bit를 set(1) 또는 clear(0)한다.
- setbitCommand in bitops.c
a. offset의 값을 가져온다. 512MB이하여야 한다. 아닐경우 "-ERR bit offset is not an integer or out of range\r\n"를 리턴한다.
b. value의 값을 가져온다. LONG_MIN과 LONG_MAX사이여야 한다. 아닐 경우 "-ERR bit is not an integer or out of range\r\n"를 client에게 보낸다.
c. offset이 0이나 1이 아니면 "-ERR bit is not an integer or out of range\r\n"를 client에게 보낸다.
d. key를 찾는다.
e. key가 없으면 empty string을 새로 만든다.
f. key가 있으면 type이 string인지 확인한다. 그리고 나서 key가 shared 또는 encoded이면 copy를 하여 기존의 다른 값이 변하지 않도록 한다.
g. string의 크기가 offset만큼 크지 않으면 offset 설정이 가능하도록 string의 크기를 증가시킨다. 이때 추가되는 부분의 bit값은 0으로 한다.
h. offset 부분의 값을 value로 바꾼다.(key의 값이 바뀌므로 watch중인 client에 signal을 보낸다.)
i. 값을 바꾼 bit의 원래 값을 client에게 보낸다.
* GETBIT key offset
Time complexity: O(1)
key에 저장된 value의 offset 위치의 값을 리턴한다.
- getbitCommand in bitops.c
a. offset 값이 정상적인지 확인한다.
b. key가 없으면 ":0\r\n"을 client에게 보낸다. type이 string이 아니면 에러를 리턴한다.
c. key가 있으면 offset 위치의 값을 client에게 보낸다.(":1\\r\n" or ":0\r\n")
d. offset의 위치가 key의 string 크기를 벗어나면 0으로 가정하고 값을 리턴한다.
* SETRANGE key offset value
Time complexity: O(1)
string의 부분을 변경한다.
- setrangeCommand in t_string.c
a. offset값을 가져온다. 값이 0보다 작으면 "-ERR offset is out of range\r\n"을 client에게 보낸다.
b. key를 찾는다.
c. key가 없는 경우 다음의 순서로 진행한다.
c-1. value의 크기가 0이면 ":0\r\n"을 client에게 보낸다.
c-2. offset + value의 크기가 최대 크기를 넘으면 에러를 리턴한다.
c-3. key에 빈 스트링을 넣는다.
d. key가 있는 경우
d-1. key의 타입이 string인지 확인한다.
d-2. value의 크기가 0이면 저장되어 있는 key의 value의 크기를 리턴한다.
d-3. offset + value의 크기가 최대 크기를 넘으면 에러를 리턴한다.
d-4. object가 shared이거나 encoded이면 object를 복사한다.
e. value의 크기가 0보다 크면 key의 value의 offset위치의 값을 변경한다. 이때 offset위치가 저장되어 있는 value의 크기보다 크면 0(zero byte)을 붙여서 값 변경이 가능하도록 해준다.
f. 변경된 value의 크기를 리턴한다.
* GETRANGE key start end
Time complexity: O(N)
string의 지정한 부분의 값을 가져온다. 음수의 start와 end는 뒤에서 부터를 의미한다. 이전 버전에서는 SUBSTR이었다.(코드에 남아있으므로 사용은 가능하다.)
- getrangeCommand in t_string.c
a. key가 없으면 "$0\r\n\r\n"를 리턴한다.
b. start가 음수인 경우 뒤에서 부터 value에서의 실제 위치를 계산했을 때 value의 0 index보다 더 작게 가면 0으로 설정한다.
c. end가 음수인 경우 뒤에서 부터 value에서의 실제 위치를 계산했을 때 value의 0 index보다 작으면 0으로 설정한다.
d. end가 value의 크기보다 크면 값을 value의 크기로 조정한다.
c. end보다 start가 더 크면 "$0\r\n\r\n"를 리턴한다.
기억해 두면 좋은 Git 명령어
1. Git 설정
$ git config --global user.name "John Doe"
$ git config --global user.email john@gmail.com
선호하는 에디터가 있으면 아래도 해준다.
$ git config --global core.editor vi
- 도움말 보기
$ git help <verb>
2. 기본 명령어
- Git 저장소 만들기
$ git init
- 저장소 clone하기
$ git clone git://github.com/schacon/grit.git
- 저장소에 파일 추가하기
$ git add *.c
- 저장소에 commit하기
$ git commit -m "initial commit"
- 파일의 상태 확인하기
$ git status
- 무시하고 싶은 파일은 .gitignore에 적어준다. 표준 Glob 패턴 입력이 가능하다.
- 변경 내용 확인하기(수정한 파일과 staged된것의 내용 비교)
$ git diff
- 변경 내용 확인하기(staged된것과 저장소의 내용 비교)
$ git diff --cached
or
$ git diff --staged
- 파일 삭제하기
$ git rm test.txt
- 파일 삭제시 파일이 변경된 상태라면 git rm이 되지 않는다. 그러므로 위의 명령에 -f를 주거나 rm 후 git rm을 해야 한다.
- 파일을 실제로 지우지는 않고 저장소에서만 제거하고 싶으면
$ git rm --cached readme.txt
- 파일 이름 변경하기
$ git mv README.txt README
or
$ mv README.txt README
$ git rm RADME.txt
$ git add README
- 히스토리 조회하기
$ git log
- staged 상태인 것 되돌리기
$ git reset HEAD readme.txt
- 수정한 파일을 수정이전 버전으로 되돌리기
$ git checkout -- readme.txt
- 현재 프로젝트에 등록된 리모트 저장소 확인
$ git remote -v
- 새 리모트 저장소 추가
$ git remote add [단축이름] [url]
- 리모트 저장소와 연결된 추적 브랜치 만들기
$ git checkout -b [로컬 브랜치 이름] [리모트 저장소 이름]:[리모트 브랜치 이름]
- 리모트 저장소에서 데이터 가져오기
$ git fetch [remote-name]
- 리모트 저장소에서 데이터 가져와서 머지까지 하기
$ git pull [remote-name]
- 파일을 리모트 저장소에 올리기
$ git push [리모트 저장소 이름] [브랜치 이름]
브랜치 이름이 로컬과 리모트가 다른 경우
$ git push [리모트 저장소 이름] [로컬 브랜치 이름]:[리모트 브랜치 이름]
- 리모트 브랜치 삭제하기
$ git push [리모트 저장소 이름] :[리모트 브랜치 이름]
- 리모트 저장소의 구체적인 정보 확인하기
$ git remote show origin
- 리모트 저장소의 이름 바꾸기
$ git remote rename pb paul => pb를 paul로 바꾼다.
- 리모트 저장소 삭제하기
$ git remote rm paul
- tag 조회하기
$ git tag
- 간단한 tag 만들기(lightweight tag)
$ git tag v1.4
- 자세한 tag 만들기(annotated tag)
$ git tag -a v1.4 -m 'my version 1.4'
- tag 정보 확인하기
$ git show v1.4
- 예전 커밋에 tag 넣기
$ git tag -a v1.2 9fceb02 => 커밋 체크섬 일부를 마지막에 넣어줌
- tag를 리모트 서버에 전송하기
$ git push origin v1.4
- 여러개의 tag를 한번에 보내기
$ git push origin --tags
- 브랜치 목록 보기
$ git branch
- 브랜치 만들기(만들기만 하고 이동하지는 않음)
$ git branch testing
- 브랜치 이동하기
$ git checkout testing
- 머지된 브랜치 삭제하기
$ git branch -d testing
- 머지가 안된 브랜치 강제로 삭제하기(조심해서 사용하자)
$ git branch -D testing
- 브랜치 머지하기
$ git merge master => master의 내용을 현재 브랜치로 머지함
- 현재 checkout한 브랜치 기준으로 머지정보 확인하기
$ git branch --merged
$ git branch --no-merged
- rebase 하기
$ git rebase master
- server 브랜치를 master 브랜치로 rebase 하기
$ git branch master server
$ git config --global user.name "John Doe"
$ git config --global user.email john@gmail.com
선호하는 에디터가 있으면 아래도 해준다.
$ git config --global core.editor vi
- 도움말 보기
$ git help <verb>
2. 기본 명령어
- Git 저장소 만들기
$ git init
- 저장소 clone하기
$ git clone git://github.com/schacon/grit.git
- 저장소에 파일 추가하기
$ git add *.c
- 저장소에 commit하기
$ git commit -m "initial commit"
- 파일의 상태 확인하기
$ git status
- 무시하고 싶은 파일은 .gitignore에 적어준다. 표준 Glob 패턴 입력이 가능하다.
- 변경 내용 확인하기(수정한 파일과 staged된것의 내용 비교)
$ git diff
- 변경 내용 확인하기(staged된것과 저장소의 내용 비교)
$ git diff --cached
or
$ git diff --staged
- 파일 삭제하기
$ git rm test.txt
- 파일 삭제시 파일이 변경된 상태라면 git rm이 되지 않는다. 그러므로 위의 명령에 -f를 주거나 rm 후 git rm을 해야 한다.
- 파일을 실제로 지우지는 않고 저장소에서만 제거하고 싶으면
$ git rm --cached readme.txt
- 파일 이름 변경하기
$ git mv README.txt README
or
$ mv README.txt README
$ git rm RADME.txt
$ git add README
- 히스토리 조회하기
$ git log
- staged 상태인 것 되돌리기
$ git reset HEAD readme.txt
- 수정한 파일을 수정이전 버전으로 되돌리기
$ git checkout -- readme.txt
- 현재 프로젝트에 등록된 리모트 저장소 확인
$ git remote -v
- 새 리모트 저장소 추가
$ git remote add [단축이름] [url]
- 리모트 저장소와 연결된 추적 브랜치 만들기
$ git checkout -b [로컬 브랜치 이름] [리모트 저장소 이름]:[리모트 브랜치 이름]
- 리모트 저장소에서 데이터 가져오기
$ git fetch [remote-name]
- 리모트 저장소에서 데이터 가져와서 머지까지 하기
$ git pull [remote-name]
- 파일을 리모트 저장소에 올리기
$ git push [리모트 저장소 이름] [브랜치 이름]
브랜치 이름이 로컬과 리모트가 다른 경우
$ git push [리모트 저장소 이름] [로컬 브랜치 이름]:[리모트 브랜치 이름]
- 리모트 브랜치 삭제하기
$ git push [리모트 저장소 이름] :[리모트 브랜치 이름]
- 리모트 저장소의 구체적인 정보 확인하기
$ git remote show origin
- 리모트 저장소의 이름 바꾸기
$ git remote rename pb paul => pb를 paul로 바꾼다.
- 리모트 저장소 삭제하기
$ git remote rm paul
- tag 조회하기
$ git tag
- 간단한 tag 만들기(lightweight tag)
$ git tag v1.4
- 자세한 tag 만들기(annotated tag)
$ git tag -a v1.4 -m 'my version 1.4'
- tag 정보 확인하기
$ git show v1.4
- 예전 커밋에 tag 넣기
$ git tag -a v1.2 9fceb02 => 커밋 체크섬 일부를 마지막에 넣어줌
- tag를 리모트 서버에 전송하기
$ git push origin v1.4
- 여러개의 tag를 한번에 보내기
$ git push origin --tags
- 브랜치 목록 보기
$ git branch
- 브랜치 만들기(만들기만 하고 이동하지는 않음)
$ git branch testing
- 브랜치 이동하기
$ git checkout testing
- 머지된 브랜치 삭제하기
$ git branch -d testing
- 머지가 안된 브랜치 강제로 삭제하기(조심해서 사용하자)
$ git branch -D testing
- 브랜치 머지하기
$ git merge master => master의 내용을 현재 브랜치로 머지함
- 현재 checkout한 브랜치 기준으로 머지정보 확인하기
$ git branch --merged
$ git branch --no-merged
- rebase 하기
$ git rebase master
- server 브랜치를 master 브랜치로 rebase 하기
$ git branch master server
피드 구독하기:
글 (Atom)