eungju/Hints for Computer System Design.html

## Hints for Computer System Design.html
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="generator" content="pandoc">
  <title></title>
  <style type="text/css">code{white-space: pre;}</style>
  <!--[if lt IE 9]>
    <script src="http://html5shim.googlecode.com/svn/trunk/html5.js"></script>
  <![endif]-->
</head>
<body>
<h1 id="컴퓨터-시스템-설계-요령1">컴퓨터 시스템 설계 요령<sup><a href="#fn1" class="footnoteRef" id="fnref1">1</a></sup></h1>
<p>버틀러 램슨(Butler W. Lampson)</p>
<p>Computer Science Laboratory<br />Xerox Palo Alto Research Center<br />Palo Alto, CA 94304</p>
<h1 id="요약">요약</h1>
<p>몇몇 컴퓨터의 설계와 구현에 대한 연구를 통해 시스템 설계에 관한 몇가지 일반적인 요령을 얻었다. 여기서 이 요령들을 많은 예를 들어 설명했으며, 쓰인 예는 알토(Alto)와 도라도(Dorado) 같은 하드웨어부터 브라보(Bravo)와 스타(Star) 같은 응용 프로그램까지 다양하다.</p>
<h1 id="서론">1. 서론</h1>
<p>컴퓨터 시스템 설계는 알고리즘 설계와 상당히 다르다.</p>
<ul>
<li>외부 인터페이스(즉, 요구사항)가 더 모호하게 정의되며, 더 복잡하고, 그리고 더 잘 바뀐다.</li>
<li>컴퓨터 시스템은 훨씬 많은 내부 구조를 가지며, 따라서 내부 인터페이스도 많다.</li>
<li>성공의 척도가 훨씬 덜 분명하다.</li>
</ul>
<p>시스템 설계자는 가능성의 바다에서 허우적거리는 자신을 발견하곤 한다. 한 선택이 다른 선택에 대한 자유를 얼마나 제약할지, 또 전체 시스템의 크기나 성능에 얼마나 영향을 줄지 분명하지 않다. 시스템을 구축하는 '최선'의 방법은 없을지도 모른다. 시스템의 주요 부분 조차도 말이다. 그러니 형편없는 방법을 택하는 것을 피하고, 부분들 사이의 역할을 명확하게 나누는 것이 훨씬 더 중요하다.</p>
<p>필자는 여러 컴퓨터 시스템을 설계하고 구축했는데, 성공한 시스템도 있고, 실패한 시스템도 있다. 필자는 또한 성공하거나 실패한 다른 시스템들도 사용하고 연구했다. 이런 경험에서 성공적인 시스템을 설계하기 위한 몇 가지 일반적인 요령을 얻었다. 필자가 이 요령들을 고안하지는 않았다. 요령들 대부분은 노련한 설계자들이 사용하는 일상적인 지혜의 일부이기 때문이다. 허나, 노련한 전문가 조차도 자주 잊어서, 두 번째 시스템[6] 후에 네 번째 시스템이 나타난다.</p>
<p><em>면책 조항</em>: 이 요령들은</p>
<ul>
<li>참신하지도 않고(몇 가지 예외가 있긴 하지만),</li>
<li>바보도 따라할 수 있는 안전한 처방도 아니고,</li>
<li>시스템 설계나 운영의 법칙도 아니고,</li>
<li>정밀하게 체계화되지도 않았고,</li>
<li>일관되지도 않고,</li>
<li>항상 적합하지도 않고,</li>
<li>모든 선도적 전문가들이 동의하지도 않았고,</li>
<li>작동을 보장하지도 않는다.</li>
</ul>
<p>요령은 단지 요령일뿐이다. 어떤 요령은 아주 보편적이면서 막연하고, 어떤 요령은 흔히 알고 있는 것보다 광범위하게 적용할 수 있는 구체적인 기법이다. 요령과 요령을 설명한 예 모두 의도적으로 상당히 단순화했다. 요령들 상당수는 논란의 여지가 있다.</p>
<p>모듈화, 상향이나 하향 또는 반복 설계 방법론, 자료 추상화 기법 등과 같이 이미 널리 퍼진 기법을 장려하지는 않으려고 했다. 간혹 인기있는 시스템 설계 방법론을 무작정 적용할 때 빠질 수 있는 함정을 지적하기는 했다.</p>
<p>다수의 예를 들어 요령들을 설명했는데, 예들 대부분은 내가 참여했던 시스템에서 가져왔다. 예는 이더넷 근거리 통신망과 알토(Alto)와 도라도(Dorado) 개인용 컴퓨터 같은 하드웨어에서부터, SDS 940과 알토 운영체제와 리스프(Lisp)와 메사(Mesa) 프로그래밍 시스템과 같은 운영체제를 거쳐, 브라보(Bravo) 편집기와 스타(Star) 사무 시스템과 같은 응용 프로그램, 도버(Dover) 프린터와 그레이프바인(Grapevine) 메일 시스템과 같은 네트웍 서버까지 다양하다. 가능하다면 가장 뻔한 예는 피하고 대신 잘 알려진 기법의 예상치 못한 사용법을 보여주는 예를 사용하려고 했다. 대부분의 구체적인 예에는 출처를 명시했지만 요령에는 극히 소수에만 출처를 명시했다. 대부분 떠도는 이야기의 일부라, 다수의 출처를 모두 추적하기는 매우 어렵기 때문이다.</p>
<blockquote>
<p>그리고 아비가 주는 몇 가지 교훈을 네 기억에 새겨 두거라.</p>
</blockquote>
<p>시스템 설계라는 의문으로 가득한 과정에 대한 안내를 햄릿 인용으로<sup><a href="#fn2" class="footnoteRef" id="fnref2">2</a></sup> 장식하는 것도 적절해 보인다. 별다른 표시가 없다면, 인용은 레어트스(Laertes)에 대한 폴로니어스(Polonius)의 충고(1 막 3 장 58-82 행)에서 따온 것이다. 일부는 표시된 것처럼 다른 곳에서 인용했다. 각 인용은 인용 다음에 나오는 내용에 적용된다.</p>
<p>각 요령을 요약하여 적절하게 해석했을 때 요령의 핵심을 드러내는 표어로 표현했다. 그림 1에 표어들을 두 축에 따라 배치했다.</p>
<ul>
<li>좋은 시스템을 만드는데 <em>어째서</em> 도움이 되는가: 기능으로(작동하는가?), 속도로(충분히 빠른가?), 오류 대처로(지속적으로 작동하는가?)</li>
<li>시스템 설계의 <em>어디에</em> 도움을 주는가: 완전함 보장에, 인터페이스 선택에, 구현 고안에.</li>
</ul>
<p>되풀이된 동일한 표어들은 굵은 선으로 연결했고, 관련된 표어들은 가는 선으로 연결했다.</p>
<p>이 논문의 본론은 다음 <em>어째서</em>들을 표제로 하여 기능(제 1 절), 속도(제 2 절), 오류 대처(제 3 절) 세 절로 나뉜다.</p>
<h1 id="기능">2. 기능</h1>
<p>가장 중요하면서, 또 가장 막연한 요령들은, 시스템에서 올바른 기능을 얻어 내는 것과 관련이 있다. 즉, 당신이 원하는 일을 시스템이 수행하도록 하는 것이다. 이 부류의 요령들은 대부분 어떤 추상화를 사용하는 ''클라이언트''로부터 해당 추상화의 ''구현''을 분리하는 ''인터페이스''라는 개념과 관련이 있다. 두 프로그램 사이의 인터페이스는 각 프로그래머가 자기 프로그램의 올바름을 증명하기 위해 필요한 다른 프로그램에 대한 가정들의 집합이다([5]에서 옮겨왔다). 인터페이스 정의는 시스템 설계에서 가장 중요한 부분이다. 또한 보통 가장 어렵기도 한데, 인터페이스 설계는 세 가지 서로 상충하는 요구를 만족시켜야하기 때문이다. 인터페이스는 간단하고, 완전하며, 충분히 작고 빠르게 구현될 수 있어야 한다. 슬프도다, 인터페이스로 구체화된 가정들은 너무나도 자주 결국 오해였음이 드러아 버리는구나. 파르나스(Parnas)의 고전적인 논문[38]과 장치 인터페이스에 관한 최근의 논문[5]은 인터페이스 설계에 관한 훌륭하면서 실용적인 조언을 담고 있다.</p>
<p>인터페이스 설계가 어려운 주된 이유는 모든 인터페이스가 하나의 작은 프로그래밍 언어이기 때문이다. 인터페이스는 일군의 객체들과 이 객체들을 다루는데 사용되는 연산들을 정의한다. 구체적인 문법을 제외한다면, 프로그래밍 언어 설계의 다른 모든 측면이 나타난다. 따라서 호어(Hoare)의 언어 설계 요령[19]을 본 논문의 보충 교재로 읽을 수 있다.</p>
<h2 id="단순하게-유지하라">2.1 단순하게 유지하라</h2>
<blockquote>
<p>완벽함은 더 이상 더할 것이 없을 때가 아니라,<br />더 이상 뺄 것이 없을 달성된다. (생텍쥐페리(A. Saint-Exupery))</p>
</blockquote>
<blockquote>
<p>네 친구들은, 우정이 시련을 견디고 나면,<br />네 영혼에 강철 굴렁쇠로 꼬옥 껴안을 것이나,<br />악수로 손바닥 신경이 무뎌질 것은 없지,<br />새로 부화한 풋내기 동패들마다 악수로 말이다.</p>
</blockquote>
<p>* <em>한 번에 한 가지만 하되, 잘 하라</em>. 인터페이스는 추상화에 필요한 최소한의 필수 요소만 담아야 한다. 일반화하지 마라. 일반화는 일반적으로 그르다.</p>
<blockquote>
<p>우리는 감당할 수 없는 기회에 직면해 있다. (월트 켈리(W. Kelley))</p>
</blockquote>
<p>인터페이스가 너무 많은 일을 감당하려 한다면 인터페이스의 구현체는 크고, 느리며 또 복잡해지고 만다. 인터페이스는 정한 만큼의 서비스를 제공하겠다는 계약이다. 인터페이스의 클라이언트는 이 계약에 의존하는데, 이 계약은 통상 인터페이스 명세서에 상세히 기록한다. 클라이언트는 인터페이스를 사용하는데 적정한 비용(시간이나 다른 희소한 자원)이 드는지에도 영향을 받는다. '적정한'에 대한 정의는 통상 어디에도 상세하게 기록하지 않는다. 만약 여섯 단계의 추상화가 있고, 매 단계마다 '적정한' 비용보다 50%씩 더 들면, 모든 단계를 거쳐 제공되는 서비스의 비용은 10배 넘게 차이가 나게 된다.</p>
<blockquote>
<p>KISS: Keep It Simple, Stupid(단순하게 유지하라, 시시할 정도로). (작자 불명)</p>
</blockquote>
<blockquote>
<p>미심쩍으면, 제외하라. (작자 불명)</p>
</blockquote>
<blockquote>
<p>기능을 제거하라. (찰스 태커(C. Thacker))</p>
</blockquote>
<p>다른 말로는,</p>
<blockquote>
<p>무엇이든 될 수 있는 대로 단순해야 한다. 단 지나치면 안된다. (아인슈타인(A. Einstein))</p>
</blockquote>
<p>따라서, 서비스 비용은 예측 가능해야 하며, 또한 인터페이스는 구현자가 제공할 수 있는 것 이상을 약속해서는 안된다. 특히, 인터페이스는 단지 몇몇 클라이언트만이 필요로하는 기능을 약속하면 안되는데, 구현자가 다른 클라이언트에게 피해를 주지 않고 소수만이 필요로 하는 기능을 제공하기 어렵기 때문이다. 더 나은 구현자나, 혹은 문제를 더 잘 이해한 10년 후에나 등장할 구현자는, 할 수 있을지 모르겠지만, 여러분의 구현자가 그리할 수 없다면, 여러분의 야망은 접어두는 것이 현명하다.</p>
<p>예를 들어, PL/1은 심각한 문제에 봉착했는데 광범위한 자료형의 상당히 많은 일반 연산에 대해 일관된 의미를 부여하려 시도했기 때문이다. 초기 구현체들은 모든 경우를 비효율적으로 다루었고, 15년이 지나 최적화된 컴파일러가 나타났어도, 프로그래머들은 뭐가 빠를지 뭐가 느릴지 예측하기 어려웠다[31]. 파스칼(Pascal)이나 C 같은 언어는 훨씬 쓰기 쉬운데, 모든 연산이 문맥이나 인자와 상관없이 대략 일정한 비용을 요하고, 사실상 대부분의 연산들에 거의 동일한 비용이 들기 때문이다.</p>
<p>당연히, 위의 규칙은 가상 메모리, 파일, 화면 제어, 산술연산 같은 클라이언트가 몹시 많이 사용하는 인터페이스에 가장 강력하게 적용된다. 암호 검사, 사용자 명령 해석, 72 포인트 글자 인쇄와 같이 가끔 쓰이는 기능에는 성능을 약간 희생해도 괜잖다. (어쨌든 비용은 예측 가능해야만 한다는 것이 이 말의 참뜻인데, 비용이 최소 비용의 몇 배가 될 수는 있다) 그리고 이와 같은 신중한 규칙은 더 나은 구현체를 만드는 방법을 배우는 것이 목적인 연구에는 적용되지 않는다. 하지만 연구는 자주 실패하므로, 연구자가 아닌 다른 사람들은 절대 연구의 성공에 의존해서는 안된다.</p>
<blockquote>
<p>알골 60은 그 선조들 뿐만 아니라,<br />거의 모든 후손들의 개선작이기도 했다. (호어(C. Hoare))</p>
</blockquote>
<p>지나치게 제공한 예는 무수히 많다. 알토 운영체제[29]는 평범한 n 바이트 읽기/쓰기 파일 인터페이스를 제공했으며, 또 인터리스프-D[7]를 위해 각각의 가상 페이지를 정해진 디스크 페이지에 저장하는 평범한 페이징 시스템으로 확장되었다. 이 둘의 구현체는 모두 작고(파일을 위해 약 900 줄, 페이징을 위해 약 500 줄) 빨랐다(페이지 오류는 한 번의 디스크 접근과 디스크 접근 시간의 극히 일부에 해당하는 일정한 계산 비용을 썼으며, 클라이언트는 무척 쉽게 디스크를 최고 속도로 구동할 수 있었다). 알토 운영체제를 계승한 파일럿(Pilot) 시스템[42]은 멀틱스와 몇몇 다른 시스템을 따라 가상 페이지들이 임의의 파일 페이지에 연결될 수 있도록 했는데, 따라서 가상 메모리 시스템 내에 파일 입출력을 포함했다. 구현체는 아주 크고(코드 약 11000 줄) 느렸다(페이지 오류가 발생하면 거의 두 번의 디스크 접근을 일으켰고 디스크를 최고 속도로 구동하지 못했다). 추가 기능에 비싼 댓가를 치뤘다.</p>
<p>이런 인터페이스를 훌륭하게 구현하는 것이 불가능하다는 뜻은 아니며, 단지 어려울 뿐이다. 이 시스템은 여러 명의 아주 유능하고 숙련된 사람들이 설계하고 구현했다. 순환성을 해결하는 것이 문제의 일부이다. 파일 시스템은 가상 메모리를 사용하려는데, 가상 메모리는 파일을 써야 한다. 이 문제를 푸는 아주 일반적인 방법이 알려져 있기는 하지만[22], 까다롭고 또 정상적인 경우에도 엄청난 비용과 복잡성을 초래하기 쉽다.</p>
<blockquote>
<p>그리고, 이리하여 결국, 착오된 목표가<br />음모 꾸민 자의 머리통을 박살 내는. (5막 2장 387행)</p>
</blockquote>
<p>또 다른 예는 범용성이 얼마나 쉽게 예상치 못한 복잡성을 초래할 수 있는지 보여준다. 테넥스(Tenex) 시스템은 다음과 같은 아무런 문제도 없어 보이는 기능 조합을 가지고 있다:</p>
<ul>
<li>테넥스는 할당되지 않은 가상 페이지에 대한 참조를 트랩<sup><a href="#fn3" class="footnoteRef" id="fnref3">3</a></sup>을 통해 사용자 프로그램에게 보고한다.</li>
<li>시스템 호출은 확장 기계의 기계 명령어로 취급되므로, 시스템 호출이 일으킨 할당되지 않은 가상 페이지에 대한 모든 참조 또한 똑같이 사용자 프로그램에게 보고된다.</li>
<li>시스템 호출의 크기가 큰 인자는, 문자열을 포함해서, 참조로 전달 된다.</li>
<li>CONNECT 라는 시스템 호출은 다른 디렉토리에 접근하기 위해 사용된다. 인자 중 하나는 문자열인데 대상 디렉토리의 암호를 담고 있다. 암호가 틀리면, 3초 동안 기다린 후에 실패하는데, 빠른 속도로 암호를 추측하는 것을 막기 위해서이다.</li>
</ul>
<p>CONNECT는 다음과 같은 반복 형식으로 구현되었다.</p>
<pre class="pseudo"><code>    for i:=0 to Length(directoryPassword) do
        if directoryPassword[i] != passwordArgument[i] then
            Wait three seconds; return BadPassword
        end if
    end loop;
    connect to directory; return Success</code></pre>
