지난 글에서 테이블을 네 개로 쪼갰습니다. 덕분에 갱신 이상은 사라졌지만, 학생 목록 하나를 보려면 매번 조인을 써야 하고, 학과 조교에게 다른 학과 학생까지 보여 주게 됩니다. 조인을 미리 써 둔 결과를 이름으로 부를 수 있으면 두 문제가 함께 풀립니다.

• 기본 릴레이션(base relation): 디스크에 실제로 저장된 릴레이션. 지금까지 만든 네 테이블입니다.
• 유도된 릴레이션(derived relation): 기본 릴레이션에서 질의로 끌어낸 릴레이션.

뷰(view)는 이 유도된 릴레이션에 이름을 붙인 것이고, 데이터를 따로 저장하지 않으므로 가상 릴레이션(virtual relation)이라고도 부릅니다. 저장되는 것은 결과가 아니라 질의의 정의뿐입니다.

2. 뷰 정의와 동적인 창

CREATE VIEW cse_student AS
SELECT sid, name, year
FROM   student
WHERE  dept_id = 'CSE';

SELECT * FROM cse_student WHERE year >= 3;

정의만 저장하므로, 기본 릴레이션이 바뀌면 다음에 뷰를 읽을 때 그 변화가 그대로 보입니다. 뷰를 기본 릴레이션에 대한 동적인 창(dynamic window)이라고 부르는 이유입니다. 창을 통해 보는 풍경이지 사진이 아닙니다.

사진에 해당하는 것이 스냅샷(snapshot)입니다. 특정 시점의 결과를 실제로 저장해 두므로 기본 릴레이션이 바뀌어도 따라 변하지 않고, 대신 조인이나 집계를 매번 다시 하지 않습니다. 뷰는 저장 공간을 쓰지 않는 대신 읽을 때마다 계산하고, 스냅샷은 그 반대를 택합니다.

3. 뷰로 데이터에 접근할 때 일어나는 일

뷰에 질의를 던지면 DBMS는 이렇게 처리합니다.

1. 시스템 카탈로그에서 그 이름이 뷰인지 확인하고 정의를 꺼냅니다.
2. 사용자 질의의 뷰 이름을 그 정의로 바꿔 넣습니다. 이를 뷰 확장 또는 질의 수정(query modification)이라고 합니다.
3. 합쳐진 질의를 기본 릴레이션 위에서 최적화해 실행합니다.

위 예라면 SELECT sid, name, year FROM student WHERE dept_id = 'CSE' AND year >= 3이 실제로 실행됩니다. 뷰를 거친다고 단계가 하나 늘어나는 것이 아니라, 두 조건이 합쳐진 하나의 질의가 됩니다.

4. 뷰의 장점

정규화로 테이블을 쪼개면 기존 질의가 전부 깨지는데, 쪼개기 전 모양의 뷰를 만들어 두면 응용 프로그램은 바뀐 것을 모른 채 돌아갑니다.

무결성 쪽은 예시가 필요합니다.

CREATE VIEW cse_student AS
SELECT sid, name, dept_id, year
FROM   student
WHERE  dept_id = 'CSE'
WITH CHECK OPTION;

-- 거부됩니다. 삽입 직후 이 뷰에서 보이지 않게 되기 때문입니다
INSERT INTO cse_student VALUES (1005, '정하늘', 'MTH', 1);

WITH CHECK OPTION이 없으면 이 삽입이 통과합니다. 뷰를 통해 넣었는데 뷰에서는 보이지 않는 행이 생깁니다.

5. 뷰의 갱신과 갱신 불가능한 뷰

PostgreSQL은 9.3부터 단순한 뷰를 자동으로 갱신 가능하게 처리합니다. FROM 절에 항목이 하나뿐이고, 최상위에 WITH, DISTINCT, GROUP BY, HAVING, LIMIT, OFFSET이 없으며, 선택 목록에 집단 함수나 윈도우 함수가 없어야 한다는 조건입니다. 이를 벗어나면 읽기 전용이 되고, 그래도 갱신하고 싶으면 INSTEAD OF 트리거로 어느 테이블을 어떻게 고칠지 직접 정해 줘야 합니다. SQL Server도 복잡한 뷰는 INSTEAD OF 트리거로 처리합니다.

6. 시스템 카탈로그

DBMS는 테이블, 열, 인덱스, 뷰, 제약조건, 사용자 권한 같은 정보를 어딘가에 적어 둬야 합니다. 그 저장소가 시스템 카탈로그(system catalog), 또는 데이터 사전(data dictionary)입니다. 여기 담긴 데이터는 데이터에 관한 데이터라서 메타데이터(metadata)라고 부릅니다.

흥미로운 점은 카탈로그 자체가 릴레이션으로 되어 있어서 평소 쓰던 SELECT로 조회된다는 것입니다.

-- 표준 SQL (세 DBMS 모두 지원)
SELECT table_name FROM information_schema.tables;

-- SQL Server
SELECT name FROM sys.objects WHERE type = 'V';     -- 뷰 목록

-- PostgreSQL
SELECT relname FROM pg_class WHERE relkind = 'v';

7. 질의 처리와 통계 정보

카탈로그는 질의 처리의 모든 단계에서 읽힙니다. 테이블과 열이 존재하는지, 타입이 맞는지, 권한이 있는지, 뷰 확장에 쓸 정의가 무엇인지를 전부 여기서 확인합니다.

그중에서도 옵티마이저가 쓰는 것이 통계 정보입니다. 릴레이션의 행 수와 블록 수, 각 열의 서로 다른 값의 개수, 값의 분포 히스토그램, 널 비율, 인덱스의 단계 수 같은 것들이 저장됩니다. PostgreSQL은 pg_statistic에 담고 pg_stats 뷰로 읽기 좋게 보여 주며, SQL Server는 sys.stats로 노출합니다.

8. 카탈로그는 직접 갱신하지 않습니다

사용자가 카탈로그를 UPDATE로 고칠 수는 없습니다. SQL Server는 시스템 카탈로그에 대한 임의 갱신을 막고, 카탈로그 뷰 자체가 갱신 불가능한 뷰입니다. PostgreSQL은 카탈로그가 일반 테이블이라 기술적으로는 손댈 수 있지만, 직접 고치면 시스템을 망가뜨릴 수 있으니 하지 말라고 문서가 명시합니다.

갱신은 DDL을 통해 간접적으로 일어납니다. CREATE TABLE을 실행하면 DBMS가 카탈로그에 행을 넣고, CREATE INDEX를 실행하면 인덱스 정보가 추가됩니다. 사용자는 결과를 바꾸는 명령을 내리고, 카탈로그는 그 결과로 바뀝니다.

지금까지 본 계층들은 전부 소프트웨어였습니다. 커널 안에서 돌았습니다. link 계층은 다릅니다. 대부분 adaptor, 즉 네트워크 인터페이스 카드(NIC) 안에 하드웨어로 들어 있습니다.

경계가 여기서 갈립니다. 드라이버까지는 소프트웨어, 프레임을 만들어 전선에 밀어 넣는 일은 칩이 합니다. 충돌을 감지하고 물러나는 판단도 CPU가 아니라 이 칩이 내립니다. 마이크로초 단위로 반응해야 해서 소프트웨어에 맡길 수 없습니다.

2. 풀어야 할 문제

링크가 점대점이면 고민할 게 없습니다. 선 하나에 둘뿐이니 아무 때나 보내면 됩니다.

broadcast 링크는 다릅니다. 매체 하나를 여럿이 공유합니다. 둘이 동시에 보내면 신호가 겹쳐 둘 다 망가집니다. 이것이 collision(충돌)이고, 아무도 쓸 수 없게 된 시간만 남습니다.

그래서 "누가 언제 보낼지" 정하는 규칙이 필요합니다. MAC 프로토콜(Medium Access Control, 매체 접근 제어)이 그 규칙입니다. 중재자를 따로 둘 수 없고 참여자들끼리 정해야 한다는 점이 어렵습니다.

3. 세 가지 접근

circuit switching 대 packet switching과 같은 긴장 관계입니다. 미리 나눠두면 안정적이지만 놀고, 그때그때 쓰면 효율적이지만 충돌합니다. 이더넷은 여기서도 후자를 택했습니다.

taking turns도 짚고 갑니다. 토큰이라는 짧은 특수 프레임을 노드들이 고리 모양으로 돌리고, 토큰을 쥔 노드만 보냅니다. 충돌이 원천적으로 없고 붐빌 때 성능이 안정적입니다. 대신 한가할 때도 토큰이 돌아오기를 기다려야 하고, 토큰을 쥔 노드가 죽으면 전체가 멈춥니다. 이 취약성 때문에 밀려났습니다.

4. CSMA와 충돌이 생기는 틈

random access의 개선안은 사람의 대화와 같습니다. 보내기 전에 먼저 들어봅니다. 이것이 CSMA(Carrier Sense Multiple Access, 반송파 감지 다중 접속)입니다. 비어 있으면 보내고 누가 쓰고 있으면 기다립니다.

들어보고 보내도 충돌이 납니다. 원인은 propagation delay입니다.

t=0    A가 채널을 듣는다 → 비어 있다 → 전송 시작
t=1    A의 신호가 아직 B에 도착하지 않았다
       B가 채널을 듣는다 → 비어 있다 → 전송 시작
t=2    두 신호가 겹친다

거리가 멀수록 이 틈이 커집니다. 듣는 행위와 신호가 퍼지는 속도 사이의 시차는 없앨 수 없습니다.

5. CSMA/CD와 binary exponential backoff

다음 개선은 충돌을 감지하면 즉시 멈추는 것입니다. 끝까지 보내봐야 깨진 프레임이니 채널만 낭비합니다. CD(Collision Detection)를 붙인 CSMA/CD가 고전 이더넷의 방식입니다.

1. adaptor가 프레임을 들고 채널을 듣습니다.
2. 비어 있으면 보내고, 쓰고 있으면 빌 때까지 기다립니다.
3. 보내는 동안에도 계속 듣습니다. 끝까지 아무 일 없으면 성공입니다.
4. 충돌을 감지하면 즉시 멈추고, 잼 신호를 짧게 쏴서 다른 노드들도 알게 합니다.
5. 무작위 시간만큼 기다렸다 2번으로 돌아갑니다.

5번이 관건입니다. 고정된 시간으로 하면 같은 두 노드가 또 같은 순간에 재시도해 영원히 부딪칩니다. 그래서 무작위로 고르되, 충돌이 거듭될수록 범위를 넓힙니다.

import random

def backoff_slots(collisions: int) -> int:
    m = min(collisions, 10)          # 범위는 10회에서 멈춤
    return random.randint(0, 2**m - 1)

고른 K에 슬롯 시간을 곱한 만큼 기다립니다. 고전 이더넷의 슬롯은 512 비트 시간입니다. 범위는 10회에서 멈추고, 16번 시도해도 실패하면 프레임을 버리고 상위에 알립니다.

발상이 congestion control과 같습니다. 붐비는 정도를 알려주는 사람이 없으니, 실패 횟수를 신호 삼아 혼자 물러나는 폭을 조절합니다.

6. 스위치가 문제를 없앤 방식

이 모든 고민은 허브 시절의 것입니다. 허브는 들어온 신호를 모든 포트로 그대로 흘려보냅니다. 포트가 몇 개든 매체는 하나이고, 붙은 호스트 전부가 한 충돌 영역에 들어갑니다.

스위치는 신호를 흘리지 않고 프레임을 받아 저장했다가 목적지 포트로만 내보냅니다. 포트마다 독립된 링크가 되고, 충돌 영역이 포트 하나로 쪼그라듭니다. 거기에 보내는 선과 받는 선을 분리한 전이중을 더하면 겹칠 신호 자체가 없습니다.

MAC 프로토콜이 풀려던 문제를 알고리즘이 아니라 장비 구조로 치워버린 셈입니다. 스위치가 어떻게 목적지 포트를 알아내는지는 다음 편에서 다룹니다.

7. 그래서 왜 아직 배우는가

세 가지가 남습니다.

첫째, 문제가 사라진 게 아니라 무선으로 옮겨갔습니다. 공기는 쪼갤 수 없는 공유 매체입니다. 게다가 무선에서는 보내면서 듣기가 어려워 충돌 감지 자체가 안 됩니다. 감지 대신 회피로 방향을 틀어야 했습니다.

둘째, 프레임 형식에 흔적이 남아 있습니다. 최소 프레임 64바이트가 그것입니다. 전송이 끝나기 전에 충돌 신호가 왕복해야 했고, 그 왕복 시간이 512 비트 시간, 즉 64바이트였습니다. 충돌이 사라진 지금도 이 규격은 그대로입니다.

셋째, 설정이 어긋나면 되살아납니다. 한쪽만 반이중으로 잡히면 그쪽은 CSMA/CD로 동작하는데 반대쪽은 아무 때나 보냅니다. 링크는 붙어 있는데 성능만 바닥으로 떨어지는 전형적인 증상입니다.

LRU는 "가장 오래 전에 참조된 페이지"를, LFU는 "참조 횟수가 가장 적은 페이지"를 쫓아냅니다. 둘 다 각 페이지가 언제, 몇 번 참조됐는지를 알아야 합니다.

문제는 운영체제가 그 정보를 가질 수 없다는 것입니다. 페이지가 이미 메모리에 있으면 주소 변환은 하드웨어가 처리하고 끝납니다. 운영체제는 CPU를 얻지 못하므로 그 참조가 일어났다는 사실 자체를 모릅니다. page fault가 났을 때만 개입할 수 있는데, 그때 알 수 있는 것은 "지금 이 페이지가 없다"는 사실뿐입니다.

