상위 수준 설계 패턴

상위 수준 소프트웨어 설계 패턴:

• 계산-데이터 이중성.
• 변경-데이터 이중성.
• 부분 계산과 다단계 계산.
• 일반화된 뷰.
• 불변식의 생성, 성장, 유지.

이러한 패턴과 아이디어는 종종 깊게 연결되어 함께 사용된다.

계산-데이터 이중성​

두 가지 측면이 있다:

• 계산(로직과 행동)을 데이터로 바꾼다.
• 실행 상태를 명시적인 데이터로 바꾼다.

계산(로직과 행동)을 데이터로 바꾸는 이점:

• 클로저(람다 식, 함수 값). 캡처된 데이터를 동반한 함수. 코드 조각과 캡처 데이터를 함께 재사용할 수 있게 한다. 추상화에 도움을 준다: 계산의 생성(함수 값 생성)과 계산의 실행(함수 실행)을 분리한다. (부분 계산과 다단계 계산과 연관됨)
• 합성. 데이터로 전환된 계산은 더 쉽게 합성할 수 있다. 함수형 프로그래밍은 간단한 빌딩 블록을 갖고 이를 합성해 복잡한 로직을 만들 것을 장려한다.
• 유연성. 데이터로 전환된 계산은 동적으로 변경 및 재구성할 수 있다.

실행 상태를 명시적인 데이터로 바꾸는 이점:

• 관찰: 명시적 실행 상태는 관찰·표시가 쉽다(머신 코드는 최적화되고 플랫폼 의존적이므로, 머신 코드의 실행 위치와 런타임 스택은 명시적 데이터보다 관찰·조작이 더 어렵다)
• 직렬화: 명시적 실행 상태는 직렬화/역직렬화가 가능하여 데이터베이스에 저장하거나 네트워크로 전송할 수 있다. (예: Restate)
• 중단: 명시적 실행 상태는 실행을 일시 중단하고 나중에 재개할 수 있게 한다. 스레드 중단은 더 어렵고 덜 효율적이다 1.
• 수정: 명시적 실행 상태는 수정할 수 있다. 취소와 롤백을 쉽게 만든다. (실행 스택과 실행 상태를 수정하는 것은 어렵고, 많은 주류 언어는 이를 지원하지 않는다.)
• 분기 복제: 제어 흐름의 분기를 복제할 수 있어, 일부 종류의 시뮬레이션에 유용하다.

계산과 실행 상태의 구분은 모호하다. 클로저는 데이터를 캡처한다. 실행 상태는 또한 계산인 컨티뉴에이션으로 볼 수 있다.

대수적 효과와 경계된 컨티뉴에이션​

대수적 효과(Algebraic effect): 이펙트 핸들러는 어떤 코드 범위(scope)에서 코드를 실행한다. 이펙트 핸들러 아래에서 코드가 실행될 때, 그 코드가 이펙트를 수행하면 제어 흐름이 이펙트 핸들러로 점프하고, 이펙트 핸들러의 스코프까지의 실행 상태(경계된 컨티뉴에이션)가 저장된다. 이펙트 핸들러는 그 실행 상태를 사용해 재개(resume)할 수 있다. 대수적 효과에 대한 간단한 소개

**경계된 컨티뉴에이션(delimited continuation)**은 데이터로 전환된 실행 상태다. "경계된"이라는 말은 실행 상태에 이펙트 처리 스코프 내의 스택프레임만 포함되기 때문이다.

"경계되지 않은" 컨티뉴에이션은(단일 스레드를 가정한) 프로그램 전체의 실행 상태를 담는다. 경계된 컨티뉴에이션은 "로컬"이고, 컨티뉴에이션은 "글로벌"이다. "로컬"한 것이 더 세밀하고 유용하다.

**컨티뉴에이션 전달 스타일(CPS)**은 프로그램을 표현하는 방식이다. CPS에서는 각 함수가 컨티뉴에이션을 인자로 받는다. 반환은 컨티뉴에이션을 호출하는 것이 된다. 컨티뉴에이션을 호출하는 것은 실행을 계속하는 것이다. 컨티뉴에이션의 출력은 "프로그램 전체의 최종 출력"이다(만약 IO나 가변 상태가 관여하면, "프로그램 전체의 최종 출력"은 비어 있을 수도 있다).

DSL을 너무 멀리 가지 말라​

참고: Configuration complexity clock

다양한 비즈니스 요청을 처리하려 할 때, 하나의 해법은 유연한 규칙 엔진을 만드는 것이다. 규칙 엔진을 구성하여 모든 요청을 처리할 수 있다.

하지만 여기에는 뚜렷한 트레이드오프가 있다:

• 규칙 엔진의 추상화 수준이 높아, 미리 정의된 많은 일을 내부에서 처리한다면: 새 요구가 미리 정의된 동작과 충돌할 때 적응력이 떨어진다. 단순한 인터페이스 = 하드코딩된 기본값 = 낮은 사용자 정의 가능성.
• 규칙 엔진의 추상화 수준이 낮다면, 일을 하려면 더 많은 구성이 필요하다. 그냥 코딩하는 것보다 편하지 않다. 새로운 DSL이 된다. 새로운 DSL은 흔히 주류 언어보다 열악한데, 그 이유는:
  • 새 DSL은 디버그 지원이 빈약한 경우가 많다.
  • 새 DSL은 IDE 지원이 없는 경우가 많다.
  • 기존 라이브러리 생태계가 없다. 바퀴를 재발명해야 한다.
  • 새 DSL은 실전 검증이 부족하고 버그가 더 많다.