<p>다음 수법으로 길이가 n인 암호를 평균 128^n/2 번이 아닌 64n 번의 시도로 알아낼 수 있다(테넥스는 문자열에 7 비트 문자를 쓴다). passwordArgument의 첫 번째 문자를 어느 페이지의 마지막 문자가 되도록 하고 그 다음 페이지는 할당되지 않은 페이지가 되도록 배치한 후, 모든 문자를 암호의 첫 번째 문자로 시험한다. 만약 CONNECT가 BadPassword를 돌려준다면, 추측은 틀렸다. 시스템이 할당되지 않은 페이지에 대한 참조를 보고한다면, 추측은 맞았다. 이제 passwordArgument 의 두 번째 문자를 페이지의 마지막 문자가 되도록 배치한 후, 알고 있는 방법으로 계속 진행한다.</p>
<p>이런 기묘하고 흥미로운 오류를 설계자는 알아채지 못했는데 테넥스 시스템 호출이 제공하는 인터페이스가 상당히 복잡하기 때문이다. 할당되지 않은 페이지에 대한 참조가 보고될 가능성을 내포하는 것이 예이다. 또 다른 면에서 보면, 시스템 코드의 평범한 메모리 참조 명령어가 제공하는 인터페이스도 상당히 복잡하다. 비정상적인 참조가 시스템 코드에게 통제할 기회를 전혀 주지 않고 클라이언트에게 보고될 가능성을 내포하는 것이 예이다.</p>
<blockquote>
<p>어느 바보나 1 달러에 할 수 있는 일을<br />10센트면 할 수 있는 사람이 기술자다. (작자 불명)</p>
</blockquote>
<p>어쨌든, 가끔은, 깔끔하고 강력한 인터페이스의 빠른 구현체를 만들기 위해 많은 노력을 기울일 가치가 있다. 충분히 널리 쓰이는 인터페이스라면, 구현체를 설계하고 최적화하는데 들인 노력을 몇 배로 보상 받을 수도 있다. 하지만 기존의 사례를 통해 중요성을 알게 된 인터페이스에만 이런 노력을 기울여야 한다. 또한 빠른 구현체를 만들 수 있다고 보장할 수 있어야 한다.</p>
<p>예를 들어, 댄 잉겔스(Dan Ingalls)는 알토의 고해상도 상호작용 표시 장치에 대해 수 년간 실험한 끝에 래스터 이미지를 다루기 위한 BitBlt 혹은 RasterOp 인터페이스[21, 37]를 고안했다. 그 구현체는 알토 표준 명령어 집합을 위한 에뮬레이터 전체 만큼 많은 마이크로코드로 작성되었고 만드는데 엄청난 기술과 경험이 필요했다. 하지만 성능은 앞서 쓰였던 문자를 레스터로 변환하는 단일 목적 연산 만큼이나 좋았으며, 또 단순함과 범용성 덕분에 화면 표시 응용프로그램을 만들기 훨씬 쉬웠다.</p>
<p>도라도 메모리 시스템[8]은 고속 입출력을 위한 캐시와 전용 고대역폭 경로를 가지고 있다. 도라도는 매 64 ns 사이클 마다 읽거나 쓸 수 있는 캐시와, 그리고 초당 500MBits의 I/O 대역폭과, 캐시와 I/O 모두에 대한 가상 주소를 제공하며, 또한 마이크로프로그래머가 신경 써야하는 특이한 주의 사항도 없다. 그렇지만, 구현체는 850개의 MSI<sup><a href="#fn4" class="footnoteRef" id="fnref4">4</a></sup>칩을 썼고 설계에 수 사람-년의 시간이 들었다. 이는 메모리 인터페이스에 대한 이전의 폭넓은 경험(30년이다!)과, 통상적으로 메모리 접근이 성능을 제한하는 요소라는 인식에 의해서만 정당화 될 수 있었다. 그렇다 하더라도, 되돌아 보면 이런 고속 I/O 대역폭은 비용을 지불한 만큼 가치가 없다. 이 시스템은 화면 표시 장치에 주로 쓰였는데, 듀얼포트 프레임 버퍼(dual-port frame buffer)가 거의 확실히 더 나았을 것이다.</p>
<p>마지막으로, 이 충고를 따르기 쉽다고 생각하지 마라.</p>
<p>* <em>올바르게 이해하라</em>. 추상화도 단순함도 올바른 이해를 대체할 수는 없다. 사실, 추상화가 심각한 문제를 일으킬 수도 있는데, 여기 교훈적인 이야기를 살펴 보자. 문서 편집기와 사무 정보 시스템은 대개 다루는 문서 내에 이름 붙은 필드를 포함할 수 있는 기능이 있다. 예를 들면, 편지 서식은 '주소'와 '인사말' 필드를 가질 수 있다. 일반적으로 문서는 일련의 문자들로 표현되고, 필드는 {이름: 내용}과 같은 형태로 표현된다. 여러 연산들 중, 주어진 이름으로 필드를 찾는 FindNamedField라는 프로시저가 있다. 한 때 널리 쓰였던 어느 상용 시스템은 O(n^2) 시간 복잡도의 FindNamedField 프로시저를 사용했는데, 여기서 n은 대상 문서의 길이다. 이처럼 놀라운 결과를 얻은 이유는 i번째 필드를 찾는 FindIthField 프로시저(부가적인 자료 구조를 쓰지 않는다면 O(n) 시간이 걸리는)를 우선 작성하고, 그 다음 FindNamedField(name)을 다음과 같이 아주 자연스러운 프로그램으로 구현했기 때문이다.</p>
<pre class="psuedo"><code>    for i := 0 to numberOfFields do
        FindIthField; if its name is name then exit
    end loop</code></pre>