즉 페이징 시스템에서 순수한 LRU와 LFU는 구현할 수 없습니다. 버퍼 캐시나 웹 캐시처럼 소프트웨어가 모든 접근을 거치는 곳에서는 쓸 수 있지만, 페이지 교체에는 근사 알고리즘이 필요합니다.

2. Clock 알고리즘

그래서 하드웨어가 아주 작은 힌트만 남겨 줍니다. 페이지 테이블 항목의 비트 두 개입니다.

• reference bit: 그 페이지가 참조되면 하드웨어가 1로 바꿉니다
• modified bit (dirty bit): 그 페이지의 내용이 변경되면 1로 바꿉니다

Clock 알고리즘은 이 reference bit만 보고 동작합니다. 프레임들을 원형으로 늘어놓고 포인터를 돌립니다.

reference bit이 1이면 "최근에 쓰였구나" 하고 0으로 바꾼 뒤 넘어갑니다. 한 번 더 기회를 주는 셈이라 second chance 알고리즘이라고도 합니다. 포인터가 한 바퀴 돌아 다시 왔을 때도 0이라면, 그 사이에 한 번도 참조되지 않았다는 뜻이므로 교체합니다. 자주 쓰이는 페이지는 포인터가 올 때마다 비트가 1이라 계속 살아남습니다.

modified bit을 함께 보면 더 개선됩니다. 이 비트가 1인 페이지는 내용이 바뀌었으므로 쫓아낼 때 디스크에 써야 합니다. 비용이 크므로 같은 조건이면 modified bit이 0인 페이지를 먼저 내보냅니다.

NUR(Not Used Recently), NRU(Not Recently Used)라는 이름으로도 불립니다.

3. 프레임을 몇 개나 줄 것인가

교체 알고리즘과 별개로, 각 프로세스에 프레임을 몇 개 배정할지 정해야 합니다. 너무 적게 주면 명령 하나를 수행하는 동안에도 page fault가 반복됩니다.

작은 예제

가용 프레임이 62개이고 P1은 10페이지, P2는 127페이지입니다.

1. equal allocation: 31개씩 줍니다. P1은 10페이지뿐이라 21개가 놀고, P2는 127페이지인데 31개라 턱없이 모자랍니다
2. proportional allocation: P1에게 10 ÷ 137 × 62 ≈ 4개, P2에게 127 ÷ 137 × 62 ≈ 57개를 줍니다

쫓아낼 페이지를 어디서 고르느냐도 갈립니다.

4. Thrashing

프로세스에 프레임이 충분하지 않으면 심각한 일이 벌어집니다.

1. 프레임이 모자라 page fault가 자주 납니다
2. page fault 처리는 디스크 입출력이므로 그 프로세스는 Blocked가 됩니다
3. CPU가 놀기 시작합니다
4. 운영체제는 "CPU 이용률이 낮으니 프로세스를 더 올리자"고 판단합니다
5. 프로세스가 늘어 프레임이 더 모자라집니다. 1번으로 돌아갑니다

이 악순환을 쓰래싱(thrashing)이라고 합니다. 시스템이 일은 거의 못 하고 페이지를 올렸다 내렸다 하는 데만 시간을 씁니다.

가로축은 동시에 올라간 프로세스 수, 세로축은 CPU 이용률입니다. 어느 지점까지는 프로세스를 늘릴수록 CPU가 바빠지지만, 임계점을 넘으면 급격히 떨어집니다.

5. Working set과 PFF

해법은 "각 프로세스가 지금 실제로 필요로 하는 만큼은 보장해 주자"입니다.

근거는 참조 지역성(locality of reference)입니다. 프로그램은 특정 시점에 주소 공간의 일부 집중적으로 참조합니다. 그 집합을 locality set이라 하고, 이를 일정 기간 동안의 참조로 추정한 것이 working set입니다.

추정 방법은 단순합니다. window size(Δ)를 정하고, 최근 Δ번의 참조에 등장한 페이지들을 working set으로 봅니다.

작은 예제

Δ = 4이고 참조열이 1 2 3 1 2 4 5 5 5입니다.

필요한 프레임 수가 시점마다 달라집니다. working set 알고리즘은 이 크기만큼 프레임을 주고, 그만큼도 줄 수 없으면 그 프로세스를 통째로 swap out해서 suspended 상태로 만듭니다. 어설프게 조금 주는 것보다 아예 빼는 편이 전체에 이롭기 때문입니다.

PFF(Page Fault Frequency)는 다른 접근입니다. 각 프로세스의 page fault rate를 직접 보면서, 상한선을 넘으면 프레임을 더 주고 하한선 아래로 내려가면 프레임을 뺏습니다. 줄 프레임이 없으면 역시 swap out합니다.

6. 페이지 크기

페이지를 작게 하면 어떤 일이 생기는지 한꺼번에 봐야 합니다.

• 페이지 수가 늘어 페이지 테이블이 커집니다
• 내부 조각이 줄어듭니다. 낭비되는 자투리가 작아집니다
• 디스크 입출력 효율이 나빠집니다. 디스크는 한 번에 많이 읽을수록 유리합니다
• 필요한 정보만 정확히 올릴 수 있어 메모리 이용은 효율적이 됩니다

장단이 엇갈리므로 어느 쪽도 공짜가 아닙니다. 다만 메모리가 커지고 디스크 전송량이 중요해지면서, 내부 조각을 감수하더라도 페이지를 크게 하는 쪽으로 가는 흐름이 있습니다.

트리 순회는 규칙만 정하면 끝이었습니다. 왼쪽을 보고 자신을 보고 오른쪽을 보면 모든 노드를 한 번씩 지납니다. 같은 노드로 되돌아올 일이 없기 때문입니다.

그래프는 사이클이 있습니다. 1에서 2로 갔다가 3을 거쳐 다시 1로 돌아올 수 있습니다. 규칙만으로 돌면 같은 정점을 무한히 맴돕니다.

그래서 그래프 순회에는 반드시 "이미 방문했는가"를 기록하는 장치가 붙습니다. 방문한 정점에는 표시를 남기고, 표시가 있으면 들어가지 않습니다.

2. 깊이 우선이라는 전략

DFS는 갈 수 있는 데까지 깊이 들어갑니다. 더 갈 곳이 없으면 한 발 물러나 아직 안 가 본 갈래를 찾고, 거기서 다시 끝까지 들어갑니다.

      (1)---(2)
       |   / |
       |  /  |
      (3)---(4)
             |
            (5)

   인접 리스트
   1: 2, 3
   2: 1, 3, 4
   3: 1, 2, 4
   4: 2, 3, 5
   5: 4

1에서 출발하면 1 → 2 → 3 → 4 → 5 순서로 방문합니다. 2에서 1로 돌아가는 간선과 3에서 1, 2로 가는 간선은 이미 방문 표시가 있어 그냥 지나칩니다. 5에서 막히면 되돌아 나오는데, 그때는 모두 방문한 뒤라 그대로 끝납니다.

3. 구현

def dfs(v):
    global curr_time
    mark[v] = "visited"           # 방문 표시
    pre[v] = curr_time            # 들어온 시각
    curr_time += 1

    for w in G[v]:                # v의 이웃들
        if mark[w] != "visited":
            dfs(w)                # 아직 안 갔으면 들어간다

    post[v] = curr_time           # 빠져나온 시각
    curr_time += 1

for 루프가 v의 이웃을 훑는 부분입니다. 16편에서 인접 리스트가 유리하다고 한 작업이 바로 이것입니다. 인접 행렬이면 이웃이 아닌 칸까지 n개를 전부 확인해야 합니다.

재귀가 끝나고 돌아오는 것이 "한 발 물러나는" 동작에 해당합니다. 되돌아갈 자리를 따로 관리하지 않아도 되는 것은 03편의 콜 스택이 대신 기억해 주기 때문입니다.

그래프가 여러 덩어리로 나뉘어 있으면 한 번의 dfs로 전부 닿지 못합니다. 그래서 바깥에서 모든 정점을 돌며 아직 방문하지 않은 곳에서 다시 시작합니다.

for v in range(n):
    if mark[v] != "visited":
        dfs(v)

이 루프가 dfs를 부른 횟수가 그래프의 연결 요소 개수입니다.

4. 방문 시각 기록

pre[v]는 v에 들어간 시각, post[v]는 v에서 빠져나온 시각입니다. curr_time을 하나씩 올리며 찍습니다.

   방문 순서 1 -> 2 -> 3 -> 4 -> 5

   정점   pre   post
    1      0      9
    2      1      8
    3      2      7
    4      3      6
    5      4      5

이 두 숫자가 유용한 이유는 구간이 되기 때문입니다. v의 [pre, post] 구간 안에 w의 구간이 통째로 들어 있으면, w는 v에서 출발해 도달한 정점입니다. 두 구간이 겹치지 않으면 서로 다른 갈래에 있습니다. 구간은 포함하거나 떨어지거나 둘 중 하나이고, 절반만 겹치는 경우는 생기지 않습니다.

덕분에 "u가 v의 조상인가" 같은 질문에 숫자 두 개 비교로 답할 수 있습니다.

5. DAG와 사이클

방향 그래프 중 사이클이 없는 것을 DAG(directed acyclic graph)라고 합니다. 작업들 사이의 선후 관계, 빌드 의존성, 데이터 처리 파이프라인처럼 "A가 끝나야 B를 할 수 있다"는 관계가 DAG입니다. 사이클이 있으면 서로를 기다리게 되어 순서를 정할 수 없습니다.

DFS로 사이클이 있는지 판정할 수 있습니다. 아직 빠져나오지 않은 정점, 즉 지금 재귀 호출이 진행 중인 정점으로 돌아가는 간선을 만나면 사이클입니다. pre는 찍혔는데 post가 아직 비어 있는 정점이 그 조건에 해당합니다.

6. 시간복잡도

각 정점을 한 번씩 방문하고 각 간선을 양쪽에서 한 번씩 확인하므로 O(n+m)입니다. 간선이 적은 그래프라면 이 차이가 큽니다.

지난 글에서 테이블 하나를 네 개로 쪼갰습니다. 갱신 이상은 사라졌지만, 대신 원래 한 번에 읽던 정보를 매번 조인해서 모아야 합니다.

-- 수강 목록 하나를 보여주는 데 세 테이블이 필요합니다
SELECT s.name, d.dept_name, c.title, e.grade
FROM enroll e
JOIN student s    ON e.sid = s.sid
JOIN department d ON s.dept_id = d.dept_id
JOIN course c     ON e.cid = c.cid;

비용은 결국 읽어야 할 블록 수입니다. 조인마다 상대 테이블의 블록을 찾아가야 하고, 인덱스를 타더라도 임의 접근이 따라붙습니다. 이 화면이 초당 수천 번 호출되는 목록 페이지라면 조인 비용이 그대로 응답 시간이 됩니다.

2. 역정규화란

역정규화(denormalization)는 성능을 위해 정규화로 제거한 중복을 의도적으로 다시 만드는 것입니다. 중요한 것은 "의도적"입니다. 정규화를 몰라서 합쳐 둔 스키마와 결과물은 같아 보여도 둘은 다릅니다. 역정규화는 어떤 이상 현상을 감수하는지 알고, 그 대가로 무엇을 얻는지 측정한 뒤에 내리는 결정입니다.

3. 대표적인 방법

-- 파생 열: 학과별 학생 수를 매번 세지 않고 저장
ALTER TABLE department ADD student_count INT NOT NULL DEFAULT 0;

-- 중복 열: 수강 목록에서 과목명 조인을 피하려고 복사
ALTER TABLE enroll ADD title VARCHAR(50);

4. 되살아나는 것

두 번째 예시를 넣는 순간 cid → title이라는 함수적 종속성이 enroll 안에 들어옵니다. enroll의 기본키는 (sid, cid, semester)이므로 title은 키의 일부에만 종속하는 부분 함수적 종속성입니다. 2NF 위반으로 되돌아간 것입니다.

따라서 갱신 이상이 그대로 돌아옵니다. 과목명이 바뀌면 그 과목의 모든 수강 행을 고쳐야 하고, 한 군데라도 놓치면 같은 cid에 두 이름이 공존합니다. 역정규화의 비용은 저장 공간이 아니라 이 일관성을 지킬 책임이 DBMS에서 사람에게 넘어온다는 점입니다.

5. 중복을 동기화하는 방법

트리거가 여기서 쓰입니다. 애플리케이션 코드에만 두면 다른 경로로 들어온 변경을 놓친다는 지적도 그대로 적용됩니다.

구체화된 뷰는 DBMS마다 성격이 꽤 다릅니다. SQL Server의 인덱스된 뷰는 원본이 바뀌면 자동으로 동기화되지만 쓸 수 있는 질의 형태에 제약이 있습니다. PostgreSQL의 MATERIALIZED VIEW는 자동 갱신이 없어서 REFRESH MATERIALIZED VIEW를 직접 실행하거나 스케줄러에 걸어야 하고, 그 갱신도 증분이 아니라 질의 전체를 다시 계산합니다.

6. 판단 순서

1. 정규화된 스키마를 먼저 만듭니다.
2. 느린 질의를 실행 계획으로 확인합니다. 조인이 아니라 인덱스 부재나 잘못된 조건이 원인인 경우가 더 흔합니다.
3. 인덱스로 해결되는지 봅니다. 커버링 인덱스는 중복을 만들지 않고 조인을 줄이는 수단입니다.
4. 그래도 부족하면 역정규화하되, 동기화 수단을 함께 정합니다.

중복을 만들기 전에 할 수 있는 일을 먼저 하는 순서입니다.

