Distributed System 5-3

Posted Apr 4, 2020

By Tony Kwon

27 min read

분산시스템 — Naming Part 3 (Name Space Distribution, Resolution & Attribute-based Naming)

이 문서는 Tanenbaum의 Distributed Systems를 기반으로 한 강의(슬라이드 36번부터 53번까지)를 정리한 것이다. 다루는 범위는 DNS 네임서버의 세 계층 특징에서 시작하여, name resolution의 두 방식(iterative와 recursive)과 local name server를 거쳐, 세 번째 분류인 Attribute-based naming(RDF, LDAP, DHT 기반 분산 구현과 AVTree)까지이다. 이 문서는 5장 Naming의 마지막 강의를 정리한 것이며, 두 번째 강의 정리본인 dsc_ch5_pt2.md를 잇는다.

0. 지난 시간 복습

지난 시간에는 Structured naming을 다루며 이름 자체가 계층을 이루는 네임스페이스, 경로명, 하드·심볼릭 링크, 마운트를 살펴보았고, 그 구현 예인 DNS에서 네임서버가 계층적으로 분산된다는 점과 name resolution을 iterative·recursive 두 방식으로 나눌 수 있다는 점까지 소개하였다. 이번 시간에는 그때 다음 시간으로 미뤘던 DNS 네임서버 계층별 특징과 두 resolution 방식의 세부(서버 부하, 캐싱, 통신 비용)를 마저 살펴본 뒤, 세 번째 분류인 Attribute-based naming으로 넘어가 5장 Naming을 마무리한다.

1. DNS 네임서버의 세 계층 (Global / Administrational / Managerial)

DNS는 전체 도메인 네임 공간을 계층적으로 나누어, 전 세계에 흩어진 여러 네임서버가 자신이 담당하는 부분에 대한 요청에만 응답하도록 구성한다. 이 네임서버들의 특징은 크게 세 계층으로 나누어 살펴볼 수 있다.

Global layer: 루트 네임서버와 그 바로 아래의 네임서버들로 구성된다. .com, .edu, .gov, .kr 같은 최상위 도메인이 여기에 해당한다.
Administrational layer: 한 기관(organization) 단위로 관리되는 네임서버들이다. .com 아래의 회사들이나 ac.kr, co.kr 등이 여기에 해당한다.
Managerial layer: 가장 말단의 네임서버들로, 한 기관 안의 더 작은 조직(부서 등)이 관리한다.

계층별 특징은 트리의 위치로 직관적으로 이해된다 (★)

각 계층의 특징은 트리에서 루트 쪽 노드와 말단 쪽 노드의 성질로 생각하면 거의 그대로 따라 나온다.

변화율(rate of change): 말단으로 내려갈수록 자기가 관리하는 이름을 더 자주 바꾼다. 루트 쪽의 .com, .edu 같은 도메인은 거의 바뀌지 않으며, 새 최상위 도메인을 추가하는 일은 세계적인 합의가 필요한 큰 일이다.
응답 속도: 말단으로 내려갈수록 빠르다. 매니저리얼 레이어의 서버는 자신이 관리하는 이름의 IP 주소를 직접 알고 있어 즉시 응답하지만, 루트는 자신이 직접 알지 못하고 하위 서버로 위임해야 하므로 시간이 더 걸린다.
가용성 요구(availability requirements): 루트일수록 높다. 매니저리얼 레이어의 서버는 잠깐 꺼져도 영향 범위가 좁지만, 루트 서버가 잠깐 멈추면 영향을 받는 노드가 매우 많아진다.

계층 비교 표 (Fig. 5-14)

항목	Global layer	Administrational layer	Managerial layer
지리적 스케일	전 세계	기관(organization) 단위	부서(department) 단위
네임서버 노드 수	적음	중간	많음
룩업 응답 속도	느림	중간	빠름(즉시)
업데이트 전파	느림(lazy)	비교적 빠름	즉시
레플리카 수	많음	적음	적음
클라이언트 캐싱	함(yes)	함(yes)	때때로(sometimes)