DSL은 추상화 수준이 높고, 새 요구가 대부분 그 추상화를 따를 때 유용하다.

호출을 데이터로 대체하기​

시스템 호출은 비싸다. 시스템 호출을 데이터로 대체하면 성능을 높일 수 있다:

• io_uring: 많은 IO 작업을 메모리에 써 넣어 두고, 시스템 호출 한 번으로 일괄 제출한다. 2
• 그래픽스 API: 오래된 OpenGL은 시스템 호출로 상태를 바꾸고 드로우 콜을 디스패치했다. Vulkan, Metal, WebGPU 같은 최신 그래픽스 API는 모두 커맨드 버퍼를 사용한다. 연산을 커맨드 버퍼의 데이터로 만들어두고, 시스템 호출 한 번으로 많은 명령을 제출한다.

변경-데이터 이중성​

변경(mutation)은 데이터로 표현될 수 있다. 데이터는 변경으로 해석될 수 있다.

• 제자리 변경만 하는 대신, 나중에 변경을 수행하기 위한 명령(또는 이벤트)을 큐잉할 수 있다. 그 명령이 처리되어 실제 변경이 수행된다. (이는 또한 계산을 단계 간에 이동시키는 것이다)
• 레이어드 파일시스템(Docker). 파일을 변경하거나 추가하는 것은 새 레이어를 만드는 것이다. 변하지 않은 이전 레이어는 캐시·재사용된다.
• 이벤트 소싱. 최신 상태를 일련의 이벤트(로그, 변경)로부터 유도한다. 최신 상태를 오래된 상태 + 변경의 뷰로 표현한다. 이 아이디어는 데이터베이스 WAL, 데이터 복제, 람다 아키텍처 등에 채택되었다.
• CQRS(Command Query Responsibility Segregation). 시스템은 두 개의 파사드를 가진다: 조회 파사드는 변경을 허용하지 않고, 명령 파사드는 명령만 받으며 데이터를 주지 않는다.

이점:

• 변경이 암묵적 실행 이력이 아니라 명시적 데이터이므로, 변경을 관찰·감사·디버깅하기 쉽다. 감사와 재생(replay)이 쉽다.
• 변경을 재생하고 롤백하기 쉽다.
• 전체 데이터를 보내지 않고도 데이터 변경을 복제(동기화)할 수 있다.

롤백​

롤백에 관해:

• 트랜잭션 데이터베이스는 커밋되지 않은 트랜잭션을 롤백할 수 있다. (MySQL InnoDB는 디스크에서 제자리 변경을 하지만 undo/redo 로그를 쓴다. PostgreSQL의 MVCC 쓰기는 디스크에 append-only다.)
• 편집 소프트웨어는 종종 되돌리기(undo)를 지원해야 한다. 이전 단계의 데이터를 저장하되, 변하지 않은 하위 구조를 공유하여 최적화하는 방식으로 구현되는 경우가 많다.
• 서버 상태 예측으로(가시적 레이턴시를 줄이기 위해) 동작하는 멀티플레이어 게임 클라이언트는 서버 메시지로 예측이 틀렸을 때 롤백해야 한다.
• CPU는 분기 예측과 투기 실행을 한다. 분기 예측 실패나 기타 실패가 있으면 내부적으로 롤백한다. (스펙터 취약점과 멜트다운 취약점은 롤백이 캐시의 부수효과를 취소하지 않아, 접근 속도 차이로 측정될 수 있기 때문에 발생한다.)

때로는 사용자 경험을 개선하기 위해, 롤백 대신 충돌한 변경을 재적용(replay)해야 한다. 이는 더 복잡하다.

디프 계산(diffing)​

어떤 곳에서는 새로운 상태를 지정하고, 그 변경(디프)을 계산해야 한다. 예:

• Git. 파일 스냅샷을 기반으로 디프를 계산한다. 그 디프는 이후 조작(예: 병합, 리베이스, 체리픽)에 사용될 수 있다.
• React. 가상 데이터 구조에서 디프를 계산해 실제 DOM에 적용한다. 가상 데이터 구조의 변경을 실제 DOM과 동기화한다.
• Kubernetes. 어떤 파드/볼륨/...이 존재해야 하는지를 구성한다. Kubernetes는 현실과 구성 간의 디프를 관찰하고, 디프를 메우기 위해(예: 새 파드 시작, 파드 제거) 동작한다.

재생성에 의한 변경(mutate-by-recreate)​

Mutate-by-recreate: 데이터를 불변으로 유지한다. 전체 데이터를 다시 만들어 바꾼다.

멀티스레딩에서 읽기 위주의 데이터는, 데이터 구조를 불변으로 만들고 그에 대한 하나의 가변 원자적 참조만 유지하는 것이 종종 유리하다. 업데이트는 전체 데이터 구조를 재생성하고 참조를 원자적으로 바꾼다. 이를 RCU(read-copy-update) 또는 COW(copy-on-write)라고 한다.

순수 함수형 언어(예: Haskell)에서는 직접적으로 변경하는 방법이 없다. 변경은 재생성으로만 시뮬레이션할 수 있다.

이중 시간 모델링(bitemporal modelling)​

