TIL — Storage Systems & Linked List Deep Dive

1. 디스크 구조 (Magnetic Disk)

1-1. 기본 구성

디스크는 여러 플래터(Platter) 로 구성된다. 각 플래터의 한 면에는 트랙(Track) 이 있고, 트랙은 다시 섹터(Sector) 단위로 나뉜다 (보통 512B ~ 4KB).

플래터 1면 = 여러 트랙
트랙 1개 = 여러 섹터

섹터는 트랙의 일부이며, 트랙은 섹터로 나뉜다. 반대는 아니다.

1-2. 실린더(Cylinder)

여러 플래터에서 동일 반지름 위치의 트랙을 묶은 것을 말한다. 이를 통해 헤드가 같은 위치에서 여러 플래터를 동시에 읽을 수 있다.

1-3. 논리적 디스크 블록 (Logical Block Addressing)

운영체제는 디스크의 물리 구조를 알 필요가 없다. 단지 0 ~ N-1 범위의 블록 번호(LBA)만 다룬다. 물리적 변환은 디스크 컨트롤러(Controller) 가 처리한다. 결과적으로 디스크는 운영체제 입장에서 1차원 배열처럼 보인다.

1-4. 디스크 오버헤드의 기원

이 두 가지 물리적 지연이 오버헤드(Overhead)의 출발점이다. 이후 CPU 캐시 미스, 네트워크 지연 등에도 같은 개념이 확장됐다.

2. 플래시 메모리 (Flash Memory)

2-1. 기본 특성

• 비휘발성 저장 매체 (전원이 꺼져도 데이터 유지)
• 전자를 Floating Gate에 저장하여 0/1을 표현
• 읽기는 빠르지만 삭제는 블록 단위로만 가능
• 쓰기는 덮어쓰기가 불가능하므로 새 블록에 기록 후, 낡은 블록은 나중에 정리된다.

2-2. NAND vs NOR 비교

NOR은 코드 저장에 적합하고, NAND는 데이터 저장에 적합하다.

2-3. NOR Flash의 한계

• 각 셀마다 주소선이 직접 연결되어 접근 속도는 빠르지만, 배선 수가 많아 집적도가 낮다.
• 덮어쓰기가 불가능하므로 항상 블록 단위로 지워야 한다. 따라서 NOR은 읽기 위주의 코드 저장용으로 사용된다.

3. FTL (Flash Translation Layer)

3-1. 개념

FTL은 NAND Flash에 포함된 것이 아니라, SSD나 eMMC의 컨트롤러 펌웨어 내부에 존재하는 소프트웨어 계층이다.

[Host OS]
   ↓ (LBA 요청)
[Flash Controller (FTL)]
   ↓ (물리 주소 변환)
[NAND Flash Chips]

운영체제의 논리적 블록 요청을 실제 물리 블록으로 변환한다.

3-2. 주요 역할

3-3. Wear-Leveling

자주 쓰이는 블록만 손상되는 현상을 방지하기 위해 FTL은 쓰기 요청을 자동으로 분산시킨다. 이 과정은 운영체제가 아닌 FTL이 담당한다.

3-4. Garbage Collection

1. 새 데이터는 항상 새로운 블록에 기록된다.
2. 기존 블록은 유효/무효로 구분된다.
3. 무효 블록은 FTL이 주기적으로 정리하여 재활용한다.

SSD가 시간이 지나면서 느려지는 이유는 이 정리 과정과 wear-leveling이 동시에 일어나기 때문이다.

4. Linked List & Pointer

4-1. 정렬 삽입 로직

정렬된 단일 연결 리스트에 새로운 값을 삽입하고, 삽입된 노드의 인덱스를 반환한다.

int insertSortedLL(LinkedList* list, int value) {
    Node* newNode = createNode(value);
    Node* curr = list->head;
    Node* prev = NULL;
    int index = 0;

    while (curr && curr->data < value) {
        prev = curr;
        curr = curr->next;
        index++;
    }

    if (!prev) { // 맨 앞 삽입
        newNode->next = list->head;
        list->head = newNode;
    } else { // 중간 또는 끝 삽입
        prev->next = newNode;
        newNode->next = curr;
    }

    return index;
}

4-2. 포인터 연결 순서

[A] → [B]
   ↓
[A] → [C] → [B]

1. C의 next를 B로 연결
2. A의 next를 C로 연결

4-3. Double Pointer

새 노드를 head로 삽입할 때는 *ptrHead = newNode; 로 접근해야 한다.

4-4. 안전한 순회

while (curr != NULL) {
    // ...
    curr = curr->next;
}

curr->next 접근 전에 반드시 curr != NULL을 확인해야 한다. 그렇지 않으면 segmentation fault가 발생한다.

4-5. 시간 복잡도

5. 핵심 요약

6. 느낀 점

• 오버헤드라는 개념이 물리적 디스크 지연에서 출발했다는 점이 인상 깊었다.
• NOR과 NAND의 구조적 차이는 단순한 속도 차이가 아니라, CPU 직접 실행 가능 여부로 이어진다.
• Linked List 삽입 로직을 직접 구현하면서 포인터가 연결 구조의 핵심이라는 사실을 명확히 이해했다.
• FTL의 구조를 통해 SSD 내부 동작이 어떻게 추상화되는지 구체적으로 파악할 수 있었다.