AS 안에서는 목표가 분명합니다. 빠른 길을 고르면 됩니다. 관리자가 혼자 정하니 비용도 마음대로 매깁니다.

경계를 넘으면 사정이 바뀝니다. 옆 AS는 남의 회사입니다. 내부 구조를 보여주지 않고, 내 트래픽을 공짜로 날라줄 이유도 없습니다. 홉이 하나 적은 길이 있어도 그 길을 쓰면 돈이 나간다면 쓰지 않습니다.

그래서 inter-AS 라우팅은 최단 경로 문제가 아닙니다. "어디로 보낼 수 있는가"와 "어디로 보내고 싶은가"를 가리는 문제입니다. 이 일을 BGP(Border Gateway Protocol)가 맡습니다. 사실상 유일한 inter-AS 프로토콜입니다.

2. AS 번호

AS마다 전 세계에서 유일한 번호를 받습니다. IANA가 지역 등록기관에 나눠주고, 등록기관이 ISP나 기관에 배정합니다.

원래는 16비트라 65536개였습니다. 이것도 부족해져서 32비트로 늘렸습니다. 구형 라우터와 섞여 돌아가는 동안에는 23456번을 자리표시자로 써서 호환을 맞췄습니다. 2026년 기준 전 세계 BGP 테이블에 보이는 활성 AS는 약 8만 개입니다.

3. 세 가지 관계

AS끼리의 연결은 계약 관계로 갈립니다. 둘만 알면 됩니다.

provider-customer: 고객이 사업자에게 돈을 내고 인터넷 연결을 삽니다. 사업자는 고객의 트래픽을 어디로든 날라줍니다. 작은 ISP가 큰 ISP의 고객이 되고, 기업이 ISP의 고객이 됩니다.

peering: 비슷한 규모의 AS 둘이 돈을 주고받지 않고 직접 연결합니다. 서로의 고객끼리 오가는 트래픽만 이 선으로 보냅니다. 둘 다 상위 사업자에게 낼 돈이 줄어드니 이득입니다.

여기서 핵심 규칙이 하나 나옵니다. peer끼리는 서로의 트래픽을 중계해주지 않습니다. A가 B에게 "나를 거쳐 C로 가라"고 알려주면, A는 돈 한 푼 못 받고 회선만 씁니다. 그래서 알려주지 않습니다. 고객에게서 배운 경로는 모두에게 알리고, peer나 사업자에게서 배운 경로는 자기 고객에게만 알립니다.

이 규칙이 정책의 전부에 가깝습니다. 경로를 고르는 기준이 거리가 아니라 돈이라는 뜻입니다.

4. BGP의 동작

BGP는 path vector(경로 벡터) 방식입니다. distance vector처럼 이웃과 정보를 주고받지만, 거리 숫자 대신 거쳐온 AS 목록 전체를 실어 보냅니다.

광고 하나에 중요한 속성이 두 개 붙습니다.

AS_PATH가 count-to-infinity 문제를 원천에서 없앱니다. 거리 숫자만 받으면 그 값이 어디를 거친 것인지 알 수 없었습니다. BGP는 경로를 통째로 받습니다. 받은 AS_PATH 안에 자기 AS 번호가 들어 있으면 루프이므로 그냥 버립니다.

세션은 TCP 179번 포트 위에서 돕니다. 한 번 맺어두고 계속 유지하며, 바뀐 부분만 UPDATE 메시지로 보냅니다. RIP이 30초마다 표를 통째로 보내던 것과 다릅니다.

BGP 세션은 두 종류입니다.

• eBGP: 다른 AS의 게이트웨이와 맺습니다. 바깥 경로를 배워 옵니다.
• iBGP: 같은 AS 안의 라우터끼리 맺습니다. 배워 온 바깥 경로를 내부에 퍼뜨립니다.

5. 경로를 고르는 순서

같은 목적지로 가는 경로를 여러 개 받으면 BGP는 이 순서로 거릅니다.

1. LOCAL_PREF가 높은 것. 관리자가 직접 매기는 선호도입니다. 고객 경로에 높은 값을 주고 사업자 경로에 낮은 값을 줍니다.
2. AS_PATH가 짧은 것.
3. 그 밖의 세부 규칙들.

1번이 2번보다 앞에 있다는 점이 전부를 말해줍니다. 짧은 길보다 정책이 먼저입니다.

6. IGP와 BGP 비교

distance vector는 값이 바뀌면 이웃에게 알리고, 받은 쪽이 다시 계산합니다. 좋아지는 쪽은 빠릅니다. x-y 비용이 4에서 1로 내려가면 y가 곧바로 새 값을 알리고, 이웃들이 한 번씩 고치면 끝납니다.

문제는 나빠질 때입니다. 노드는 이웃이 불러준 숫자만 볼 뿐, 그 숫자가 어떤 경로를 거친 값인지 모릅니다. 이 한 가지 맹점에서 모든 문제가 나옵니다.

2. count-to-infinity

11편의 세 노드로 보겠습니다. x-y가 4, y-z가 1, x-z가 50이고, 수렴한 상태에서 y는 x까지 4, z는 x까지 5(y 경유)를 알고 있습니다.

여기서 y-x 비용이 60으로 올랐습니다. y가 다시 계산합니다.

Dy(x) = min( 60+0, 1 + Dz(x)=5 ) = 6   → z 경유

y는 z를 거치면 6이라고 믿습니다. 그런데 z의 5는 y를 거치는 값입니다. 둘이 서로를 가리키는 고리가 생겼습니다.

멈추는 쪽은 z입니다. z에게는 직접 링크 50이 있습니다. 1 + Dy(x)가 50에 닿는 순간 z가 직접 링크로 갈아탑니다. Dy(x)가 6에서 2씩 올라 50에 이를 때까지 23번이 걸리고, 그제야 y도 min(60, 1+50) = 51로 정착합니다.

링크 하나가 나빠졌을 뿐인데 수십 번을 주고받았습니다. 이것이 count-to-infinity입니다. 11편 비교표에 적은 "나쁜 소식이 더디게 퍼짐"의 실체입니다.

3. poisoned reverse와 그 한계

고치는 방법은 단순합니다. z가 x로 갈 때 y를 거친다면, z는 y에게 자기의 x까지 거리를 ∞라고 알립니다. y가 z를 통해 x로 가려는 생각을 아예 막는 것입니다.

같은 상황을 다시 돌려보겠습니다.

Dy(x) = min( 60+0, 1 + ∞ ) = 60   → 직접 링크

y가 한 번에 올바른 값을 잡습니다. 이어서 z가 min(50, 1+60) = 50으로 직접 링크를 택하면 끝입니다. 두 번의 교환으로 정리됐습니다.

다만 이 규칙은 두 노드 사이의 오해만 막습니다. 고리가 세 노드 이상으로 길어지면 뚫립니다. A-B-C가 고리를 이룰 때 A는 B를, B는 C를 통해 간다고 믿는데, A와 C는 직접 이웃이 아니라 서로에게 ∞를 알릴 일이 없습니다. 그래서 실제 프로토콜은 "충분히 큰 값을 무한대로 치고 거기서 끊는" 장치를 하나 더 둡니다.

4. 라우팅에 계층이 필요한 이유

지금까지는 라우터 전부가 하나의 그래프에 들어 있다고 가정했습니다. 인터넷에서는 불가능합니다. 이유가 둘입니다.

하나는 규모입니다. 라우터가 수억 대인데 모두를 한 그래프에 넣으면 link state는 지도를 뿌리다 끝나고, distance vector는 수렴하지 못합니다.

다른 하나는 자율성입니다. KT와 SKT가 각자의 내부 구조를 서로에게 공개할 이유가 없습니다. 경로를 고르는 기준도 다릅니다. 어떤 회사는 지연을 줄이려 하고, 어떤 회사는 돈이 덜 드는 쪽을 고릅니다. 하나의 알고리즘에 억지로 묶을 수 없습니다.

5. autonomous system

그래서 인터넷은 라우터를 AS(Autonomous System, 자율 시스템) 단위로 묶습니다. 한 기관이 관리하는 라우터 집합이 하나의 AS입니다. ISP 하나, 대학 하나, 대기업 하나가 각각 AS가 됩니다.

AS마다 전 세계에서 유일한 AS 번호를 받습니다. 주소를 나눠주는 기관이 번호도 관리합니다.

굵은 선 하나가 AS 사이를 잇습니다. 그 양 끝에 있는 라우터를 게이트웨이 라우터라고 부릅니다. 이 라우터만 바깥세상과 대화합니다.

6. intra-AS와 inter-AS

라우팅이 두 종류로 갈립니다.

• intra-AS routing: 한 AS 안에서 경로를 고릅니다. 관리자가 혼자 정하면 되니 알고리즘을 자유롭게 고릅니다. 목표는 성능입니다.
• inter-AS routing: AS와 AS 사이의 경로를 고릅니다. 남의 조직과 합의해야 하니 목표가 달라집니다. 성능보다 정책이 앞섭니다.

intra-AS 프로토콜을 묶어 IGP라고 부릅니다. 대표가 RIP과 OSPF입니다. inter-AS 쪽은 사실상 하나뿐입니다.

7. RIP

RIP은 distance vector를 그대로 구현한 프로토콜입니다. 메트릭이 홉 수 하나뿐입니다. 링크가 빠르든 느리든 거쳐 가는 라우터 수만 셉니다.

특징적인 숫자가 둘 있습니다. 쓸 수 있는 최대 홉 수는 15이고, 16은 "닿을 수 없음"을 뜻합니다. "충분히 큰 값에서 끊는" 장치가 이것입니다. count-to-infinity가 돌더라도 16에서 멈추니 금방 정리됩니다. 대신 16홉 이상 떨어진 곳에는 쓸 수 없어 작은 네트워크 전용이 됩니다.

30초마다 이웃에게 자기 표를 통째로 보내고, 메시지는 UDP 520번 포트로 나갑니다. 라우팅 프로토콜이 응용 계층처럼 UDP 위에서 도는 셈입니다.

8. OSPF

OSPF는 link state 방식입니다. 각 라우터가 자기 링크 상태를 AS 전체에 뿌리고, 받은 지도로 Dijkstra를 돌립니다.

RIP과 달리 링크 비용을 관리자가 정합니다. 대역폭을 반영해 빠른 링크에 낮은 값을 주면 빠른 길이 선택됩니다. 홉 수 제한도 없습니다.

규모를 감당하려고 AS 안을 다시 area로 나눕니다. 지도를 area 안에서만 뿌리고, area끼리는 backbone을 통해 요약된 정보만 주고받습니다. 계층을 한 겹 더 넣은 것입니다.

메시지는 TCP도 UDP도 쓰지 않고 IP 위에서 직접 돕니다. protocol 번호는 89입니다. IP 헤더 표의 protocol 필드가 여기서 쓰입니다. 이웃 인증도 지원해서, 아무나 끼어들어 가짜 링크 정보를 뿌리는 것을 막습니다.

9. 두 프로토콜 비교

프로그램을 실행할 때 주소 공간 전체를 메모리에 올릴 필요는 없습니다. 오류 처리 코드처럼 한 번도 실행되지 않는 부분이 많기 때문입니다.

요구 페이징(demand paging)은 페이지가 실제로 참조될 때 메모리에 올리는 방식입니다. 얻는 것이 분명합니다.

• 메모리에 올리는 양이 줄어 더 많은 프로세스를 동시에 띄울 수 있습니다
• 디스크 입출력이 줄고 프로그램 시작이 빨라집니다
• 물리 메모리 크기보다 큰 프로그램도 실행할 수 있습니다

구분은 valid-invalid bit으로 합니다. 메모리에 올라와 있으면 valid, 디스크에 있거나 안 쓰는 영역이면 invalid입니다.

2. page fault

CPU가 invalid인 페이지를 참조하면 page fault가 발생합니다. 주소 변환은 하드웨어가 하다가 멈추고, 이때부터는 운영체제가 처리합니다.

중요한 점은 마지막 단계입니다. 중단된 명령을 처음부터 다시 실행합니다. 그리고 디스크 입출력이 끼어 있으므로 그동안 그 프로세스는 Blocked 상태가 되고 CPU는 다른 프로세스에게 갑니다.

3. 비용은 얼마나 큰가

page fault가 얼마나 자주 나는지를 page fault rate라고 하며 0과 1 사이 값입니다. 0이면 한 번도 발생하지 않는 것이고 1이면 모든 참조에서 발생하는 것입니다.

작은 예제

메모리 접근이 100ns, page fault 한 번 처리에 8ms(= 8,000,000ns)가 든다고 합시다. 디스크가 끼어 있어서 자릿수가 다릅니다.

1. page fault가 없을 때: 100ns
2. page fault rate가 0.1%(p = 0.001)일 때: EAT = (0.999 × 100) + (0.001 × 8,000,000) = 99.9 + 8,000 = 약 8,100ns
3. 1000번에 한 번 틀렸을 뿐인데 평균 접근 시간이 80배가 됐습니다

결론은 하나입니다. page fault는 어쩌다 한 번도 비싸기 때문에, 발생 횟수를 줄이는 것이 전부입니다.

4. 빈 프레임이 없다면

2절의 "빈 프레임 확보" 단계에서 free frame이 하나도 없을 수 있습니다. 그러면 메모리에 있는 페이지 중 하나를 골라 쫓아내야 합니다. 이것이 페이지 교체(page replacement)이고, 무엇을 쫓아낼지 정하는 것이 교체 알고리즘입니다.

목표는 page fault rate를 최소화하는 것입니다. 3절의 숫자가 이유입니다.

아래 예제는 모두 같은 참조열을 씁니다.

1 2 3 4 1 2 5 1 2 3 4 5