이중 시간 모델링: 두 종류의 기록을 저장한다. 하나는 데이터베이스에 데이터가 업데이트된 시각을 기록하고, 다른 하나는 현실을 반영하는 데이터와 시각을 기록한다. (때로는 현실이 변하지만 데이터베이스가 즉시 수정되지 않는다. 때로는 데이터베이스가 잘못된 정보를 담고 있다가 나중에 수정된다.)

충돌-자유 복제 데이터 타입(CRDT)​

CRDT(Conflict-free replicated data type): 변경들을 결합할 수 있고, 결합 순서에 결과가 의존하지 않는다. 즉각적인 통신 없이도 분산 시스템에서 최종적(eventual) 일관성을 달성할 수 있게 한다.

CRDT에서, 변경을 결합하는 연산 ∗*는 다음을 만족해야 한다:

• 교환법칙: a∗b=b∗a a * b = b * a. 결합 순서는 중요하지 않다.
• 결합법칙: a∗(b∗c)=(a∗b)∗c a * (b * c) = (a * b) * c. 결합 순서는 중요하지 않다.
• 멱등성: a∗a=a a * a = a. 변경을 중복 적용해도 결과가 변하지 않는다. (정확히 한 번 전달을 보장한다면 멱등성은 필요 없다.)

CRDT의 예시:

CRDT: 마지막 쓰기 우선​

예를 들어 멀티플레이어 게임에 문이 있고, 상태는 열림/닫힘(불리언)이라고 하자.

각 연산은 (timestamp, doorState)의 튜플이다. 결합은 타임스탬프 기준 최대값 선택(두 연산 중 더 큰 타임스탬프의 것을 선택)이다.

여러 플레이어가 정확히 같은 타임스탬프에 연산할 수 있으므로, **동률 해결자(tie-breaker)**로 플레이어 ID를 추가한다. 이제 연산은 (timestamp, playerId, doorState)가 된다. 결합은 (timestamp, playerId)의 튜플 기준 최대값 선택이다. timestamp가 같으면 더 큰 playerId가 이긴다.

일반적인 멀티플레이 게임 구현은 CRDT를 사용하지 않는다는 점에 유의하자. 서버가 진실의 원천인 게임 상태를 갖는다. 클라이언트는 동작을 서버에 보내고, 서버는 동작을 검증한 뒤 게임 상태를 바꾸고 이를 모든 클라이언트에 브로드캐스트한다.

CRDT: 더 낮은 깊이가 이김​

프레임버퍼에 실삼각형을 그리는 것도 CRDT로 볼 수 있다.

프레임버퍼 전체를 하나의 연산으로 볼 수 있다. 프레임버퍼의 각 픽셀은 깊이 값을 가진다. 두 프레임버퍼를 결합할 때, 같은 위치의 두 픽셀에 대해 더 낮은 깊이의 것을 택한다.

(두 프레임버퍼가 같은 픽셀에서 깊이가 같고 색이 다를 수 있다. 고유 삼각형 ID를 동률 해결자로 사용할 수 있다.)

실제 GPU 래스터화는 CRDT를 쓰지 않고 하나의 중앙집중식 프레임버퍼로 동작한다는 점에 유의하자.

CRDT: 협업 텍스트 편집​

협업 텍스트 편집 시스템에서 각 문자는 ID를 가진다. 두 가지 연산을 지원한다:

• 삽입: insertAfter(charId, timestamp, userId, charToInsert, newCharId)는 ID가 charId인 문자 뒤에 새 문자를 삽입한다. newCharId는 전역적으로 유일하다.
• 삭제: delete(charId)는 문자에 보이지 않음 플래그만 표시한다(무덤표시 tombstone을 유지한다).

문서 시작에 "루트 문자"가 있다. 이는 보이지 않으며 삭제할 수 없다.

같은 문자 뒤에 대한 두 삽입의 동률 해결자는 (timestamp, userId)이다. 더 큰 타임스탬프가 먼저 나타난다. 같은 타임스탬프에서는 더 큰 사용자 ID가 먼저 나타난다.

이는 트리를 이룬다. 각 문자는 노드이며, 가시성 불리언 플래그를 가진다. 각 insertAfter 연산은 새 문자로 향하는 간선이다. 문서는 트리를 깊이 우선 순회(간선 순서는 동률 해결자 기준)하며 보이지 않는 문자를 숨기면서 형성된다. 34

부분 계산과 다단계 계산​

데이터의 일부만 계산하고, 남아 있는 계산에 관한 정보를 미래 사용을 위해 유지한다.

• 게으른 평가에서는 관측되지 않은 데이터는 계산되지 않는다.
• 지연된 변경. 변경-데이터 이중성과 관련됨.
• 즉시 실행되는 코드를 나중에 실행(해석)될 데이터(식 트리, DSL 등)로 바꾼다. 계산-데이터 이중성과 관련됨.
• 다단계 프로그래밍에서는 일부 데이터는 고정이고 일부 데이터는 미지수다. 고정 데이터는 최적화에 사용될 수 있다. 이는 런타임 상수 값 폴딩으로 볼 수 있다. JIT은 바이트코드를 런타임 상수로 취급하고 인터프리터 코드에서 폴딩하는 것으로 볼 수 있다.
• 값을 함수나 식 트리로 대체하면 현재는 미지인 데이터를 다루는 데 도움이 된다.
• 대기 중인 계산을 표현하기 위해 future(프로미스) 객체를 사용한다.
• Idris에서는 구멍(hole)을 두고 그 타입을 검사하는 것이 증명에 도움이 될 수 있다.

