Distributed System - 5. Naming

1. Names, identifiers and addresses

- Name : entity를 가리키는 bit나 char의 나열

- Entity : Name이 붙을 수 있는 모든 것

=> Entity에 접근하기 위해서는 Access Point(AP)를 통해야하며, 이 AP도 역시 entity이다.

- Address : AP의 Name

- Naming system : 어떻게 각 Entity의 name을 결정할 것이며 이러한 name을 가지고 어떻게 해당 entity까지 접근할지, 그리고 그 name 들을 어떻게 관리, 유지할지를 결정할지를 정하는 것이다.

 

- Identifiers(ID)란?

1. Pure name : 이름에 아무런 의미가 없는 형태.

2. Identifier : entity와 1대1 매칭이 되며, 재사용 불가, 각 entity는 오직 하나의 ID 만을 지닌다.

=> 이러한 Identifier를 구성하고 이를 이용해 검색을 하는 방법(Naming)에는 Flat, Structed, Attribute based Naming 이 있다.

---

2. Flat Naming

- Flat Naming은 random bit를 ID로 부여한다. 

- Flat Naming entity search protocol : Broadcasting, Home-based approaches, DHT, hierarchical approaches

- Flat Naming에서 특정 ID의 entity를 찾는 방법 중 하나는 Broadcasting 이다. 즉, WAN 단위에서는 쓸 수가 없다.

- 해당 검색 프로토콜의 예시로는 ARP가 있다.

- Flat Naming의 검색 방법 중 또 하나로는 Forwarding pointer 방법이 있다.

=> Forwarding Pointer : entity가 이동했을 시, 기존 위치에 자신의 다음 위치 주소를 남긴다. (부재 시 어디로 오세요 와 같은 형태) 그러나 잦은 entity migration이 발생 시, pointer가 너무 많이 남아 Long chain이 되고 Fault에 취약해지게 된다.

또한, Pointer를 추적하는 Dereferencing 과정이 Latency를 상승시킨다.

 

=> 이러한 Forwarding Pointer의 Long chain Fault sensitivity, Latency 단점을 해소하기 위해 Home-based approaches 라는 방법이 제시된다. Single-tiered 구조로 Home에서 모든 Care of Address(CA)를 관리하는 것이다. 

=> Home-based approaches의 단점 

1. HA가 지속적으로 CA를 관리하고 Tracking 해야하므로 부담이 생긴다. 

2. HA는 fix되어 있다. 실제로 CA entity와 Client가 바로 옆에 있어도 HA까지 다녀와야 통신을 할 수 있다.

(Geographical Scalability 감소)

3. 만약 enitity가 permanent migration을 해서 더 이상 움직이지 않아도 계속 HA는 CA를 관리해야한다.

- Home-based approaches

1. Home Address(HA)를 통해 Host home에 접근한다.

2. Host는 현재 찾으려는 entity의 CA를 반환하고, 해당 entity한테도 이 사실을 알린다.

3. Client와 CA entity가 통신을 시작한다.

- Distributed Hash Tables (DHT) : 앞서 다룬 Chord의 경우이다.

1. 많은 노드들을 logical ring으로 표현한다. 

2. 각 노드는 m-bit의 식별자를 가지며 m개의 shortcut을 지닌다.

3. 각 노드는 id>=k 인 data의 정보를 가진다.

-> 이러한 구조에서 Linear Search O(N)보다 효율적인 방법을 찾자.

# Chord finger tables

=> 각 node p의 finger table은 이러한 공식으로 link를 가진다. (1<=i<=m 인 자연수)

=> 검색을 할 때는 data key k를 넘지 않는 최대의 successor로 요청을 보낸다.