<p>일단 (무분별하게 선택된) 추상화 FindIthField가 주어진다면, FindIthField의 비용에 대한 활발한 인식만이 이런 재앙을 막을 수 있을 것이다. 물론, 추상화를 반대한다는 주장은 아니지만, 추상화로 인한 위험에도 주의를 기울이는 것이 좋다.</p>
<h2 id="귀결">2.2 귀결</h2>
<p>단순함과 일반화에 관한 규칙은 많은 흥미로운 귀결을 갖는다.</p>
<blockquote>
<p>복장은 지갑이 허용하는 한에서,<br />그러나 요란굉장은 금물, 화려하되 번지레하지는 않게.</p>
</blockquote>
<p>* <em>빠른 것을 만들어라</em>. 범용적이고 강력한 것보다 빠른 것이 낫다. 빠르면, 클라이언트는 원하는 기능을 프로그램할 수 있고, 또 다른 클라이언트는 또 다른 기능을 프로그램할 수 있다. 더 느리지만 더 강력한 연산보다 빠르게 실행되는기초 연산을 갖추는 편이 훨씬 낫다(물론, 빠르고, 강력한 연산이 최고다. 어떻게 하는지만 안다면). 느리고 강력한 연산의 문제점은 강력함을 원하지 않는 클라이언트도 기초 기능을 위해 더 많은 비용을 지불해야 한다는 것이다. 대체로 강력한 연산은 적절한 선택이 아니라고 밝혀졌다.</p>
<blockquote>
<p>시간만 있다면 (왜냐면 죽음은 사나운 보안관이라<br />사정없이 체포해 간다) 오, 당신들한테 말해 줄 텐데--<br />하지만 그만. (5막 2장 339행)</p>
</blockquote>
<p>예를 들면, 많은 연구([23, 51, 52]와 같은)에서 프로그램은 대부분의 시간을 무척 간단한 적재(load), 저장(store), 동치 검사(test for equality), 하나 증가(adding one) 연산을 수행하는데 쓰는 것으로 드러났다. 이런 간단한 연산을 빠르게 실행하는 명령어들을 갖춘 801[41]이나 RISC[39] 같은 컴퓨터가 간단한 경우의 연산도 오래 걸리는 더 범용적이고 강력한 명령어들을 갖춘 VAX 같은 컴퓨터 보다 프로그램을 더 빨리 실행한다(동일한 양의 하드웨어를 사용했다면). 구현에 동일한 양의 하드웨어를 사용했다면, 프로그램 실행 시간이 두 배나 더 걸리기도 한다 클라이언트가 필요로 하는 것보다 한층 더 거창한 의견을 가진 컴퓨터는 더욱 나쁘게 동작한다[18].</p>
<p>대규모 시스템에서 시간이 어디에 쓰이는지 찾아내려면, 시간을 많이 쓰는 코드를 정확하게 지적해주는 측정 도구가 필요하다. 아주 소수의 시스템만 이런 도구 없이 적절히 조율할 수 있을 정도로 충분히 파악할 수 있다. 일반적으로 시간의 80%가 코드의 20%에서 쓰이는데, 보통 선행 분석이나 직감은 확신을 가지고 이 20%의 코드를 찾아낼 수 없다. 인터리스프-D는 효과적인 도구들을 사용한 성능 조율로 10 배나 빨라졌다.</p>
<p>* <em>강력함을 감추지 마라</em>. 이 표어는 바로 앞 표어와 밀접한 관련이 있다. 낮은 단계의 추상화가 어떤 작업을 재빨리 마칠 수 있도록 해준다면, 상위의 추상화 단계들이 이 강력함을 보다 일반적인 작업 속으로 감추어서는 안된다. 추상화의 목적은 클라이언트가 원치 않는 속성을 숨기는 것이다. 클라이언트가 원하는 속성을 숨겨서는 안된다. 물론 종종 자원을 다중화하는 추상화를 하는데, 이 때 비용이 들 수 밖에 없다. 하지만 단일 클라이언트에게 모든 혹은 거의 모든 자원을 제공할 수 있어야 한다. 약간의 성능 저하는 감수할 수 있다.</p>
<p>예컨데, 알토의 디스크 하드웨어[53]는 디스크 회전 속도로 실린더 전체를 전송할 수 있다. 기초 파일 시스템[29]은 연속된 파일 페이지들을 디스크의 최고 회전 속도로 클라이언트 메모리에 전송할 수 있고, 클라이언트가 각 섹터에 대해 약간의 연산을 수행할 시간도 있었다. 고로 약간의 섹터만 버퍼에 담아 두면 디스크 회전 속도로 전체 디스크를 훑을 수 있다. 이러한 기능은 다양한 어플리케이션을 작성하는데 이용되었는데, 망가진 파일 시스템을 재구축하는 정리기(scavenger)부터, 파일들에서 패턴과 일치하는 부분 문자열을 찾는 프로그램까지 다양하다. 파일 시스템의 스트림 수준 추상화는 n 바이트를 클라이언트 메모리로 읽어 들이거나 메모리에서 스트림으로 쓸 수 있다. 이 때 n 바이트 중에서 한 디스크 섹터를 완전히 점유하는 부분은 최고 디스크 회전 속도로 전송될 수 있다. 로더, 컴파일러, 편집기와 많은 다른 프로그램들의 성능은 큰 파일을 빠르게 읽을 수 있는 이 능력 덕분이었다. 스트림 수준의 클라이언트는 디스크 페이지를 있는 그대로 다룰 수 있는 편익을 포기했다. 이 것이 높은 수준의 추상화에 지불된 유일한 댓가이다.</p>
<p>* <em>프로시저 인자를 사용하라</em>. 인터페이스에 유연성을 주려면 프로시저를 인자로 넘겨라. 필요하다면 시스템 보호나 이식성을 위해 프로시저 인자를 다양한 방식으로 제한하거나 변환할 수도 있다. 이 기법은 인터페이스를 상당히 단순화할 수 있어서, 작은 프로그래밍 언어가 될 정도로 파라메터가 뒤범벅되는 것을 막아준다. 한가지 간단한 예는 집한에서 어떤 조건을 만족하는 모든 원소를 돌려주는 나열 프로시저이다. 가장 깔끔한 인터페이스는 클라이언트가 조건을 검사하는 필터 프로시저를 전달하는 것인데, 패턴이나 다른 특수 언어를 정의하는 것보다 낫다.</p>
<p>이 주제는 다양하게 번형할 수 있다. 더 흥미로운 예는 버클리 940 시스템의 스파이(Spy) 시스템 모니터링 기능이다[10]. 스파이는 허가되지 않은 사용자 프로그램이 수퍼바이저(supervisor)의 코드에 패치(patch)를 심을 수 있도록 해준다. 패치는 기계어로 작성되지만, 패치를 설치하는 과정에서 임의의 주소로 분기하지는 않는지, 루프가 있지는 않은지, 너무 길지는 않은지, 그리고 통계 수집을 위해 마련한 메모리의 지정된 영역에만 저장하는지 검사한다. 스파이를 이용하면, 시스템을 사용하는 학생들도 시스템을 고장내거나 시스템 운영을 방해하지 않을까 걱정할 필요 없이 측정법을 세세한 부분까지 조율할 수 있다.</p>
<p>이 기법의 강력함을 보여주는 또 하나의 특이한 예는 CDC 6400을 위한 칼(Cal) 시분할 시스템의 FRETURN 메카니즘이다[30]. 모든 슈퍼바이저 호출(supervisor call) C에서 또 다른 슈퍼바이저 호출 CF를 만들 수 있는데, CF는 정상적인 경우에는 C와 똑같이 실행되지만, C가 오류를 돌려주면 주어진 실패 처리기에게 제어를 넘긴다. CF는 더 많은 일을 할 수 있지만(예를 들면, 빠르지만 용량이 제한된 저장 장치의 파일들을 느린 저장 장치의 큰 파일로 연장할 수 있다), (바라건대) 정상적인 경우에는 C 만큼 빠르다.</p>
<p>그렇지만, 특화된 언어를 사용하는 편이 더 나을 수도 있는데, 특화된 언어가 최적화를 위한 정적 분석에 용이하다면 그렇다. 정적 분석 용이성이 데이터베이스 질의 언어 설계에서 주요 기준인 것이 그 예이다.</p>
<p>* <em>클라이언트에게 맡겨라</em>. 제어를 이리 저리 넘기는 비용이 싸기만 하다면, 하나의 인터페이스는 오직 한가지 문제만 해결하고 나머지는 클라이언트에게 남겨두는 방식으로 단순함, 유연함, 그리고 높은 성능을 모두 겸비할 수 있다. 예를 들면, 많은 파서는 문맥 자유 문법을 인식하는 것으로 자신의 역할을 제한하고 구문 분석 결과를 기록하기 위해서 클라이언트가 제공한 &quot;의미 해석 루틴&quot;를 호출한다. 클라이언트가 무슨 일이 있었는지 알아내려면 순회해야만 하는 구문 분석 트리를 항상 만드는 방식보다 이 방식이 명백히 더 낫다.</p>
<p>동기화 장치로서 모니터(monitor)[20, 25]의 성공은 잠금과 신호 메카니즘은 아주 작은 역할만 맡고, 모든 실제 작업은 모니터의 프로시저로 구현되는 클라이언트 프로그램에게 남겨두었다는데 일부 기인한다. 이렇게 하면 단순하면서 빠른 모니터를 구현할 수 있다. 클라이언트가 버퍼 할당이나 자원 관리 또는 다른 뭔가가 필요하면, 필요한 기능을 스스로 구현하거나 다른 라이브러리를 호출하고, 필요한 만큼만 댓가를 치르기 때문이다. 모니터가 모니터 락(monitor lock)이나 조건 변수(condition variable)를 기다리는 프로세스들의 실행 계획을 제어할 수 없다는 사실은, 흔히 약점이라고 언급되지만, 실은 장점인데, (각 프로세스 부류마다 다른 조건 변수를 사용하여) 클라이언트에게 자신의 필요에 맞는 실행 계획을 제공할 자유를 주어서, 적합하게 동작할 가망이 없는 내장 메카니즘에 댓가를 치르거나 싸우지 않아도 되기 때문이다.</p>
<p>유닉스 시스템[44]은 하나 이상의 문자 스트림을 입력으로 받고, 하나 이상의 스트림을 출력으로 내보내고, 한가지 동작만 하는 작은 프로그램을 만들도록 장려한다. 이런 방침을 적절히 따르면, 각각의 프로그램은 인터페이스가 단순하고 한가지 일을 잘하게 되고, 클라이언트는 자신의 코드와 이런 일군의 작은 프로그램들을 조합하여 정확히 원하는 효과를 얻게 된다.</p>
<p>제 3 절에서 논의하는 <em>단 대 단</em> 표어는 단순하게 유지하라의 또 다른 귀결이다.</p>
<h2 id="연속성">2.3 연속성</h2>
<p>설계를 개선하려는 욕망와 안정성 혹은 연속성을 바라는 욕구 사이에는 긴장이 지속된다.</p>
<p>* <em>기본 인터페이스는 안정적으로 유지하라</em>. 인터페이스는 시스템의 한 부분 이상, 때로는 어마 어마하게 많은 부분들이 공유하는 가정들을 구체적으로 표현하기 때문에, 되도록 변경하지 않아야 바람직 하다. 타입 검사를 하지 않는 언어로 프로그램한 시스템이라면, 공개 인터페이스의 변경은 어림도 없다. 인터페이스의 클라이언트들을 추적하여 인자 수의 불일치나 포인터와 정수를 혼동하는 등의 기초적인 불일치 조차 검사할 수 있는 방법이 없기 때문이다. 메사(Mesa)[15] 같은 완벽한 타입 검사와 언어 차원의 인터페이스를 지원하는 언어에서는, 시스템을 무너뜨리지 않으면서 인터페이스를 변경하기 한결 수월하다. 하지만 타입 검사가 더 이상 지켜지지 않는 가정들을 대부분 찾아낼 수 있어도, 여전히 프로그래머는 잘못된 가정들을 바르게 고쳐야만 한다. 시스템이 커져서 코드가 25 만 줄 이상이 되면 고쳐야할 양은 감당할 수 없을 정도가 된다. 무엇을 고쳐야할지 정확하게 알더라도, 고치는데 너무 오래 걸린다. 수 년이 지나도 안정적인 인터페이스로만 연결한 작은 조각으로 시스템을 나누는 방법 밖에는 없다. 전통적으로 프로그래밍 언어나 운영 체제 커널이 정의한 인터페이스만 이 정도로 안정적이다.</p>
<p>* <em>머물 곳을 유지하라</em>. 인터페이스를 변경해야만 한다면 머물 곳을 남겨 두어라. 이 개념을 설명하기 위해 조금 다른 두 가지 예를 살펴보자. 하나는 호환 패키지인데, 새 시스템 위에 이전 인터페이스를 구현한다. 호환 패키지는 예전 인터페이스에 의존하는 프로그램도 계속 작동할 수 있도록 해준다. 많은 새로운 운영체제들(테넥스[2]와 칼[5]을 포함해서)은 이전 시스템(각기 TOPS-10과 스코프(Scope))의 수퍼바이저 호출을 흉내내어 이전 소프트웨어도 사용할 수 있도록 했다. 일반적으로 이런 시뮬레이터는 이전 소프트웨어를 다시 구현하는 비용에 비해서 적은 노력을 요하고, 납득할만한 성능을 얻기도 어렵지 않다. 다른 수준에서, IBM 360/370 시스템은 1401과 7090 같은 구식 컴퓨터의 명령어 집합을 그대로 흉내내는 기능을 제공했다. 여기서 더 나아가면, 가상 머신에 이르는데, 가상 머신은 컴퓨터 위에서 (여러 대의) 컴퓨터를 흉내낸다[9].</p>
<p>조금 다른 예는 세계 바꿔치기 디버거(world-swap debugger)인데, 이 디버거는 대상 시스템(디버깅 대상 시스템)의 실제 메모리를 보조 저장 장치에 기록하고 디버거를 실행하는 시스템에서 이를 읽어들이는 방식으로 작동한다. 그 다음 디버거는 사용자에게 대상 세계에 대한 완벽한 접근을 제공하고, 대상 메모리 주소를 보조 저장 장치 상의 적절한 위치로 연결시켜 준다. 세심한 주의를 기울이면 대상을 원래 자리로 바꿔치고 실행을 계속하는 것도 가능하다. 세련된 디버깅 방법은 아니지만, 시스템의 매우 낮은 계층도 편리하게 디버깅할 수 있는데, 세계 바꿔치기 디버거는 간단한 세계 바꿔치기 메카니즘을 제외한 다른 어떤 기능이 대상 시스템에서 정상적으로 동작하지 않더라도 상관없기 때문이다. 이는 부트스트래핑(bootstrapping) 동안에 특히 유용하다. 다양한 변형도 있다. 한 예로, 디버거를 다른 컴퓨터에서 실행할 수 있는데, 디버거로 부터 네트웍을 통해 도착하는 워드 읽기(ReadWord), 워드 쓰기(WriteWord), 정지(Stop) 그리고 진행(Go) 명령을 해석할 수 있는 작은 ‘원격 디버깅’ 핵심 장치만 대상 세계에 있으면 된다. 또한 디버깅 대상이 시분할 시스템의 한 프로세스라면, 디버거를 다른 프로세스에서 실행할 수 있다.</p>
<h2 id="제대로-구현하기">2.4 제대로 구현하기</h2>
<blockquote>
<p>완벽함에는 조금씩 다가가야 한다. 완벽함은 시간의 느긋한 손길을 필요로 하니까. (볼테르(Voltaire))</p>
</blockquote>
<p>* <em>하나는 내다 버릴 계획을 세워라</em>. 어쨌든 그렇게 될테니까[6]. 만약 시스템에 새로운 기능이 하나라도 있다면, 만족할만한(충분히 작고, 빠르고, 유지보수 가능한) 결과를 얻기 위해서는 첫 번째 구현을 버리고 깡그리 다시 구현해야 할지도 모른다. 프로토타입을 계획에 포함하면 비용이 훨씬 적게 든다. 유감스럽게도, 종종 프로토타입이 두 개 필요한데, 새로운 시도가 많다면 특히 그렇다. 이전 시스템에서 많은 부분을 모방할 수 있다면 운이 좋다고 할 수 있다. 요컨데 테넥스(Tenex)는 SDS 940을 바탕으로 만들었다 [2]. 이전 시스템이 지나치게 거창했더라도 모방할 것이 많다. 유닉스(Unix)는 멀틱스(Multics)에서 많은 개념을 차용했다[44].</p>
<p>구현체가 성공적이었더라도, 시스템의 발전에 따라 예전에 내린 결정들을 되짚어 볼 가치가 있다. 특히, 부하나 환경(메모리 크기를 예로 들 수 있다)의 특정한 성질을 고려한 최적화는 통상 최적에서 상당히 벗어나게 된다.</p>
<blockquote>
<p>네 생각을 발설하지 말고,<br />제멋대로 튀는 생각을 행동으로 옮기지도 말 것.</p>
</blockquote>
<p>* <em>비밀을 지켜라</em>. 구현의 비밀을 발설하지마라. 여기서 비밀은 클라이언트 프로그램이 하지 말아야 하는 구현에 대한 가정이다([5]의 구절을 인용했다). 다시 말하면, 변경될지 모르는 가정이다. 인터페이스는 변경할 수 없는 것을 정의한다(인터페이스와 클라이언트를 동시에 변경하지 않으면서). 당연히, 시스템의 각 부분이 다른 부분에 대해 적은 가정을 할수록 시스템을 프로그램하고 수정하기 쉽다. 다른 한 편, 그런 시스템을 설계하기는 쉽지 않을지 모른다. 좋은 인터페이스를 설계하기 어렵기 때문이다. 그리고 강력함을 감추지 않으려는 욕구와 상충된다.</p>
<blockquote>
<p>효율적인 프로그램은 논리의 벼랑 끝에서 하는 훈련이다. (다익스트라(E. Dijkstra))</p>
</blockquote>
<p>비밀을 지키는데는 또 다른 위험이 따른다. 성능을 향상 시키는 한가지 방법은 시스템의 한 부분이 다른 부분에 대해 가지는 가정의 수를 늘이는 것이다. 추가적인 가정은 할 일의 양을 줄여 주고, 종종 아주 많이 줄여 준다. 한 예로, 크기가 n인 집합이 정렬된 상태임을 안다면, 소속 검사에 걸리는 시간은 n이 아니라 log n 이다. 이 기법은 알고리즘 설계와 작은 모듈의 최적화에 아주 중요하다. 대규모 시스템에서는 각 부분을 독립적으로 개선할 수 있는 능력이 일반적으로 더 중요하다. 올바른 균형을 맞추는 것은 기예로 남아있다.</p>
<blockquote>
<p>오, 나쁜 쪽 반은 버리세요,<br />그리고 나머지 반과 함께 더 순결하게 사세요. (3막 4장 157행)</p>
</blockquote>
<p>* <em>나누어 정복하라</em>. 어려운 문제를 해결하기 위한 잘 알려진 방법이다. 문제를 여러 개의 쉬운 문제로 바꾼다. 결과로 나온 프로그램은 보통 재귀적이다. 자원에 제약이 있으면 재귀적 방법은 조금 다른 형태가 된다. 먹을 수 있는 만큼 뜯어 먹고, 나머지는 다음 반복을 위해 남겨 둔다.</p>
<p>알토의 디스크 정리 프로그램이 좋은 예인데, 정리 프로그램은 디스크 전체를 훑어서 디스크의 각 섹터에 기록된 페이지 번호와 파일 식별자로 파일 시스템의 디렉토리 구조와 인덱스를 재구축한다[29]. 이 프로그램을 최근에 재작성한 프로그램은 주 저장 장치에 자료 구조를 구축하는 단계를 가지는데, 파일 내에서 연속된 페이지이면서 또한 디스크에서도 연속된 페이지가 자료 구조에서 하나의 항목이 된다. 보통 파일을 적당히 연속적으로 할당하기 때문에 이 구조는 지나치게 커지지 않는다. 하지만 디스크가 심하게 파편화되면, 이 구조는 주 저장 장치에 다 담을 수 없다. 이런 상황이 발생하면, 정리기는 파일들 중 절반에 대한 정보는 버리고 나머지 반만 가지고 계속한다. 파일들 중 절반에 대한 인덱스를 재구축한 후, 나머지 파일들에 대해 이 과정을 반복 한다. 필요하다면 작업을 더 나눈다. 이 방법은 하나의 파일에 대한 인덱스가 지나치게 클 때만 실패한다.</p>
<p>또 다른 흥미로운 예가 도버 래스터 프린터[26, 53]에서 나타났다. 이 프린터는 일련의 문자들과 직사각형들을 하나의 커다란 m x n 비트 배열로 주사 변환(scan-convert)하는데, 각 비트가 1이면 종이에 잉크들 찍고, 0이면 잉크를 찍지 않는다. 이 프린터에서 m=3300이고 n=4200이므로, 비트 배열의 크기는 천사백만 비트이고 메모리에 저장하기에는 너무 크다. 프린터는 쓸만한 디스크가 공급할 수 있는 속도보다 빠르게 비트를 소비하기 때문에, 비트 배열을 디스크에 저장할 수도 없다. 대신에, 전체 비트 배열을 밴드라 불리는 16 x 4200 비트 조각으로 나누고, 프린터 전자 회로에는 한 밴드 짜리 버퍼를 두 개 장착했다. 문자들과 직사각형들은 각 밴드에 부여된 버킷으로 분류되었다. 버킷은 대응하는 밴드에서 시작하는 객체를 담았다. 한 밴드 버퍼를 대응 버킷으로 채워서 주사 변환하고, 채운 밴드를 프린터로 내보내고 다음 버킷으로 다른 버퍼를 채우는 동안 프린트로 내보낸 버퍼를 0으로 채운다. 밴드의 경계를 넘어 가는 객체는 다음 버킷에도 넣는다. 이것이 문제를 작게 나눌 수 있도록 해주는 책략이다.</p>
<p>때때로 의도적으로 자원에 제약을 가하는 것이 편리한데, 정해진 크기를 단위로 자원을 양자화한다. 자원을 양자화하면 할당과 해제 관리도 단순해지고 단편화(fragmentation)의한 종류도 막아 준다. 고전적인 예는 가상 메모리로 정해진 크기의 페이지를 쓰는 것다. 크기가 정해지지 않은 세그먼트 대신에 페이지를 쓴다. 논리적으로 관련된 정보를 함께 두어서, 주 저장장치와 보조 저장장치 사이에서 하나의 단위로 정보를 전송하는 명백한 장점에도 불구하고, 페이지를 쓰는 시스템이 더 잘 작동했다. 이에 대한 이유는 복잡하며 체계적으로 연구되지 않았다.</p>
<blockquote>
<p>그리고 미지의 저승으로 날아가 버리느니<br />차라리 그런 해악을 견디는 게 낫다고 여기게 만든다면. (3막 1장 81행)</p>
</blockquote>
<p>* <em>좋은 개념을 다시 사용하라</em>. 개념을 일반화해서 사용하지 말아라. 개념을 특수화한 구현은 개념을 일반화한 구현보다 훨씬 더 효과적일 것이다. 다음 절의 캐시에 대한 논의는 이 일반적인 원칙이 적용된 많은 예를 제시한다. 또 다른 흥미로운 예는 신뢰성을 위해 데이터를 <em>복제</em>한다는 개념이다. 적은 양의 데이터는 두 개나 그 이상의 디스크 드라이브에 기록해서 쉽게 한 컴퓨터에서 복제할 수 있다[28]. 데이터의 양이 많거나 데이터가 독립된 다른 컴퓨터에 기록되어야 한다면, 복사본이 항상 동일하다고 보장하기 쉽지 않다. 깁포드(Gifford)[16]는 트랜잭션 저장소 시스템 위에 데이터 복제를 구축해서 이 문제를 어떻게 해결하는지 보여주었는데, 임의의 큰 변경도 원자적 연산(4 절을 보라)으로 수행할 수 있었다. 트랜잭션 저장소 자체도 로그를 신뢰성있게 저장하기 위해 단순한 지역 복제 방식을 이용한다. 여기에 순환성은 없는데, 코드가 아니라 오직 개념만 두 번 사용했기 때문이다. 이 상황에서 복제를 사용하는 제 3의 방법은 커밋 기록을 여러 컴퓨터에 저장하는 것이다[27].</p>
<p>스타 사무 시스템[47]의 사용자 인터페이스는 시스템의 거의 모든 객체(텍스트, 그래픽, 파일 폴더 혹은 파일 서랍, 레코드 파일, 프린터, 수신함과 송신함 등)에 적용할 수 있는 적은 수의 조작법(문자 입력, 이동, 복사, 삭제, 속성 보기)을 제공한다. 조작의 정확한 의미는 객체의 종류에 따라 달랐는데, 사용자가 자연스럽다고 느끼는 한도 내였다. 한 예로, 문서를 송신함으로 복사하면 문서는 메시지로 전송되고, 선의 끝점을 옭기면 선은 고무줄처럼 움직였다. 틀림없이 구현은 여러 가지 면에서 상당히 달랐다. 하지만 범용적인 조작들이 시스템을 단순히 사용하기 쉽게 만들기만 한 것은 아니다. 범용적인 조작은 어떤 조작이 가능한지 그리고 객체 종류에 따라 구현을 어떻게 구성할지에 대한 사고 방식을 나타낸다.</p>
<h2 id="모든-경우-다루기">2.5 모든 경우 다루기</h2>
<blockquote>
<p>절망적인 상태의 질병은<br />절망적인 처방으로만 고칠 수 있는 법, 아니면 절대. (3막 7장 9행)</p>
</blockquote>
<blockquote>
<p>그러므로 이 계획은<br />후방 혹은 예비군이 있어 대비해야 하느니,<br />시험 중 대포가 우리 면전에서 터질 경우를. (4막 3장 151행)</p>
</blockquote>
<p>* <em>보통의 경우와 최악의 경우는 따로 다루어라.</em> 일반적으로 두 경우에 대한 요구사항이 상당히 다르기 때문이다.</p>
<ul>
<li>보통의 경우에는 빨라야 한다.</li>
<li>최악의 경우라도 어느 정도 진전이 있어야 한다.</li>
</ul>
<p>대부분의 시스템은 일부 프로세스에게 불공평하게 실행 기회를 주거나 서비스를 제공하지 않아도 괜찮다. 심지어 전체 시스템을 교착상태(deadlock)에 빠뜨려도 괜찮다. 이런 사태가 자동으로 감지되고 너무 자주 일어나지만 않으면 된다. 이 경우 통상 일부 프로세스를 비정상 종료시키거나, 심지어 전체 시스템을 비정상 종료시켜서 복구한다. 처음에는 형편없어 보이겠지만, 주당 한 번의 비정상 종료는 20% 나은 성능을 위한 댓가로는 대체로 싼 편이다.</p>
<p>물론 시스템은 훌륭한 오류 복구 기능을 갖추어야 한다(단 대 단 원칙 적용. 4절을 보라). 오류 복구 기능은 어쨌든 필요한데, 비정상 종료를 일으키는 수많은 또 다른 원인들이 있기 때문이다.</p>
<p>캐시와 힌트(3절)는 정상적인 경우를 위한 특별한 처방의 예이지만, 다른 예도 많다. 인터리스프-D와 세다 프로그래밍 시스템은 참조 횟수 세기 가비지 콜렉터(reference-counting garbage collector)[11]를 사용한다. 이들에게는 가비지 컬렉터에 중요한 최적화가 적용되었다. 프로시저의 활성 레코드(activation record)나 로컬 프레임(local frame)에 위치한 포인터는 세지 않는다. 대신에, 가비지를 수집할 때마다 프레임을 조사한다. 이 방법은 참조 횟수 세기를 많이 줄여주는데, 대부분의 포인터는 지역 변수를 가리키도록 지정되기 때문이다. 프레임은 그다지 많지 않아서, 프레임을 조사하는 시간이 짧고 거의 실시간으로 수집된다. 세다는 더 나아가 어느 지역 변수가 포인터를 담고 있는지도 추적하지 않는다. 대신에, 모든 지역 변수가 포인터를 담고 있다고 가정한다. 더 이상 참조되지 않는 어느 객체의 주소를 우연히 담고 있는 정수가 그 객체를 해제하지 못하게 한다는 뜻이다. 측정 결과 저장공간의 1% 미만만 온당치 않게 유지된다고 밝혀졌다[45].</p>
<p>참조 횟수 세기 덕분에 점진적 가비지 콜렉터를 만들기 쉬워져서, 수집하는 동안 계산을 멈출 필요가 없어졌다. 그렇지만, 참조 횟수 세기는 더 이상 쓰이지 않는 순환 참조 구조는 정리할 수 없다. 세다는 그래서 전통적인 추적하여 쓸어내기(trace-and-sweep) 콜렉터도 사용했다. 이 방법은 실시간 어플리케이션에는 알맞지 않다. 전체 시스템이 수 초 동안이나 멈추기 때문이다. 그렇지만 상호대화 어플리케이션에서 누적된 순환 참조 구조를 정리하기 위해 휴식 시간 동안에 사용할 수 있다.</p>
<p>참조 횟수 세기의 또 다른 문제는 참조 횟수가 주어진 공간보다 커질 수 있다는 것이다. 이런 일은 매우 드문데, 왜냐하면 극히 소수의 객체만이 두 세 개 이상의 참조를 가지기 때문이다. 참조 횟수 최대값을 고정해버리면 간단하다. 안타깝게도, 일부 어플리케이션에서 큰 자료 구조의 루트는 많은 곳에서 참조된다. 루트가 고정되어 버리면, 상당한 저장공간을 의도하지 않게 영구적으로 점유하게 된다. 매력적인 해결책은 '넘침 횟수' 테이블을 두는 것인데, 이 테이블은 객체의 주소를 키로 쓰는 해시 테이블이다. 참조 횟수가 한계에 이르면 참조 횟수를 반으로 줄이고, 넘침 횟수를 하나 증가시키고, 객체의 넘침 플래그를 켠다. 참조 횟수가 0이 될 때, 넘침 플래그가 켜져 있으면 과정을 반대로 수행한다. 고로 고작 4 비트 정도면 7까지 셀 수 있는 공간이 되고, 참조 횟수가 4 이상 증가하거나 감소하는 드문 경우에만 넘침 테이블을 사용한다.</p>
<p>자원을 동적으로 할당하고 해제하는 경우가 많은데(예를 들면, 페이징 시스템에서 실제 메모리), 종종 아이템 하나를 해제하기 위해 일시적으로 추가 자원이 필요할 때가 있다(페이지를 어디에다 써 놓을지 알려면 어떤 테이블을 읽어 들여야 할 수도 있다). 보통 완충영역(작업 없이 비울 수 있는 변경되지 않은 페이지)이 있는데, 최악의 경우 완충영역이 사라져버릴 수도 있다(모든 페이지가 변경됐다). 이 때 매트리스 밑에 조그만 자원을 예비로 남겨 두고, 위기 상황이 닥쳤을 때만 꺼내 쓰는 기교를 부릴 수 있다. 하나의 아이템을 해제하는데 필요한 자원의 한계를 정해야만 한다. 이 한계는 매트리스 밑에 남겨둘 예비 자원의 크기를 결정하며, 자원을 다중화하는데 필요한 고정비용으로 간주해야 한다. 위기가 닥치면, 한 번에 단 하나의 아이템만 해제해야 하는데, 그리하여 모든 예비 자원이 해제 작업에만 쓰이게 된다. 엄청나게 느려지겠지만 어쨌든 진전되리라는 것은 확실하다.</p>
<p>가끔은 정상적인 경우와 최악의 경우에 완전히 다른 전략이 알맞다. 브라보 편집기[24]는 편집할 문서를 표현하기 위해 '조각 테이블'을 사용한다. 조각 테이블은 조각이 원소인 배열인데, 파일에 저장된 문자열을 가리키는 포인터들이다. 각 조각은 문자열 첫 문자의 파일 내 주소와 문자열의 길이를 담고 있다. 일반적인 편집을 하는 동안에는 문자열을 절대 수정하지 않는다. 그대신, 예를 들어 일부 문자를 삭제하면, 삭제된 문자가 포함된 조각은 두 조각으로 나뉘는데, 하나는 삭제되지 않고 남은 첫 번째 문자열을 가리키고, 다른 하나는 삭제되지 않고 남은 두 번째 문자열을 가리킨다. 키보드로 입력한 문자들은 파일 끝에 추가되고, 삽입이 일어난 조각은 세 조각으로 나뉘는데, 첫 번째는 삽입 지점 이전의 문자열, 두 번째는 삽입된 문자열, 세 번째는 삽입 지점 이후의 문자열이다. 몇 시간 동안 편집하면 수 백 개의 조각이 생기고 결국 꼼짝도 못하게 된다. 대청소를 할 때가 됐다. 문서의 모든 문자를 순서대로 새 파일에 쓰면 된다. 이제 조각 테이블을 새 파일을 가리키는 하나의 조각으로 대체할 수 있고, 그러면 계속 편집할 수 있다. 대청소는 특별한 종류의 가비지 컬렉션이다. 대청소는 백그라운드에서 할 수 있어서 사용자는 편집을 멈추지 않아도 된다(브라보가 이렇게 하지는 않지만).</p>
<h1 id="속도">3. 속도</h1>
<p>이 절은 빠른 시스템을 만드는 요령을 설명하는데, 빠른 시스템을 만드는 것이 왜 중요한지는 여기서 논의하지 않겠다. 벤틀리(Bentley)의 뛰어난 저서[55]가 이 주제를 잘 다루고 있으며 관련된 다른 주제들도 담고 있다.</p>
<blockquote>
<p>돈은 꾸지도 꿔 주지도 말 것,<br />꿔 주면 종종 돈 잃고 친구 잃게 마련이지,<br />그리고 꾸면 절약정신이 무뎌지는 법.</p>
</blockquote>
<p>* <em>자원을 분리하라</em>. 확신이 없을 때는 자원을 공유하는 것보다, 각기 정해진 자원을 쓰는 것이 낫다. 전용으로 배정된 자원은 일반적으로 빠르게 할당할 수 있고, 빠르게 접근할 수 있으며, 또한 자원 할당기가 어떻게 동작할지 예상하기도 더 쉽다. 분명한 단점은 더 많은 전체 자원이 필요하다는 것이다. 다중화 오버헤드(multiplexing overhead)를 무시하면, 공유 풀에서 자원을 가져올 때보다 더 많은 자원이 필요하다. 어쨌든, 대부분의 경우, 추가 자원에 드는 비용이 적거나, 단편화로 낭비되는 비용보다 다중화 오버헤드가 더 크거나, 혹은 둘 다이다.</p>
<p>예를 들면, 프로세서의 레지스터에 있는 정보에 접근하는 것이 메모리에서 가져오는 것보다 항상 더 빠르다. 컴퓨터가 고성능 캐시를 장착한 경우에도 마찬가지다. 레지스터는 악명이 높은데, 레지스터는 지능적으로 할당하기 까다로울 수 있고, 또 프로시저 호출과 복귀 때 수행하는 레지스터 저장과 복구는 레지스터의 속도상의 이점을 상쇄시킬 수 있기 때문이다. 하지만 많은 수의 작은 프로시저를 사용하는 검증된 현대적 스타일로 작성된 프로그램이라면, 16 개의 레지스터는 모든 지역 변수와 임시 변수를 담는데 거의 언제나 충분하고, 그러므로 레지스터 할당은 문제가 되지 않는다. 레지스터 집합 n개를 스택으로 준비하면, 복귀 없이 n번 연속 호출되었을 때만 저장이 필요하다[14, 39].</p>
<p>입출력 채널, 부동소수점 보조연산장치, 또는 이들과 비슷한 전용 계산 장치들은 이 원칙의 다른 응용이다. 부가 하드웨어가 비싸다면 하나의 프로세서를 다중화하여 이런 서비스들을 제공하지만, 부가 하드웨어가 싸다면 다양한 목적에 맞는 계산 능력을 고정적으로 할당하는 것도 가치가 있다.</p>
<p>앞서 언급한 인터리스프 가상 메모리 시스템[7]은 각 가상 주소에 상응하는 디스크 주소를 모두 추적해야 한다. 이 정보 자체도 가상 메모리에 담을 수 있으나(다수의 시스템이 이렇게 한는데, 파일럿[42]도 그 중 하나다), 가상 메모리에 대한 정보를 가상 메모리에 담으려면 순환성을 피해야하므로 다소 복잡해진다. 대신에, 실제 메모리가 이 목적을 위해 전용되었다. 디스크가 엄청나게 파편화되지만 않으면 전용으로 사용된 공간은 순환성을 예방하기 위한 코드가 차지하는 공간보다 더 적다.</p>
<p>* <em>정적 분석을 사용하라</em>, 할 수 있으면. 이 표어는 바로 앞 표어의 일반화이다. 정적 분석은 프로그램의 성능을 향상 시키는데 쓰일 수 있는 프로그램의 속성을 찾아낸다. &quot;할 수 있으면”이 덫이다. 적절한 정적 분석이 불가능할 때는, 부적절한 정적 분석으로 자신을 현혹하지 말고, 그냥 물러나 동적인 기법을 사용하라.</p>
<p>앞에서 나왔던 레지스터에 대한 발언은 컴파일러가 레지스터를 어떻게 할당할지 쉽게 결정할 수 있다는 사실에 근거를 둔다. 그냥 지역 변수와 임시 변수를 레지스터에 담으면 된다. 하지만 대부분의 컴퓨터는 여러 벌의 레지스터 집합을 가지고 있지도 않고 레지스터들을 효율적으로 쌓을 수 있는 방법도 없다. 효율적인 레지스터 할당은 그러므로 훨씬 더 어렵다. 성공이 보장되지 않는 정교한 프로시저간 분석이 필요하고, 하여튼 프로그램이 변경될 때마다 다시 수행해야만 한다. 그러므로 약간의 동적 분석(레지스터 쌓기)이 유용하다. 물론 컴파일러가 영리하다면 큰 프로시저의 정적 분석은 여전히 가치가 있다.</p>
<p>프로그램은 데이터를 순차적으로 읽을 때 훨씬 빨리 읽을 수 있다. 데이터를 순차적으로 읽으면 어떤 데이터가 다음에 필요할지 예측하기 쉬워서 데이터를 버퍼에 미리 읽어 놓을 수 있다. 대개의 경우 데이터를 디스크에 순차적으로 할당할 수 있는데, 그러면 적어도 10배 이상 빨리 전송할 수 있게 된다. 이러한 성능 향상은 프로그래머가 데이터를 예측 가능한 패턴에 따라 접근할 수 있도록, 즉, 그리하여 정적 분석이 가능하도록 데이터를 배치했기 때문이다. 프로그램을 사후 분석하여 디스크 전송을 최적화하려는 많은 시도가 있었으나, 하지만 내가 아는한 성공한 적은 없다. 디멘드 페이징(demand paging)이 쓰인 동적 분석이 적어도 사후 분석 최적화 만큼은 항상 좋았다.</p>
<p>어떤 종류의 정적 분석은 어떤 불변식이 유지된다는 사실을 이용한다. 이런 불변식에 의존하는 시스템은 하드웨어 장애나 소프트웨어 버그를 만나 불변식이 깨지는 상황을 맞으면 아마 그리 견고하지 않을 것이다.</p>
<p>* <em>동적 번역</em>. 편리한(간결하고, 쉽게 수정하거나 표시할 수 있는) 표현을 빨리 해석할 수 있는 표현으로 바꾸는 동적 번역은 컴파일이라는 오래된 개념의 중요한 변종이다. 한 번에 조금씩 번역하는 것은 분할 컴파일의 배후에 있는 개념이다. 분할 컴파일은 적어도 포트란 2까지 거슬러 올라간다. 점진적 컴파일러는 문장, 프로시저, 기타 등등이 변경되면 자동으로 번역한다. 미첼(Mitchell)은 편리한 표현과 빠른 표현 사이의 연속체 상에서의 매끄러운 이동을 연구했다[34]. 미첼의 기법을 단순화한 버전은 요구가 있으면 항상 번역하고 번역 결과를 캐시한다. 그러므로 단 하나의 해석기만 필요하고, 또 캐시 교체 외에는 아무런 결정도 필요 없다.</p>
<p>예를 들면, 실험적인 스몰토크(Smalltalk) 구현체는[12] 기준 스몰토크 컴파일러가 생산한 바이트코드를 편리한(이 경우에는, 간결한) 표현으로 사용하는데, 프로시저 하나가 호출되면 프로시저를 바이트코드에서 기계어로 번역한다. 번역된 코드의 명령어 수 천 개 정도를 담을 수 있는 크기의 캐시를 유지한다. 이 기법이 효과를 발휘하려면, 캐시는 평균적으로 프로시저가 적어도 n번 실행될 수 있을 만큼 충분히 커야만 하는데, 여기서 n은 번역되지 않은 코드를 실행하는 시간에 대한 번역 시간의 비이다.</p>
<p>C-머신(C-machine) 스택 캐시[14]는 약간 다른 예를 제공한다. 이 장치에서, 명령어는 명령어 캐시로 페치된다. 명령어가 적제되면서, 지역 프레임 포인터 FP에 상대적인 오퍼랜드 주소는 절대 주소로 변환된다. 이 때 FP의 현재 값(프로시저가 실행되는 동안에는 변하지 않는다)을 이용한다. 이에 더해, 결과로 나온 절대 주소가 현재 스택 데이터 캐시에 있는 주소 범위 내에 있다면, 오퍼랜드는 레지스터 모드로 바뀐다. 이후 명령어를 실행하면 스택 데이터 캐시의 레지스터에 직접 접근하게 된다. FP 값을 명령어의 주소에 덧붙여서 번역된 명령어의 캐시 키를 만드는데, 이렇게 해서 동일한 프로시저가 여러번 활성화되어도 여전히 동작하게 된다.</p>
<blockquote>
<p>그대 나를 가슴 속에 품은 적이 있다면. (5막 2장 349행)</p>
</blockquote>
<p>* <em>결과를 캐시하라</em>. 값비싼 계산은 다시 하지말고 결과를 캐시하라. 연관 저장소에 [f, x, f(x)] 세 쌍을 저장하고 f와 x를 키로 써서, f(x)를 찾아서 가져올 수 있다. 이 방식은 제한된 용량으로 인해 f(x)가 캐시에서 교체되기 전에 f(x)가 다시 필요하게 되면 더 빠르다. 얼마나 더 빠른지는 f(x)를 계산하는 비용이 얼마나 비싼지에 달려 있다. 한가지 심각한 문제는 f(x)가 함수의 성질을 만족하지 않을 때인데(동일한 인자에 대해 다른 결과를 줄 수 있다), f(x)의 값이 변경되면 캐시 엔트리를 무효화하거나 갱신할 수 있는 방법이 필요하다. 캐시 갱신은 f(x + d) = g(x, d, f(x)) 형태의 등식을 따르는데, 이 등식에서 g를 계산하는 비용이 f를 계산하는 것보다 싸다. 예를 들면, x는 1000 개의 숫자로 이루어진 배열이고, f는 배열 원소의 합이고, d는 배열 원소 중 하나의 새 값인데, 이를 [i, v] 쌍으로 나타낸다. 그러면 g(x, [i, v], sum)은 sum - xi + v이다.</p>
<p>캐시가 모든 '활성' 값들을 담기에 너무 작으면 쓰래시가 발생하고, 게다가 f를 다시 계산하는 비용이 비싸다면 성능은 심하게 저하된다. 그러므로 캐시의 크기를 적응적으로 선택하는 것이 현명하다. 캐시 적중률이 낮아지면 캐시의 크기를 키워야 하고 오랜 시간 동안 많은 엔트리가 사용되지 않으면 크기를 줄여야 한다.</p>
<p>캐시의 고전적인 예는 주 저장장치 접근 속도를 향상 시키는 하드웨어이다. 이 캐시의 엔트리는 [Fetch, 주소, 주소의 내용] 세 쌍이다. Fetch 연산은 함수의 성질을 만족하지 않는 것이 확실하다. Fetch(x)는 Store(x)가 수행된 후에는 다른 답을 내놓는다. 따라서 저장 연산 후에 꼭 캐시를 갱신하거나 무효화해야 한다. 가상 메모리 시스템도 완전히 같은 방식으로 동작한다. 주 저장장치가 캐시 역할을 하고, 디스크가 주 저장장치 역할을 하고, 전송 단위는 페이지나 세그먼트 등이 된다.</p>
<p>하지만 거의 대다수의 단순하지 않은 시스템은 조금 특화된 캐시를 적용한다. 상호작용 시스템이나 시분할 시스템이 특히 그렇다. 이런 시스템이 다루는 기본적인 문제는 작고 빈번한 변경에 반응하여 복잡한 상태를 점진적으로 갱신하는 것이다. 이런 일을 임시변통으로 처리하면 오류가 발생하기 매우 쉽다. 최선의 조직화 원칙은 각각의 변경 후에 전체 상태를 재계산하되 계산에서 값비싼 결과는 모두 캐시하는 것이다. 변경은 적어도 잘못 나타나게 될 캐시 엔트리는 무효화해야 한다. 무효화할 엔트리를 정확하게 집어내기 너무 어렵다면, 더 많은 엔트리를 무효화하고, 무효화된 엔트리를 복구하기 위한 더 많은 계산을 댓가로 치루어야 한다. 성공의 비결은 작은 변경이 적은 수의 엔트리만 무효화하도록 캐시를 조직화하는 것이다.</p>
<p>예를 들면, 브라보 편집기[24]에는 <code>DisplyLine(document, firstChar)</code> 함수가 있었는데, 이 함수는 표시된 문서에서 <code>document[firstChar]</code>가 첫 번째 문자인 줄을 나타내는 비트맵을 반환한다. 이 함수는 또한 <code>lastChar</code>와 <code>lastCharUsed</code>도 반환하는데, 각기 줄에 표시된 마지막 문자 번호와 비트맵을 만들면서 조사한 마지막 문자 번호이다(이 둘은 보통 동일하지 않은데, 줄 바꿈을 결정하기 위해서는 줄의 마지막 문자를 봐야하기 때문이다). 이 함수는 줄 바꿈을 계산하고, 정렬하고, 글꼴 테이블을 사용하여 문자를 래스터 그림으로 변환하는 등의 일을 한다. 화면에 현재 표시된 줄 하나 하나가 엔트리인 캐시가 있는데, 가끔은 바로 위 아래의 몇 줄을 더 캐시하기도 한다. <code>i</code>에서 <code>j</code> 사이의 문자를 바꾸는 편집은 <code>[i .. j]</code>와 <code>[firstChar .. lastCharUsed]</code>가 겹치는 모든 캐시 엔트리를 무효화 시킨다. 화면은 다음과 같이 다시 계산된다.</p>
<pre class="pseudo"><code>    loop
        (bitMap, lastChar, ) := DisplayLine(document, firstChar); Paint(bitMap);
        firstChar := lastChar + 1
    end loop</code></pre>