관련: I'm not mutable, I'm partially instantiated

지연(비동기) 계산 vs 즉시 계산:

• 즉시 메모리를 해제하는 것은 즉시 계산이다. GC는 지연 계산이다.
• 스트림 처리(Stream processing)는 즉시 계산이다. 배치 처리는 지연 계산이다.
• PyTorch의 대부분의 행렬 연산은 비동기다. GPU가 백그라운드에서 계산한다. 텐서 객체의 내용은 아직 미지일 수 있으며(내용을 읽으려 하면 CPU는 GPU를 기다린다).
• PostgreSQL과 SQLite는 저장 공간을 재배치하는 지연된 "vacuum"이 필요하다.
• 모바일 GPU는 종종 타일 기반 렌더링을 한다. 버텍스 셰이더가 실행된 후, 삼각형은 즉시 래스터화되지 않고 타일로 디스패치된다(하나의 삼각형이 여러 타일로 갈 수 있다). 각 타일이 분리되어 래스터화하고 픽셀 셰이더를 실행한다. 이는 메모리 대역폭 요구와 전력 소모를 줄일 수 있다.

프로그램 수명주기​

계산, 최적화, 안전성 검사는 다음 시점에 수행될 수 있다:

• 사전 컴파일 단계. (코드 생성, IDE 린팅 등)
• 컴파일 단계. (컴파일 타임 계산, 매크로, 의존 타입 정리 증명 등)
• 런타임 단계. (런타임 검사, JIT 컴파일 등)
• 최초 실행 이후. (오프라인 프로파일 기반 최적화 등)

컴파일 타임에 수행되는 대부분의 계산은 런타임에도 수행할 수 있다(추가 성능 비용과 함께). 하지만 그 비용을 피하려고 컴파일 타임에 하려면 더 어려워진다.

Rust와 C++에는 **정적-동적 이형성(Statics-Dynamics Biformity)**이 있다(참고): 대부분의 런타임 계산 기법을 컴파일 타임에 쉽게 사용할 수 없다. 컴파일 타임 메커니즘을 사용하려면 데이터를 타입으로 인코딩해야 하는 경우가 많고, 이는 타입 곡예(type gymnastics)를 요구한다.

컴파일 타임과 런타임 계산의 이형성을 해결(또는 부분적으로 해결)하는 방법들:

• Zig의 컴파일 타임 계산과 리플렉션. 참고
• 의존 타입 언어(예: Idris, Lean)
• Scala의 다단계 프로그래밍. 참고. 이는 컴파일 타임이 아니라 런타임이지만 목적은 매크로나 코드 생성과 유사하다. 런타임에 동적으로 코드를 합성하고 JIT의 대상이 되게 한다.

미지 값 또는 중첩(superposition)에 대한 실행​

관련:

• 심볼릭 실행
• 중첩(superposition)을 이용한 프로그램 탐색

일반화된 뷰​

SQL 데이터베이스의 뷰는 쿼리의 결과를 나타내는 "가짜" 테이블이다. 뷰의 데이터는 다른 테이블(또는 뷰)로부터 파생된다.

뷰의 일반화된 개념: 뷰는 하나의 정보 모델을 받아 다른 정보 모델로 표현하고, 그 다른 정보 모델처럼 조작을 가능하게 한다.

일반화된 뷰는 다음처럼 이해할 수 있다:

• 정보를 캡슐화한다. 실제 기저 정보를 숨기고 파생 정보만 노출한다.
• 정보를 "가짜로" 만든다.

일반화된 뷰 개념의 예:

• 비트는 회로의 전압에 대한 뷰다. 5
• 정수는 비트에 대한 뷰다.
• 문자는 정수에 대한 뷰다. 문자열은 문자에 대한 뷰다. 6
• 다른 복잡한 데이터 구조는 이진 데이터에 대한 뷰다. (포인터는 가리키는 데이터에 대한 뷰로 볼 수 있다)
• 맵(딕셔너리)은 함수로 볼 수 있다.
• 조회 가속화 구조(예: 데이터베이스 인덱스) 역시 기저 데이터에 대한 뷰다.
• 캐시는 기저 데이터/계산에 대한 뷰다.
• 게으른 평가는 계산 결과에 대한 뷰를 제공한다.
• 가상 메모리는 물리 메모리에 대한 뷰다.
• 파일 시스템은 디스크의 데이터에 대한 뷰다. 디스크에 없는 데이터도 파일처럼 볼 수 있다(유닉스의 everything-is-file 철학).
• 파일 시스템의 심볼릭 링크는 파일 시스템 내 다른 지점에 대한 뷰다.
• 데이터베이스는 디스크/메모리 상의 데이터에 대한 일반화된 뷰를 제공한다.
• 리눅스 네임스페이스, 하이퍼바이저, 샌드박스 등은 시스템의 여러 측면에 대한 뷰를 제공한다.
• 프록시, NAT, 방화벽, 가상화된 네트워킹 등은 조작된 네트워크 뷰를 제공한다.
• 데이터베이스의 트랜잭션 격리는 데이터에 대한 뷰를 제공한다(예: 스냅샷 격리).
• 복제 데이터와 중복 데이터는 원본 데이터에 대한 뷰다.
• 다단계 스토리지 시스템. 작고 빠른 것부터 크고 느린 것까지: 레지스터, 캐시, 메모리, 디스크, 클라우드 스토리지.
• 앞서 언급한 계산-데이터 이중성과 변경-데이터 이중성도 뷰잉(viewing)으로 볼 수 있다.
• PyTorch에서 전치(transpose)는(기본적으로) 기저 행렬 데이터를 바꾸지 않는다. 데이터가 어떻게 보이는지만 바꾼다.