캐시는 잘 바뀌지 않는 데이터에 대해서만 의미가 있다. 저장해 둔 값이 금방 바뀌면 캐시된 값은 쓸모가 없기 때문이다. 그래서 변화가 적은 글로벌·어드미니스트레이셔널 레이어의 결과는 잘 캐시되지만, 변화가 잦은 매니저리얼 레이어의 결과는 캐시 효과가 제한적이어서 “때때로”에 그친다.

루트가 변화가 적다는 특징은 가용성·레플리카 특징과 맞물린다. 루트는 중요도가 높아 함부로 꺼서는 안 되고, 안정적으로 계속 돌아야 하며, 그래서 백업 용도로 레플리카도 많이 둔다.

2. Name Resolution — Iterative vs Recursive

구조적 이름에서 name resolution을 수행하는 방법에는 iterative와 recursive 두 가지가 있다. 실제 DNS에서는 둘이 섞여서 쓰이지만, 여기서는 이해를 위해 각 방식을 극단적으로 단순화하여 살펴본다. 단순화를 위해 네임서버는 복제되지 않았고 클라이언트 측 캐시도 없다고 가정한다. 아래에서는 Root:<nl, vu, cs, ftp, pub, globe, index.html>이라는 구조적 이름을 resolve하는 상황을 예로 든다.

Iterative resolution (반복적 방법)

클라이언트의 네임 리졸버가 전체 이름을 일단 루트 네임서버에 던진다.
루트는 자신이 아는 첫 레이블 nl만 풀어, nl 도메인을 관리하는 네임서버의 주소를 클라이언트에게 돌려준다.
클라이언트는 그 nl 서버에게 나머지 경로를 다시 질의하고, nl 서버는 vu 서버 주소를 돌려준다. 이렇게 클라이언트가 한 단계씩 직접 다음 서버에 질의하며, 질의하는 경로의 길이가 점점 짧아진다.
어느 레벨에서 나머지 전체를 아는 서버(예: 해당 zone을 통째로 관리하는 FTP 서버)를 만나면, 그 서버가 최종 주소를 돌려준다(Fig. 5-15).

Recursive resolution (재귀적 방법)

클라이언트가 전체 이름을 루트에 한 번 넘기면, 루트는 클라이언트에게 바로 돌려주지 않고 자신이 직접 nl 서버에 나머지 경로를 질의한다.
nl 서버는 다시 vu 서버에, vu 서버는 cs 서버에 연쇄적으로 질의한다. 가장 아래에서 최종 결과가 나오면, 그 결과를 역방향으로 루트까지 올려 보낸다.
마지막으로 루트가 클라이언트에게 최종 주소를 한 번에 돌려준다. 즉 클라이언트는 한 번 질의하고 결과만 받는다(Fig. 5-16).

두 방식의 Trade-off (★)

항목	Iterative	Recursive
서버 한 대의 부담	작음(다음 서버 주소만 알려주고 끝)	큼(나머지 과정을 대신 수행하고 응답을 기다림)
캐싱	클라이언트 측 리졸버에서만 가능	중간 서버들도 결과를 보므로 효과적
통신 비용	클 수 있음(클라이언트가 매번 왕복)	적을 수 있음(클라이언트는 처음·끝만 통신)

재귀적 방식은 서버 한 대가 처리할 일이 많아 더 높은 성능을 요구한다. 특히 전 세계의 요청을 받는 루트 서버가 모든 요청을 재귀적으로 처리하면 오버헤드가 막대해진다. 그래서 글로벌 레이어의 네임서버는 보통 재귀적 처리를 하지 않고, “다른 서버에게 물어보라”고 알려주는 반복적 처리만 한다. 아래 레이어에서 재귀적으로 처리하는 식으로 두 방식이 섞인다.

캐싱 측면에서 둘은 크게 갈린다. 재귀적 방식에서는 결과가 서버들 사이를 오르내리므로 중간 서버들이 그 결과를 보고 캐시해 둘 수 있다. 반면 반복적 방식에서는 서버들 사이에 상호작용이 없어 중간 서버가 결과를 보지 못하므로 캐시할 것이 없고, 캐싱은 클라이언트 측 리졸버에서만 가능하다.