(단, k가 자신의 id보다 크면서 자신의 Finger Table[1]보다는 작으면 1로 보낸다.

=> node 4의 FT는 4+2^0, 4+2^1, 4+2^2...4+2^4 로 4,6,8,12,20이 될 것이고, 해당 노드들의 successor가 shortcut link를 가진다. (9, 14, 20)

=> 만약, key 26 item을 node1에서 찾고자 하면, node 1 에서는 26을 넘지 않는 가장 큰 node인 18로 request를 보낸다. 이후 18은 26을 넘지 않는 가장 큰 노드인 21로 보내고, 21은 26이 자신 보다 크고, FT[1]보다는 작으므로 FT[1]인 28로 보낸다. 이후 검색이 끝난다.

=> 보면, 결국 shortcut link는 최대치에서 1/2 씩 해가며 link를 지니는 것이다. 따라서 Linear Search O(N)에 비해 O(log N)의 시간 복잡도를 지녀 효율적이다. (FT 관리의 부담은 생긴다.)

 

- Hierarchical approaches : 이름은 Flat하게 짓지만, 실제 Structure의 연결은 계층적으로 구성하는 접근이다. (예시로는 DNS 가 있다.)

=> 제일 상위 노드는 하위 노드의 정보를 알게 된다. 예를 들어 S 대학교 컴퓨터 공학과 XXX 를 Search request를 보내면, 한국 전국의 대학교를 알고 있는 node까지 올라간다. 이 후 해당 node는 S 대학교 node로 request를 relay하고 S 대학교 노드는 컴퓨터 공학과 node로 relay, 컴퓨터 공학과 node는 XXX를 찾아 반환한다.

=> 각 노드는 아래 노드의 Pointer 정보를 알고 있다.

=> 또한 Replication된 정보가 여러 노드에 존재 가능하며 이 경우 M은 양 쪽 중 어디든 선택 가능하다.

=> HLS : Insert Opt.

1. 특정 node가 어떤 Group에 Insert request가 오면 상위 노드로 최대 root 까지 Insert 요청이 올라간다. 

그러나 만약 중복되어 새로 들어온 node 값을 이미 아는 노드(M)이 있을 경우, M 쪽에서 더 이상의 forwarding은 이루어지지 않는다.

2. 이후 해당 leaf node까지 Pointer chain이 생긴다. (leaf는 address를 저장, intermediate, root node는 pointer를 저장.

---

3. Structured Naming

 

Naming System의 또 다른 방식으로는 Structured가 있다. 이는 각 노드의 이름에 의미를 담는 방법이다.

Structured naming을 사용하는 Name Space는 Graph 형태로 표현이 가능하다.

Name Space는 Tree의 형태로 표현이 가능하다. 또한 각 leaf node는 Entity를 가리키고, 중간 노드인 Directory node는 각 leaf node로 향하는 edge를 레퍼런스한다.

Directory node에는 (Node ID, Edge label) 로 구성되는 쌍이 저장되게 된다. Root로부터 출발하여 각 edge label을 이어붙이는 방식으로 노드의 이름이 정해진다. (Ex : node 7은 /home/steem/mbox edge를 접근하여 검색 가능하다.)

후에 Attributed-based naming system에서 다루게 되겠지만, Directory node는 attribute 또한 저장할 수 있다.

 

=> 그렇다면 name을 resolve하기 위해 어떤 root node(초기 노드)부터 시작해야할지 알 수 있을까? 예를 들어 /home/steem/mbox만 가지고는 n0에 접근할 수 없다. 이를 해결하기 위한 방법으로는 추측하는 방법이 있다. name의 context를 확인하는 것이다.

예를 들면 www.distributed-systems.net의 형식의 name  search query가 들어오면 DNS name server로부터 시작하면 되고, /home/maarten/mbox와 같은 검색이 들어오면 local NFS file server부터 시작하면 된다.

 

* Name linking

Naming graph를 통해 Name을 특정 노드에 연결하는 방식이다. 이는 2가지 주요 방식이 있다.

1. Hard link : 이름을 특정 경로를 따라 지정된 노드까지 직접 연결한다.

=> 경로 기반으로 이름이 특정 노드에 고정되며, 경로를 따라가야지만 목적지에 도달할 수있다.

2. Soft link : 특정 노드가 다른 노드의 이름을 포함하게 한다. 

=> 노드 N의 이름을 해석하여 N으로 이동하고, N의 content를 읽어 해당 노드의 이름을 가져온다, 이후 name resolution을 이어간다.

=> Symbolic link의 기본 개념이다. n6에서 n5로의 soft link가 있다.

 

* Mounting

Name resolution은 Mounting을 통해 서로 다른 name space를 연결할 수 있다.

1. Foreign name space : 연결되는 name space

2. Mount point : Foreign name space로 향하는 node id를 가지고 있는 현 name space의 노드

3. Mounting point : Foreign name space와의 연결점.

=> Mount point의 content에는 해당 노드의 id도 있지만, 그 Foreign name space가 사용하는 access protocol, server name 도 포함하므로 protocol/server name/mounting point name 순으로 들어가게 된다.

nfs 프로토콜로 flits.cs.vu.nl 서버로 접속해 /home/steen 부터 name resolution을 이어간다.

* Name-space implementation

- name resolution 과정과 name space management를 여러 노드로 분산 시켜 Name space를 구현할 수 있다.

이 때, name space의 노드들을 3 가지 계층으로 관리하게 된다.

1. Global level : 최상위 directory nodes, 네트워크 전체의 name space 구조를 정의, 여러 관리 조직이 공동 관리해아한다. (DNS 등)

2. Administrational level : 중간 수준의 directory nodes, 각 그룹이 독립적인 관리 조직에 할당될 수 있다.

3. Managerial level : 낮은 수준의 directory nodes, 단일 조직에서 관리하며 Directory node를 local name server에 매핑하는 것이 주요 과제이다.

=> Global 할 수록 노드의 코스트가 올라가므로 수가 적고 백업(복제)본이 많다. 또한 Client 쪽에서 Caching을 해주어야한다. (계속 조회하면 비용이 높다.)

 

* Iterative name resolution

각 노드에 개별 방문해서 쿼리를 날리고 답변을 받고 답변이 온 쪽으로 다시 쿼리를 날리는 것을 반복하는 name resolution 방식. 각 쿼리의 답변 메시지는 자신의 한단계 자식 노드의 이름이 된다.

 

* Recursive name resolution

Root name server에 한번 접근하면 하위 서버로 재귀적으로 쿼리를 날려 한번에 최종 이름을 받아오는 방식이다. 상위 서버는 하위 서버에 답변이 오면 해당 경로를 캐싱해두어 다음 쿼리 코스트를 낮춘다.

* Scalability issues

- Size scalability : high-level server일 수록 많은 수의 request를 처리할 수 있어야한다.

=> Global, Administrational level에서의 노드는 거의 변경되지 않는다고 가정 시, 노드를 여러 서버에 복제하여 가장 가까운 서버에 name resolution 처리를 시작하도록 만들어 request를 분산시킨다.

- 문제 : 이동성이 있는 entity를 다룰 때는 실시간 업데이트가 잦으므로 복제에 부담이 생긴다.

 

- Geographical scalability : 거리가 멀면 멀 수록 Recursive 방식이 Iteration 방식보다 효율적이다.

(물론 한 서버가 요청을 도맡아 처리한다는 점이나 캐싱을 한다는 점에서 cost가 높아지긴 한다.)

---

5. Attribute-based naming

많은 경우 entity를 이름으로 검색하는 대신, attribute를 기반으로 이름짓고 검색하는 것이 편리하다.

엄격하게 이름으로 검색하지 않고 entity의 attribute를 기반으로 검색을 할 수 있기 때문이다.(traditional directory services) 

그러나 이렇게 포괄적인 attribute만 가지고 검색을 하게 되면 Lookup operation이 매우 비싸지게 된다.

(요청된 attribute 값을 모든 entity의 attribute 값과 비교해야함.)

=> Basic directory service를 DB에 attribute 기반으로 구현하고, 이를 structured naming system과 엮는다.

 

* Lightweight Directory Access Protocol (LDAP) - hierarchical implementation

=> 각 directory entry는 (attribute, value) 쌍을 포함하며, unique하게 이름지어진다.

=> Directory Information Base : LDAP service에서 관리하는 모든 directory entry들의 집합.

=> DIB의 모든 기록은 unique하게 이름지어지므로 조회될 수 있다.

DIT

=> Directory Information Tree : LDAP directory service의 naming graph. 각 노드는 directory entry를 가르킨다.

위의 사진과 같이 각 Directory entry가 Attribute = Value의 형태로 값을 가지고 있다면, 다음과 같이 검색이 가능해진다.

=> Leaf node (Host)들은 구분자로 Host Name을 지닌다.

 

* Distributed Index - decentralized implementation

=> Attributes set A = {a1, ... , an} 가 있다고 가정하자.

=> 각 attribute element ak 는 R이라는 set에서 value를 가지고 있다고 해보자.

=> 각 attribute ak는 Sk = {Sk1, ... , Skn} 만큼의 server를 가진다고 해보자.

=> F : F(ak,v) = Skj 라는 global mapping이 가능하다. (attribute ak 의 value 중 특정 v에 포함되는 서버들의 집합.)

=> 만약 L(ak,v)가 F(ak,v)의 리턴 set of keys 라면 해당 키들에 대해 검색을 시도할 수 있다.

- 단점 :

1. k attribute들이 있다면 k개의 server들에 접근해야한다.

2. 너무 쿼리의 폭이 포괄적이면 엄청난 양의 L이 돌아온다.

3. a = [1000,2000]과 같은 범위 쿼리에 대한 지원이 불가능하다. (분산된 서버에 저장되어있으므로 범위 내의 값을 한번에 가져올 수 없다.)

* 쉽게 설명

1. price=1500 & category = elec 으로 쿼리 입력

2. F(ak, v) 매핑으로 price가 저장되어있는 서버의 리스트, category가 저장되어있는 서버의 리스트를 받음.

3. price 서버 리스트에게는 price =1500 을 요청, category 서버 리스트에는 elec의 검색을 요청

4. 받은 최종 결과를 쿼리를 날린 client 측에서 종합 처리