더 일반적으로:

• 이진 데이터와 정보 간 매핑이 곧 뷰다. 정보는 비트+문맥이다. 문맥은 비트가 정보로 매핑되는 방식이다. 타입은 이진 데이터에서 정보로의 뷰잉을 담는다.
• 추상화는 서로 다른 것들을 같은 것으로 보이게 하는 것을 포함한다.

동적 타입 언어에도 "타입"이 있다​

동적 타입 언어에도 "타입"이 있다. 여기서의 "타입"은 메모리 내 데이터와 정보 간의 매핑이다.

동적 언어에서도, 데이터는 런타임에 여전히 "모양(shape)"을 가진다. 프로그램은 특정 "모양"의 데이터에 대해서만 정상 동작한다.

예를 들어, 파이썬에서 어떤 함수가 문자열 배열을 받도록 되어 있는데 문자열 하나를 넘기면, 각 문자를 문자열로 취급해 버려 잘못된다.

주류 언어의 타입 시스템은 비교적 더 단순하고 표현력이 낮은 경우가 많다. 어떤 데이터의 "모양"은 복잡하여 주류 언어의 타입 시스템으로는(타입 소거 없이) 쉽게 표현할 수 없다.

동적 언어의 장점:

• 표현력이 낮은 타입 시스템의 속박을 피한다.
• 타입 소거와 관련된 문법상의 불편을 피한다(타입 언어의 타입 소거는 형변환 같은 불편을 요구한다).
• 프로그램의 한 부분을 바꾸며 빠르게 반복할 수 있다. 다른 부분과의 호환이 맞기 전에라도(정적 타입 언어에서는 지금 사용하지 않는 코드의 컴파일 에러도 모두 해결해야 한다). 이는 양날의 검이다. 테스트되지 않은 깨진 코드는 놓치기 쉽다.
• 타입과 타입 정의를 적는 데 드는 시간을 절약한다.

하지만 정적 타입 언어와 IDE도 발전하고 있다. 더 표현력 있는 타입 시스템은 타이핑 마찰을 줄인다. 타입은 실수를 잡아주고, 코드를 이해하는 데 도움을 주며, IDE 기능에도 도움을 준다. 타입 추론과 IDE 완성은 타입을 입력하는 시간을 절약해 준다. 그래서 주류 동적 언어(JS, Python)도 타입 주석을 받아들이고 있다.

계산-저장소 트레이드오프​

뷰는 저장소나 계산(또는 둘의 조합)으로 뒷받침될 수 있다.

현대의 고도로 병렬적인 계산은 종종 IO와 동기화가 병목이다. 새로운 계산 하드웨어 유닛을 추가하는 것은 쉽다. 이 하드웨어 유닛들 사이로 정보를 효율적으로 흐르게 하는 것이 어렵다.

메모리 IO가 병목이 될 때는, 저장하는 것보다 재계산이 이로울 수 있다.

여러 종류의 "포인터"​

• GC 언어의 레퍼런스. 실제 구현은 포인터, 컬러드 포인터, 핸들(객체 ID)일 수 있다. 이동식 GC에 의해 포인터 값이 바뀔 수 있다. 하지만 언어 차원의 의미론은 이동 후에도 변하지 않는다.

• ID. 문자열 ID, 정수 ID, UUID 등 모든 종류의 ID는 객체에 대한 참조로 볼 수 있다. 참조된 객체가 제거된 후에도 ID가 남아 있으면, 그 ID는 "댕글링 ID"가 된다.

  • 특별한 ID로 경로(path)가 있다. 예를 들어 파일 경로는 파일을, URL은 웹 리소스를, 권한 경로는 권한을 가리킨다. 이들은 계층적(트리형) 구조의 노드로 들어가는 "포인터"다.
  • 내용 주소 가능한 ID. 객체의 해시를 객체의 ID로 사용한다. Git, 블록체인, IPFS, Unison 같은 언어에서 사용된다.

• 이터레이터. 이터레이터는 컨테이너의 한 요소를 가리키는 포인터로 볼 수 있다.

• 지퍼(Zipper). 지퍼는 두가지를 담는다: 1) 구멍이 있는 컨테이너 2) 그 구멍 위치의 요소. 이터레이터와 달리 지퍼는 전체 컨테이너 정보를 담는다. 순수 함수형 언어에서 자주 쓰인다.

• 렌즈(Lens).

불변식의 생성, 성장, 유지​

대부분의 알고리즘은 불변식을 만들어 내고, 키우고, 유지하는 아이디어를 사용한다:

• 불변식 생성. 가장 작은 규모, 가장 단순한 경우에서 불변식을 만든다.
• 불변식 성장. 작은 불변식을 결합하거나 확장해 더 크게 만든다. 이는 종종 추이 규칙을 활용한다. 작업을 끝낼 만큼 불변식이 충분히 커질 때까지 수행한다.
• 불변식 유지. 데이터 구조에 대한 모든 변경은 그 불변식을 유지해야 한다.