통신 비용은 Fig. 5-18로 비교된다. 반복적 방식에서는 클라이언트가 멀리 있는 각 서버와 매번 왕복해야 하지만, 재귀적 방식에서는 서버들끼리 가까이서 빠르게 통신하고 클라이언트는 긴 왕복을 처음과 끝 두 번만 겪는다. 다만 이것이 절대적인 것은 아니며, 네임서버들 사이의 거리에 따라 달라질 수 있다.

Local name server

많은 조직은 모든 클라이언트가 공유하는 local name server를 따로 둔다. 이 서버가 클라이언트의 네임 리졸버 역할을 대신하며, 캐시된 데이터를 많이 가지고 있어 대부분의 요청을 캐시된 값으로 바로 응답한다. 캐시에 없으면 직접 iterative나 recursive resolution을 거쳐 결과를 받아 클라이언트에게 알려준다.

건국대 같은 기관에서 네트워크를 설정할 때 입력하는 DNS 서버 주소가 바로 이 local name server에 해당한다고 보면 된다. 이 서버가 캐시된 값을 주거나, 없으면 직접 resolution을 대행한다.

3. Attribute-based Naming (속성 기반 네이밍)

세 번째 이름 짓기 방법은 attribute-based naming이다. Flat name은 이름 안에 아무 의미가 없어 가장 다루기 어려웠고, structured name은 이름 안에 리소스를 찾아가는 경로 정보를 담았다. Attribute-based naming은 한 걸음 더 나아가, 찾으려는 리소스의 속성(attribute)을 직접 나열한 것을 이름으로 삼는다.

찾으려는 리소스의 속성을 (attribute, value) 쌍으로 표현하고, 여러 쌍을 나열하면 그 자체가 이름이 된다. 사용자는 정확한 이름 대신 자신이 찾는 것의 속성만 기술하면 된다.
한 엔티티는 여러 속성의 집합으로 표현된다고 가정한다.

Flat·Structured naming과의 대비 (★)

Structured name은 하나의 경로가 유일하게 한 엔티티로 매핑된다. 반면 attribute-based name은 공통 속성을 가진 여러 엔티티를 하나의 이름으로 한꺼번에 지칭할 수 있다.
그 대신 name resolution이 더 복잡하고 비싸다. 그 속성을 가진 엔티티가 유일하지 않을 수 있어 모두 뒤져야 하므로, exhaustive search가 필요하다.
flat name이 전혀 사람 친화적이지 않고 structured name이 부분적으로 사람 친화적이라면, attribute-based name은 더 사람 친화적으로 이름을 지을 수 있게 해 준다. 이 방식은 directory service라고도 부른다.

RDF — 속성을 기술하는 프레임워크

속성을 시스템마다 제멋대로 정의하면 찾기가 더 어려워지므로, 속성을 기술하는 공통 규칙이 필요하다. 그 예가 RDF(Resource Description Framework)이다. RDF는 리소스를 주어(subject), 술어(predicate), 목적어(object)의 triple로 기술한다. 예를 들어 (Person, name, Alice)는 “이름이 Alice인 Person”이라는 리소스를 기술한 것이다.

Structured naming이나 flat naming에서는 먼저 찾으려는 리소스의 정확한 이름을 알아야 한다. 그러나 attribute-based naming에서는 이름 자체가 속성으로 이루어지므로 속성을 다소 추상적으로 표현할 수 있어, 정확한 이름을 모르더라도 일부 속성만으로 엔티티를 찾을 수 있다.

4. LDAP — 계층적 구현

LDAP(Lightweight Directory Access Protocol)는 분산 디렉토리 서비스를 구현하는 대표적 방법으로, structured naming과 attribute-based naming을 결합한다.

LDAP의 디렉토리 서비스는 directory entry라는 레코드들로 구성되며, 이 엔트리를 여러 노드가 나누어 분산 관리한다. 디렉토리 엔트리는 DNS의 resource record(도메인 네임과 IP 주소의 쌍)에 대응한다고 보면 된다.
속성에는 값이 하나인 single-valued attribute와 값이 여럿인 multiple-valued attribute가 있다.