Optimal 알고리즘은 가장 먼 미래에 참조될 페이지를 쫓아냅니다. 이 참조열에 프레임 3개로 적용하면 page fault가 7번으로, 어떤 알고리즘도 이보다 적을 수 없습니다. 다만 미래의 참조를 미리 알아야 하므로 실제 시스템에서는 쓸 수 없습니다. 다른 알고리즘이 얼마나 잘하는지 재는 기준(offline 알고리즘)으로만 씁니다. MIN, OPT, Belady의 알고리즘이라고도 부릅니다.

FIFO는 가장 먼저 들어온 페이지를 쫓아냅니다. 구현이 쉽지만 "오래 전에 들어왔지만 계속 쓰이는 페이지"도 그냥 내보냅니다. 프레임 3개로 돌리면 page fault가 9번입니다.

작은 예제 (Belady's anomaly)

보통 프레임을 늘리면 page fault가 줄어야 합니다. FIFO로 같은 참조열을 프레임 4개에 돌려 봅니다.

프레임을 늘렸는데 page fault가 더 늘었습니다. 이 현상을 Belady의 이상 현상(Belady's anomaly)이라고 하며 FIFO에서 나타납니다.

5. LRU와 LFU

미래를 모르니 과거를 보고 추측합니다. 보는 방향이 둘입니다.

• LRU(Least Recently Used): 가장 오래 전에 참조된 페이지를 쫓아냅니다. 최근에 쓴 것은 또 쓸 가능성이 높다는 가정입니다
• LFU(Least Frequently Used): 참조 횟수가 가장 적은 페이지를 쫓아냅니다. 자주 쓰인 것은 또 쓰일 가능성이 높다는 가정입니다

둘 다 완벽하지 않습니다. LRU는 방금 한 번 참조된 페이지를 무조건 살려 두므로, 어쩌다 한 번 쓰인 페이지가 자리를 차지합니다. LFU는 횟수만 보므로 옛날에 많이 쓰이고 지금은 안 쓰는 페이지가 계속 남습니다. 반대로 방금 올라온 페이지는 횟수가 적어 바로 쫓겨납니다.

6. 구현과 시간 복잡도

두 알고리즘은 자료구조에서도 갈립니다.

LRU는 참조 시각 순으로 이어진 연결 리스트를 씁니다. 페이지가 참조되면 그 노드를 떼어 맨 뒤로 보내면 끝이고, 쫓아낼 때는 맨 앞을 꺼냅니다. O(1)입니다.

LFU는 그렇게 되지 않습니다. 참조 횟수가 1 늘면 그 페이지가 리스트의 어디로 가야 하는지 다시 찾아야 하므로 연결 리스트로는 O(n)입니다. 그래서 횟수를 기준으로 하는 힙(heap)으로 구현해 O(log n)으로 줄입니다. LRU보다 구현이 복잡하고 비용이 큰 이유입니다.

7. 알고리즘 비교

지하철 노선도를 생각해 보면 한 역에서 다른 역으로 가는 길이 여러 개이고, 돌아서 제자리로 오는 순환도 있습니다. 환승역은 여러 노선에 동시에 속합니다. 부모가 하나라는 트리의 전제가 전부 깨집니다.

비행 노선, 도로망, 소셜 네트워크의 친구 관계도 마찬가지입니다. 이런 관계는 "무엇이 무엇과 이어져 있는가"만 기록하는 자료구조로 다뤄야 합니다.

2. 정의와 용어

그래프는 정점(vertex, node)의 집합 V와 간선(edge)의 집합 E로 정의합니다.

   G = (V, E)

        (1)-------(2)
         |      /  |
         |    /    |
         |  /      |
        (3)-------(4)

   V = {1, 2, 3, 4}
   E = {(1,2), (1,3), (2,3), (2,4), (3,4)}

• 인접: 두 정점이 간선으로 바로 이어져 있으면 인접하다고 합니다. 1과 2는 인접하고, 1과 4는 인접하지 않습니다
• 차수(degree): 한 정점에 붙은 간선의 수. 위에서 2의 차수는 3입니다
• 경로: 간선을 따라 이어지는 정점들의 나열. 1에서 4로 가는 경로는 1-2-4, 1-3-4 등 여러 개입니다
• 사이클: 출발한 정점으로 되돌아오는 경로. 1-2-3-1이 사이클입니다

간선에 방향이 없으면 무방향 그래프, 있으면 방향 그래프입니다. 친구 관계는 서로에게 성립하므로 무방향이고, 팔로우 관계나 일방통행 도로는 방향 그래프입니다.

앞으로 정점 수를 n, 간선 수를 m으로 씁니다.

3. 표현법이 풀어야 할 문제

그래프를 저장한다는 것은 결국 인접 관계를 기록하는 일입니다. 어떤 정점과 어떤 정점이 이어져 있는지만 알면 나머지는 거기서 나옵니다. 방법은 두 가지입니다.

4. 인접 행렬

n × n 크기의 행렬을 만들고, 간선이 있으면 1, 없으면 0을 적습니다.

        1  2  3  4
    1 [ 0  1  1  0 ]
    2 [ 1  0  1  1 ]
    3 [ 1  1  0  1 ]
    4 [ 0  1  1  0 ]

무방향 그래프에서는 (1,2)와 (2,1)이 같은 간선이므로 대각선을 기준으로 대칭입니다. 방향 그래프에서는 대칭이 아닙니다. 1에서 2로 가는 간선만 있으면 G[1][2]만 1이 됩니다.

1 대신 숫자를 넣으면 가중치도 표현됩니다. 거리나 비용을 적어 두면 됩니다.

G = [[0] * n for _ in range(n)]
G[u][v] = G[v][u] = 1          # 무방향 그래프에 간선 하나 추가

단점은 메모리입니다. 간선이 하나도 없어도 n²칸을 잡습니다. 정점이 1만 개면 1억 칸이고, 그중 실제로 쓰이는 칸은 간선 수만큼뿐입니다.

5. 인접 리스트

그래서 각 정점마다 자기와 인접한 정점들만 나열하는 방식이 나왔습니다. 연결 리스트를 정점 수만큼 두는 형태입니다.

   1 -> 2 -> 3
   2 -> 1 -> 3 -> 4
   3 -> 1 -> 2 -> 4
   4 -> 2 -> 3

나열 순서는 상관없습니다. 정렬해 둘 필요도 없고, 들어온 대로 쭉 늘어놓으면 됩니다. 가중치는 노드에 함께 저장하면 됩니다.

G = [[] for _ in range(n)]
G[u].append(v)
G[v].append(u)

연결 리스트로 직접 구현할 때 새 간선을 맨 앞에 넣으면 PushFront라 O(1)이지만, 맨 뒤에 붙이려면 tail을 들고 있지 않은 한 끝까지 따라가야 합니다. 순서가 상관없으니 앞에 넣는 편이 맞습니다.

6. 비교

행렬은 G[u][v]를 한 번 보면 끝나므로 확인과 삭제가 상수 시간입니다. 리스트는 u의 목록을 훑어야 해서 그 길이만큼 걸립니다.

반대로 "u와 이어진 정점을 전부 보라"는 작업에서는 리스트가 낫습니다. 행렬은 이어지지 않은 칸까지 n개를 전부 확인해야 하지만, 리스트는 실제 이웃만 봅니다. 17편의 DFS처럼 그래프를 훑는 알고리즘이 바로 이 작업을 반복합니다.

7. sparse와 dense

어느 쪽이 나은지는 그래프 모양이 정합니다.

• sparse graph: 정점에 비해 간선이 적은 그래프. 도로망이나 소셜 네트워크처럼 각 정점이 몇 개와만 이어진 경우
• dense graph: 간선이 많아 n²에 가까운 그래프

sparse graph에 인접 행렬을 쓰면 대부분이 0인 칸을 n²개 들고 있게 됩니다. 이때는 인접 리스트가 메모리에서 압도적입니다. dense graph라면 어차피 m이 n²에 가까우므로 메모리 차이가 줄고, 조회가 상수인 행렬이 유리합니다.

수강 정보를 테이블 하나에 몰아넣었다고 해봅시다.

조회는 조인 없이 끝나니 편해 보입니다. 문제는 갱신할 때 드러납니다.

• 수정 이상(modification anomaly): 컴퓨터공학의 이름이 바뀌면 그 학과 학생의 모든 수강 행을 고쳐야 합니다. 하나라도 빠뜨리면 같은 dept_id에 두 이름이 공존합니다.
• 삽입 이상(insertion anomaly): 아직 수강 신청을 하지 않은 신입생을 넣을 수 없습니다. cid가 없으면 기본키가 성립하지 않기 때문입니다. 학생을 넣으려고 가짜 과목을 만들어야 합니다.
• 삭제 이상(deletion anomaly): 박지훈이 유일한 수강 기록을 취소하면 그 학생의 이름과 소속까지 사라집니다.

정규화(normalization)는 이런 이상 현상이 생기지 않도록 릴레이션을 작은 릴레이션들로 분해하는 과정입니다. 분해의 기준이 되는 것이 함수적 종속성입니다.

2. 함수적 종속성과 결정자

애트리뷰트 X의 값이 정해지면 Y의 값이 하나로 정해질 때, Y가 X에 함수적으로 종속(functional dependency)되었다고 하고 X → Y로 씁니다. 이때 왼쪽의 X를 결정자(determinant)라고 부릅니다.

위 테이블에는 이런 종속성이 있습니다.

sid                    → name, dept_id
dept_id                → dept_name
cid                    → title, credit
(sid, cid, semester)   → grade

중요한 점은 이것이 현재 데이터를 보고 찾는 것이 아니라 업무 규칙에서 나온다는 사실입니다. 지금 동명이인이 없다고 해서 name → sid가 성립하는 것은 아닙니다.

여기서 두 가지 용어가 갈라집니다.

• 완전 함수적 종속성(full functional dependency): 복합 키의 전체에 종속. (sid, cid, semester) → grade가 그렇습니다. 셋 중 하나라도 빼면 성적이 정해지지 않습니다.
• 부분 함수적 종속성(partial functional dependency): 복합 키의 일부에만 종속. (sid, cid, semester) → name은 사실 sid → name이므로 부분 종속입니다.
• 이행적 함수적 종속성(transitive functional dependency): X → Y이고 Y → Z이면 X → Z가 따라옵니다. sid → dept_id → dept_name이 그렇습니다.

3. 릴레이션 분해

분해(decomposition)는 릴레이션 하나를 둘 이상으로 나누는 것입니다. 아무렇게나 나누면 안 되고, 분해한 릴레이션들을 자연 조인했을 때 원래 릴레이션이 그대로 복원되어야 합니다. 이 조건을 만족하는 분해를 무손실 분해(lossless decomposition)라고 합니다. 복원했을 때 없던 행이 생기면 정보를 잃은 것입니다.

4. 제1정규형

모든 애트리뷰트의 값이 더 나눌 수 없는 원자값이면 제1정규형(1NF)입니다.

-- 위반: 한 칸에 값이 여러 개
-- sid = 1001, phone = '010-1111-2222, 02-333-4444'

-- 1NF: 값마다 행을 나눕니다
CREATE TABLE student_phone (
  sid   INT         NOT NULL,
  phone VARCHAR(20) NOT NULL,
  CONSTRAINT pk_student_phone PRIMARY KEY (sid, phone)
);

다치 애트리뷰트가 별도 릴레이션이 된 것과 같은 이야기입니다.

5. 제2정규형

1NF이면서 모든 비키 애트리뷰트가 기본키에 완전 함수적으로 종속되면 제2정규형(2NF)입니다. 부분 함수적 종속성을 없애는 단계입니다.

테이블의 기본키는 (sid, cid, semester)인데 name은 sid에만, title은 cid에만 종속합니다. 이 부분 종속들을 떼어냅니다.

이제 학생을 수강 기록 없이도 넣을 수 있고, 수강을 취소해도 학생 정보는 남습니다. 삽입 이상과 삭제 이상이 사라졌습니다.

6. 제3정규형

2NF이면서 비키 애트리뷰트가 기본키에 이행적으로 종속되지 않으면 제3정규형(3NF)입니다.

student(sid, name, dept_id, dept_name)에는 아직 sid → dept_id → dept_name이 남아 있습니다. 학과 이름이 바뀌면 그 학과 학생 행을 전부 고쳐야 하는 수정 이상이 그대로입니다. 한 번 더 분해합니다.

CREATE TABLE student (
  sid     INT         NOT NULL,
  name    VARCHAR(20) NOT NULL,
  dept_id CHAR(3),
  year    INT,
  CONSTRAINT pk_student PRIMARY KEY (sid),
  CONSTRAINT fk_student_dept FOREIGN KEY (dept_id) REFERENCES department(dept_id)
);

CREATE TABLE department (
  dept_id   CHAR(3)     NOT NULL,
  dept_name VARCHAR(30) NOT NULL,
  building  VARCHAR(20),
  CONSTRAINT pk_department PRIMARY KEY (dept_id)
);

공통 스키마가 여기서 다시 나옵니다. ER 모델에서 사상으로 얻은 것과 정규화로 분해해 얻은 것이 같은 결과에 도달합니다.

7. BCNF

3NF까지 왔는데도 이상 현상이 남는 경우가 있습니다. 조건이 "비키 애트리뷰트"에 걸려 있어서, 키를 이루는 애트리뷰트가 다른 애트리뷰트에 종속되는 상황을 잡지 못하기 때문입니다.

지도교수가 과목 하나만 맡는다고 해봅시다.

advise(sid, cid, professor)
  (sid, cid)       → professor
  professor        → cid        -- 교수 한 명은 한 과목만 담당

후보키는 (sid, cid)와 (sid, professor)입니다. professor는 cid를 결정하지만 그 자체로는 후보키가 아닙니다. 그래서 교수가 담당 과목을 바꾸면 그 교수의 모든 행을 고쳐야 하고, 아직 수강생이 없는 교수의 담당 과목은 저장할 수 없습니다.

BCNF(Boyce-Codd Normal Form)는 모든 결정자가 후보키일 것을 요구합니다. advise를 (professor, cid)와 (sid, professor)로 분해하면 만족합니다.

8. 정규형 비교

뒤로 갈수록 조건이 강해집니다. BCNF를 만족하면 앞의 셋을 모두 만족합니다.

페이지 테이블 항목에는 프레임 번호만 있는 것이 아닙니다. 비트 몇 개가 함께 붙습니다.

valid-invalid bit은 그 페이지가 지금 물리 메모리에 올라와 있는지를 나타냅니다.

• valid: 해당 페이지가 메모리에 있고 프레임 번호가 유효합니다
• invalid: 그 페이지가 메모리에 없습니다. 디스크의 swap area에 밀려나 있거나, 애초에 그 프로세스가 쓰지 않는 주소 영역입니다

invalid라고 해서 곧바로 오류는 아닙니다. 앞 글에서 주소 공간 전체를 메모리에 올리지 않는다고 했으므로, 필요할 때 디스크에서 가져오면 됩니다.

protection bit은 그 페이지에 어떤 연산을 허용할지 나타냅니다. code 영역은 바뀔 일이 없으므로 읽기와 실행만 허용하고, data와 stack은 쓰기까지 허용합니다. mode bit, limit register와 마찬가지로 하드웨어가 검사하며, 위반하면 trap이 걸립니다.

2. inverted page table

페이지 테이블은 프로세스마다 하나씩 있습니다. 앞 글에서 하나가 4MB까지 간다고 했으니, 프로세스가 많아지면 테이블만으로 메모리가 모자랍니다.

역발상이 가능합니다. 지금까지는 "페이지마다 한 항목"이었는데, 이것을 "물리 프레임마다 한 항목"으로 뒤집습니다. 그러면 테이블 크기가 물리 메모리 크기에만 비례하고, 시스템 전체에 딱 하나만 있으면 됩니다.

물리 메모리가 1GB이고 페이지가 4KB라면 프레임은 약 26만 개입니다. 프로세스가 몇 개든 항목은 26만 개로 고정입니다.

대신 항목에 어느 프로세스의 몇 번 페이지인지를 적어 둬야 하므로 pid와 페이지 번호가 함께 들어갑니다. 그리고 치명적인 단점이 생깁니다. 페이지 번호로 바로 찾아갈 수 없고 테이블 전체를 뒤져야 합니다. 그래서 앞 글의 associative register처럼 병렬 검색이 가능한 하드웨어가 필요합니다.

3. 공유 페이지

같은 프로그램을 여러 사람이 동시에 실행하는 상황을 생각해 봅니다. 각자의 data와 stack은 다르지만 code는 완전히 같습니다. 똑같은 내용을 메모리에 여러 벌 올릴 이유가 없습니다.

공유 페이지(shared page)는 그 code 페이지를 물리 메모리에 한 벌만 두고, 여러 프로세스의 페이지 테이블이 같은 프레임을 가리키게 하는 방식입니다.

작은 예제

code 10MB, 사용자별 data 1MB인 편집기를 40명이 동시에 씁니다.

1. 공유하지 않으면: (10 + 1) × 40 = 440MB
2. code를 공유하면: 10 + (1 × 40) = 50MB

조건이 있습니다. 공유되는 코드는 실행 중에 자기 자신을 바꾸지 않는 재진입 가능 코드(re-entrant code)여야 합니다. 읽기 전용이어야 한 벌을 여럿이 동시에 써도 안전합니다. 1절의 protection bit이 이것을 보장합니다.

4. 세그먼테이션

페이징은 주소 공간을 같은 크기로 자릅니다. 자를 때 내용이 무엇인지는 보지 않습니다. 그래서 code 영역이 페이지 3.5개 분량이면 마지막 페이지에 data 일부가 섞여 들어갑니다.

세그먼테이션(segmentation)은 자르는 기준을 바꿉니다. code, data, stack처럼 의미 있는 단위로 자릅니다. 각 조각이 세그먼트이고 크기는 제각각입니다.

논리 주소는 세그먼트 번호(segment number)와 오프셋(offset)으로 나뉩니다. 세그먼트 테이블의 각 항목은 둘을 갖습니다.

• base: 그 세그먼트가 시작하는 물리 주소
• limit: 그 세그먼트의 길이

변환은 앞 편의 MMU와 같습니다. 오프셋이 limit보다 작으면 base를 더하고, 크거나 같으면 trap을 겁니다. 세그먼트 테이블의 위치와 길이는 STBR(Segment Table Base Register)과 STLR(Segment Table Length Register)이 가리킵니다.

세그먼테이션의 가치는 세 가지에서 드러납니다.

보호와 공유는 세그먼테이션이 낫고, 할당은 페이징이 낫습니다. 세그먼트는 크기가 다르므로 앞앞 글의 외부 조각과 first fit, best fit 문제가 그대로 돌아옵니다.

5. segmentation with paging

그러면 둘을 합치면 됩니다. 의미 단위로 세그먼트를 나누되, 각 세그먼트를 다시 페이지 단위로 잘라서 올립니다.

핵심 차이는 세그먼트 테이블 항목이 무엇을 가리키느냐입니다. pure segmentation에서는 base가 물리 메모리의 시작 주소를 가리켰습니다. segmentation with paging에서는 그 자리에 그 세그먼트의 페이지 테이블 주소가 들어갑니다.

세그먼트가 물리 메모리에 통째로 연속해서 올라가지 않으므로 외부 조각이 사라집니다. 동시에 보호와 공유는 여전히 세그먼트 단위로 걸 수 있습니다. 두 기법의 좋은 쪽만 취한 구조입니다.

컴퓨터들이 케이블로 이어져 있을 때 "A와 B가 같은 네트워크에 속하는가", 케이블을 하나 새로 연결하면 "두 네트워크가 하나로 합쳐진다" 정도만 알면 되는 경우가 있습니다. 무리 안에 누가 있는지 나열할 필요도, 정렬할 필요도 없습니다.

집합을 다루는 연산에는 합집합, 교집합, 차집합, 소속 여부를 묻는 membership 등이 있지만, 이런 상황에서 필요한 것은 두 가지뿐입니다.

• find(x): x가 속한 집합을 알려 준다
• union(x, y): x가 속한 집합과 y가 속한 집합을 합친다

여기에 원소 하나짜리 집합을 만드는 make_set(x)이 더해집니다. 집합이므로 원소는 중복되지 않고, 각 원소는 정확히 하나의 집합에만 속합니다.

2. 연결 리스트로 만들면

원형 양방향 연결 리스트로 각 집합을 표현할 수 있습니다. 합치는 일은 쉽습니다. join이 링크 몇 개만 바꾸므로 상수 시간입니다.

   {1, 2, 3}            {4, 5}

   1 <-> 2 <-> 3        4 <-> 5
   ^___________|        ^_____|

문제는 find입니다. x가 어느 집합에 속하는지 답하려면 그 집합을 대표하는 무언가를 돌려줘야 하는데, 원형 리스트에서는 어디가 대표인지 알 수 없어 한 바퀴 돌아야 합니다. O(n)입니다.

union도 마찬가지입니다. 두 원소가 이미 같은 집합인지 확인해야 하는데, 그 확인이 find라서 결국 O(n)이 듭니다.

3. 트리로 바꾸기

그래서 각 집합을 트리로 표현합니다. 트리의 루트가 그 집합의 대표가 됩니다.

핵심은 링크 방향입니다. 지금까지의 트리는 부모가 자식을 가리켰지만, 여기서는 자식이 부모를 가리킵니다. 내려갈 일은 없고 "내 위로 올라가면 누가 대표인가"만 알면 되기 때문입니다.

   {1, 2, 3}          {4, 5}

      (1)              (4)
      / \               |
    (2) (3)            (5)

   1과 4가 각 집합의 대표

루트는 부모가 없으므로 자기 자신을 부모로 둡니다. 이렇게 하면 "부모가 자기 자신이면 루트"라는 한 가지 조건으로 판정이 끝납니다.

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = self        # 자기 자신이 부모면 루트
        self.rank = 0

def make_set(x):
    return Node(x)

def find(x):
    while x.parent is not x:      # 루트에 닿을 때까지 올라간다
        x = x.parent
    return x

find는 트리를 한 줄기 올라가므로 O(h)입니다. union은 한쪽 루트를 다른 쪽 루트의 자식으로 매달면 됩니다.

4. 어느 쪽을 밑에 넣을 것인가

막 붙이면 트리가 한 줄로 늘어날 수 있습니다. 그러면 h가 n이 되어 find가 다시 O(n)입니다. 이진 탐색 트리가 겪은 문제와 같습니다.

그래서 각 루트에 rank를 두고, 높이가 낮은 쪽을 높은 쪽 밑에 넣습니다. 낮은 트리를 매달면 전체 높이가 늘지 않습니다.

before: rank 1인 트리와 rank 0인 트리

      (v) rank 1          (w) rank 0
      /   \
    (a)   (b)

after: w가 v 밑으로. 높이는 그대로 1

      (v) rank 1
      / |  \
    (a)(b) (w)

높이가 늘어나는 경우는 둘의 rank가 같을 때뿐입니다.

before: 둘 다 rank 1

      (v)              (w)
      /                /
    (a)              (b)

after: 높이가 1에서 2로

         (v) rank 2
         /   \
      (a)     (w)
              /
            (b)

def union(x, y):
    v, w = find(x), find(y)
    if v is w:                    # 이미 같은 집합
        return
    if v.rank > w.rank:
        w.parent = v
    else:
        v.parent = w
        if v.rank == w.rank:      # 같을 때만 rank가 하나 는다
            w.rank += 1

5. 높이가 O(log n)인 이유

높이가 h인 트리를 만들려면 노드가 최소 몇 개 필요한지 세어 보면 됩니다. 그 최소 개수를 N_h라고 하면, 높이가 h인 트리는 높이 h-1짜리 두 개를 합칠 때만 생깁니다.

   N_h = 2·N_(h-1) = 2^h·N_0

N_0은 1이므로 N_h = 2^h입니다. 즉 높이 h인 트리에는 노드가 적어도 2^h개 들어 있습니다. 전체 노드가 n개이니 2^h ≤ n이고, 따라서 h ≤ log₂n입니다.

rank 규칙 하나로 find와 union이 모두 O(log n)에 묶입니다.

6. 경로 압축

여기서 한 단계 더 줄일 수 있습니다. find로 루트까지 올라가는 김에, 지나온 노드들이 루트를 직접 가리키도록 부모를 바꿔 버리는 방법입니다. 같은 원소를 다시 찾을 때 한 번에 올라갑니다.

def find(x):
    if x.parent is not x:
        x.parent = find(x.parent)   # 올라가면서 루트를 직접 가리키게 한다
    return x.parent

rank와 경로 압축을 함께 쓰면 연산당 비용이 사실상 상수에 가까워집니다. 정확히는 아주 느리게 자라는 함수가 붙는데, 현실적인 n에서는 4 이하입니다.

7. 시간복잡도

연결 리스트의 union이 O(n)인 것은 합치는 작업 자체가 아니라 그 앞의 find 때문입니다.

student가 100만 행이고 블록 하나에 40행이 들어간다면 전체는 2만 5천 블록입니다. 학번 하나로 한 명을 찾는 질의가 평균 1만 블록 넘게 읽어야 합니다. 찾는 값이 없으면 2만 5천 블록을 모두 읽습니다.

인덱스(index)는 이 비용을 줄이려고 따로 두는 작은 파일입니다. 책 뒤의 찾아보기와 같은 구조로, (탐색키, 포인터) 쌍만 담습니다. 레코드 하나가 데이터 레코드보다 훨씬 작으니 같은 블록에 훨씬 많이 들어가고, 그래서 훨씬 적은 블록 접근으로 위치를 알아냅니다. 인덱스가 정의된 필드를 탐색키(search key)라고 부릅니다.

2. 희소 인덱스와 밀집 인덱스

인덱스 항목을 몇 개나 둘지에 따라 갈립니다.

• 희소 인덱스(sparse index): 데이터 블록마다 항목 하나만 둡니다. 블록 안에서는 순차로 찾습니다. 데이터 파일이 그 탐색키로 정렬돼 있어야만 가능합니다.
• 밀집 인덱스(dense index): 모든 레코드마다 항목을 둡니다. 데이터 파일의 정렬 여부와 무관합니다.

희소 쪽이 훨씬 작아 단계 수를 줄이는 데 유리하고, 밀집 쪽은 인덱스만 읽고도 값의 존재 여부를 판정할 수 있습니다. 데이터 파일을 건드리지 않고 답을 내는 커버링 인덱스의 출발점이 이것입니다.

3. 기본, 클러스터링, 보조 인덱스

탐색키가 무엇이냐에 따라 세 가지로 나뉩니다.

앞의 둘이 테이블당 하나뿐인 이유는 같습니다. 파일을 물리적으로 정렬하는 기준은 하나밖에 가질 수 없기 때문입니다. 반면 보조 인덱스는 데이터 파일의 배치와 무관하므로 필요한 만큼 만들 수 있고, 대신 포인터를 따라 임의 접근이 발생합니다.

4. 다단계 인덱스

인덱스도 결국 파일입니다. 데이터가 커지면 인덱스 자체가 수백 블록이 되고, 인덱스를 뒤지는 비용이 다시 문제가 됩니다. 그래서 인덱스에 다시 인덱스를 겁니다. 이것이 다단계 인덱스(multilevel index)입니다.

한 단계 올라갈 때마다 블록 수가 팬아웃(fan-out)만큼 나뉘므로, 블록 수가 아무리 커져도 단계 수는 로그 규모로만 늘어납니다. 팬아웃이 100이면 1억 건도 네 단계면 닿습니다. 이렇게 올라가다 한 블록에 전부 담기는 최상위 단계를 마스터 인덱스(master index)라고 부릅니다. 탐색은 언제나 여기서 시작하므로 이 블록은 버퍼에 상주시키는 것이 유리합니다.

실제 DBMS는 이를 B+ 트리로 구현합니다. 내부 노드에는 길잡이 키만 두고 모든 탐색키를 리프에 모으며, 리프끼리 양방향으로 이어 둡니다.

리프를 잇는 이 선이 범위 검색을 지탱합니다. sid >= 1005는 1005를 찾아 내려간 뒤 리프를 따라 옆으로 읽으면 끝나고, 매번 루트부터 다시 내려오지 않습니다. 어떤 값이든 루트에서 리프까지 거리가 같아 조회 성능이 고르다는 점도 함께 따라옵니다.

5. SQL에서 인덱스 정의하기

표준 SQL에는 인덱스를 만드는 문장이 없습니다. 인덱스는 논리적 스키마가 아니라 물리적 설계의 영역이고, 같은 질의 결과를 내는 데 영향을 주지 않기 때문입니다. 그래서 CREATE INDEX는 DBMS마다 제공하는 확장입니다.

-- 단일 애트리뷰트
CREATE INDEX ix_student_dept ON student(dept_id);

-- 유일성까지 함께 보장
CREATE UNIQUE INDEX ix_student_sid ON student(sid);

-- 다수의 애트리뷰트: 복합 인덱스
CREATE INDEX ix_enroll_sid_cid ON enroll(sid, cid);

SQL Server는 CLUSTERED / NONCLUSTERED를 붙여 저장 구조까지 지정하고, 생략하면 비클러스터형입니다. PostgreSQL은 USING btree, USING hash처럼 인덱스 종류를 고릅니다. 삭제 문법도 갈려서 SQL Server는 DROP INDEX ix_student_dept ON student, PostgreSQL은 DROP INDEX ix_student_dept입니다.

여기서 이름이 겹치는 함정 하나. SQL Server의 클러스터형 인덱스는 3절의 클러스터링 인덱스가 아니라 테이블 자체를 B+ 트리로 저장하는 구조이고, 리프가 곧 데이터 행입니다. PostgreSQL에는 그런 구조가 없어 모든 인덱스가 히프를 가리키는 보조 인덱스입니다.

6. 복합 인덱스에서 순서가 중요한 이유

(sid, cid) 인덱스는 sid로 먼저 정렬하고 같은 sid 안에서 cid로 정렬합니다. 전화번호부를 성으로 묶고 그 안에서 이름순으로 정렬한 것과 같습니다.

그래서 WHERE sid = 1001과 WHERE sid = 1001 AND cid = 'C101'은 이 인덱스를 쓰지만, WHERE cid = 'C101'만 거는 질의는 쓰지 못합니다. 성을 모른 채 이름만으로 전화번호부를 뒤지는 셈이기 때문입니다. 복합 인덱스를 설계할 때 열의 순서가 곧 쓸 수 있는 질의의 범위를 정합니다.

질의가 요구하는 열이 인덱스 안에 전부 있으면 데이터 파일을 아예 읽지 않습니다.

7. 장점과 단점

인덱스는 공짜로 조회를 빠르게 하는 장치가 아니라 읽기 성능을 쓰기 성능과 저장 공간으로 사는 거래입니다.

8. 인덱스 선정 지침과 튜닝

• WHERE, 조인 조건, ORDER BY, GROUP BY에 자주 등장하는 열이 1순위입니다.
• 기본키와 유일 제약조건에는 대부분의 DBMS가 인덱스를 자동으로 만듭니다. 따로 만들 필요가 없습니다.
• 선택도(selectivity)가 높은 열, 즉 값의 종류가 많아 조건 하나로 행이 크게 줄어드는 열에 효과가 있습니다.
• 갱신이 잦은 열, 행 수가 적은 테이블에는 신중합니다.
• 인덱스 개수 자체를 관리합니다. 쓰지 않는 인덱스는 쓰기 비용만 남깁니다.

튜닝은 추측이 아니라 측정에서 시작합니다. 실행 계획을 먼저 보고, 어떤 인덱스가 실제로 쓰이는지 확인한 뒤에 바꿉니다. 통계 정보가 낡으면 옵티마이저가 잘못된 선택을 하므로 PostgreSQL의 ANALYZE, SQL Server의 UPDATE STATISTICS로 갱신해 둡니다.

9. 인덱스가 사용되지 않는 경우

-- 좌변을 가공하면 인덱스를 쓰지 못합니다
WHERE YEAR(created_at) = 2024          -- 안 됨
WHERE created_at >= '2024-01-01'       -- 됨
  AND created_at <  '2025-01-01'

• 인덱스 열에 함수나 연산을 적용한 경우
• 복합 인덱스의 선두 열이 조건에 없는 경우
• LIKE '%검색어'처럼 앞부분이 열려 있는 패턴
• <>, NOT IN 같은 부정 조건
• 데이터 타입이 달라 암묵적 형 변환이 일어나는 경우
• 결과 행이 전체의 상당 비율이어서 전체 스캔이 더 싼 경우

마지막 항목만 성격이 다릅니다. 앞의 다섯은 인덱스를 쓸 수 없는 상황이고, 마지막은 쓸 수 있는데도 옵티마이저가 쓰지 않기로 판단한 상황입니다.

라우터는 패킷을 버려도 알려주지 않습니다. 보낸 쪽은 응답이 없다는 것만 알 뿐, 어디서 왜 막혔는지 짚을 수 없습니다. 이 틈을 ICMP(Internet Control Message Protocol, 인터넷 제어 메시지 프로토콜)가 메웁니다.

ICMP 메시지는 IP 데이터그램에 실려 다닙니다. 그래도 계층은 네트워크 계층으로 칩니다. 상위 계층을 위해 일하지 않고, 네트워크 계층이 제 사정을 알리는 데만 쓰기 때문입니다. 헤더는 type과 code 각 1바이트로 시작합니다. type으로 크게 나누고 code로 사유를 좁힙니다.

type 3의 code 3은 자주 만나게 됩니다. 호스트는 살아 있는데 그 포트에서 아무도 듣지 않을 때 돌아옵니다. demultiplexing이 갈 곳을 못 찾았다는 뜻입니다.

traceroute는 이 중 type 11을 써먹습니다. TTL을 1부터 하나씩 올려가며 패킷을 던지면, 라우터들이 차례로 TTL을 0으로 만들면서 자기 주소로 "시간 초과"를 돌려보냅니다. 그 주소를 순서대로 적으면 경로가 나옵니다.

2. 라우팅을 그래프로 바꾸기

라우터를 점으로, 링크를 선으로, 링크 비용을 선의 가중치로 놓습니다. 그러면 라우팅은 최소 비용 경로를 찾는 문제가 됩니다.

푸는 길은 둘입니다. 모두가 지도 한 장을 똑같이 나눠 갖고 각자 계산하거나, 지도 없이 옆 노드와 숫자만 주고받거나.

3. link state: 지도를 나눠 갖고 Dijkstra

link state(링크 상태) 방식에서는 라우터마다 자기에게 붙은 링크 사정을 네트워크 전체에 뿌립니다. 그래서 모두가 같은 지도를 갖게 되고, 각자 Dijkstra 알고리즘을 돌려 자기 기준 최단 경로를 구합니다.

절차는 이렇습니다. 아직 확정하지 않은 노드 가운데 비용이 가장 작은 것을 하나 집어 확정합니다. 그 노드를 거치면 더 싸지는 이웃이 있는지 보고, 있으면 값을 고칩니다. 전부 확정할 때까지 이 두 가지를 반복합니다.

위 그래프에서 u를 출발점으로 돌려보겠습니다.

칸마다 비용과 직전 노드를 적었습니다. x를 확정하자 w까지 가는 값이 5에서 4로 내려갔고, y를 확정하자 다시 3으로 내려갔습니다. 마지막에 경로를 거꾸로 따라가 "처음에 넘길 이웃"만 남기면 forwarding table이 됩니다. u에서는 w로 가는 것도 z로 가는 것도 전부 x로 내보내면 됩니다.

4. distance vector: 옆 노드와 숫자만 주고받기

distance vector(거리 벡터) 방식에서는 아무도 지도를 갖지 않습니다. 노드는 목적지마다 최소 비용을 적은 표 하나만 들고 있습니다. 그 표를 옆 노드에게 보냅니다. 받은 쪽은 자기 표를 고쳐보고, 값이 바뀌었으면 다시 자기 옆으로 보냅니다.

고칠 때 쓰는 식이 Bellman-Ford 방정식입니다.

dx(y) = min over v { c(x, v) + dv(y) }

x에서 y까지 얼마나 드는지 알고 싶으면, 이웃 v마다 "x에서 v까지 드는 값 + v가 알려준 y까지의 값"을 더해보고 제일 작은 것을 고릅니다. 전체 경로를 몰라도 이웃까지의 비용과 이웃이 불러준 숫자만 있으면 계산이 끝납니다.

x-y가 2, y-z가 1, x-z가 7인 세 노드로 따라가 보겠습니다.

처음  : x는 z까지 7이라고 알고 있다
y 알림: "나는 z까지 1"
x 계산: min(7, 2 + 1) = 3
결과  : x는 z로 갈 때 y를 거치기로 한다

값이 더 안 바뀔 때까지 이 주고받기를 반복하면 전체가 최단 경로에 수렴합니다.

5. 두 방식 비교

마지막 줄을 조금 풀면 이렇습니다. 링크가 싸졌다는 소식은 금방 퍼집니다. 반면 비싸졌다는 소식은 이웃끼리 서로의 옛날 값을 보며 조금씩만 올리기 때문에, 제값에 닿기까지 여러 번 주고받아야 합니다.

페이징(paging)은 프로세스의 주소 공간을 같은 크기의 페이지(page) 단위로 자르고, 물리 메모리도 같은 크기의 페이지 프레임(page frame)으로 잘라 두는 기법입니다. 그리고 페이지를 비어 있는 아무 프레임에나 올립니다.

크기가 모두 같으므로 "이 조각이 들어갈 자리가 있는가"를 따질 필요가 없습니다. 빈 프레임이 하나라도 있으면 거기 넣으면 됩니다. 앞 글의 first fit이나 best fit 같은 배치 전략도, 외부 조각도 사라집니다.

대신 치러야 할 값이 있습니다. 페이지가 흩어져 있으므로 어느 페이지가 어느 프레임에 있는지 기록해 둬야 합니다. 그 표가 페이지 테이블(page table)입니다.

2. 주소 변환

논리 주소를 둘로 나눠 읽습니다.

• 페이지 번호(page number, p): 주소의 윗부분. 페이지 테이블의 몇 번째 항목을 볼지 가리킵니다
• 페이지 오프셋(page offset, d): 주소의 아랫부분. 그 페이지 안에서 몇 번째 바이트인지 가리킵니다

변환 규칙은 "페이지 번호만 바꾸고 오프셋은 그대로 둔다"입니다. 페이지와 프레임의 크기가 같으므로 안쪽 위치는 변하지 않기 때문입니다.

작은 예제

페이지 크기가 4096바이트(4KB)이고, 논리 주소 13000번지에 접근합니다.

1. 페이지 번호: 13000 ÷ 4096 = 3 → p = 3
2. 오프셋: 13000 − (3 × 4096) = d = 712
3. 페이지 테이블의 3번 항목을 봅니다. 프레임 번호가 9라고 합시다
4. 물리 주소: (9 × 4096) + 712 = 37576번지

오프셋 712는 끝까지 그대로 따라왔습니다.

3. 페이지 테이블은 어디에 두는가

페이지 테이블은 프로세스마다 하나씩 있고 항목 수가 많습니다. 레지스터에 넣기에는 너무 크므로 메인 메모리에 상주합니다. 그 위치와 크기는 레지스터 두 개가 가리킵니다.

• PTBR(Page Table Base Register): 페이지 테이블의 시작 주소
• PTLR(Page Table Length Register): 페이지 테이블의 길이

문맥 교환이 일어나면 이 레지스터 값만 새 프로세스의 것으로 바꾸면 됩니다.

여기서 성능 문제가 생깁니다. 페이지 테이블이 메모리에 있으므로, 데이터 한 번 읽으려면 메모리에 두 번 접근해야 합니다. 한 번은 페이지 테이블을 보려고, 한 번은 실제 데이터를 읽으려고. 그대로 두면 모든 메모리 접근이 두 배로 느려집니다.

4. TLB

그래서 자주 쓰는 변환 결과만 따로 캐싱합니다. 이 캐시가 TLB(Translation Look-aside Buffer)입니다.

TLB는 associative register로 만들어집니다. 원하는 페이지 번호가 몇 번째에 있는지 모르므로 전체 항목을 동시에 병렬로 검색하는 하드웨어입니다. 그래서 빠르지만 비싸고, 용량이 작아 일부만 담습니다.

주의할 점은 TLB에 담긴 변환 정보가 그 프로세스 전용이라는 것입니다. 문맥 교환이 일어나면 이전 프로세스의 변환 정보는 무효가 되므로 TLB를 flush해야 합니다. 문맥 교환 비용에는 이것도 포함됩니다.

작은 예제 (EAT)

실제 평균 접근 시간을 EAT(Effective Access Time)라고 합니다. 메모리 접근 100ns, TLB 접근 20ns, TLB 적중률 80%로 계산합니다.

1. TLB 적중: TLB 20 + 메모리 100 = 120ns
2. TLB 실패: TLB 20 + 페이지 테이블 100 + 데이터 100 = 220ns
3. EAT = (0.8 × 120) + (0.2 × 220) = 96 + 44 = 140ns

TLB가 없으면 항상 200ns입니다. 적중률 80%만으로 140ns까지 내려왔습니다. 적중률이 성능을 좌우한다는 것이 숫자로 보입니다.

5. 2단계 페이지 테이블

남은 문제는 페이지 테이블 자체의 크기입니다. 숫자로 보면 분명합니다.

32비트 주소 체계에 페이지 크기 4KB를 쓰면, 한 프로세스의 페이지 수는 2³² ÷ 2¹² = 약 100만 개입니다. 항목 하나가 4바이트라면 페이지 테이블 하나가 4MB입니다. 프로세스를 100개 띄우면 페이지 테이블만 400MB를 차지합니다.

더 아까운 점은 대부분의 항목이 비어 있다는 것입니다. 프로그램이 4GB 주소 공간을 전부 쓰는 일은 없습니다. 쓰지도 않는 주소에 대한 항목까지 100만 개를 만들어 두는 셈입니다.

해법은 페이지 테이블을 두 단계로 나누는 것입니다. 바깥 테이블만 항상 두고, 안쪽 테이블은 실제로 쓰는 영역에 대해서만 만듭니다. 논리 주소를 세 부분으로 쪼개 읽습니다.

p1으로 바깥 테이블에서 안쪽 테이블의 위치를 찾고, p2로 안쪽 테이블에서 프레임 번호를 찾고, 거기에 d를 더합니다. 안쪽 테이블 하나는 1024 × 4바이트 = 4KB로 정확히 한 페이지 크기입니다.

쓰지 않는 영역은 바깥 테이블 항목을 비워 두면 그만이므로 안쪽 테이블을 아예 만들지 않습니다. 그만큼 공간을 아낍니다. 대신 변환 단계가 늘어 메모리 접근이 한 번 더 필요해집니다. 이 손해는 TLB가 메워 줍니다.

노드는 자식을 2개, 3개, 또는 4개 가질 수 있습니다. 자식이 k개인 노드는 키를 k-1개 담습니다.

   2-노드           3-노드                4-노드
   [ a ]          [ a | b ]          [ a | b | c ]
   /   \          /   |   \          /   |   |   \
  <a   >a       <a  a~b   >b       <a  a~b  b~c  >c

키 사이사이의 구간이 자식 하나씩에 대응합니다. 이진 탐색 트리와 같은 원리인데, 갈림길이 둘이 아니라 최대 넷입니다.

여기에 조건이 하나 붙습니다. 모든 리프 노드가 같은 레벨에 있어야 합니다. 이 조건이 균형 그 자체입니다. AVL처럼 높이 차를 재거나 Red-Black처럼 색을 칠할 필요 없이, 어느 경로로 내려가든 길이가 같습니다.

            [ 30 ]
           /      \
    [10 | 20]    [40 | 50 | 60]

   리프 두 개가 모두 레벨 1

2. 높이

레벨마다 자식이 최소 2개, 최대 4개로 갈라지므로 높이는 다음 범위에 들어옵니다.

   log₄n <= h <= log₂n

모든 노드가 4-노드면 가장 빠르게 퍼져 h가 log₄n이고, 전부 2-노드면 이진 트리와 같아 log₂n입니다. 어느 쪽이든 O(log n)이므로 탐색은 로그 시간입니다.

3. 삽입은 항상 리프에

새 키는 언제나 리프 노드에 넣습니다. 중간 노드에 끼워 넣는 경우는 없습니다. 리프가 전부 같은 레벨이어야 하는데, 중간에 자식을 하나 더 매달면 그 아래만 레벨이 깊어져 조건이 깨지기 때문입니다.

문제는 리프가 이미 4-노드일 때입니다. 키를 하나 더 받을 자리가 없습니다. 이때 쓰는 것이 split입니다.

4-노드 [a|b|c]를 만나면 가운데 키 b를 부모로 올려보내고, 남은 a와 c를 각각 2-노드로 쪼갭니다.

before: [10|20|30]을 쪼개기 직전

          [ 40 ]
         /      \
  [10|20|30]    [50]

after: 20이 부모로 올라가고 좌우가 갈라짐

       [ 20 | 40 ]
       /    |     \
    [10]  [30]    [50]

부모의 키가 하나 늘고 자식이 하나 늘었습니다. 바꾸는 노드 수가 정해져 있으므로 split 한 번은 O(1)입니다.

삽입은 루트에서 리프로 내려가면서, 지나는 길에 4-노드를 만나면 미리 쪼갭니다. 이렇게 하면 쪼갤 때 부모가 꽉 차 있는 일이 없습니다. 부모가 4-노드였다면 이미 위에서 쪼갰기 때문입니다.

루트가 4-노드인 경우에는 올려보낼 부모가 없습니다. 이때는 가운데 키가 새 루트가 되고 트리의 높이가 1 늘어납니다.

   [10|20|30]        =>        [ 20 ]
                               /     \
                            [10]     [30]

2-3-4 트리가 자라는 유일한 방향이 위쪽이라는 점이 중요합니다. 아래로 늘어나지 않으니 리프가 같은 레벨이라는 조건이 저절로 유지됩니다.

4. 삭제와 underflow

삭제에서 문제가 되는 것은 2-노드입니다. 키가 하나뿐이라 그 키를 빼면 노드가 비어 버립니다. 이를 underflow라고 합니다.

해결은 두 가지입니다.

형제에게서 빌리기: 바로 옆 형제가 3-노드나 4-노드면 여유가 있습니다. 형제의 키 하나를 부모로 올리고, 부모의 키 하나를 빈 노드로 내립니다. 빌려 온 쪽은 2-노드가 되고 빈 노드는 채워집니다.

fusion: 형제도 2-노드라 빌릴 데가 없으면 합칩니다. 부모의 키 하나를 내려서 형제와 묶어 3-노드를 만듭니다.

  before: 가운데 자식이 비었고 형제도 2-노드

          [ 20 | 40 ]
          /    |     \
       [10]   [ ]    [50]

  after: 부모의 20을 내려 왼쪽 형제와 합침

             [ 40 ]
            /      \
      [10 | 20]    [50]

fusion은 부모의 키를 하나 가져가므로 부모가 다시 underflow에 빠질 수 있습니다. 그러면 같은 처리를 위로 반복합니다. 루트까지 올라가 루트의 키가 전부 내려가면 루트가 사라지고 높이가 1 줄어듭니다.

5. Red-Black 트리와의 변환

2-3-4 트리와 Red-Black 트리는 서로 바꿀 수 있습니다. 13편에서 본 색 조건이 사실 이 트리를 이진 트리로 눌러 담은 결과입니다.

  2-노드            3-노드                  4-노드
                                             (b)B
   (a)B            (b)B                     /    \
                   /                      (a)R   (c)R
                (a)R

   1레벨           2레벨                    2레벨

노드 안의 키 하나를 블랙으로 두고, 같은 노드에 함께 있던 나머지 키를 레드로 매답니다. 그러면 한 노드가 1~2레벨을 차지합니다. 레드가 연달아 나오지 않는 것은 한 노드에 키가 최대 3개뿐이기 때문이고, 모든 경로의 블랙 수가 같은 것은 모든 리프가 같은 레벨이기 때문입니다. split이 Red-Black의 색 교환에, fusion이 삭제 쪽 처리에 대응합니다.

6. 시간복잡도

세 연산이 모두 같은 복잡도입니다. 전부 루트에서 리프까지 한 번 내려가고, 내려가는 길에서 하는 일이 상수 시간이기 때문입니다.

Red-Black 트리는 각 노드에 레드 또는 블랙 색을 두고, 다음 조건을 지키는 이진 탐색 트리입니다.

1. 모든 노드는 레드 또는 블랙이다
2. 루트는 블랙이다
3. 모든 리프는 블랙이다
4. 레드 노드의 두 자식은 블랙이다
5. 각 노드에서 리프로 가는 모든 경로의 블랙 노드 수가 같다

            (13)B
           /     \
        (8)R      (17)R
        /  \      /    \
    (1)B  (11)B (15)B  (25)B
       \
       (6)R

  13에서 리프로 가는 어느 경로를 택해도 블랙 노드 수가 같다
  레드인 8과 17의 자식은 모두 블랙이다

여기서 리프는 값을 담은 노드가 아니라 자식이 없는 자리를 채우는 가상의 nil 노드로 보는 것이 편합니다. 그래야 "모든 경로"를 셀 때 끝이 일정해집니다.

4번과 5번이 균형 장치입니다. 5번은 모든 경로의 블랙 수를 같게 묶고, 4번은 그 사이에 레드를 연달아 끼우지 못하게 막습니다.

2. 왜 높이가 O(log n)인가

노드 v에 대해 h(v)를 v의 높이, bh(v)를 v를 제외하고 리프까지 가는 경로의 블랙 노드 개수라고 합니다. 5번 조건 덕분에 bh(v)는 경로와 무관하게 하나로 정해집니다.

그러면 다음이 성립합니다.

   v의 부트리 노드 수 >= 2^bh(v) - 1

v가 리프면 bh(v)=0이고 식은 0 ≥ 0입니다. 그렇지 않으면 두 자식의 bh는 bh(v) 또는 bh(v)-1이므로, 각 부트리가 최소 2^(bh(v)-1)-1개를 가지고, 양쪽과 자기 자신을 더하면 2^bh(v)-1이 됩니다.

한편 4번 조건 때문에 어떤 경로에서도 레드는 블랙 사이사이에만 들어갑니다. 루트에서 리프까지 가는 경로의 절반 이상이 블랙이므로 bh(루트) ≥ h/2입니다. 이를 위 식에 넣으면

   n >= 2^(h/2) - 1      =>      h = O(log n)

AVL이 높이 차를 직접 재서 얻은 결론을, Red-Black 트리는 색 조건만으로 얻습니다.

3. 삽입

새 노드는 일단 레드로 넣습니다. 블랙으로 넣으면 그 경로의 블랙 수가 하나 늘어 5번이 바로 깨지는데, 레드로 넣으면 5번은 그대로이고 4번만 위험해지기 때문입니다.

넣은 뒤 상황은 네 가지입니다.

x가 루트인 경우: 2번 조건에 맞게 블랙으로 바꾸고 끝냅니다.

부모가 블랙인 경우: 레드 자식이 블랙 부모 밑에 붙었으니 아무 조건도 깨지지 않습니다. 할 일이 없습니다.

부모가 레드이고 삼촌도 레드인 경우: 레드가 연달아 나와 4번이 깨졌습니다. 부모와 삼촌을 블랙으로, 할아버지를 레드로 바꿉니다. 이 부트리를 지나는 경로의 블랙 수는 그대로입니다.

before

            (G)B                          (G)R   <- 여기서 다시 검사
           /    \                        /    \
        (P)R    (U)R        ==>       (P)B    (U)B
        /                             /
     (X)R                          (X)R

할아버지가 레드가 되었으니 그 위에서 다시 4번이 깨질 수 있습니다. 그래서 할아버지를 새 x로 보고 같은 검사를 반복합니다. 색만 바꾸고 위로 올라가는 경우입니다.

부모가 레드이고 삼촌이 블랙인 경우: 색만 바꿔서는 블랙 수를 맞출 수 없습니다. 회전이 필요합니다. x와 부모와 할아버지가 한 방향이면 한 번, 꺾여 있으면 두 번 돌립니다.

before: 한 방향인 경우

            (G)B                           (P)B
           /    \       rotateRight(G)     /    \
        (P)R    (U)B      + 색 교환      (X)R    (G)R
        /   \                                   /   \
     (X)R    C                                 C    (U)B

올라온 P를 블랙으로, 내려간 G를 레드로 바꿉니다. 이 경우는 여기서 끝납니다. 부트리의 꼭대기가 블랙이 되어 위쪽에서 볼 때 달라진 것이 없기 때문입니다.

정리하면 레드-레드 충돌을 색 교환으로 위로 밀어 올리다가, 삼촌이 블랙인 지점을 만나면 회전 한두 번으로 마무리합니다. 올라가는 거리가 O(log n)이고 회전은 상수 번입니다.

4. 삭제

삭제는 삽입보다 훨씬 복잡합니다. 블랙 노드를 지우면 그 경로의 블랙 수가 하나 줄어 5번이 깨지는데, 이를 메우려고 형제의 색과 모양에 따라 여러 경우를 나눠 처리해야 합니다.

다만 회전 횟수는 상수로 끝납니다. 색을 바꾸며 위로 전파하는 부분은 반복되지만, 실제 회전은 세 번을 넘지 않습니다. AVL의 삭제가 레벨마다 회전할 수 있었던 것과 갈리는 지점입니다.

5. AVL과 비교

높이는 AVL이 더 낮으므로 탐색이 잦은 쪽에서는 AVL이 유리합니다. 반대로 삽입과 삭제가 잦으면 삭제 회전이 상수로 끝나는 Red-Black이 유리합니다. 둘 다 복잡도는 같고, 차이는 상수와 실제 작업량에서 납니다.

모든 테이블을 레코드가 도착한 순서대로만 쌓아 두면, 학번으로 한 명을 찾는 질의도 100만 행을 전부 읽습니다. 파일 조직(file organization)은 레코드를 디스크에 어떤 순서로 배치할지 정하는 결정이고, 그 선택이 어떤 질의가 빨라지고 어떤 질의가 느려질지를 거의 다 정합니다.

2. 히프 파일

삽입되는 순서대로 파일 끝에 붙입니다. 정렬도 색인도 없습니다.

삽입은 마지막 블록만 건드리므로 가장 쌉니다. 대신 탐색은 전체 스캔입니다. 값이 유일하면 평균 블록의 절반, 없는 값을 찾을 때는 전부 읽습니다. 삭제는 자리만 비우기 때문에 빈 공간이 쌓이면 주기적으로 재편성해야 합니다. 대량 적재나 전체 스캔 위주의 작업에 맞습니다.

3. 순차 파일

탐색키 순으로 정렬해 저장합니다. 범위 검색과 정렬 출력이 유리하고, 블록 단위 이진 탐색으로 탐색 범위를 로그 규모로 줄일 수 있습니다.

문제는 삽입입니다. 중간에 들어갈 레코드 하나 때문에 뒤쪽을 전부 밀 수는 없으므로 오버플로 영역에 따로 쌓고 포인터로 잇습니다. 이 영역이 길어질수록 정렬 순서의 이점이 사라져서 주기적으로 병합해 다시 써야 합니다.

4. 인덱스된 순차 파일

정렬된 데이터 파일에 인덱스를 얹은 구조입니다. 등호 검색은 인덱스로, 범위 검색은 인덱스로 시작점을 찾은 뒤 순차 접근으로 처리합니다. 두 가지를 모두 감당하는 대신 순차 파일의 삽입 문제를 그대로 물려받습니다. 오버플로 체인이 길어지면 재구성이 필요합니다. 이 약점을 구조적으로 해결한 것이 B+ 트리입니다.

5. 해시 파일

탐색키에 해시 함수를 적용해 레코드를 담을 버킷을 정합니다. 등호 검색은 계산 한 번과 블록 접근 한두 번으로 끝납니다.

대신 순서 정보가 없으므로 범위 검색, 정렬 출력, 부분 일치 검색을 할 수 없습니다. WHERE year = 3은 되지만 WHERE year BETWEEN 2 AND 3은 버킷 전부를 뒤져야 합니다. 버킷이 차면 오버플로 체인이 생기고, 데이터가 늘어날 때 버킷 수를 어떻게 늘릴지가 과제로 남습니다.

6. 네 가지 비교

7. 파일 내 클러스터링과 파일 간 클러스터링

클러스터링(clustering)은 함께 읽힐 레코드를 물리적으로 가까이 두는 것입니다. 블록 단위로 읽으므로, 같은 블록에 있으면 한 번의 접근으로 따라옵니다.

• 파일 내 클러스터링: 한 릴레이션 안에서 특정 애트리뷰트 값이 같은 레코드를 인접하게 둡니다. student를 dept_id 순으로 저장하면 같은 학과 학생이 같은 블록에 모입니다.
• 파일 간 클러스터링: 서로 다른 릴레이션의 연관된 레코드를 같은 블록에 섞어 둡니다. 학과 레코드 바로 뒤에 그 학과 소속 학생 레코드를 두는 식입니다. 조인 비용은 줄지만 student만 훑는 질의는 쓸데없이 학과 레코드까지 읽게 됩니다.

-- SQL Server: 테이블 자체를 이 순서로 저장
CREATE CLUSTERED INDEX ix_student_dept ON student(dept_id);

-- PostgreSQL: 일반 인덱스를 만든 뒤 한 번 재배치
CREATE INDEX ix_student_dept ON student(dept_id);
CLUSTER student USING ix_student_dept;

두 문장은 겉보기와 달리 다른 일을 합니다. PostgreSQL의 CLUSTER는 일회성 작업이라 이후의 갱신은 그 순서를 따르지 않고, 원하면 명령을 주기적으로 다시 실행해야 합니다. SQL Server의 클러스터형 인덱스는 저장 구조 자체라 계속 유지됩니다.

주소를 사람이 직접 설정하면 두 가지가 곤란합니다. 같은 주소를 두 대에 잘못 줘서 충돌이 나고, 노트북처럼 네트워크를 옮겨 다니는 기기는 옮길 때마다 다시 설정해야 합니다. 게다가 전체 기기 수만큼 주소를 영구히 예약해두면 켜지지 않은 기기 몫까지 주소를 낭비하게 됩니다.

DHCP(Dynamic Host Configuration Protocol, 동적 호스트 구성 프로토콜)는 접속하는 순간 주소를 빌려주는 방식으로 이를 해결합니다. 핵심은 lease(임대)입니다. 주소를 영구히 주는 것이 아니라 기간을 정해 빌려주고, 기간이 끝나면 회수해 다른 기기에 줍니다. 켜져 있는 기기 수만큼의 주소만 있으면 됩니다.

받는 것은 주소 하나가 아닙니다. 보통 네 가지가 함께 옵니다.

• 할당받은 IP 주소와 임대 기간
• subnet mask, 즉 어디까지가 같은 서브넷인지
• 기본 게이트웨이(first-hop 라우터)의 주소
• DNS 서버의 주소

이 네 가지가 있어야 비로소 통신이 됩니다. 주소만 있고 게이트웨이를 모르면 서브넷 밖으로 나갈 수 없기 때문입니다.

2. DORA 시나리오

과정은 네 단계이고 머리글자를 따 DORA라고 부릅니다.

DHCP는 UDP를 씁니다. 서버는 67번, 클라이언트는 68번 포트입니다. TCP를 쓸 수 없는 이유는 분명합니다. 연결을 맺으려면 주소가 필요한데 지금 그 주소를 받으러 가는 중이기 때문입니다.

DISCOVER가 broadcast인 것도 같은 이유입니다. 출발지 주소로 쓸 것이 없어 0.0.0.0을 쓰고, 서버 주소도 모르니 255.255.255.255로 뿌립니다.

두 단계로 끝나지 않고 네 단계인 것은 서버가 여러 대일 수 있기 때문입니다. 여러 OFFER가 오면 클라이언트가 하나를 골라야 하고, REQUEST는 그 선택을 모든 서버에게 알리는 역할을 합니다. 선택받지 못한 서버는 제안했던 주소를 회수합니다. 임대 기간이 절반쯤 지나면 클라이언트는 같은 주소를 연장 요청하므로, 계속 쓰는 동안 주소가 바뀌지는 않습니다.

3. MTU: 링크마다 다른 상한

여기서부터는 데이터그램 자체 이야기입니다.

link 계층은 한 번에 실어 나를 수 있는 양에 상한이 있습니다. 이것이 MTU(Maximum Transmission Unit, 최대 전송 단위)이고, 이더넷은 1500바이트입니다. 문제는 이 값이 링크 종류마다 다르다는 점입니다.

network 계층은 경로상의 링크들이 어떤 MTU를 갖는지 미리 알지 못합니다. 그래서 아래 계층 사정은 모르는 채로 데이터그램을 내려보냅니다. 그러다 자기 MTU보다 큰 데이터그램을 내보내야 하는 라우터를 만나면 선택지는 둘뿐입니다. 버리거나, 쪼개거나.

IPv4는 쪼개는 쪽을 택했습니다.

4. fragmentation 계산

4000바이트짜리 데이터그램이 MTU 1500인 링크를 만난 경우를 계산해보겠습니다. 헤더 20바이트를 빼면 원본 데이터는 3980바이트이고, 각 조각도 헤더 20바이트를 가지므로 데이터는 최대 1480바이트까지 실을 수 있습니다.

주목할 점이 두 가지입니다.

첫째, offset이 185와 370인 것은 fragment offset 필드가 8바이트 단위로 세기 때문입니다. 1480번째 바이트는 1480 ÷ 8 = 185로 기록됩니다. 13비트밖에 안 되는 필드로 65535바이트 범위를 가리켜야 해서 나온 절충입니다. 그래서 마지막이 아닌 조각의 데이터 크기는 반드시 8의 배수여야 합니다.

둘째, 세 조각 모두 identification 값이 같고 MF 비트로 끝인지 아닌지를 구분합니다. 마지막 조각만 MF가 0이고 offset이 0이 아니므로, 수신 측은 "offset이 0인 조각"과 "MF가 0인 조각"을 양 끝으로 삼아 범위를 복원합니다.

5. reassembly는 목적지에서만

조립은 최종 목적지 호스트에서만 합니다. 조각들이 서로 다른 경로를 탈 수 있어 중간 라우터가 전부를 본다는 보장이 없고, 조립에 필요한 버퍼와 타이머를 코어에 두지 않겠다는 설계 방침 때문입니다.

한 번 쪼개진 조각이 더 작은 MTU를 만나면 다시 쪼개집니다. 조각의 조각도 결국 목적지에서 한 번에 조립되므로 문제는 없습니다.

프로그램을 컴파일하면 주소가 0번지부터 시작합니다. 그런데 실제 메모리에는 다른 프로그램들도 올라가 있으므로 0번지에 놓일 리가 없습니다. 주소가 두 종류라는 뜻입니다.

• 논리 주소(logical address): 프로세스마다 독립적으로 갖는 주소 공간. 모든 프로세스가 0번지부터 시작합니다. 가상 주소라고도 합니다
• 물리 주소(physical address): 메모리에 실제로 올라가는 위치

CPU가 내보내는 주소는 항상 논리 주소입니다. 따라서 메모리에 닿기 전에 누군가 물리 주소로 바꿔 줘야 합니다.

2. 주소 바인딩

논리 주소를 물리 주소로 결정하는 일을 주소 바인딩(address binding)이라고 합니다. 언제 결정하느냐에 따라 셋으로 나뉩니다.

compile time binding은 물리 주소가 컴파일 시점에 박히므로, 그 자리가 비어 있지 않으면 실행할 수 없습니다. 지금 쓰는 시스템은 모두 execution time binding입니다. 실행 도중에도 프로세스를 다른 위치로 옮길 수 있어야 하기 때문인데, 매 주소 접근마다 변환이 필요하므로 하드웨어 지원이 필수입니다.

3. MMU

그 하드웨어가 MMU(Memory Management Unit)입니다. 레지스터 두 개를 씁니다.

• relocation register: 이 프로세스가 올라간 물리 메모리의 시작 주소
• limit register: 이 프로세스가 쓸 수 있는 주소 공간의 크기

변환 규칙은 "논리 주소에 시작 주소를 더한다"입니다. 여기에 더해, 남의 영역을 침범하지 않는지 limit register로 검사합니다.

작은 예제

relocation register가 14000, limit register가 3000입니다.

1. CPU가 논리 주소 346을 내보냅니다
2. 346 < 3000이므로 범위 안입니다
3. 346 + 14000 = 14346번지에 접근합니다
4. 이번엔 CPU가 논리 주소 3500을 내보냅니다
5. 3500 >= 3000이므로 자기 영역 밖입니다. MMU가 trap을 걸어 운영체제로 제어를 넘기고, 운영체제는 대개 그 프로세스를 강제 종료합니다

mode bit이 권한을 막았다면, limit register는 영역을 막습니다. 둘 다 소프트웨어가 아니라 하드웨어가 검사한다는 점이 같습니다.

4. 메모리를 아끼는 기법들

메모리는 늘 부족하므로 "안 쓰는 것은 안 올린다"는 아이디어가 여러 형태로 나옵니다.

swapping에서는 주소 바인딩 방식이 바로 문제가 됩니다. compile time이나 load time binding이면 swap in할 때 원래 있던 자리로만 돌아갈 수 있습니다. execution time binding이면 아무 빈 자리에나 올리면 됩니다.

5. 연속 할당과 분할 방식

메모리는 크게 운영체제 상주 영역과 사용자 프로세스 영역으로 나뉩니다. 사용자 영역을 어떻게 나눠 주느냐에서 갈립니다.

• 연속 할당(contiguous allocation): 프로세스를 메모리의 연속된 한 덩어리에 올립니다
• 불연속 할당(noncontiguous allocation): 프로세스를 여러 조각으로 나눠 흩어진 위치에 올립니다

연속 할당은 다시 둘로 나뉩니다.

6. 두 종류의 조각

조각(fragmentation)은 쓸 수 있는데 쓰이지 못하는 메모리입니다. 생기는 자리가 다릅니다.

• 외부 조각(external fragmentation): 분할들 사이사이에 남은 공간. 전부 합치면 충분한데 연속되지 않아 쓸 수 없습니다
• 내부 조각(internal fragmentation): 할당된 분할 안쪽에 남은 공간. 10MB 영역에 7MB 프로세스를 넣으면 3MB가 쓰이지 못한 채 묶입니다

고정분할은 정해진 칸에 넣으므로 내부 조각이 생기고, 가변분할은 딱 맞게 주므로 내부 조각은 없지만 프로세스가 빠져나간 자리에 외부 조각이 생깁니다.

7. 어느 자리에 넣을 것인가

가변분할에서 비어 있는 공간을 hole이라고 합니다. 크기가 제각각인 여러 hole 중 어디에 넣을지 고르는 문제를 dynamic storage allocation problem이라고 하며, 전략이 셋입니다.

어느 전략을 써도 외부 조각은 남습니다. 흩어진 조각을 한쪽으로 몰아 하나의 큰 공간으로 만드는 작업이 compaction인데, 실행 중인 프로세스를 옮기는 일이라 비용이 매우 크고 execution time binding일 때만 가능합니다.

결국 연속 할당으로는 한계가 있습니다. 프로세스를 잘게 나눠 흩어진 자리에 올리면 외부 조각 문제가 사라지는데, 이것이 paging과 segmentation입니다.