추이 규칙에 대하여: X와 Y가 모두 불변식을 따른다면, X와 Y를 "합치는" 결과 또한 불변식을 따른다. "추이적"이기 때문에 불변식을 전체를 다시 검사하지 않고도 키울 수 있다. 불변식이 언어 수준에서 강제되면, 그것은 "전염적"일 수 있다.

알고리즘의 불변식​

• 병합 정렬. 가장 작은 규모에서(예: 두 원소) 정렬된 부분 수열을 만든다. 그런 다음 두 정렬된 부분 수열을 병합해 더 큰 것을 만들고 계속한다. 정렬됨의 불변식이 전체 수열로 성장한다.
• 퀵 정렬. 피벗을 선택한다. 수열을 피벗보다 작은 부분, 큰 부분(그리고 같은 부분)으로 분할한다. 분할함으로써 LeftPartElements<Pivot<RightPartElements\text{LeftPartElements} < \text{Pivot} < \text{RightPartElements}의 불변식을 만든다. 이런 불변식을 가장 작은 규모(개별 원소)까지 재귀적으로 만들면, 전체 수열이 정렬된다.
• 이진 검색 트리. LeftSubtreeElements≤ParentNode≤RightSubtreeElements\text{LeftSubtreeElements} \leq \text{ParentNode} \leq \text{RightSubtreeElements}의 불변식을 만든다. 노드가 하나뿐일 때 가장 작은 규모에서 불변식이 생성된다. 이후의 모든 삽입은 그 불변식을 따르며, 그 불변식을 키우고 유지한다.
• 다익스트라 알고리즘. 방문한 노드들은 시작 노드로부터의 최단 경로가 알려진 노드들이다. 이미 최단 경로를 아는 노드를 사용해 그래프를 "확장"하면서, 새로운 노드의 시작점으로부터의 최단 경로를 알게 된다. 목적지 노드까지 확장될 때까지 알고리즘은 반복적으로 새 노드를 불변식에 추가한다.
• 동적 계획법. 문제를 하위 문제로 분해한다. 하위 문제 간 순환 의존이 없다. 하나의 문제 결과는 하위 문제 결과들로부터 빠르게 계산될 수 있다(예: max, min).
• 해시맵 조회는 hash(a)≠hash(b)\text{hash}(a) \neq \text{hash}(b)가 a≠b a \neq b를 함의하기 때문에 데이터를 건너뛸 수 있다. 정렬된 탐색 트리 조회는 (a<b)∧(b<c)(a < b) \land (b < c)가 a<c a < c를 함의하기 때문에 데이터를 건너뛸 수 있다.
• 병렬화는 종종 결합법칙을 활용한다: a∗(b∗c)=(a∗b)∗c a * (b * c) = (a * b) * c. 예: a∗(b∗(c∗d))=(a∗b)∗(c∗d)a*(b*(cd))=(a * b) * (c * d)에서, a∗b ab와 c∗d c*d는 서로 독립적이므로 병렬로 계산할 수 있다. 예: 합, 곱, 최댓값, 최솟값, 최대 기준(max-by), 최소 기준(min-by), 리스트 연결, 집합 합집합, 함수 합성, 논리 AND, 논리 OR. (항등원을 가진 결합법칙은 모노이드.)
• ......

애플리케이션의 불변식​

예를 들어, 비즈니스 로직의 불변식:

• 사용자 이름은 중복될 수 없다.
• 은행 계좌 잔액은 음수가 되어서는 안 된다. 초과 지출 금지.
• 상품 재고 수량은 음수가 되어서는 안 된다. 초과 판매 금지.
• 호텔의 하나의 방은 시간이 겹치게 두 번 예약될 수 없다.
• 주문이 결제된 후에 상품이 배송되어야 한다.
• 알림은 유실되거나 중복되어서는 안 된다.
• 사용자는 자신의 권한 밖의 정보를 조회·변경할 수 없다.
• 구독이 끝나면 사용자는 기능을 사용할 수 없다.
• ......

데이터의 불변식:

• 중복 데이터, 유도 데이터, 가속화 데이터 구조(인덱스, 캐시)는 기저 데이터(진실의 원천)와 일관되어야 한다.

• 클라이언트 측 데이터는 서버 측 데이터와 일관되어야 한다.

• 메모리 안전 불변식. 포인터는 유효한 데이터를 가리켜야 한다. use-after-free 금지. 한 번만 free. 등등.

• 사용하지 않는 메모리는 해제해야 한다.

• 스레드 안전 불변식.

  • 많은 연산은 3단계를 포함한다: 읽기-계산-쓰기.
  • 다른 스레드가 읽기와 쓰기 사이에 변경하면 오작동한다. 이전 읽기 결과는 더 이상 유효하지 않다.
  • 일부 연산은 더 많은 단계(여러 번의 읽기/쓰기)를 포함한다. 부분적으로 수정된 상태가 노출되면 불변식이 위반된다.
  • 스레드 안전하지 않은 데이터 구조는 스레드 간에 공유되어서는 안 된다.
  • 스레드 안전하지 않은 데이터 구조는 반드시 락 아래에서 접근해야 한다.

• 어떤 후속 동작이 실패하면, 그 전에 수행된 일부 동작의 변경은 취소되어야 한다. (임시 트랜잭션, 애플리케이션 관리 롤백)

불변식 유지하기​

불변식을 유지하는 타이밍:

• 즉시 불변식 유지
• 지연된 불변식 유지(오래된 데이터 허용. 캐시, 배치 처리)

불변식을 유지하는 책임 주체:

• 데이터베이스/프레임워크/OS/언어 등이 불변식을 유지하는 책임을 진다. 예를 들어, 데이터베이스는 인덱스와 물질화 뷰의 유효성을 유지한다. 그들이 버그가 없다면, 불변식은 위반되지 않는다.
• 애플리케이션 코드가 불변식을 유지하는 책임을 진다. 이는 더 오류가 발생하기 쉽다.

두 번째 경우(애플리케이션 코드가 불변식을 유지)에는, 오류 가능성을 낮추기 위해 데이터와 불변식 유지 코드를 캡슐화하고, 캡슐화된 API의 모든 사용이 불변식을 위반하지 않도록 해야 한다. 어떤 API 사용이 불변식을 깰 수 있고 개발자가 구현을 고려해야만 이를 알 수 있다면, 이는 누수된 추상화다.

예를 들어, 일반적인 유지해야 할 불변식은 유도 데이터와 기저 데이터(진실의 원천) 간의 일관성이다. 여러 해결책이 있다:

• 유도 데이터를 항상 요청 시 계산으로 만든다. 더는 수동으로 불변식을 유지할 필요가 없다. 하지만 성능 비용이 들 수 있다.

  • 불변 계산 결과의 캐싱은 이를 더 빠르게 하면서도 요청 시 계산의 의미론을 유지할 수 있다.

• 유도 데이터를 가변 상태로 저장하고 진실의 원천과 수동으로 일관되게 유지한다. 이것이 가장 오류가 발생하기 쉬운 해결책이다. 기저 데이터에 대한 모든 수정은 유도 데이터에 업데이트를 "알려야" 한다. 때로 알림은 함수를 호출하는 것이다. 때로 알림은 네트워킹을 포함한다.

  • 더 복잡한 경우: 유도 데이터가 기저 데이터로 반영되어야 하는 방식으로 수정되어야 한다. 이는 단일 진실의 원천(single source of truth)을 위반한다. 훨씬 더 오류가 발생하기 쉽다.
  • 더더욱 복잡한 경우: 클라이언트 측은 서버 측 데이터 예측으로 가시적 레이턴시를 줄여야 하고, 잘못된 예측은 서버 측 데이터로 수정되어야 한다. 이는 단일 진실의 원천을 위반할 뿐 아니라, 종종 롤백과 재생 메커니즘을 요구한다.

• 앞서 언급한 다른 도구(데이터베이스/프레임워크/OS/언어 등)에 의존해 불변식을 유지한다.

현실의 레거시 코드에서 불변식은 종종 문서화되지 않는다. 코드 속에 암묵적이다. 불변식을 모르는 개발자는 이를 쉽게 깨뜨릴 수 있다.

타입 시스템도 불변식 유지에 도움을 준다. 하지만 단순한 타입 시스템은 단순한 불변식만 유지할 수 있다. 복잡한 불변식을 유지하려면 복잡한 타입이 필요하다. 너무 복잡해지면, 타입이 실행 코드보다 길어지고 타입 에러를 해결하기 어려워진다. 이는 트레이드오프다.

통계적 불변(경향)​

소프트웨어 세계에는 집중과 두꺼운 꼬리(80/20)가 흔하다:

• 대부분의 사용자는 소프트웨어의 몇 가지 공통 기능만 사용한다.
• 대부분의 복잡성(과 버그)은 소수의 기능 요구에서 온다.
• CPU 시간의 대부분은 몇몇 핫 코드 실행에 쓰인다.
• 데이터 접근의 대부분은 소수의 핫 데이터에 집중된다(캐시가 효과적이려면 이게 필요하다).
• 실행에서 대부분의 분기는 한쪽으로 치우친다(분기 예측이 효과적이려면 이게 필요하다).
• 대부분의 개발자는 몇몇 언어, 라이브러리, 프레임워크만 사용한다. (생태계의 마태 효과)
• 대부분의 코드와 개발 노력은 엣지 케이스를 해결하는 데 쓰인다. 주요 케이스 처리는 얼마 되지 않는다. 7
• 사용자가 겪는 버그의 대부분은 소수의 발생하기 쉬운 버그에서 비롯된다.
• 하드웨어의 트랜지스터 중 대부분은 대부분의 시간에 사용되지 않는다. 많은 트랜지스터는 드물게 쓰인다. (많은 트랜지스터는 드물게 쓰이는 명령을 위해 존재한다. 관련 하드웨어 결함은 테스트를 피하기 쉽다. 참고: Silent Data Corruptions at Scale, Cores that don’t count)

많은 최적화는 확률이 높은 경우가 일어난다고 가정하는 데 기반한다:

• 분기 예측은 확률이 높은 분기가 실행될 것이라 가정한다. 예측이 틀리면 투기 실행이 롤백한다.
• 캐시는 핫 데이터를 접근할 것이라 가정한다. 핫 데이터 바깥을 접근하면 캐시가 적중하지 않는다.
• 낙관적 동시성 제어는 경합이 없을 것이라 가정한다. 경합이 있으면 롤백하고 재시도한다. 많은 경합이 없는 한 비관적 동시성 제어(락)보다 대기와 통신이 적게 든다.

해당하는 GoF 설계 패턴​

GoF 설계 패턴