디렉토리 엔트리 예

속성(attribute)	값(value)
Country (C)	NL
Locality (L)	Amsterdam
Organization (O)	Vrije Universiteit
OrganizationalUnit (OU)	Comp. Sc.
CommonName (CN)	Main server
(multiple-valued) Mail_Servers	여러 메일 서버 주소
(multiple-valued) FTP_Server	FTP 서버 주소
(multiple-valued) WWW_Server	웹 서버 주소

위에서 아래로 Country → Locality → Organization → OrganizationalUnit으로 갈수록 지리적·조직적 범위가 점점 좁아진다. 즉 “네덜란드 암스테르담의 Vrije 대학 컴퓨터과학과의 메인 서버”를 속성으로 지정해 그 IP 주소를 요청하는 식이다. Mail_Servers처럼 값이 여럿인 속성은 하나의 속성이 여러 엔티티로 매핑될 수 있음을 보여 준다.

LDAP의 용어와 트리 구조

DIB(Directory Information Base): LDAP 디렉토리 서비스의 모든 디렉토리 엔트리의 집합이다.
RDN(Relative Distinguished Name): 각각의 naming attribute, 즉 위 표의 한 행 하나를 가리킨다.
Globally unique name: RDN들을 순서대로 나열한 전역 이름이다. 예를 들어 /C=NL/O=Vrije Universiteit/OU=Comp.Sc.는 DNS 이름 nl.vu.cs와 유사하다.
DIT(Directory Information Tree): globally unique name을 따라 디렉토리 엔트리들을 계층적 트리로 조직한 것으로, LDAP의 naming graph를 이룬다. 루트부터 주어진 속성을 따라 경로를 내려가면 해당 엔티티를 찾을 수 있다. exhaustive search의 비용을 줄이기 위해 이렇게 네임스페이스를 계층적으로 구성한다.

검색 — DSA, DUA, 그리고 와일드카드 질의

DSA(Directory Service Agent): DIT를 뒤지며 룩업 요청을 처리하는 서버, 즉 네임서버 역할을 하는 노드이다.
DUA(Directory User Agent): 클라이언트를 대표하며, 표준 프로토콜에 따라 DSA에 질의를 보낸다.
질의 예: search("&(C=NL)(O=Vrije Universiteit)(OU=*)(CN=Main Server)")는 “네덜란드 Vrije 대학의 모든(OU=*) 학과의 메인 서버”를 찾는다. 와일드카드 때문에 대학까지는 유일한 경로로 내려가지만 그 아래 모든 학과의 경로를 일일이 뒤져야 하므로, search cost가 커지는 대신 여러 결과를 한 번에 얻는다.

“이 대학의 모든 메인 서버를 찾아 달라”는 질의는 structured naming이나 flat naming으로는 어떻게 요청을 구성해야 할지 떠올리기 어렵다. 그 방식들은 먼저 리소스의 정확한 이름을 알아야 하기 때문이다. 속성을 추상적으로 표현할 수 있는 attribute-based naming에서는 이런 질의가 자연스럽게 가능하다. 디렉토리 서비스의 검색 비용이 일반적으로 비싼 이유 중 하나가 바로 이렇게 결과가 유일하지 않을 수 있다는 점이다.

5. 분산 Attribute-based Naming — DHT 매핑과 AVTree

LDAP는 클라이언트가 서버에 질의하는 centralized 방식이다. 같은 attribute-based naming을 서버 없이 P2P로 분산하려는 연구도 있다.

분산 시스템 아키텍처에서는 centralized 진영과 decentralized(P2P) 진영의 논쟁이 늘 있으며, 정답은 없고 적용 상황에 따라 달라진다. attribute-based naming도 이 논쟁의 예외가 아니어서 탈중앙화 구현이 시도되었다.

DHT로 분산하기