<p><code>DisplayLine</code> 호출은 캐시에 [document, firstChar]에 해당하는 엔트리가 존재하면 이를 이용해 생략된다. 마지막에 사용되지 않은 모든 캐시 엔트리는 삭제된다. 삭제된 엔트리가 무효하지는 않지만, 줄 바꿈이 바뀌어서 줄이 더 이상 그 위치에서 시작하지 않기 때문에 더 이상 필요가 없다.</p>
<p>동일한 개념을 아주 다른 상황에도 적용할 수 있다. 브라보에서 문서는 여러 문단으로 구성될 수 있는데, 각 문단은 왼쪽과 오른쪽 여백, 줄간 여백 등으로 규정된다. 일반적인 페이지 레이아웃의 경우 페이지 레이아웃을 하는데 필요한 문단의 모든 정보를 아주 간결하게 표현할 수 있다.</p>
<ul>
<li>문단의 줄 수</li>
<li>각 줄의 높이(보통 모든 줄은 높이가 같다)</li>
<li>페이지 분리 속성들</li>
<li>문단 앞과 뒤의 간격</li>
</ul>
<p>보통의 경우 위의 정보는 서너 바이트로 부호화할 수 있다. 30 페이지 짜리 장은 300 문단 쯤일 것이고, 이 모든 정보에 1k 바이트 정도가 필요하다. 이는 한 페이지 상의 문자들을 명시하는데 필요한 정보보다 적은 양이다. 페이지 레이아웃 계산을 한 페이지를 위한 줄 레이아웃 계산에 견준다면, 한 장의 페이지를 분할하는 것은 한 페이지를 렌더링 하는데 필요한 시간 보다 더 적게 걸려야 한다. 각 장을 독립적으로 레이아웃할 수도 있다.</p>
<p>이게 가능한 이유는 <code>[paragraph, ParagraphShape(paragraph)]</code>를 엔트리로 가지는 캐시이다. 문단이 편집되면, 해당 캐시 엔트리를 무효화하고 재계산해야만 한다. 편집이 일어날 때 즉시 할 수도 있고(편집된 문단이 화면 상이라면 적합한데, 보통 그렇다. 하지만 전역 치환일 때는 그리 적합하지 않다), 백그라운드로 할 수도 있고, 혹은 페이지 재분할이 요청되었을 때만 할 수도 있다.</p>
<blockquote>
<p>의상은 종종 그 사람을 표현하거든.</p>
</blockquote>
<p>* <em>힌트를 사용하라</em>. 힌트를 써서 정상적인 실행의 속도를 높여라. 힌트는, 캐시 엔트리와 마찬가지로, 어떤 계산의 결과를 저장한 것이다. 힌트는 캐시와 두 가지 점에서 다르다. 힌트는 틀릴 수도 있고, 반드시 연관 검색으로 접근하지 않아도 된다. 힌트는 틀릴 수 있기 때문에, 되돌릴 수 없는 동작을 수행하기 전에 힌트가 올바른지 검사할 방법이 꼭 있어야 한다. 힌트는 ‘진실’과 비교하여 검사한다. 진실은 항상 옳아야 하지만 효율적인 실행보다 힌트를 검사하는 용도로 최적화할 수 있는 정보이다. 캐시 엔트리와 마찬가지로, 힌트의 목적은 시스템이 빠르게 동작하도록 만드는 것이다. 그러므로 힌트는 거의 항상 옳아야 한다는 뜻이다.</p>
<p>예를 들면, 알토[29]와 파일럿[42] 운영체제에서 파일은 각기 유일한 식별자를 가졌고, 또 각 디스크 페이지는 '레이블' 필드를 가져서 데이터 전송 속도를 느리게 하지 않으면서 데이터를 읽거나 쓰기 전에 레이블의 내용을 확인할 수 있다. 페이지 레이블은 그 페이지를 담고 있는 파일의 식별자와 파일에서 그 페이지의 번호를 담고 있다. 다른 페이지와 구별하여 각 파일의 0번 페이지는 ‘리더 페이지'라 불렀고 파일이 속한 디렉토리와 디렉토리에서 파일의 문자열 이름을 담고 있다. 이것이 파일 시스템이 근거로 하는 진실이고, 진실을 올바르게 유지하는 것은 아주 힘들다.</p>
<p>그렇지만 단지 이 정보만으로는, 디렉토리에서 파일 이름으로 파일의 식별자를 찾을 수도, 또 페이지 i의 디스크 주소를 찾을 수도 없다. 전체 디스크를 뒤지지 않고는 방법이 없다. 동작하기는 하지만 받아들일 수 없을 정도로 느린 방식이다. 그래서 각 시스템은 이런 작업의 속도를 향상시키기 위해 힌트를 관리한다. 두 시스템은 모두 디렉토리를 [이름, 파일 식별자, 첫 페이지의 주소] 세 쌍들을 담은 파일로 나타낸다. 각 파일은 페이지 번호를 페이지의 디스크 주소로 사상하는 자료 구조를 가졌다. 알토는 각 레이블의 다음 레이블을 가리키는 링크를 사용한다. 이는 페이지 n에서 페이지 n+1을 빠르게 얻을 수 있도록 했다. 파일럿은 직접 사상을 구현한 B-트리를 사용하는데, 연속된 파일 페이지가 연속된 디스크 페이지를 점유하는 일반적인 경우에 유리하다는 점을 이용했다. 이런 힌트에서 얻은 정보를 사용할 때 옳은지 확인하는데, 레이블을 확인하거나 리더 페이지에서 파일 이름을 읽어서 확인한다. 잘못된 정보라고 증명되면, 디스크를 훑어서 전체 힌트를 재구축할 수 있다. 마찬가지로, 미할당 디스크 페이지를 기록한 비트 테이블도 힌트이다. 진실은 미할당 페이지 레이블의 특별한 값으로 나타내는데, 페이지가 할당될 때와 파일 식별자와 페이지 번호를 레이블에 덮어 쓰기 전에 그 값을 확인한다.</p>
<p>힌트의 또 다른 예는 아르파넷[32]에서 처음 사용된 저장 후 전달(store and forward) 라우팅이다. 네트웍의 각 노드는 모든 다른 노드에 대한 최적의 경로를 제공하는 테이블을 관리한다. 이 테이블은 각 노드가 자신의 이웃 노드와의 연결 품질에 대한 의견을 모든 다른 노드에게 알리는 주기적 방송에 의해 갱신된다. 이 방송 메시지는 동기화 되지도 않고 배달된다는 보장도 없기 때문에, 노드들은 어느 때나 서로 다른 정보를 가질 수 있다. 이 경우에 진실은 각 노드가 자신의 식별자를 알고 따라서 자신이 목적지인 패킷을 받았음을 아는 것이다. 그 외에는, 라우팅은 최선을 다할 뿐이다. 상황이 그다지 빨리 변하지 않는다면 거의 최적 경로를 제공한다.</p>
<p>더 흥미로운 예는 이더넷[33]인데, 이더넷은 케이블에 전송 신호가 없다는 것을 패킷을 송신해도 된다는 힌트로 사용한다. 두 송신자가 동시에 힌트를 취하면, 둘 다 감지할 수 있는 충돌이 발생한다. 둘 다 멈추고, 임의로 선택한 간격 동안 기다린 후에, 다시 시도한다. n번 연속으로 충돌이 발생하면, 송신자의 수가 2^n이라는 힌트로 취하고, 그래서 각 송신자는 임의 지연 간격의 평균을 초기값의 2^n배로 정한다. 이 '지수적 물러서기(exponential backoff)'는 망에 과부하가 걸리지 않도록 보장한다.</p>
<p>아주 다르게 응용한 힌트는 스몰토크 프로그램[12]의 속도를 높인다. 스몰토크에서 프로시저가 호출될 때 실행되는 코드는 프로시저 첫 번째 인자의 타입에 따라 동적으로 결정된다. 요컨데 Print(x, format)은 x의 타입의 일부인 Print 프로시저를 호출한다. 스몰토크에는 선언이 없기 때문에, x의 타입은 정적으로 알 수 없다. 대신, 각 객체는 [프로시저 이름, 코드의 주소] 쌍들의 테이블을 가리키는 포인터를 가지고, 그래서 프로시저 호출이 실행될 때, x의 테이블에서 Print를 찾는다(친숙하지 않은 스몰토크 용어와 문법을 평범하게 바꿨고, 조금 과하게 단순화 했다). 이 방식은 비싸다. 대개 x의 타입은 직전의 타입과 동일한 것으로 드러났다. 따라서 Print(x, format) 호출을 위한 코드는 다음과 같이 조정할 수 있다.</p>
<pre class="pseudo"><code>    push format; push x;
    push lastType; call lastProc</code></pre>