• 계산-데이터 이중성:

  • 팩토리 패턴. 객체 생성 코드를 팩토리 객체로 바꾼다.
  • 프로토타입 패턴. 객체 생성 코드를 프로토타입 복사로 바꾼다.
  • 책임 연쇄 패턴. 다수의 처리기 객체가 명령 객체를 파이프라인으로 처리한다.
  • 커맨드 패턴. 명령(행동)을 객체로 바꾼다.
  • 인터프리터 패턴. 데이터를 계산으로 해석한다.
  • 이터레이터 패턴/제너레이터. 반복 코드를 상태 머신으로 바꾼다.
  • 전략 패턴. 전략을 객체로 바꾼다.
  • 옵저버 패턴. 이벤트 처리 코드를 옵저버로 바꾼다.

• 변경-데이터 이중성:

  • 커맨드 패턴. 계산-데이터 이중성도 수반한다. 커맨드는 변경, 행동, 계산을 모두 표현할 수 있다.

• 부분 계산과 다단계 계산:

  • 빌더 패턴. 객체 생성 과정을 여러 단계로 바꾼다. 각 단계가 일부를 만든다.
  • 책임 연쇄 패턴. 처리를 파이프라인으로 분리한다. 계산-데이터 이중성에도 속한다.

• 일반화된 뷰:

  • 어댑터 패턴. 한 인터페이스를 다른 인터페이스로 본다.
  • 브리지 패턴. 기저의 서로 다른 구현을 하나의 인터페이스로 본다.
  • 컴포지트 패턴. 여러 객체를 하나의 객체로 본다.
  • 데코레이터 패턴. 객체를 감싸 동작을 바꾸되 같은 객체로 본다.
  • 퍼사드 패턴. 여러 복잡한 인터페이스를 하나의 단순한 인터페이스로 본다.
  • 프록시 패턴. 프록시 객체가 다른 것들에 대한 뷰를 제공한다.
  • 템플릿 메서드 패턴. 서로 다른 구현을 동일한 인터페이스 메서드로 본다.
  • 플라이웨이트 패턴. 공통 데이터를 공유해 메모리를 절약한다. 공유 데이터를 소유 데이터로 본다.

• 불변식의 생성, 성장, 유지:

  • 이에 정확히 대응하는 GoF 패턴은 없다.

다른 GoF 설계 패턴 간단 설명:

• 방문자 패턴. 패턴 매칭으로 대체할 수 있다.
• 상태 패턴. 상태를 다형적 객체로 만든다.
• 메멘토 패턴. 상태를 백업해 롤백을 가능케 한다. 주로 OOP에서 데이터가 행동에 묶여 있기 때문에 존재한다. 별도의 메멘토는 단지 데이터이며, 행동과 분리되어 있다. 메멘토 패턴은 변경을 데이터로 바꾸지 않으므로 변경-데이터 이중성에 속하지 않는다.
• 싱글턴 패턴. 전역 변수와 유사하지만, 지연 초기화 가능, 다형적일 수 있음 등 차이가 있다.
• 미디에이터 패턴. 다른 추상화들을 중앙집중적으로 관리하는 하나의 추상화.

각주​

1. 별도의 스레드를 사용해 일시 중단 가능한 계산을 수행하는 것은 가능하다. 그러나 OS 스레드는 비싸고 컨텍스트 스위치도 비싸다. 수동으로 구현한 상태 머신이 더 빠르다. ↩

2. 초기 설정 후 시스템 호출을 완전히 피하기 위해 폴링을 사용할 수도 있지만, 그에 따른 비용이 있다. ↩

3. 최적화가 있다. 각 문자에 유일 ID를 저장하지 않기 위해, 많은 불변 텍스트 블록을 저장하고 문자 ID로 (textBlockId, offsetInTextBlock)를 사용할 수 있다. 연속된 삽입과 삭제는 병합될 수 있다. 트리는 계속 커지며 병합이 필요하다. 정확한 구현은 복잡하다. ↩

4. 협업 텍스트 편집의 또 다른 방법은 운영 변환(Operational Transformation)이다. (documentVersion, offset)을 커서로 사용한다. 서버는 커서를 문서의 최신 버전으로 변환할 수 있다: offset 앞에 삽입이 있으면 offset이 그에 맞게 증가한다. 삭제가 있으면 offset이 그에 맞게 감소한다. 이를 인덱스 리베이싱이라고도 한다. ↩

5. 또한: 하드 디스크에서는 자기장이 비트로 보이고, CD에서는 픗과 랜드가 비트로 보이고, SSD에서는 플로팅 게이트의 전자 위치가 비트로 보이고, 광섬유에서는 광 펄스가 비트로 보인다. 양자 컴퓨터에서는 양자 상태(전자 스핀 등)가 비트로 보일 수 있다. ...... ↩

6. 구체적으로, 바이트는 코드 유닛으로, 코드 유닛은 코드 포인트로, 코드 포인트는 문자열로 보인다. 코드 포인트는 그래핌 클러스터로도 보일 수 있다. ↩

7. 초보자에게 흔한 오해는 "소프트웨어가 화면에 뭔가 보이면 90% 완성"이라는 것이다. 실제로는, 개념 증명은 보통 20% 완성에 불과하다. 실제 사용에는 모서리 경우가 너무 많다. 하나의 모서리 경우라도 처리하지 않으면 버그다. 대부분의 코드는 일반 케이스가 아니라 모서리 케이스를 처리하는 데 쓰인다. 각 모서리 케이스가 트리거될 확률은 작지만, 많은 모서리 케이스 중 하나라도 트리거될 확률은 높다. ↩