탈중앙화 구현에서는 속성과 그 정보를 여러 노드가 분산하여 가지고, DHT(Distributed Hash Table) 기법을 사용한다. 어떤 속성을 해시값으로 바꾸고, 그 해시값을 담당하는 노드를 Chord 규칙(해시값보다 크거나 같은 노드 중 가장 작은 노드가 담당)으로 찾는다. 따라서 핵심은 “찾으려는 속성”을 “해시값”으로 매핑하는 작업이며, 이를 위해 AVTree를 사용한다.

AVTree (Attribute-Value Tree)

AVTree는 속성 description을 트리로 치환한 것이다. 트리의 엣지는 attribute를 나타내고, 노드는 그 attribute의 value를 나타낸다. 루트 노드 자체는 의미가 없다. 예를 들어 “type은 book, genre는 fantasy, (book의) author는 Tolkien, title은 LOTR(Lord of the Rings)”라는 description은 다음과 같은 트리가 된다. 아래에서 화살표 앞은 엣지(attribute), 괄호 안은 노드(value)이다.

root
├─ type→ (book)
│        ├─ author→ (Tolkien)
│        └─ title→  (LOTR)
└─ genre→ (fantasy)

각 경로마다 해시값을 하나씩 부여한다. 슬라이드의 예에서는 여섯 개의 해시값이 만들어진다.

해시	경로(path)	의미
h1	hash(type-book)	타입이 book인 모든 것
h2	hash(type-book-author)	book이고 author 속성을 가진 것
h3	hash(type-book-author-Tolkien)	Tolkien이 쓴 모든 book
h4	hash(type-book-title)	book이고 title 속성을 가진 것
h5	hash(type-book-title-LOTR)	제목이 LOTR인 book
h6	hash(genre-fantasy)	장르가 fantasy인 모든 것

해시값 hi를 담당하는 노드가 그 속성에 해당하는 실제 리소스(에 대한 참조)를 보유한다. Partial query, 예를 들어 “톨킨이 쓴 모든 책”을 찾는 질의는 그 자체로 하나의 작은 AVTree(type→book→author→Tolkien)가 되며, 그 트리에서 h1·h2·h3 세 개의 해시값이 만들어진다. 이 가운데 담당 범위가 가장 좁은, 즉 가장 구체적인 h3을 골라 그 해시값을 담당하는 노드를 P2P 상에서 찾아 질의하면 된다.

같은 리소스도 여러 해시값으로 찾을 수 있지만, 상위 경로의 해시값(예: h6의 genre-fantasy)은 담당 범위가 너무 넓고 하위 경로의 해시값(예: h3의 Tolkien의 책)은 더 구체적이다. 따라서 질의는 가능한 한 구체적인 해시값을 골라 그 담당 노드에 물어보는 편이 효율적이다.

한눈에 보는 전체 구조

Structured naming (이어서)
├─ Name space distribution (DNS 네임서버를 계층적으로 분산)
│   ├─ Global layer         (전세계, 변화 적음, 가용성 중요, 레플리카 많음)
│   ├─ Administrational     (기관 단위, 캐시 yes)
│   └─ Managerial layer     (부서 단위, 응답 빠름, 캐시 sometimes)
└─ Name resolution
    ├─ Iterative   (클라이언트가 매 단계 직접 질의 / 서버 부담↓ / 캐시는 클라이언트만)
    ├─ Recursive   (서버가 연쇄 처리 / 서버 부담↑ / 캐시·통신비용 유리)
    └─ Local name server (조직 공유 리졸버, 캐시 보유)

Attribute-based naming (속성을 나열한 것이 이름)
├─ 개념        ((attribute,value) 쌍, 여러 엔티티 지칭 가능, exhaustive search)
├─ RDF         (triple: subject, predicate, object — 예: (Person, name, Alice))
├─ LDAP        (structured + attribute 결합)
│   ├─ directory entry (≈ DNS resource record), DIB / RDN / DIT
│   ├─ globally unique name (/C=NL/O=.../OU=... ≈ nl.vu.cs)
│   └─ DSA(서버) / DUA(클라이언트), 와일드카드 질의 → search cost↑
└─ 분산 구현   (DHT 매핑, AVTree로 경로별 해시 h1~h6, partial query)

KONKUK, DISTRIBUTED_SYSTEM

This post is licensed under CC BY 4.0 by the author.