<p>그리고 모든 Print 프로시저는 다음과 같이 시작한다.</p>
<pre class="psuedo"><code>    lastT := Pop(); x := Pop(); t := type of x;
    if t != lastT then LookupAndCall(x, &quot;Print&quot;) else the body of the procedure end if.</code></pre>
<p>여기서 <code>lastType</code>과 <code>lastProc</code>는 코드에 담긴 즉치값이다. LookupAndCall은 찾은 x의 타입과 코드의 주소를 lastType와 lastProc 필드에 다시 저장해야 한다. x의 타입이 다음에도 동일하다면, 프로시저는 바로 호출된다. 측정 결과 이 캐시의 성공률은 약 96%이었다. 명령어 페치 유닛(instruction fetch unit)을 가진 컴퓨터에서, 이 기법은 lastProc로 이동하는 것을 최고 속도로 진행할 수 있는 좋은 성질을 갖는다. 따라서 힌트가 옳을 때 스몰토크 호출은 보통 서브루틴 호출 만큼이나 빠르다. t != lastT 검사는 대개의 경우 분기하지 않도록 조정할 수 있다.</p>
<p>같은 개념이 다른 차림으로 S-1[48]에도 사용됐는데, S-1은 명령어 캐시에 각 명령어를 위한 추가 비트가 있었다. 명령어를 적재할 때 비트를 꺼놓고, 명령어가 분기를 유발하게 되면 비트를 켜서, 명령어 페치 유닛이 따라야 하는 경로를 선택하는데 이 비트를 사용했다. 예측이 틀리게 되면, 비트를 바꾸고 다른 경로를 따른다.</p>
<p>* <em>미심쩍다면, 단순하지만 확실한 방법(brute force)을 써라</em>. 특히 하드웨어 가격이 하락하므로, 특수 용도 계산 사이클이 많이 필요한 직관적이면서 쉽게 분석할 수 있는 해결책이 특정한 가정이 만족될 때만 원활하게 동작하는 복잡하고 특성을 파악하기 어려운 해결책보다 더 낫다. 예를 들면, 켄 톰슨(Ken Thompson)의 체스 컴퓨터 벨레(Belle)는 수(手)를 만들고 말의 위치를 평가하기 위해 정교한 체스 전략보다 특수 용도 하드웨어에 주로 의지한다. 벨레는 세계 컴퓨터 체스 대회에서 여러 차례 우승했다. 또 다른 교육적인 예는 시분할 시스템을 누른 개인용 컴퓨터의 성공이다. 시분할 시스템이 훨씬 더 영리한 기능을 많이 포함하고 훨씬 적은 사이클을 낭비하지만, 개인용 컴퓨터가 대화식 컴퓨터를 실현하는데 비용면에서 가장 효과적인 방법으로 차츰 인정받았다.</p>
<p>점근적으로(asymtotically) 더 빠른 알고리즘이 꼭 더 우수하지는 않다. 두 n x n 행렬을 O(n^2.5)보다 빠르게 곱하는 알고리즘도 있지만, 상수항이 너무나 과중했다. 더 세속적인 기록을 보자. 7040 왓포(Watfor) 컴파일러는 심볼을 찾는데 선형 탐색을 사용했다. 학생들이 만든 프로그램은 심볼이 몇 개 되지 않아서 더 나은 알고리즘을 위한 초기화 시간을 만회할 수 없었기 때문이다.</p>
<p>* <em>백그라운드에서 계산하라</em>. 되도록이면 백그라운드에서 계산하라. 대화식 혹은 실시간 시스템에서, 요청에 응답하기 전에 가능한 적은 양의 일만 하는 것이 좋다. 두 가지 이유 때문이다. 첫 째, 즉각적인 응답은 사용자에게 좋고, 둘 째, 보통 작업량이 크게 달라서, 백그라운드 작업을 할 수 있는 비어 있는 프로세스 시간이 있을 가능성이 높다. 많은 종류의 일을 백그라운드로 미룰 수 있다. 인터리스프와 세다 가비지 콜렉터[7, 11]는 거의 모든 작업을 백그라운드에서 처리한다. 많은 페이징 시스템이 변경된 페이지 쓰기와 교체 후보 준비를 백그라운드에서 한다. 전자 메일도 백그라운드 프로세스가 배달하고 회수할 수 있는데, 보통 한 두 시간 내의 배달은 허용되기 때문이다. 많은 은행 시스템은 밤에 계정들에 대한 자료를 정리하고 취합하여 다음 날 아침까지 준비되도록 한다.</p>
<p>이 네 가지 예는 차례대로 점점 더 적은 포그라운드 작업과 백그라운드 작업 사이의 동기화를 필요로 한다. 동기화 양이 커질수록 미묘한 오류를 피하려면 더욱 주의가 필요하다. 극단적인 예는 [13]에 나오는 실행 중 가비지 콜렉션(on-the-fly garbage collection) 알고리즘이다. 하지만 대부분의 경우 두 개의 다른 독립적인 프로세스 사이의 간단한 생산자-소비자 관계만으로도 동기화 가능하다.</p>
<p>* <em>배치(batch) 처리를 사용하라</em>. 가능하다면 배치로 처리하라. 뭔가를 점진적으로 수행하면 거의 항상 비용이 더 드는데, 디스크와 테이프는 순차적으로 접근할 때 훨씬 잘 동작 한다는 점을 제쳐두더라도 마찬가지다. 또한, 배치로 처리하면 오류 복구가 훨씬 간단해진다. 뱅크 오브 아메리카는 출납계원이 예금과 인출을 기록할 수 있는 대화식 시스템을 가지고 있다. 시스템은 아침에 현재 계좌 잔고들을 읽어 들여서 일과 동안에 최선을 다해 계좌 잔고를 관리한다. 하지만 다음 날 이른 아침에 전날 처리된 온라인 자료는 모두 폐기하고 밤 동안의 배치 수행 결과로 대체된다. 이런 설계는 신뢰성 있는 장기 보관 자료에 대한 은행의 요구를 쉽게 만족시킬 수 있고, 아무런 중요한 기능도 잃지 않는다.</p>
<blockquote>
<p>조심해라, 겁내는 게 가장 안전하다. (1장 3막 43행)</p>
</blockquote>
<p>* <em>안전 제일</em>. 자원을 할당할 때, 최적의 상태를 달성하려 말고 대참사를 피하려고 노력하라. 가상 메모리, 네트웍, 디스크 할당, 데이터베이스 구성, 그리고 다른 자원 할당 문제를 수 년간 다룬 경험으로 범용 시스템은 자원의 사용을 최적화할 수 없다고 분명히 말할 수 있다. 다른 한편으로, 시스템에 과부하를 주어 시스템의 처리량을 형편없이 떨어뜨리기는 무척 쉽다. 부하의 특성을 극도로 잘 파악하고 있지 않다면, 어떤 자원에 대한 요구가 용량의 3분의 2를 넘어서면 시스템이 잘 동작하기를 기대할 수 없다. 다행히 하드웨어는 싸고 점점 더 싸지기 때문에, 잉여 용량을 제공할 수 있다. 메모리가 특히 싼데, 그래서 특히 행운이다. 어느 정도까지는 넉넉한 메모리가 프로세스 싸이클이나 통신 대역폭 같은 다른 자원을 더 완전히 사용하도록 도움을 줄 수 있기 때문이다.</p>
<p>최적화에 대한 애석한 진실은 첫 번째 페이징 시스템에 의해 드러났다. 그 시대에는 메모리가 아주 비쌌고, 그래서 사람들은 페이지 교체를 교묘하게 최적화하여 모든 바이트를 최대한 짜내려는 생각을 품었다. 관련된 프로시저를 동일한 페이지에 넣고, 이전 참조로 부터 참조될 다음 페이지를 예측하고, 데이터나 코드를 공유하는 작업을 같이 수행하는 등의 최적화 기법을 생각해냈다. 아무도 이런 최적화 기법을 습득하지 못했다. 대신, 메모리는 싸졌고, 따라서 시스템은 단순한 디멘드 페이징이 동작하기에 충분한 여유를 제공하기 위해 메모리를 썼다. 우리는 쓰레싱(thrashing)이나, 혹은 가용 메모리를 너무 과도하게 요구하는 것을 피하는 것만이 정작 중요하다는 것을 배웠다. 쓰레시가 발생한 시스템은 디스크를 기다리는데 모든 시간을 써버린다.</p>
<p>교묘한 최적화가 성공한 유일한 시스템은 아주 잘 알려진 부하를 가진 시스템이다. 그 예로, 360/50 APL 시스템[4]은 각각의 사용자를 위한 동일한 크기의 작업공간과 사용자 모두를 위한 공통 시스템 코드로 구성되었다. 이런 구성은 모든 시스템 코드가 메모리에 상주하고, 각 사용자에게 디스크의 연속된 조각을 할당하고, 각 계산 단위를 메모리에서 내리고(swap-out) 올리는(swap-in) 것을 겹칠 수 있게 해주었다. 이 구성은 잘 동작했다.</p>
<blockquote>
<p>알토의 가장 좋은 점은 밤에 빨라지지 않는다는 것이다. (모리스(J. Morris))</p>
</blockquote>
<p>프로세서 시간에 대해서도 비슷한 교훈을 얻었다. 대화식일 때는 계산 요구에 대한 응답 시간이 중요한데, 사용자가 응답을 기대리기 때문이다. 계산의 우선순위, 작업 집합(working set)의 크기, 메모리 적재, 과거 기록, I/O 요청 가능성 등을 고려하여 프로세서 실행 계획을 조율하려는 수많은 시도가 있었다. 이런 노력은 실패했다. 가장 단순한 매개변수들만이 인지할 수 있는 효과를 냈다. 대화식 대 비대화식 계산으로 구분하거나 또는 높음, 포그라운드, 백그라운드 단계로 우선순위를 구분하는 것이다. 가장 성공적인 기법은 각 작업에 사이클을 고정된 비율만 배정해서 100% 이상 할당하지 않는다. 사용하지 않은 싸이클은 버려지거나, 혹 운이 좋다면, 백그라운드 작업에 쓰인다. 이 전략의 자연스런 연장은 개인용 컴퓨터인데, 이 경우 한 사용자가 적어도 하나의 프로세서를 가진다.</p>
<blockquote>
<p>누구든 귀를 주되 목소리는 몇 사람만.<br />각 사람의 평가는 듣되, 네 판단은 유보할 것.</p>
</blockquote>
<p>* <em>부하를 흘려라</em>. 요구를 통제해야 한다. 시스템에 과부하가 걸리게 내버려 두어서는 안된다. 이 규칙은 앞 규칙의 귀결이다. 부하를 흘리는 많은 방법이 있다. 대화식 시스템은 새 사용자를 거부할 수 있고, 이에 대해 기존 사용자에게 서비스를 거부할 수도 있다. 메모리 관리자는 모든 작업의 작업 집합(working set)이 이용 가능한 메모리에 들어 맞도록 맡을 작업을 제한할 수 있다. 네트웍은 패킷을 폐기할 수 있다. 최악의 상황이 닥치게 되면, 시스템은 크래시하고 신중하게 다시 시작할 수 있다.</p>
<p>밥 모리스(Bob Morris)는 공유 대화식 시스템은 터미널 마다 커다란 빨간 버튼이 있어야 한다고 제안했다. 서비스가 만족스럽지 않다면 사용자는 빨간 버튼을 누르고, 그러면 시스템은 서비스를 향상시키거나 그럴 수 없다면 사용자를 내던져야 한다. 충분히 긴 기간에서 보면 정당한 선택이 된다. 이 아이디어는 유용한 정도의 서비스를 제공하지 못하는 터미널 앞에서 사용자가 시간을 낭비하지 않도록 사용자를 지키기 위한 것이다.</p>
<p>아르파넷(Arpanet)[32]의 최초 명세는 망이 수락한 패킷은 수신 컴퓨터가 꺼졌거나 네트웍 노드가 패킷을 가지고 있는 동안 장애가 나는 경우를 제외하고는 배달을 보장했다. 이것은 좋은 생각이 아니었다. 이 규칙은 최악의 경우에는 데드락을 피하기 아주 어렵게 만들었고, 규칙을 지키려는 시도는 정상적인 경우에도 많은 복잡한 문제와 비효율성을 일으켰다. 더군다나, 클라이언트에게도 이득이 없는데, 여전히 호스트나 네트웍 장애로 인한 패킷 손실에 대처해야 하기 때문이다(4절 단 대 단을 보라). 결국 이 규칙은 폐기되었다. 펍(Pup) 인터넷[3]은 훨씬 더 다양한 전송 장비에 대응했는데, 정체의 기미가 보이면 항상 가차없이 패킷을 폐기했다.</p>
<h1 id="오류-대처">4. 오류 대처</h1>
<blockquote>
<p>신뢰성의 피할 수 없는 대가는 단순함이다. (호어(C. Hoare))</p>
</blockquote>
<p>신뢰성 높은 시스템을 만들기가 아주 어렵지만은 않은데, 신뢰성을 어떻게 높이는지 알기만 하면 된다. 하지만 기존의 설계를 바꾸어 높은 신뢰성을 갖추기는 매우 어렵다.</p>
<blockquote>
<p>무엇보다 이 점--네 자신에 진실되거라,<br />그러면 당연히, 밤이 낮을 따르듯,<br />네가 누구에게든 거짓될 수 없다는 결론이 따르지.</p>
</blockquote>
<p>* <em>단 대 단(end-to-end)</em>. 어플리케이션 수준의 오류 복구는 신뢰성 높은 시스템을 위해 절대적으로 필요하며, 다른 모든 오류 감지나 복구는 논리적으로는 필요하지 않지만 오로지 성능 때문에 필요하다. 살처(Saltzer)[46]가 이러한 사실을 처음 밝혔고 이는 아주 광범위하게 적용할 수 있다.</p>
<p>예를 들면, A 컴퓨터에 부착된 디스크의 파일 시스템에서 B 컴퓨터에 부착된 다른 디스크의 다른 파일 시스템으로 파일을 옮기는 동작을 생각해보자. 올바른 비트들이 진짜로 B의 디스크에 있는지 확신하기 위해서는, B의 디스크에서 파일을 읽어야만 하고, 적당한 길이(64 비트라고 하자)의 체크섬을 계산하여, A의 디스크에 있는 비트들의 체크섬과 같은지 확인해야 한다. A의 디스크에서 A의 메모리로, A에서 네트웍을 거쳐 B로, B의 메모리에서 B의 디스크로의 전송을 각기 검사하는 것만으로는 충분하지 않은데, 어떤 다른 지점에서 문제가 있거나, 비트들이 메모리에 있는 동안 망가지는 등 어떠한 일이든 있을 수 있기 때문이다. 이런 다른 검사는 필요하지도 않다. 단 대 단 검사에서 실패한다면 전송과정 전체를 반복할 수 있기 때문이다. 물론 전체를 재전송하는 것은 작업량이 많다. 오류가 잦은 경우에 중간 점검은 반복해야하는 작업량을 줄일 수 있다. 하지만 중간 점검은 순전히 성능에만 관련된 문제이고, 파일 전송의 신뢰성과는 관련이 없다. 실제로, 캠브리지에 설치된 링 기반 시스템에서는 관례적으로 58 메가바이트 크기의 전체 디스크 팩을 복사하고 단 대 단 검사만 했다. 그런데 오류가 아주 드물어서 20분이 걸리는 복사 작업을 반복해야하는 경우는 거의 없었다[36].</p>
<p>힌트의 많은 용법은 이 개념을 응용한 것이다. 앞에서 설명했던 알토 파일 시스템을 예로 들면, 디스크 섹터를 쓰기 전에 섹터의 레이블을 검사하는 것은 섹터를 쓰려는 디스크 주소가 옳다는 것을 보장해준다. 디스크 주소가 올바르도록 취하는 모든 예방 조치가 중요할 수도, 심지어 필수적일 수도 있다. 성능을 위해서는 그렇다. 하지만 파일 시스템의 신뢰성에는 영향을 주지 않는다.</p>
<p>펍 인터넷[3]은 다양한 수준에서 단 대 단 전략을 채용했다. 펍 인터넷 전산망이 제공하는 주요 서비스는 출발지에서 목적지으로 데이터 패킷을 전송하는 것이다. 데이터 패킷은 오류율과 다른 특성들이 크게 차이나는 여러 전산망을 거칠 수 있다. 패킷을 저장했다가 전송하는 인터넷 노드는 공간이 부족하여 부득불 패킷을 폐기하기도 한다. 패킷의 최적 경로는 대략적으로만 예측할 수 있을 뿐이며, 이러한 예측은 전산망의 일부가 작동을 멈추거나 복구되면 크게 빗나가게 된다. 이런 불확실성에도 불구하고, 펍 인터넷은 단지 “최선형(best efforts)” 배달만 시도하는 간단한 구현으로 우수한 서비스를 제공한다. 패킷은 송신자에게 알리지 않고 유실될 수 있고, 전송 중에 손상될 수도 있다. 이런 문제에 대처할 수 있도록 클라이언트는 자체적인 오류 제어를 제공해야 하고, 또 실제로 상위 수준 펍 프로토콜은 신뢰성 있는 바이트 스트림과 같은 더 복잡한 서비스를 제공한다. 어쨌든 패킷 전송층은 클라이언트에게 문제를 보고하려고 시도하는데, 어느 정도 오류 제어(16 비트 체크섬)를 제공하여, 가능한 경우에 폐기된 패킷의 송신자에게 알려주는 등의 시도를 한다. 이런 서비스는 신뢰성이 보장되지 않는 통신과 과부하에도 불구하고 성능을 향상 시키기 위한 조치이다. 이 역시 최선형이라면, 구현을 그리 복잡하게 만들지 않는다.</p>
<p>단 대 단 전략에는 두 가지 문제점이 있다. 첫 째, 저렴한 방법으로 성공 여부를 판단할 수 있어야 한다. 둘 째, 시스템이 운영되어 과중한 부하에 놓이기 전에는 드러나지 않는 심각한 성능적 결함을 가친 채 시스템이 운영되도록 할 수 있다.</p>
<blockquote>
<p>당신을 기억하라?<br />의당, 내 기억의 페이지에서<br />온갖 하잖은 멍텅구리 기록들을 지워 버리고,<br />책에서 베낀 온갖 격언, 온갖 이미지들, 온갖 지나간 일상들,<br />청춘과 관찰이 거기 베껴 놓은 온갖 것들을 지워 버리고,<br />당신의 명령 단 하나만 살리라,<br />내 두뇌의 책과 두루마리 안에<br />다른 잡스러운 것과 뒤섞이지 않고. (1막 5장 97행)</p>
</blockquote>
<p>* <em>변경을 로그로 남겨라</em>. 대상의 상태에 대한 진실을 로그로 기록해야 한다. 로그는 아주 단순한 자료 구조이다. 안전하고 확실하게 쓰고 읽을 수 있으며, 디스크나 또는 크래시에도 견딜 수 있는 다른 안정적인 저장 장치에도 쉽게 기록할 수 있다. 로그는 추가만 되기 때문에, 쓰기의 양이 최소화되고, 또 크래시가 발생하더라도 로그의 유효성을 보장하기 비교적 쉽다. 또한 로그를 복제하거나, 테이프에 복사본을 남기거나, 무엇을 하든 쉽고 저렴하다. 로그는 데이터베이스의 정보가 유실되지 않았음을 보장하는데 오랫동안 사용되었지만[17], 로그의 개념은 아주 일반적이어서 평범한 파일 시스템[35, 49]이나 다른 많은 쓰임새가 그다지 분명하지 않은 상황에도 사용될 수 있다. 로그가 진실을 담고 있다면, 대상의 현재 상태는 힌트라고 할 수 있다(엄밀히 힌트는 아니다. 힌트가 올바른지 검사하기 쉽지 않기 때문이다).</p>
<p>로그 기법을 사용하려면, 대상에 대한 모든 변경사항을 변경 프로시저의 이름과 인자로 구성된 로그 항목으로 기록해야 한다. 변경 프로시저는 함수의 성질을 만족해야 하는데, 이는 함수에 동일한 인자를 적용했을 때 항상 동일한 효과를 내야만 한다는 뜻이다. 다르게 말하면, 인자 외에는 프로시저의 동작에 영향을 주는 다른 상태는 없어야 한다. 로그 항목에 명시된 프로시저 호출이 나중에 다시 실행될 수 있으며, 변경될 대상이 변경이 처음 실행됐을 때와 동일한 상태라면, 변경이 처음 실행된 직후와 동일한 상태로 끝나게 된다는 뜻이다. 따라서, 일련의 로그 항목들도 재실행될 수 있으며, 처음 실행 때와 동일한 대상으로 시작하면, 처음 실행에 의해 만들어진 대상과 동일한 대상을 만들어 낸다는 뜻이다.</p>
<p>이를 위해서는, 다음 두가지 조건이 만족되어야 한다.</p>
<ul>
<li>변경 프로시저는 순수한 함수여야 한다.
<ul>
<li>결과는 인자를 제외한 다른 모든 상태의 영향을 받아서는 안된다.</li>
<li>로그가 남게 되는 대상을 제외하고는, 부작용이 없어야 한다.</li>
</ul></li>
<li>변경 프로시저의 인자는 <em>값</em>이어야만 한다. 다음 중 한 종류다.
<ul>
<li>정수, 문자열 등과 같은 즉치값. 즉치값은 배열 혹은 리스트와 같이 크기가 클 수도 있는데, 크기가 크더라도 전체 값을 로그 항목에 복사해야만 한다.</li>
<li><em>변하지 않는</em> 대상에 대한 참조.</li>
</ul></li>
</ul>
<p>대부분의 대상은 당연히 변하지 않을 수 없다. 대상은 갱신되기 때문이다. 허나, 대상의 특정한 버전은 변하지 않는다. 대상이 바뀌게 되면 그에 따라 버전도 바뀐다. 대상의 버전을 혼동없이 가리키는 간단한 방법은 [대상 식별자, 변경 횟수] 쌍이다. 대상 식별자로 대상에 대한 로그를 얻을 수 있고, 특정한 횟수만큼 로그 항목을 재실행하면 대상의 원하는 버전을 얻게 된다. 물론 재실행하려면 다른 대상의 버전들을 찾아야할 필요가 있지만, 모든 변경이 존재하는 버전을 가리키기만 한다면, 어떤 순환도 없을 것이고 이 과정은 끝나게 된다.</p>
<p>예를 들면, 브라보 편집기[24]는 문서를 편집하기 위해서 딱 두 개의 변경 함수만 갖추었다.</p>
<pre class="pseudo"><code>    Replace(old: Interval, new: Interval)
    ChangeProperties(where: Interval, what: FormattingOp)</code></pre>
<p><code>Interval</code>은 [문서 버전, 첫 문자, 끝 문자] 세 쌍이다. <code>FormattingOp</code>는 프로퍼티들에서 프로퍼티들로의 함수다. 여기서 프로퍼티는 <code>italic</code>이나 <code>leftMargin</code>이 될 수 있으며, <code>FormattingOp</code>는 <code>leftMargin := leftMargin + 10</code>이나 <code>italic := true</code>가 될 수 있다. 따라서 단지 두 종류의 로그 항목만 필요하다. 모든 편집 명령은 이 두 변경 함수의 적용으로 환원된다.</p>
<blockquote>
<p>조심해라,<br />싸움에 드는 것을, 그러나 일단 들면,<br />상대방이 너를 경계하게끔 만들어야겠지.</p>
</blockquote>
<p>* <em>행위를 원자적이고 재시작 가능하게 만들어라</em>. 원자적 행위(<em>트랜잭션</em>이라 부르기도 한다)는 완전히 수행되거나 아니면 아무런 영향도 없는 행위이다. 예를 들면, 대부분의 주 저장장치 시스템에서 한 워드를 꺼내 오거나 저장하는 행위는 원자적이다. 오류 대처에서 원자적 행위의 이점은 분명하다. 행위 수행 도중 실패해도 아무런 영향이 없어서, 실패를 복구를 할 때 행위의 어떠한 중간 상태도 다루지 않아도 된다[28]. 데이터베이스 시스템은 이전부터 원자성을 제공해왔는데[17], 행위를 완료하거나 취소하는데 필요한 정보를 저장한 로그를 이용했다. 기본 개념은 각각의 원자적 행위에 유일한 식별자를 부여하고 이 식별자를 그 행위와 관련된 모든 로그 항목에 표시하는 것이다. 행위의 완료 기록은[42] 행위가 진행 중인지, 완료되었는지(처리해야 하는 정리 작업이 남아 있어도 되는 논리적인 완료), 취소되었는지(정리할 것이 남아 있어도 되는 논리적인 취소) 알려준다. 완료 기록의 상태가 변경되는 것도 로그 항목으로 기록된다. 행위의 모든 변경에 대한 로그 항목이 없으면 행위는 완료될 수 없다. 실패하게 되면, 완료된 행위의 로그 항목은 모두 적용하고 취소된 행위의 변경은 되돌려서 복구한다. 이 기법은 다양하게 변형할 수 있다[54].</p>
<p>이 기법이 동작하려면, 로그 항목은 통상적으로 재시작 가능해야 한다. 실행을 완료하기 전에 몇 번이던지 불완전하게 실행되더라도, 결과가 바뀌지 않아야 한다는 뜻이다. 종종 이와 같은 행위를 '멱등(idempotent)'이라고 부른다. 예를 들면, 일군의 변수에 일군의 값을 저장하는 것은 재시작 가능한 행위이다. 하지만 변수의 값을 하나 증가 시키는 것은 재시작 가능한 행위가 아니다. 재시작 가능한 로그 항목은 대상의 현재 상태에 적용할 수 있다. 그러므로 대상을 예전 상태로 복구할 필요가 없다.</p>
<p>이 기초적인 기법은 어떤 종류의 영구 저장 장치에나 사용할 수 있다. 상황이 충분히 단순하다면 좀 변형된 방법도 잘 동작한다. 앞에서 설명했던 알토 파일 시스템을 예로 들면, 실제로는 디스크 레이블과 리더 페이지를 로그로 사용하여 필요할 때 파일 시스템의 다른 자료 구조를 재구축한다. 대부분의 파일 시스템과 마찬가지로, 오직 파일 할당과 디렉토리 조작만이 원자적 행위이다. 알토 파일 시스템은 클라이언트가 변경을 묶어 원자적으로 만들 수 있게 지원하지 않는다. 주니퍼(Juniper) 파일 시스템[35, 49]은 원자적 변경을 훨씬 잘 지원하는데, 각각의 클라이언트가 여러 변경을 임의로 묶어 하나의 원자적 행위로 만드는 것을 허용한다. 주니퍼 파일 시스템은 그림자 페이지(shadow pages)'라는 수법을 쓰는데, 이 수법은 파일 주소를 디스크 주소로 변환해주는 B-트리의 데이터 페이지 포인터를 바꿔서 데이터 페이지를 로그에서 파일로 옮긴다. 이 수법은 칼(Cal) 시스템에서[50] 처음 사용되었다. 평범한 파일 시스템이라도 클라이언트들이 서로 협동한다면 원자적 행위를 구현할 수 있는데, 파일에 접근하기 전에 항상 복구가 필요한지 아닌지 검사하면 된다. 복구가 필요하다면 클라이언트는 특수한 이름을 가진 로그 파일들에 기록된 로그 항목들을 실행한다[40].</p>
<p>원자적 행위를 구현하기가 일반적으로 간단하지는 않지만, 앞의 논의에서 보여주었듯이 널리 알려진 모습 만큼 아주 어렵지는 않다. 때로는 강력하지는 않지만 간편한 방법도 제 기능을 한다. 그레이프바인 메일 전송 및 등록부 시스템[1]을 예로 살펴보자. 이 시스템은 전국적인 규모의 전산망에 연결된 수많은 컴퓨터에 이름들과 배포 목록들을 담은 복제 데이터 베이스를 유지한다. 한 사이트에서 발생한 변경은 메일 시스템 자체를 이용하여 다른 사이트로 퍼져나간다. 이 방식은 변경이 언젠가 도착한다는 것은 보장하지만, 사이트의 장애와 복구 또 전산망 단절로 인해, 변경이 도착하는 순서는 크게 차이가 날 수 있다. 각 변경 메시지에는 시각이 부여되고, 이 시각이 제일 늦은 변경 메시지가 반영된다. 충분한 시간이 흐르면, 모든 사이트는 모든 변경을 받게 될 것이고 일치하게 될 것이다. 하지만, 변경이 퍼져나가는 도중에는 사이트들 사이에 불일치가 일어나기도 하는데, 예를 들어 어떤 사람이 특정한 배포 목록의 구성원인지 아닌지 일치하지 않을 수 있다. 이런 가끔씩 생기는 불일치와 지연은 이 시스템의 유용성에 별로 영향을 주지 않는다.</p>
<h1 id="결론">5. 결론</h1>
<blockquote>
<p>정말 황송하옵게도 떠나나이다, 아버지.</p>
</blockquote>
<p>훌륭한 충고와 일화를 엮은 모음집이라 읽기에 좀 지루할 수 있다. 그러니 잠들기 전에 조금씩 읽으면 가장 좋다고 생각한다. 나는 여기서 언급한 규칙들 대부분을 적어도 한 번은 무시한 적이 있으며, 거의 항상 무시한 것을 후회했다고 증언할 수 있음을 참작해주기 바란다. 아래 참고 문헌 목록은 여기서 간략하게 언급한 시스템이나 기법에 대한 온전한 이야기를 담고 있다. 또한 참고 문헌 중 상당수는 보다 완전한 이론적 설명도 담고 있다.</p>
<p>모든 표어는 이 논문의 시작 부분에 위치한 그림 1에 모아 놓았다.</p>
<h1 id="감사의-말">감사의 말</h1>
<p>이 논문의 초기 원고를 검토해준 많은 자애로운 분들과 프로그램 위원회의 비평에 감사드립니다.</p>
<h1 id="참고문헌">참고문헌</h1>
<section class="footnotes">
<hr />
<ol>
<li id="fn1"><p>이 논문은 제 9회 ACM Symposium on Operating Systems Principles에 처음 발표됐고 Operating Systems Review 15, 5, Oct. 1983, p 33-48에 처음 실렸습니다. 여기에는 조금 수정하여 실었다.<a href="#fnref1">↩</a></p></li>
<li id="fn2"><p>역주. 햄릿 인용은 김정환 역 아침이슬 출판사의 햄릿에서 옮겼다.<a href="#fnref2">↩</a></p></li>
<li id="fn3"><p>역주. 트랩(trap)은 실행 중인 프로그램에 지정한 조건이 발생하면 정해둔 루틴을 실행한다.<a href="#fnref3">↩</a></p></li>
<li id="fn4"><p>역주. 중규모 집적 회로(Medium-Scale Integration).<a href="#fnref4">↩</a></p></li>
</ol>
</section>
</body>
</html>