OkHttp 이해하기 - 6

첫 HttpEngine 생성시는 OkHttpClient와 Request와 forWebSocket의 여부를 참조합니다. forWebSocket은 HTTP 요청이 synchronous call(execute 함수 사용)인 경우에는 항상 false입니다. AsyncCall 을 사용한 asynchronous call(enqueue 함수 사용)인 경우에는 파라메타로 forWebSocket을 넘겨주게 되어 있고 이 값이 HttpEngine의 생성시 넘어오게 됩니다.
sendRequest 부터 시작해 봅니다. 이 함수에서 가장 먼저 하는 일은 헤더의 재생성입니다. 확인하는 헤더의 값은 Host, Connection, Accept-Encoding, Cookie, User-Agent입니다.
Host가 없으면 요청 url로부터 host 값을 찾은 후 이 값을 Host 헤더에 넣어줍니다.
if (request.header("Host") == null) {
  result.header("Host", hostHeader(request.url()));
}
public static String hostHeader(URL url) {
  // getEffectivePort 함수는 url에서 port를 찾고 getDefaultPort는 url의 프로토콜로부터 기본 포트(http는 80, https는 443)를 찾습니다.
  return getEffectivePort(url) != getDefaultPort(url.getProtocol())
      ? url.getHost() + ":" + url.getPort()
      : url.getHost();
}
Connection이 없고 connection의 프로토콜이 http 1.0이 아니면 Connection에 Keep-Alive를 넣어줍니다.
if ((connection == null || connection.getProtocol() != Protocol.HTTP_1_0)
    && request.header("Connection") == null) {
  result.header("Connection", "Keep-Alive");
}
Accep-Encoding이 없으면 OkHttp는 gzip을 기본으로 사용하므로 gzip을 설정해 줍니다.
if (request.header("Accept-Encoding") == null) {
  transparentGzip = true;
  result.header("Accept-Encoding", "gzip");
}
OkHttpClient의 cookie handler를 사용해서 url에 관련된 쿠키들을 찾습니다. 이렇게 찾은 값들을 Cookie와 Cookie2 헤더에 넣어줍니다. OkHttpClient에 별도로 지정하지 않았으면 기본 핸들러가 사용됩니다.
result.cookieHandler = CookieHandler.getDefault();

User-Agent가 없으면 OkHttp의 버전 정보를 넣어줍니다.
if (request.header("User-Agent") == null) {
  result.header("User-Agent", Version.userAgent());
}
다음으로는 내부 캐시를 확인합니다.
InternalCache responseCache = Internal.instance.internalCache(client);
특별한 작업을 해주지 않았으면 null이 될 것입니다. CacheStrategy.Factory를 통해 캐시된 Response가 있는지 찾습니다. 있으면 실제 connect가 필요없이 이 Response를 사용하면 될 것입니다. 캐시된 Response가 없으면 connect 함수를 통해 Connection을 만듭니다. connect 함수에서는 address를 생성하고 라우팅을 위한 정보를 찾아낸 후 이러한 정보들을 담고 있는 Connection을 생성해 줍니다. 이때 Connection은 ConnectionPool을 통해 관리가 됩니다.
Connection을 만들기 위해 제일 먼저 하는 일은 Address를 만드는 것입니다. Request로부터 url을 가져오고 나머지 Address 생성에 필요한 값들은 OkHttpClient로부터 가져옵니다.
private static Address createAddress(OkHttpClient client, Request request)
    throws RequestException {
  String uriHost = request.url().getHost();
  if (uriHost == null || uriHost.length() == 0) {
    throw new RequestException(new UnknownHostException(request.url().toString()));
  }

  SSLSocketFactory sslSocketFactory = null;
  HostnameVerifier hostnameVerifier = null;
  CertificatePinner certificatePinner = null;
  if (request.isHttps()) {
    sslSocketFactory = client.getSslSocketFactory();
    hostnameVerifier = client.getHostnameVerifier();
    certificatePinner = client.getCertificatePinner();
  }

  return new Address(uriHost, getEffectivePort(request.url()),
      client.getSocketFactory(), sslSocketFactory, hostnameVerifier, certificatePinner,
      client.getAuthenticator(), client.getProxy(), client.getProtocols(),
      client.getConnectionSpecs(), client.getProxySelector());
}
Address class는 connection에 관련된 정보들을 모아 놓고 있는 class입니다. 대부분 get함수로 이루어져 있습니다.
다음으로는 서버에 연결하기 위한 route를 설정합니다. RouterSelector.get 함수를 통해 RouteSelector를 생성할 수 있습니다.
public static RouteSelector get(Address address, Request request, OkHttpClient client)
    throws IOException {
  return new RouteSelector(address, request.uri(), client);
}

OkHttp 이해하기 - 5

HTTP 요청을 할 때마다 이에 대한 정보를 OkHttpClient가 저장하고 있습니다. 큐에 저장해 놨다가 나중에 실행한다던가 실행중인 요청을 취소한다던가 하는 것들을 하기 위해서 입니다.
크게 보면 바로 실행하는(Call에서의 execute 함수를 통한 실행)하는 것과 큐에 저장해 놓았다가 나중에 실행하는(Call에서의 enqueue 함수를 통한 실행)이 있습니다.
바로 실행하는 요청을 저장하기 위해 아래의 Deque를 사용합니다.
private final Deque<Call> executedCalls = new ArrayDeque<>();
바로 실행하기 때문에 이의 관리는 간단합니다.executed가 호출되면 executedCalls에 넣고 finished가 호출되면 executedCalls에서 빼줍니다.
나중에 실행하는 요청을 저장하기 위해서는 아래 두개의 Deque를 사용합니다. 현재 실행중인 요청은 runningCalls에 넣고 최대 요청수가 다 찾으면 readyCalls에 넣어줍니다. runningCall에서의 요청중 끝난 것이 있으면 최대 요청수를 넘었는지 아닌지 확인한 후 넘지 않았으면 readyCalls에서 앞에서 부터 순서대로 꺼내어 최대 요청수까지 실행시켜줍니다.
private final Deque<AsyncCall> readyCalls = new ArrayDeque<>();
private final Deque<AsyncCall> runningCalls = new ArrayDeque<>();
쓰레드 관리를 위해 기본으로 ThreadPoolExecutor를 제공하고 최대 요청수는 64를, 호스트당 최대 요청 수는 5를 기본 값으로 합니다. 비동기 요청을 위해 enqueue를 사용하면 아래와 같이 현재 실행중인 요청이 최대 요청수를 넘지 않고, 호스트당 최대 요청 수도 최대 값을 넘지 않으면 runningCalls에 요청을 넣고 바로 실행을 시켜줍니다. 이 조건을 만족하지 못하면 나중에 다른 요청이 끝나면 실행될 수 있도록 readyCall에 넣어줍니다.
synchronized void enqueue(AsyncCall call) {
  if (runningCalls.size() < maxRequests && runningCallsForHost(call) < maxRequestsPerHost) {
    runningCalls.add(call);
    getExecutorService().execute(call);
  } else {
    readyCalls.add(call);
  }
}
앞의 Call안의 AsyncCall의 execute 함수를 보면 맨 마지막에 모든 작업이 끝나면 finished 를 호출해 줍니다. 이 함수에서 작업이 끝난 AsyncCall을 runningCalls에서 제거하고 promoteCalls 함수를 호출하여 또다른 요청의 실행이 가능하면 readyCalls에서 하나를 꺼내어 runningCalls에 넣고 실행을 시켜줍니다.
synchronized void finished(AsyncCall call) {
  if (!runningCalls.remove(call)) throw new AssertionError("AsyncCall wasn't running!");
  promoteCalls();
}
private void promoteCalls() {
  if (runningCalls.size() >= maxRequests) return; // Already running max capacity.
  if (readyCalls.isEmpty()) return; // No ready calls to promote.

  for (Iterator<AsyncCall> i = readyCalls.iterator(); i.hasNext(); ) {
    AsyncCall call = i.next();

    if (runningCallsForHost(call) < maxRequestsPerHost) {
      i.remove();
      runningCalls.add(call);
      getExecutorService().execute(call);
    }

    if (runningCalls.size() >= maxRequests) return; // Reached max capacity.
  }
}
요청의 취소는 cancel 함수를 통해 할 수 있습니다. 이때 파라메터로 tag를 넣어줍니다. 실행 요청은 readyCall와 runningCalls와 executedCalls 이 셋중의 하나에 들어 있을 것입니다. 그러므로 이 셋을 순서대로 루프를 돌면서 원하는 Call을 찾아서 cancel 함수를 호출해 줍니다. 음 근데 readyCalls와 runningCalls는 같은 것인데 취소해주는 방식이 다르네요. 결국 같은거 같은데... 왜 이렇게 되어 있을까요?

OkHttp 이해하기 - 4

OkHttp를 통한 HTTP 요청을 하려면 가장 먼저 아래처럼 클라이언트를 만듭니다.
OkHttpClient client = new OkHttpClient();
그리고 나서 여기에 넘겨줄 Request를 만들어 줍니다.
Request request = new Request.Builder().url("http://www.google.com").build();
그리고 아래처럼 execute() 함수를 호출하면 요청에 대한 응답이 넘어오게 됩니다.
Response response = client.newCall(request).execute();

OkHttpClient는 앞으로의 HTTP 요청에 사용되는 설정등을 가지고 있습니다. 따라서, 이후 HTTP 요청을 하면 이를 기준으로 요청이 이루어 집니다. 다음으로 newCall은 어떤 역할을 할까요? newCall은 다음과 같이 Call의 인스턴스를 생성합니다.
public Call newCall(Request request) {
  return new Call(this, request);
}
Call 클래스는 하나의 HTTP 요청에 따른 Response/Request를 처리합니다. 생성시 OkHttpClient와 Request를 받아서 저장하고 있으며 필요에 따라 이것들의 값을 사용하게 됩니다. 그런데 OkHttpClient는 그대로 저장하지 않고 client.copyWithDefaults()를 통해 저장합니다. 왜 그럴까요? 이렇게 복사를 해서 저장해 놓지 않으면 혹시라도 나중에 client가 변경이 되면 그 변경사항이 지금하고 있는 HTTP 요청에 반영이 되기 때문입니다. 지금의 요청은 지금시점의 client가 적용이 되어야 하겠죠? 그래서 복사를 하는 것입니다.
Call 클래스는 바로 요청을 날리는 execute() 함수와 나중에 실행되는 enqueue() 함수가 있습니다. 먼저 execute 함수부터 살펴보죠. 한번만 실행이 가능하도록 하기 위해 executed 변수를 사용합니다. 시작시 true로 설정을 해주어서 한번 실행을 확인합니다. 다음으로는 client의 dispatcher에 요청이 실행되었음을 알리고 끝나면 끝났음을 알립니다. 이것을 함으로서 실행 중간에 취소할 수 있게 합니다. getResponseWithInterceptorChain를 통해서 서버에 Request를 보내고 이에 대한 Response를 받아옵니다.
public Response execute() throws IOException {
  synchronized (this) {
    if (executed) throw new IllegalStateException("Already Executed");
    executed = true;
  }
  try {
    client.getDispatcher().executed(this);
    Response result = getResponseWithInterceptorChain(false);
    if (result == null) throw new IOException("Canceled");
    return result;
  } finally {
    client.getDispatcher().finished(this);
  }
}
그런데 요청을 하기전에 한가지 할 수 있는 것이 있습니다. Request를 변경하는 것입니다. 예를 들어, Request를 항상 zip으로 압축해서 서버에 보내고자 한다고 생각해 봅시다. 이 경우 client의 interceptor에 zip 압축을 하는 interceptor를 저장해 놓습니다. 그러면 Request를 보내기 전에 interceptor를 통해 변경된 Request를 받은 후 이 Request를 서버에 보내는 일을 하게 됩니다. 이 일을 해주는 함수가 getResponseWithInterrceptorChain 함수입니다. 보시다시피 ApplicationInterceptorChain에 원래의 Request를 넣은 후 Interceptor chain을 실행합니다.
private Response getResponseWithInterceptorChain(boolean forWebSocket) throws IOException {
  Interceptor.Chain chain = new ApplicationInterceptorChain(0, originalRequest, forWebSocket);
  return chain.proceed(originalRequest);
}

ApplicationInterceptorChain은 Interceptor.Chain을 구현한 클래스로서 proceed 함수를 보면 가장 먼저 하는 일이 client에 interceptor가 있는지 확인합니다. 그래서 있으면 현재 index의 interceptor에 Chain을 넣어줍니다. index가 0에서 부터 1씩 증가하는 걸 보면 결국 제일 앞에서부터 순서대로 마지막까지 interceptor가 호출될 것임을 알 수 있습니다. interceptor는 Chain의 Request를 받아서 변경을 하고 다시 Chain의 proceed를 호출해주는 역할을 합니다. 그러면 가장 마지막에는 결국 getResponse가 호출되겠네요.
@Override public Response proceed(Request request) throws IOException {
  if (index < client.interceptors().size()) {
    // There's another interceptor in the chain. Call that.
    Interceptor.Chain chain = new ApplicationInterceptorChain(index + 1, request, forWebSocket);
    return client.interceptors().get(index).intercept(chain);
  } else {
    // No more interceptors. Do HTTP.
    return getResponse(request, forWebSocket);
  }
}

다음으로 enqueue를 살펴보지요. 한번 실행을 위해 executed를 true로 설정하는 것은 똑같습니다. 다음으로는 dispatcher에서 enqueue 함수를 호출하는데 이때 AsyncCall을 사용합니다.
void enqueue(Callback responseCallback, boolean forWebSocket) {
  synchronized (this) {
    if (executed) throw new IllegalStateException("Already Executed");
    executed = true;
  }
  client.getDispatcher().enqueue(new AsyncCall(responseCallback, forWebSocket));
}
나중에 dispatcher가 HTTP 요청을 실행할 상황이 되면 큐에 넣어둔 AsyncCall의 execute 함수가 호출이 됩니다. 함수를 살펴보면 간단합니다. 앞에서의 Call의 execute 함수와 같이 getResponseWithInterceptorChain를 호출하여 Response를 얻어오고 끝났음을 dispatcher에 알려줍니다. 하나의 차이점은 여기서의 호출은 다른 쓰레드에서 이루어지고 있는 것이므로 정상적으로 끝났는지 아니면 중간에 취소가 있었는지를 원래의 호출쪽에 알려주는 콜백이 들어가 있다는 점입니다. 이 역할은 Callback 클래스에서의 onResponse와 onFailure 함수를 통해 이루어지게 됩니다.
이제 getResponse 함수를 살펴봅시다.
가장 먼저 body를 확인하여 body가 있으면 새로운 Request를 만들어 줍니다. 이렇게 새 Request를 만드는 이유는 body가 있다면 헤더의 내용이 달라지기 때문입니다. body와 관련된 헤더를 처리하는 부분은 아래와 같습니다.
  // Copy body metadata to the appropriate request headers.
  RequestBody body = request.body();
  if (body != null) {
    Request.Builder requestBuilder = request.newBuilder();

    MediaType contentType = body.contentType();
    if (contentType != null) {
      // Content Type이 지정되어 있으면 헤더에 넣어준다.
      requestBuilder.header("Content-Type", contentType.toString());
    }

    long contentLength = body.contentLength();
    if (contentLength != -1) {
      // 길이를 알면
      requestBuilder.header("Content-Length", Long.toString(contentLength));
      requestBuilder.removeHeader("Transfer-Encoding");
    } else {
      // 길이를 모르면
      requestBuilder.header("Transfer-Encoding", "chunked");
      requestBuilder.removeHeader("Content-Length");
    }

    request = requestBuilder.build();
  }
다음으로 HttpEngine을 생성해 줍니다. 이 HttpEngine에서 request와 response를 처리해줍니다. 이에 사용되는 함수는 다음과 같습니다. sendRequest, readResponse, getResponse. 응답을 받고 나면 followUpRequest 함수를 통해 redirect등의 작업이 필요한지를 확인합니다. followUp이 null이 아니면 이 작업이 필요하다는 것입니다. 그럴 경우엔 기존의 HttpEngine을 종료(close 함수 사용)하고 새로운 HttpEngine을 만들어서 사용합니다. 이때의 차이점은 Connection은 이전에 사용하던 것을 그대로 재활용 한다는 것입니다.

OkHttp 이해하기 - 3

Request를 만들 때 body를 넣어주고 싶으면 RequestBody를 먼저 만들고 이것을 Request에 넣어주어야 합니다.
기억을 더듬어 보면 method 관련 함수인 post와 delete와 put과 patch를 설정해 줄 때 RequestBody를 같이 설정해 줄 수 있게 되어 있는 것이 기억나실 겁니다. 이 이외의 방법은 없죠.
그런데 RequestBody는 abstract로 다음과 같이 선언되어 있습니다.
public abstract class RequestBody {
  public abstract MediaType contentType();
  public long contentLength() throws IOException {
    return -1;
  }
  public abstract void writeTo(BufferedSink sink) throws IOException;
}

이런 우리가 직접 RequestBody를 생성할 수 없게 되어 있네요. 그럼 어떻게 해야 할까요? 그래서 RequestBody를 생성해주는 static함수들이 정의되어 있습니다. 정의를 보면 이 함수들은 content type과 content를 파라메타로 받아서 이것을 가지고 RequestBody를 생성하게 되어 있습니다. 대부분 비슷하므로 대표로 하나만 살펴보겠습니다.
public static RequestBody create(MediaType contentType, String content) {
  Charset charset = Util.UTF_8;
  if (contentType != null) {
    // content type이 설정되어 있는데 charset이 없으면 UTF-8로 설정해 줍니다.
    charset = contentType.charset();
    if (charset == null) {
      charset = Util.UTF_8;
      contentType = MediaType.parse(contentType + "; charset=utf-8");
    }
  }
  byte[] bytes = content.getBytes(charset);
  return create(contentType, bytes);
}

public static RequestBody create(final MediaType contentType, final byte[] content) {
  return create(contentType, content, 0, content.length);
}

content가 null이면 NullPointerException을 발생시키고요, abstract인 RequestBody를 바로 간단하게 생성해 줍니다.
public static RequestBody create(final MediaType contentType, final byte[] content,
    final int offset, final int byteCount) {
  if (content == null) throw new NullPointerException("content == null");
  // content의 내용중 offset에서부터 byteCount까지를 body에 넣어주니까 offset에서부터 byteCount까지가 content의 length안에 있어야 합니다. 아니면 ArrayIndexOutOfBoundsException을 발생시키는 함수입니다.
  Util.checkOffsetAndCount(content.length, offset, byteCount);
  return new RequestBody() {
    @Override public MediaType contentType() {
      return contentType;
    }

    @Override public long contentLength() {
      return byteCount;
    }

    @Override public void writeTo(BufferedSink sink) throws IOException {
      sink.write(content, offset, byteCount);
    }
  };
}

MediaType은 RFC 2045의 구현입니다. 간단히 설명하면, media type은 type과 subtype과 0개 이상의 옵션 파라메터로 이루어져 있습니다. 예를 들면 text/html; charset=UTF-8 의 경우 type은 text이고 subtype은 html이고 charset=UTF-8은 character encoding을 알려주는 옵션 파라메터입니다. MediaType은 우리가 직접 MediaType을 생성하지 않고 쉽게 생성할 수 있는 static 함수를 제공합니다. 주어진 string을 Pattern을 사용해서 분리해 냅니다.
public static MediaType parse(String string) {
  // string으로부터 type과 subtype을 찾습니다.
  Matcher typeSubtype = TYPE_SUBTYPE.matcher(string);
  // 패턴이 맞지 않으면 null을 리턴합니다.
  if (!typeSubtype.lookingAt()) return null;
  // group은 Pattern에 regular expression을 넘겨줄 때 ()에 의해 둘러싸이는 부분을 의미합니다. TYPE_SUBTYPE의 경우는 앞의 TOKEN이 group(1)이고 뒤의 TOKEN의 group(2)가 되겠네요.
  String type = typeSubtype.group(1).toLowerCase(Locale.US);
  String subtype = typeSubtype.group(2).toLowerCase(Locale.US);

  // 옵션 파라메터에서 charset를 찾습니다.
  String charset = null;
  // group에서 (?는 제외됩니다. 따라서 TOKEN, TOKEN, QUOTED의 순으로 group이 지정되게 됩니다.
  Matcher parameter = PARAMETER.matcher(string);
  for (int s = typeSubtype.end(); s < string.length(); s = parameter.end()) {
    parameter.region(s, string.length());
    if (!parameter.lookingAt()) return null; // This is not a well-formed media type.

    String name = parameter.group(1);
    if (name == null || !name.equalsIgnoreCase("charset")) continue;
    String charsetParameter = parameter.group(2) != null
        ? parameter.group(2)  // Value is a token.
        : parameter.group(3); // Value is a quoted string.
    // charset은 하나만 설정할 수 있습니다. 여러개인 경우 IllegalArgumentException을 발생시킵니다.
    if (charset != null && !charsetParameter.equalsIgnoreCase(charset)) {
      throw new IllegalArgumentException("Multiple different charsets: " + string);
    }
    charset = charsetParameter;
  }

  return new MediaType(string, type, subtype, charset);
}

OkHttp 이해하기 - 2

Headers는 헤더 정보를 name과 value로 담고 있습니다. Request에 의해 사용됩니다.

Headers도 Builder에 의해 편하게 생성될 수 있습니다. Builder는 헤더들을 ArrayList에 name과 value를 순서대로 넣어서 저장하고 있습니다. i번째에 name이 저장되어 있다면 i+1번째에 value가 저장되어 있는 것이지요.

private final List<String> namesAndValues = new ArrayList<>(20);

헤더를 넣기위한 함수를 두 가지를 제공합니다. addLenient와 add입니다. addLenient는 헤더에 대한 검증없이 무조건 저장합니다. 외부로부터 온 헤더거나 캐시되어 있던걸 다시 꺼내오는 경우에 적합한 함수입니다. 이러한 경우는 이미 검증이 된 헤더로 볼 수 있으니까요.

addLenient를 살펴보겠습니다. 헤더는 "name: value"의 형태를 띄고 있지요. 그러니 제일 먼저 첫번째 문자 이후에서 ":"의 유무를 파악합니다. ":"가 있으면 이를 기준으로 둘로 나누어 name과 value로 저장합니다. 만약 ":"가 없으면 ":"가 혹시 첫번째 문자인지 확인합니다. 이 경우는 초기 SPDY에서 발생할 수 있는 상황입니다. 이 경우 name은 비어있는 스트링으로 하고 ":"를 제외한 나머지를 value로 저장합니다. ":"이 전혀 없는 경우라면 그냥 name은 비어있는 스트링으로 하고 주어진 값을 그대로 value로 저장합니다.

Builder addLenient(String line) {

  int index = line.indexOf(":", 1);

  if (index != -1) {

    return addLenient(line.substring(0, index), line.substring(index + 1));

  } else if (line.startsWith(":")) {

    // Work around empty header names and header names that start with a

    // colon (created by old broken SPDY versions of the response cache).

    return addLenient("", line.substring(1)); // Empty header name.

  } else {

    return addLenient("", line); // No header name.

  }

}

앞에서 말했듯이 name을 먼저 저장하고 그 바로 뒤에 value를 저장합니다. value의 경우 trim을 해서 저장하는 것에 유의하세요.

Builder addLenient(String name, String value) {

  namesAndValues.add(name);

  namesAndValues.add(value.trim());

  return this;

}

이제 add함수를 살펴보겠습니다. 이 경우는 ":"가 반드시 있는지 확인합니다. 없으면 IllegalArgumentException을 내보냅니다. 여기서는 name에 trim을 하는 것에 유의하세요.

public Builder add(String line) {

  int index = line.indexOf(":");

  if (index == -1) {

    throw new IllegalArgumentException("Unexpected header: " + line);

  }

  return add(line.substring(0, index).trim(), line.substring(index + 1));

}

name과 value는 null이 아니어야 합니다. 또한 name의 경우는 길이가 0이 아니어야 하죠. 그렇기 때문에 앞에서 보았듯이 name은 저장을 위해 값을 넘겨줄 때 trim을 한 값을 넘겨주고 value는 나중에 최종적으로 저장할 때 trim을 해서 저장하는 형태를 취하고 있는 것입니다. 또한 name과 value 둘다 null value('\0')를 포함하고 있어서는 안됩니다.

public Builder add(String name, String value) {

  if (name == null) throw new IllegalArgumentException("name == null");

  if (value == null) throw new IllegalArgumentException("value == null");

  if (name.length() == 0 || name.indexOf('\0') != -1 || value.indexOf('\0') != -1) {

    throw new IllegalArgumentException("Unexpected header: " + name + ": " + value);

  }

  return addLenient(name, value);

}

특정 name의 헤더를 지우는 함수를 제공하고 있습니다. 앞에서 name과 value가 어떻게 저장되어 있는지 설명했죠? 그에 따라 찾아낸 name의 위치와 바로 그 다음의 위치도 같이 지우면 name과 value가 다 지워지게 됩니다. for문을 보면 2씩 증가시켜가면서 찾는 것을 볼 수 있습니다.

public Builder removeAll(String name) {

  for (int i = 0; i < namesAndValues.size(); i += 2) {

    if (name.equalsIgnoreCase(namesAndValues.get(i))) {

      namesAndValues.remove(i); // name

      namesAndValues.remove(i); // value

      i -= 2;

    }

  }

  return this;

}

위의 add와 addLenient는 name과 value가 하나의 스트링으로 되어 있는 값을 받아서 이를 둘로 나누어서 처리합니다. 만약 name과 value가 이미 나누어져 있는 값을 저장하고 싶으면 아래의 set함수를 사용합니다. 간단하네요. 먼저 name이 있으면 지우기 위해 removeAll을 먼저 호출해 주고 나고 name과 value를 저장합니다.

public Builder set(String name, String value) {

  removeAll(name);

  add(name, value);

  return this;

}

헤더의 name으로 value를 찾는 함수도 제공해주고 있습니다. for문을 2씩 증가시켜가면서 매칭되는 name의 위치를 찾은 후 그 다음 위치의 값을 리턴해 줍니다.

public String get(String name) {

  for (int i = namesAndValues.size() - 2; i >= 0; i -= 2) {

    if (name.equalsIgnoreCase(namesAndValues.get(i))) {

      return namesAndValues.get(i + 1);

    }

  }

  return null;

}

마지막으로 build를 호출하면 이제까지 저장된 헤더들을 Headers에 저장하고 이를 리턴해줍니다.

public Headers build() {

  return new Headers(this);

}

Headers는 name과 value를 String 배열에 저장합니다. 따라서 Builder를 생성자에서 받을 때 builder의 nameAndValues를 배열로 바꾸어서 저장합니다.

private Headers(Builder builder) {

  this.namesAndValues = builder.namesAndValues.toArray(new String[builder.namesAndValues.size()]);

}

Headers는 내부에 저장된 헤더를 참조하기 위한 다양한 함수들을 제공합니다. 이중 간단한 것은 제외하고 몇가지만 살펴보겠습니다.

헤더의 name들만을 모아서 리턴해주는 names()함수가 있습니다. 찾은 name을 TreeSet에 저장하고 값을 변경할 수 없도록하기 위해 Collections.unmodifiableSet으로 리턴합니다.

public Set<String> names() {

  TreeSet<String> result = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

  for (int i = 0, size = size(); i < size; i++) {

    result.add(name(i));

  }

  return Collections.unmodifiableSet(result);

}

특정 헤더 name의 value들 만을 리턴해주는 values 함수가 있습니다. 파라메터로 넘어온 name에 매치되는 위치를 찾아서 그 위치의 value를 List<String>에 저장하고 찾은 값이 있으면 Collections.unmodifiableList를, 없으면 Collections.<String>emptyList를 리턴합니다. 여기서도 value를 변경하지 못하도록 하기 위해 Collections의 함수들을 사용합니다.

public List<String> values(String name) {

  List<String> result = null;

  for (int i = 0, size = size(); i < size; i++) {

    if (name.equalsIgnoreCase(name(i))) {

      if (result == null) result = new ArrayList<>(2);

      result.add(value(i));

    }

  }

  return result != null

      ? Collections.unmodifiableList(result)

      : Collections.<String>emptyList();

}

Header를 다시 Builder로 변환하려면 String 배열을 List로 변환해 주어야 합니다. 이를 위해 Collections.addAll 함수를 사용합니다.

public Builder newBuilder() {

  Builder result = new Builder();

  Collections.addAll(result.namesAndValues, namesAndValues);

  return result;

}

names()와 values()의 혼합이라 할 수 있는 toMultimap() 함수도 제공됩니다. LinkedHashMap에 key를 name으로 해서 이에 속한 value들을 List<String>으로 저장합니다. 이 경우는 modify가 가능하게 리턴하는군요. 왜일까요?

public Map<String, List<String>> toMultimap() {

  Map<String, List<String>> result = new LinkedHashMap<String, List<String>>();

  for (int i = 0, size = size(); i < size; i++) {

    String name = name(i);

    List<String> values = result.get(name);

    if (values == null) {

      values = new ArrayList<>(2);

      result.put(name, values);

    }

    values.add(value(i));

  }

  return result;

}

위 함수들에 추가해서 두 개의 편리한 함수를 제공합니다. 헤더를 Map의 형태로 가지고 있으면 이를 Headers로 변환해주는 of(Map<String, String> headers) 함수와 여러개의 String 헤더를 한번 호출로 Headers로 변환해주는 of(String... namesAndValues)입니다. 이 두 함수의 구현 자체는 특별할 것이 없으므로 구현에 대한 설명은 생략하겠습니다.

앞에서 보았던 Request의 Builder와 패턴이 거의 똑같습니다. 이정도면 Builder를 어떻게 만들고 어떻게 사용하면 되는지도 쉽게 이해할 수 있겠네요.

OkHttp 이해하기 - 1

OkHttp를 사용하여 http 요청을 하려면 가장 먼저 해야할 일이 Request를 만드는 것입니다. 이 Request를 만들기 위해 Request.Builder를 제공합니다.

public final class Request {
  ...
  // Request를 만들기 위한 Builder 제공
  public static class Builder {
    ...
  }
}

그럼 Builder를 살펴봅시다.
Builder를 생성할 때 접속할 URL, 접속할 때 사용할 헤더들, 요청 바디 그리고 나중에 요청을 취소할 때 사용할 tag를 주어서 생성할 수 있습니다. 이것들을 하나하나 알아보겠습니다.
접속할 URL은 HttpUrl이나 String 또는 URL을 통해서 넣어줄 수 있습니다. 구현은 아래와 같습니다.

public Builder url(HttpUrl url) {
  if (url == null) throw new IllegalArgumentException("url == null");
  this.url = url;
  return this;
}
HttpUrl을 쓰는 경우에는 간단하네요. 그냥 내부 변수에 그대로 가지고 있게 됩니다.
url 스트링을 그대로 넘겨주는 경우에는 아래와 같이 HttpUrl로 변환하는 과정을 거치게 됩니다.
public Builder url(String url) {
  if (url == null) throw new IllegalArgumentException("url == null");

  // 웹소켓 url인지를 확인한 후 http url로 변경해 줍니다.
  if (url.regionMatches(true, 0, "ws:", 0, 3)) {
    url = "http:" + url.substring(3);
  } else if (url.regionMatches(true, 0, "wss:", 0, 4)) {
    url = "https:" + url.substring(4);
  }
  // string을 HttpUrl로 변환합니다. HttpUrl이 알아서 변환해줍니다.
  HttpUrl parsed = HttpUrl.parse(url);
  if (parsed == null) throw new IllegalArgumentException("unexpected url: " + url);
  return url(parsed);
}
URL의 HttpUrl로의 변환도 간단하네요. HttpUrl이 알아서 해줍니다.
public Builder url(URL url) {
  if (url == null) throw new IllegalArgumentException("url == null");
  HttpUrl parsed = HttpUrl.get(url);
  if (parsed == null) throw new IllegalArgumentException("unexpected url: " + url);
  return url(parsed);
}

다음으로는 헤더을 포함시킬 수 있습니다.
(헤더는 Headers라는 클래스로 구현되어 있습니다. 이에 대한 내용은 나중에 살펴봅니다.)

헤더가 중복이 되지 않게 추가하고 싶으면 아래의 함수를 사용합니다.
public Builder header(String name, String value) {
  headers.set(name, value);
  return this;
}
기존에 같은 이름의 헤더가 있어도 중복해서 추가하고 싶으면 아래의 함수를 사용합니다.
public Builder addHeader(String name, String value) {
  headers.add(name, value);
  return this;
}
특정 이름의 헤더를 지우고 싶으면 아래의 함수를 사용합니다.
public Builder removeHeader(String name) {
  headers.removeAll(name);
  return this;
}
기존의 모든 헤더를 지우고 새로운 헤더의 집합으로 바꾸고 싶으면 아래의 함수를 사용합니다.
public Builder headers(Headers headers) {
  this.headers = headers.newBuilder();
  return this;
}
헤더에 "Cache-Control"을 위한 값을 설정할 수 있는 함수는 따로 있습니다.
만약 cacheControl에 비어있는 스트링을 주면 기존의 "Cache-Control"값을 제거하고 값이 있으면 그 값을 설정하는 함수입니다.
public Builder cacheControl(CacheControl cacheControl) {
  String value = cacheControl.toString();
  if (value.isEmpty()) return removeHeader("Cache-Control");
  return header("Cache-Control", value);
}

Builder의 기본 method는 "GET"으로 되어 있습니다. 이를 바꾸고 싶으면 다음의 함수들을 사용합니다.
public Builder get() {
  return method("GET", null);
}

public Builder head() {
  return method("HEAD", null);
}

public Builder post(RequestBody body) {
  return method("POST", body);
}

public Builder delete(RequestBody body) {
  return method("DELETE", body);
}

public Builder delete() {
  return delete(RequestBody.create(null, new byte[0]));
}

public Builder put(RequestBody body) {
  return method("PUT", body);
}

public Builder patch(RequestBody body) {
  return method("PATCH", body);
}

이들이 호출해주는 method함수는 다음과 같습니다. 설정한 method 값에 따라 body가 반드시 있어야 하는지 아니면 반드시 없어야 하는지 등을 확인하고 문제가 없으면 method와 body를 설정을 해줍니다.
public Builder method(String method, RequestBody body) {
  if (method == null || method.length() == 0) {
    throw new IllegalArgumentException("method == null || method.length() == 0");
  }
  if (body != null && !HttpMethod.permitsRequestBody(method)) {
    throw new IllegalArgumentException("method " + method + " must not have a request body.");
  }
  if (body == null && HttpMethod.requiresRequestBody(method)) {
    throw new IllegalArgumentException("method " + method + " must have a request body.");
  }
  this.method = method;
  this.body = body;
  return this;
}
method와 body와의 관계는 아래와 같이 확인합니다.
POST와 PUT과 PATCH는 body가 반드시 있어야 하구요.
public static boolean requiresRequestBody(String method) {
  return method.equals("POST")
      || method.equals("PUT")
      || method.equals("PATCH");
}
POST와 PUT과 PATCH와 DELETE를 제외한 나머지는 body가 없어야 합니다. DELETE는 body가 있을 수도 있고 없을 수도 있
public static boolean permitsRequestBody(String method) {
  return requiresRequestBody(method)
      || method.equals("DELETE"); // Permitted as spec is ambiguous.
}

tag 설정은 아래와 같이 간단합니다.
public Builder tag(Object tag) {
  this.tag = tag;
  return this;
}
앞에서 tag는 요청을 취소할 때 사용하기 위한 값이라고 했는데요. 만약에 이 설정을 안해주면 Request 자체를 사용해서 요청을 취소할 수도 있습니다.

이와같이 Request에 필요한 값들을 설정한 뒤에는 build() 함수를 호출해 주면 됩니다.
public Request build() {
  if (url == null) throw new IllegalStateException("url == null");
  return new Request(this);
}
Request class는 이 Builder를 받아서 필요한 값들을 설정해하고 나중에 필요할 때 이 값들을 꺼낼 수 있는 getter를 제공합니다. 이 함수들은 간단하니 따로 살펴보지는 않겠습니다.
Request에서는 HttpUrl의 형태로 url을 저장하고 있는데요. 이것을 URL이나 URI로 내보내주는 함수를 제공하고 있습니다. 모두 처음 요청시 url로부터 값을 만들어서 저장해놓고 두번째 요청부터는 저장해 놓은 값을 사용하는 lazily initialized의 형태를 취하고 있습니다.
public URL url() {
  URL result = javaNetUrl;
  return result != null ? result : (javaNetUrl = url.url());
}

public URI uri() throws IOException {
  try {
    URI result = javaNetUri;
    return result != null ? result : (javaNetUri = url.uri());
  } catch (IllegalStateException e) {
    throw new IOException(e.getMessage());
  }
}
cache control의 경우도 마찬가지로 구현되어 있는 것을 아래의 함수로 보실 수 있습니다.
public CacheControl cacheControl() {
  CacheControl result = cacheControl;
  return result != null ? result : (cacheControl = CacheControl.parse(headers));
}
여기에 추가로 Request class는 거꾸로 Builder로 내보낼 수 있는 함수를 제공합니다. 이를 통해 Request와 Builder간에 서로 편하게 변환이 가능하게 됩니다.
public Builder newBuilder() {
  return new Builder(this);
}

마지막으로 알아야 할 것은 Builder를 만들때 잘못된 값을 넣어주는 경우에는 모두 IllegalArgumentException을 발생하게 되어 있습니다. 이에 대한 catch가 필요할 수도 있겠네요.

정리해보면 Builder를 통해 HTTP 요청에 필요한 Request를 만들어 줍니다. Builder에 설정해주는 값은 url, method, headers, body, tag의 다섯가지가 있습니다.
headers의 타입인 Headers와 body의 타입인 RequestBody는 다음에 살펴보겠습니다.

기획서에 대한 글을 읽고...

기확자와 기획서, 애증의 관계
http://minieetea.com/2014/07/archives/1903

자기전에 트위터 하다가 위의 글을 읽고 공감도 가고 생각나는 것들이 있어서 안자고 이렇게 글을...

회사에 사람이 조금씩 늘어나면서 자꾸 뭔가 프로세스를 만들려고 한다. 예를 들면, 이런거지. 기획 -> 디자인 -> 개발. 또한 하나를 할 때도 린하게 하기 보다는 큰 그림을 그리고 모든 것을 완벽(스스로 생각할 때 그렇겠지?)하게 한 다음에 진행을 하고 싶어들 하는 것 같다. 그런데, 난 이것에 반대의 입장이다. 세상에 완벽한게 있을까?(물론 애플은 뭘 내놓아도 참 잘 만들긴 하더라만). 특히나 멤버들의 능력이 엄청나게 뛰어나지 않은 상태에서는 절대 불가능할 것이다. 그러니 완벽하게 하려고 하면 할 수록 시간만 많이 잡아먹고 결국에는 그냥 무난한 또는 별거 아닌 결과만 나오게 된다고 생각한다.

나는 이것보다는 점진적으로 조금씩 무언가를 해나가는 것이 더 낫다고 생각한다.(린이 이런거지?) 회사에서 모바일 앱을 개발한다면 앱을 쓰다보면 불편한 점, 있으면 좋을 것 같은 기능들이 보일 것이다. 이것들을 그냥 바로바로 주위에 이야기 하는 거다. 개발자가 간단히 작업할 수 있는 일 같으면 개발자에게 바로 이야기해서 작업을 하도록 하고, 좀 더 심도있는 이야기가 필요할 것 같으면 스탠드업 미팅(이걸 한다면!) 같은 시간에 이야기를 꺼내어 관련된 사람들이 모여서 틀을 만들고, 간단하게 정리하고, 개발자는 그걸 구현하고, 베타 테스트를 하고, 반응이 좋으면 릴리즈를 하고 좋지 않으면 제거하고. 제거의 경우 시간낭비로 볼 수도 있겠지만 난 이러한 것들이 모여서 더 나은 발전을 이룰 수 있을 거라고 생각한다.

이렇게 어떤 생각이 떠올랐을 때 그걸 기획하고 디자인하고등등 너무 프로세스에 얽매이기 보다는 그냥 바로바로 만들어서 실제로 사용해 보는 것이 머리로만 고민하는 것 보다는 훨씬 더 빠르게 앱을 발전시킬 수 있다고 믿는다. 사용자의 피드백도 금방 얻을 수 있잖아?

BitMessage 분석

command, address version number, stream number, label, 개수, passphrase, hash값의 앞의 몇자리를 0x00으로 할 것인가, nonce trials per byte, payload length extra bytes
현재 최신 address version number는 4
nonce trials per byte는 현재 320이 최소, payload length exxtra bytes는 현재 1400이 최소

command: createChan, joinChan, createRandomAddress, createDeterministicAddress, getDeterministicAddress

address 만들기
1. 32bytes random으로 private signing key와 private encryption key를 만든다.
2. Elliptic Curve DSA 알고리즘 사용하여 public key 생성한다. 64bytes가 만들어진다.
3. 앞에서 생성된 두개(signing과 encryption)의 public key를 앞뒤로 붙인후(public signing key + public encryption key) sha512에 의한 hash를 구한다.
4. 구해진 digest를 가지고 ripemd160에 의한 hash를 구한다.
5. ripe.digest의 앞자리(1 or 2)가 0x00일 때까지 반복한다.(address의 크기를 줄이기 위한 작업)
6. address version number의 인코딩 + stream number의 인코딩 + ripe.digest
7. verify를 위해 앞의 값에 sha512를 두번 적용한 후 앞의 4bytes를 checksum으로 사용한다.
8. (6에서의 값의 hex + 7에서의 checksum의 hex) 를 integer로 변경한다.
9. integer를 base58로 인코딩한다.
10. 앞에 BitMessage를 의미하는 BM-를 덧붙인다.

양의 정수 인코딩하기
1. 253보다 작으면 big endian unsigned char
2. 253에서 65535(2^16)사이이면 (>B, 253) + >H unsigned short
3. 65536에서 2^32사이이면 (>B, 254) + >I unsigned int
4. 2^32에서 2^64사이이면 (>B, 255) + >Q unsigned long long
5. 2^64보다 큰 수는 없다.

Wallet Import Format
1. 0x80 + private key
2. sha256을 두번 적용한 hash를 구한다.
3. hash된 결과의 앞 4bytes를 checksum으로 사용한다.
4. 1의 끝에 checksum을 추가한다.
5. base58로 인코딩한다.

signature 계산
expires time + object type + address version number + stream number + tag + 0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes
 위의 내용을 private signing key로 sign한 것이 signature이다.

encrypted 계산
0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes + signature의 length + signature
위의 내용을 address의 double hash의 앞 32bytes로 암호화 한다.

실제 다른 node에 전달되는 값은 아래와 같다.
payload = POW에 의해 계산된 nonce + expires time + object type + address version number + stream number + tag + encrypted

inventoryhash: payload에 sha512를 두번 적용한 hash의 앞 32bytes
inventoryhash -> object type, stream number, payload, expires time, tag)

쉽게 배우는 알고리즘 9장 요약

Chapter 9. 그래프 알고리즘

1. 그래프

그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
    정점(Vertex): 대상이나 개체
    간선(Edge): 이들간의 관계

사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.

n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
    G = (V, E)
로 표시한다.

2. 그래프의 표현

2.1 인접행렬을 이용한 방법

그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.

행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.

2.2 인접리스트를 이용한 방법

각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.

단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.

3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)

3.1 BFS

루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.

// G: 그래프
// s: 시작정점
BFS(G, s)
{
    // s를 제외한 모든 정점을 NO로 표시한다.
    for each v in V -{s} {
        visited[v] = NO;
    }
    visited[s] = Yes;
    enqueue(Q,s);
    while (Q가 비어 있지 않으면) {
        u = dequeue(Q);
        for each v in L(u) // 정점 u의 인접 리스트
            if (visited[v] == NO) {
                visited[v] = YES;
                enqueue(Q,v);
            }
        }
    }
}

3.2 DFS

루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.

DFS(G)
{
    for each v in V {
        visited[v] = NO;
    }
    for each v in V {
        if (visited[v] == NO) {
            aDFS(v)
        }
    }
}

aDFS(v)
{
    visited[v] = YES;
    for each x in L(v) { // L(v): 정점 v의 인접리스트
        if (visited[x] == NO) {
            aDFS(x);
        }
    }
}

4. 최소신장트리(Minimum Spanning Tree)

간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.

4.1 프림 알고리즘

집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.

// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
    S는 공집합
    // 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
    for each u in V {
        d[u] = 무한대
    }
    d[r] = 0;
    while (S != V) {
        u = extractMin(V-S, d);
        S = S + [u]; // 집합 S에 u를 포함시킨다.
        for each v in L(u) { // L(u): u의 인접 정점 집합
            if (v in V-S && w(u,v) < d[v]) {
                d[v] = w(u,v);
                tree[v] = u;
            }
        }
    }
}

extractMin(Q, d[])
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}

4.2 크루스칼 알고리즘

싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.

Kruskal(G)
{
    T는 공집합
    단 하나의 정점만으로 이루어진 n개의 집합을  초기화한다.
    모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
    while (T의 간선수 < n - 1) {
        A에서 최소비용의 간선(u,v)를 제거한다.
        if (정점 u와 v가 다른 집합에 속함) {
            T = T + (u,v);
            정점 u와 v가 속한 두 집합을 하나로 합친다.;
        }
    }
}

5. 위상 정렬

싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.

topologicalSort(G)
{
    for each v in V {
        visited[v] = NO;
    }
    for each v in V {
        if (visited[v] == NO) {
            DFS-TS(v);
        }
    }
}

DFS-TS(v)
{
    visited[v] = YES;
    for each x in L(v) {
        if (visited[x] == NO) {
            DFS-TS(x);
        }
    }
    연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}

6. 최단경로

6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)

// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
    S는 공집합
    for each u in V {
        d[u] = 무한대
    }
    d[r] = 0;
    while (S != V) {
        u = extractMin(V-S, d);
        S = S + {u};
        for each v in L(u) {
            if (v in V-S && d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
}

extractMin(Q, d[])
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}

6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)

BellmanFord(G, r)
{
    for each u in V {
        d[u] = 무한대;
    }
    d[r] = 0;
    for (int i=0; i<V; i++) {
        for each (u,v) in E {
            if (d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
    // 음의 싸이클 존재여부 확인
    for each (u,v) in E {
        if (d[u] + w(u,v) < d[v]) {
            output "해없음"
        }
    }
}

6.3 모든쌍 최단경로 알고리즘

d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리

d.k(ij) = w(ij) if k=0
            min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1

FloydWarshall(G)
{
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            d(ij) = w(ij);
        }
    }
    for (int k=1; k<=n; k++) {
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=n; j++) {
                d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
            }
        }
    }
}

6.4 싸이클이 없는 그래프의 최단경로

DAG-ShortestPath(G, r)
{
    for each u in V {
        d[u] = 무한대;
    }
    d[r] = 0;
    G의 정점들을 위상정렬한다.
    for each u in V { // 위상정렬 순서대로
        for each v in L(u) {
            if (d[u] + w(u,v) < d[v]) {
                d[v] = d[u] + w(u,v);
                prev[v] = u;
            }
        }
    }
}

7. 강연결요소

유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.

// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
    그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
    G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
    DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
    앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}

쉽게 배우는 알고리즘 8장 요약

Chapter. 8 동적 프로그래밍

1. 어떤 문제를 동적 프로그래밍으로 푸는가

동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다.

다음의 두 성질을 갖고 있는 문제에 대해 동적 프로그래밍이 적합하다.

a. 최적 부분구조를 이룬다.
b. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.

2. 행렬 경로 문제
nxn행렬의 죄상단에서 시작해 한 칸씩 이동해 우하단까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동상의 규칙은 아래와 같다.
- 오른쪽이나 아래쪽으로만 이동할 수 있다.
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

c(i,j)를 원소 (i,j)에 이르는 최고점수라하고, m(i,j)는 행렬의 원소(i,j)의 값이라 하면 아래와 같이 문제를 해결할 수 있다.
c(i,j) = m(1,1) if i=j=1
         m(1,j) + c(1,j-1) if i=1, j>1
         m(i,1) + c(i-1,1) if i>1, j=1
         m(i,j) + max(c(i,j-1), c(i-1,j)) if i>1, j>1

3. 조약돌 놓기 문제
3xn 테이블의 각 칸에 숫자가 쓰여 있다. 테이블의 칸들 중 일부에 제한조건을 만족하는 방법으로 조약돌을 놓아 조약돌이 놓인 곳에 있는 수의 합을 최대로 하는 방법을 구하는 문제이다. 제한 조건은 다음과 같다.
- 가로나 세로로 인접한 두 칸에 동시에 조약돌이 놓일 수 없다.
- 각 열에는 하나 이상의 조약돌을 놓는다.

임의의 열에 조약돌을 놓을 수 있는 방법은 총 4가지다 -> 패턴에 대한 내용은 책 확인
이를 기준으로 아래와 같이 문제를 해결할 수 있다.

c(i,p): i열이 패턴p로 놓일 때의 최고 점수
w(ip): i열이 패턴p로 놓일 때 i열에 돌이 놓인 곳의 점수 합
c(i,p) = w(i,p) if i=1
         max(c(i-1,q)) + w(i,p) if i>1, q는 p와 양립하는 패턴

4. 행렬 곱셈 순서 문제
n개의 행렬이 주어지고 이들의 곱을 계산하려 한다. 행렬은 결합법칙이 성립하므로 어떤 순서로 두개씩 짝지어 계산해도 결과는 동일하다.

c(i,j): 행렬 A(i), ..., A(j)의 곱  A(i), ... A(j)를 계산하는 최소 비용
A(i): p(i-1)Xp(i) 행렬

c(i,j) = 0 if i=j
         min(c(i,k) + c(k+1,j) + p(i-1)p(k)p(j)) if i<j, i<=k<=j-1

5. 최장 공통 부분순서(LCS)
두 문자열 X(m)과 Y(n)에 대해 두 문자열에 공통적으로 존재하는 가장 긴 부분순서를 구한다.

c(i,j)를 문자열 X(i)와 Y(i)의 LCS의 길이라 하면 점화식은 다음과 같다.
c(i,j) = 0 if i=0, j=0
         c(i-1,j-1) + 1 if i,j>0 and x(i)=y(j)
         max(c(i-1,j),c(i,j-1)) if i,j>0 and x(i)!=y(j)

쉽게 배우는 알고리즘 7장 요약

7장 상호배타적 집합의 처리

1. 연결 리스트를 이용한 집합의 처리

1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
  * Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
  * Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
  * Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.

1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조

2. 트리를 이용한 집합의 처리

2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.

2.2 연산의 효율을 높이는 방법

2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.

2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.

2.2.3 효율성
책 참조

쉽게 배우는 알고리즘 6장 요약

6장 해시 테이블
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.

1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.

2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.

2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.

2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
  * x에 A를 곱한 다음 소수부만 취한다.
  * 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
  * h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안

3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것

3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.

3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.

3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.

3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.

3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
  * h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
  * f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
  * m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.

3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.

4. 검색 시간 분석
책 참조

쉽게 배우는 알고리즘 5장 요약

1. 이진 검색 트리

1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.

1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.

1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.

1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
    r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
    r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
    트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.

2. 레드블랙트리
- 균형잡인 이진검색트리

2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.

2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
  - s가 레드인경우
    p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
  - s가 블랙인 경우
    x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
    - 오른쪽 자식인 경우
      p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
    - 왼쪽 자식인 경우
      p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결

왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.

새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.

2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방

- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.

  - p가 레드이고 s가 블랙인 경우
  - p가 블랙인 경우


c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
  - x의 부모노드 : p
  - p의 다른 자식 노드 : s
  - s의 자식 노드: l과 r

각각의 경우를 살펴보자.

2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.

a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.

b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.

c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동

2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.

a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작

b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.

c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.

d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동

3. B-트리

3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.

3.2 검색
이진검색트리에서의 검색과 같다.

3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.

3.4 삭제

a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.

4. KD-트리

4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.

4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.

4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.

4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거

b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.

c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.

5 KDB-트리

5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.

5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.

5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.

6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조

7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조

쉽게 배우는 알고리즘 3장 요약

3장 정렬

1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.

2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.

3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.

4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.

5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤

6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.

- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.

- 힙으로 만드는 방법
  * 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
  * 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.

7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용

8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.

9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs

쉽게 배우는 알고리즘 2장 요약

2장. 점화식과 점근적 복잡도 분석

1. 점화식의 이해

점화식: 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법

-> 등차수열, factorial, 피보나치 수열

예)

재귀적 관계를 이용해 알고리즘의 수행시간을 점화식으로 표현할 수 있다.

병합정렬의 경우 "T(n) = 2T(n/2) + 후처리시간"으로 표현할 수 있다.

2. 점화식의 점근적 분석 방법

a. 반복 대치

T(n)을 T(n-1)로 대치하고 T(n-1)을 T(n-2)로 대치하고 계속해서 T(n-2), T(n-3), ..., T(1)까지 반복해서 대치해가는 것과 같은 방식을 사용해 점근적 복잡도를 구한다.

b. 추정후 증명

식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옮음을 귀납적으로 증명하는 방법

c. 마스터 정리

a>=1, b>1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^(log a over b) = h(n)이라 할 때 T(n)의 점근적 복잡도는 아래와 같다.

- 어떤 양의 상수 e에 대하여 f(n)/h(n) = O(1/(n^e))이면, T(n) = Theta(h(n))이다.

- 어떤 양의 상수 e에 대하여 f(n)/h(n) = Omega(n^e)이고, 어떤 상수 c(<1)와 충분히 큰 모든 n에 대해 af(n/b) <= cf(n)이면 T(n) = Theta(f(n))이다.

- f(n)/h(n) = Theta(1)이면 T(n) = Theta(h(n)log n)이다.

쉽게 배우는 알고리즘 1장 요약

1장. 알고리즘 설계와 분석의 기초

1. 몇가지 기초 사항들

알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식

2. 점근적 표기
a. Theta 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨

b. Oh 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨

c. Omega 표기법

알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨

3. 점근적 표기의 엄밀한 정의

a. Oh 표기법

Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한

b. Omega 표기법

Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한

c. Theta 표기법

Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합

d. Little Oh 표기법

o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용

e. Little Omega 표기법


w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용

Why should I have written ZeroMQ in C, not C++에의 요약

http://www.250bpm.com/blog:4

처음 ZeroMQ개발시 C++를 선택한 이유
1. data structures and algorithms(STL)의 라이브러리가 언어에 포함되어 있음
2. OOP가 가지는 장점
3. C에서는 virtual function을 사용하기 복잡하다.
4. block의 끝에서 descructor가 자동으로 호출된다.

절대 죽지 않아야 하는 ZeroMQ에게 있어서 error handling은 매우매우 중요하다. 그런데, C++의 exception은 에러를 발생시키는 지점과 에러를 처리하는 지점이 다르게 되어 있다. 이점이 undefined behaviour를 발생시키지 않아야 하는 ZeroMQ에게 있어서 좋지 않다. C처럼 에러의 발생과 처리가 한군데에서 이루어 지는 것이 좋다.
이것때문에 C++에서 exception을 사용하지 않는 형태로 ZeroMQ를 구현하였다.

그러나 여전히 문제는 남아있다. object의 initialization과 termination시에 문제가 발생한다. constructor는 return값이 없으므로 에러를 처리하려면 exception을 발생시켜야 한다. exception을 사용하지 않기로 했으므로 이를 에러를 발생시키지 않는 constructor와 에러가 발생할 수 있는 init함수로 분리하였다. 그러다보니 state의 문제가 발생한다.(semi-initialized) 이것은 descturtor의 경우도 마찬가지다. 에러가 어디서 일어나느냐에 따라 다양한 state가 있을 수 있기 때문에 이에 대한 처리는 매우 복잡해진다. C를 사용하면 이 문제가 매우 간단해진다.

C++은 undefined behaviour 보다는 빠른 개발이 더 필요한 환경에 적합한 것으로 생각된다. 시스템 프로그래밍은 C가 여전히 최고다.

AOSA의 내용중 ZeroMQ에 대한 내용 요약

http://www.aosabook.org/en/zeromq.html

ZeroMQ는 messaging system이다. 처음에는 엄청 빠른 messaging system을 만드는 것으로 시작하였다. 그래서 처음 1년은 벤치마킹 방법을 고안하고 가능한한 효율적인 아키텍쳐를 만드는데 주력하였다. 2년째에는 distributed application을 만들고 임의의 message pattern이나 다양한 전송 방법이나 여러 language binding을 지원하는데 초점을 맞추었다. 3년째에는 사용성을 향상시키고 배우기 쉽도록 만드는데 주력하였다.

1. Application vs Library

ZeroMQ는 messaging server가 아닌 library다.

퍼포먼스의 측면에서 볼 때 중간에 서버가 있으면 네트워크를 두번 타게 되는 단점이 생기고 이 서버가 bottleneck의 원인이 될 수 있다.

두번째로 생각해 볼 수 있는 것은 large-scale deployment이다. deployment가 여러 회사에 걸쳐 있게 되면 각각의 회사들은 다른 회사에 서버가 있기를 원하지 않을 것이다. 그러다보니 각각의 회사에 서버가 있게 되고 이것은 관리라든지의 어려움이 생기게 된다. 이것을 해결하려면 각각의 컴포넌트가 별도로 동작하게 하는 완전한 분산 아키텍쳐가 필요하게 된다. 결국 messaging library이다.

ZeroMQ는 서버없이 메시징을 어떻게 할 수 있을까에서 시작하였다. 이에대한 결론이 library이다.

이 아키텍쳐가 더 효율적이고 더 유연하다는 것을 그동안 증명할 수 있었다.

의도하지 않았던 결론중의 하나는 라이브러리 모델이 제품의 사용성을 향상시켰다는 것이다. 사용자들은 서버를 설치하고 운용하지 않아도 된다는 것에 많은 점수를 주었다.

배운점: 처음 프로젝트를 시작할 때 가능하다면 라이브러리의 형태로 만드는 것을 고려해라.

2. Global State

라이브러리에 전역변수는 좋지 않다. 라이브러리는 한 프로세스내에서도 여러번 로드될 수 있는데 이렇다 하더라도 전역변수는 하나만 있게 된다. 그러면 서로 다른 두 군데서 라이브러리의 전역변수는 사용하려고 하면 race condition이나 실패같은 상황이 발생 할 수 있다.
이 무제를 해결하기 위해 ZeroMQ는 전역변수를 사용하지 않는다. 따라서, ZeroMQ를 사용하는 사용자가 필요한 전역변수를 만들어서 사용해야 한다. 이것은 context라고 부르는데 전역변수를 가지고 있는 하나의 object라고 말할 수 있다. 만약 두 군데서 라이브러리를 사용하고 각자 자신의 context를 가지고 사용한다면 서로서로 상대방의 context의 존재를 모를 것이다.

배운점: 라이브러리에서 전역변수를 사용하지 말아라.

3. Performance

메시지 시스템의 속도는 throughput과 latency로 이야기 할 수 있다: throughput - 주어진 시간에 얼마나 많은 메시지가 지나 갈 수 있는가, latency - 메시지가 도착하는데 얼마의 시간이 걸리는가.
여기서 중요하게 이해하고 있어야 하는 점이 있다. latency는 A에서 B로 도착하는 데 각각의 메시지가 걸리는 시간을 의미하는 것이고 throughput은 A에서의 throughput, B에서의 throughput으로 표현되는 것이라는 것이다.

배운점: 직면한 문제를 명확하게 이해하라.

4. Critical Path

아래의 세가지가 퍼포먼스에 중요한 역할을 한다.

- Number of memory allocations
- Number of system calls
- Concurrency model

하지만, 모든 memory allocation이나 system call이 중요하지는 않다. 메시징 시스템에서는주어진 시간동안 A에서 B로 얼마나 많은 메시지를 전달할 수 있느냐가 중요하다. 또한 한 메시지를 얼마의 시간만에 전달할 수 있느냐도 중요할 수 있다.
매우 자주 사용되는 코드의 부분을 critical path라 부르는데 이 부분이 최적화에 초점이 맞추어져야 하는 부분이다.

배운점: critical path에 있지 않은 부분을 최적화하려 하지 마라.

5. Allocating Memory

message allocation과 message copying을 잘 조절하는 것이 퍼포먼스에 중요하다. 작은 메시지는 copy를 하는 것이 낫고, 큰 메시지는 allocation을 하는 것이 낫다.
ZeroMQ는 handle이라고 하는 것을 사용하는데 작은 메시지의 경우는 handle에 데이터를 저장하고 큰 메시지의 경우는 데이터에 대한 포인터만을 저장한다.

배운점: 퍼포먼스를 생각할 때 한가지만을 생각하지 마라. 각각의 경우(작은 메시지와 큰 메시지)에 다른 해결책이 있을 수 있다.

6. Batching

4개의 메시지를 각각 따로 보낸다면 전체 네트워크 스택을 4번 타야하기 때문에 좋지 않다. 이런 경우 여러 메시지를 한번(batching)에 보낼 수 있다면 좋을 것이다(throughput의 향상).   하지만, 반대로 이것은 latency가 나쁘게 된다.
ZeroMQ는 다음의 방법을 사용한다. 메시지가 많지 않고 네트워크 스택의 bandwidth를 넘지 않으면 latency를 향상시키기 위해 batching을 사용하지 않는다. 네트워크 스택의 bandwidth를 넘으면 메시지를 큐에 저장한다. 이러한 상황에서는 batching을 사용한다.

배운점: throughput을 향상시키기 위해 제일 위의 레이어에서만(아래의 레이어에서의 batching은 의미없다) batching을 사용한다. 메시지가 쌓이는 경우만 batch를 사용한다.

7. Architecture Overview

사용자는 여러 peer와 통신할 수 있는 socket이라는 것으로 ZeroMQ와 통신한다.
socket object가 사용자의 쓰레드에 있고 이 외에 ZeroMQ는 통신의 비동기를 다루기 위해 여러개의 worker 쓰레드를 만든다.(네트워크로부터 데이터 읽기, 메시지 큐에 넣기, 접속 연결 허락하기 등)
worker 쓰레드에는 여러 object가 있는데 이들은 하나의 parent를 가진다. 이 parent는 다른 쓰레드에 있을 수 있다. 대부분의 object의 parent는 socket이다. object의 parent의 parent가 socket인 경우도 있다. 따라서 socket을 시작으로 하는 tree가 생기게 된다. object는 자신의 children이 사라져야(shut down) 자신도 사라질 수 있기 때문에 이에 tree를 이용한다.
message passing에 관련이 있는 object와 관련이 없는 object로 해서 두 종류의 비동기 object가 있다. message passing에 관련이 없는 object는 주로 connection management와 관련이 있다. 예를 들어 TCP listener object는 접속하려는 TCP 연결을 기다리고 각각의 새 연결에 engine/session object를 만든다. 비슷하게 TCP connector object는 TCP peer에의 연결을 시도하고 이것이 성공하면 연결을 관리하는 engine/session object를 만든다. 연결이 실패하면 다시 연결하기를 시도한다.
message passing에 관련이 있는 object는 data transfer를 다루는 object들이다. 이 object들은 두 부분으로 구성되어 있다. session object는 ZeroMQ socket과 통신을 하고 engine object는 네트워크 부분과 통신을 한다. session object는 한 종류만 있지만 engine object는 여러 type(TCP engines, IPC engines, PGM engines등)이 있다. 추가도 가능하게 되어 있다.
session은 socket과 message를 교환한다. message를 전달하는 것은 양방향으로 되어 있고 각각은 pipe object에 의해 다루어진다. 각각의 pipe는 쓰레드들 사이에 메시지를 빠르게 전달하는데 최적화된 lock-free 큐이다.
마지막으로, 모든 socket과 모든 비동기 object들에 의해 사용이 가능하고 global state를 저장하고 있는 context object가 있다.

8. Concurrency Model

멀티코어를 잘 이용하는 것은 ZeroMQ의 요건중의 하나다. 다시 말하면 코어가 증가하면 throughput이 증가하는 것을 의미한다.
전통적인 방법(critical sections, semaphores등)으로 여러 쓰레드를 사용하는 것은 성능을 향상시키지 않는다. 여러 쓰레드를 사용하면 코어가 여러개라도 하나의 쓰레드를 사용하는 것보다 느릴 수 있다.
ZeroMQ는 actor model이라 불리는 다른 모델을 사용한다. 쓰레드들 간의 통신에 쓰레드들 사이에 전달하는 비동기 메시지를 사용하는 것이다.
한 코어당 하나의 worker thread만을 사용한다. TCP engine 같은 각각의 내부 ZeroMQ object들은 특정한 worker thread에 연결되어 있다. 따라서 critical section이나 mutex나 semaphore같은 것을 사용할 필요가 없게 된다. 또한 이 object들은 CPU 코어 사이를 이동할 필요가 없게 되기 때문에 cache pollution을 피할 수 있게 된다.
이 방법은 기존의 멀티 쓰레딩의 문제를 사라지게 한다. 하지만 여전히 많은 object들 사이에 worker thread를 공유할 필요가 있다. 이벤트의 임의의 시퀀스를 다루어야 하고 object가 CPU를 오래 사용하면 안되도록 해야 하기 때문에 하나의 이벤트 루프를 사용하기 보다는 event-driven 방식으로 object를 관리하는 스케줄러가 필요하다는 것을 의미한다.
전체 시스템은 완전히 비동기적이어야 한다. blocking을 사용하는 object가 없어야 한다. blocking을 어떤 하나의 object가 사용하면 같은 worker thread를 공유하는 다른 쓰레드가 block될 수 있기 때문이다. 모든 object는 명백히든 내부적으로든 state machine이어야 한다. 동시에 실행중인 수백, 수천개의 state machine사이에 가능한 모든 통신을 다룰 수 있어야 한다. 특히 중요한것이 shutdown process이다.
완전히 비동기적인 시스템에서의 shutdown은 매우 복잡한 작업이다. 이 부분이 ZeroMQ에서 가장 복잡한 부분이다.버그 트래커를 보면 30-50%정도가 shutdown에 관련되어 있다.

배운점: 진짜로 performance와 scalibility를 고려한다면 actor model를 고려해보라.

9. Lock-Free Algorithms

lock-free algorithm은 커널이 제공하는 mutex나 semaphore를 사용하지 않고 쓰레드간에 통신을 하기 위한 방법이다. atomic compare-and-swap(CAS)같은 CPU의 기능을 사용해서 동기화를 한다. 이것은 하드웨어 레벨에서 lock이 이루어지기 때문에 진짜로 lock-free이지는 않다.
ZeroMQ는 pipe object에서 lock-free queue를 사용해서 user thread와 worker thread사이의 메시지를 전달한다. ZeroMQ가 lock-free queue를 사용하는 두가지 흥미로운 측면이 있다.
첫째로, 각각의 queue는 하나의 write thread와 하나의 reader thread를 가진다. 1:N 통신이 필요하면 여러 queue가 만들어진다. 이렇게 하면 writer들이나 reader들에의 동기화를 신경쓸 필요가 없어지기 때문에 매우 효율적이 된다.
둘째로, lock-free algorithm이 효율적이기는 하지만 여전히 우리가 원하는 만큼의 성능을 주지는 않았다.
이것을 향상시키기 위해 사용한 방법이 batching이다. 10개의 메시지가 있다고 하자. 이 메시지들을 하나씩 queue에 넣기 보다는 10개를 모은 후 한번에 queue에 저장하는 것이 낫다.
같은 방법을 reader쪽에도 적용할 수 있다. 메시지를 하나씩 읽기보다는 이 메시지들을 reader thread만이 읽을 수있는 queue의 특정영역(pre-read buffer)에 두고 reader thread가 한번에 읽을 수 있게 한다.

배운점: lock-free algorithm은 사용하기도 어렵고, 구현하기에도 문제 많고 디버깅하기도 좋지 않다. 가능하다면 기존의 가능한 방법을 사용하자. 너무 lock-free algorithm에 의존하지 말아라.

10. API

user interface는 제품에서 매우 중요한 부분이다. 라이브러리에서는 API가 될 것이다.
ZeroMQ의 초기 API는 exchange와 queue에 AMQP의 model을 따라 만들었다. 이것을 다시 처음부터 만들 때 BSD Socket API를 따라 만들었다. 이전에는 전문가가 사용하는 제품이었다면 이후부터는 누구든지 쉽게 사용할 수 있는 제품이 되었다. 커뮤니티는 10배로 커졌고 20개 이상의 언어의 바인딩이 만들어졌다.

배운점: 만들고자 하는 것을 알고 그에 맞는 UI를 만들어라.

BSD Socket API가 오래되었지만 많은 사람들이 알고 있고 쓰고 있는 것이기 때문에 ZeroMQ의 API를 배우기가 쉬워졌다. 또한 TCP, UDP, file, pipe같은 기존의 것과 같은 API를 사용하기 때문에 이것들과 같은 데서 사용될 수도 있고 기존의 것에 ZeroMQ를 쉽게 추가할 수도 있다. 그리고 BSD Socket API가 오래 사용되었다는 것은 이것이 좋은 디자인으로 만들어졌다고 말할 수 있는 것이다. 이것을 따른다는 것은 우리의 API도 좋은 디자인을 따라간다고 할 수 있다.

배운점: 제품을 만들 때 관련 제품을 살펴보라. 어떤 제품이 실패했고 어떤 제품이 성공했는지를 보고 배워라. 배울 수 있는 모든 것(idea, API, framework등)은 다 배워라.

11. Messaging Patterns

메시징 시스템에서 가장 중요한 문제는 사용자가 어떤 메시지를 어디로 보낼 것인지를 정하는 방법을 어떻게 사용자에게 제공할 것인가 하는 것이다. 이에는 두가지 접근법이 있다.
첫째로는 "do one thing and do it well"이라는 유닉스 철학을 따르는 것이다. 이것이 의미하는 바는 문제를 제한된 영역으로 제한하여 해결해야 하는 문제를 해결하는 것이다. 이것의 예로는 MQTT가 있다.
두번째로는 일반성에 초점을 맞추어 강력하고 구성이 가능한 시스템을 만드는 것이다. AMQP가 이것의 예이다. 이 모델은 어떤 routing algorithm도 정의할 수 있게 해주는 수단을 사용자에게 제공한다.
ZeroMQ는 첫번째 모델을 따른다. 첫번째 모델은 누구나 쉽게 사용할 수 있지만 두번째는 전문가정도는 되어야 사용이 가능한다.
특정 문제에 맞는 해결을 하는 것이 일반적인 해결을 하는 것보다 낫기는 하지만 그래도 사용자에게 다양한 기능을 제공하는 것이 좋다. 이 모순을 어떻게 해결할 수 있을까?
아래의 두단계로 해결할 수 있다.
1. 특정한 문제 영역을 다루기 위한 레이어를 정의한다.(transport, routing, presentation등)
2. 서로 관련이 없는 각 레이어의 구현을 만든다.
인터넷 스택에서 transport layer를 예로 들어보자. IP layer위에 다양한 서비스(TCP, UDP, SCTP등)가 존재한다. 이들은 서로 연관을 맺지 않는다. 따라서 쉽게 새로운 서비스를 추가할 수 있고 기존의 것을 제거할 수도 있다.
같은 원리가 messaging pattern에도 적용된다. messaging pattern은 transport layer위로 scalibility layer라 불리는 layer를 구성한다. 각각의 messaging pattern은 이 레이어의 구현이다. publish/subscribe나 request/reply는 서로 연관없이 동작한다.

배운점: 복잡하고 다양한 측면을 가지는 문제를 해결하고자 할 때 하나의 일반적인 해결책이 최선이 아닐 수 있다. 대신에 문제 영역을 잘 추상화하고 각각의 레이어에 다양한 구현을 제공한다.

12. Conclusion

이 문서는 시스템적인 측면에서 large-scale distributed system을 만들면서의 우리의 경험을 이야기한다.

Linux Performance and Tuning Guidelines 초간단 요약

- 병목점 찾기
1 시스템 파악
2 시스템 백업
3 시스템의 성능 모니터링하고 분석
4 문제가 있는 병목점을 정한 후 원인 찾기
5 한번에 하나씩 시도하며 병목점 문제 해결
6 시스템의 성능이 만족스러울 때까지 3으로 돌아가 반복

- CPU performance tuning
ps -ef로 확인하여 불필요한 프로그램이 돌고 있으면 cron을 써서 중요하지 않은 시간에 돌도록 변경
CPU를 많이 쓰나 중요하지 않은 프로세스는 priority를 조정(top, renice)
SMP 머신의 경우 프로세스가 여러 프로세서에서 돌지 않도록 해준다(taskset)
실행중인 애플리케이션에 따라 CPU를 증설하는 것보다는 더 빠른 CPU로 바꾸어 주는 것이 나을 수 있다.
최신 driver나 firmware를 사용한다.

- Memory performance tuning
bigpages, hugetlb, shared memory를 사용해서 swap space를 튜닝
page의 사이즈를 늘리거나 줄이기
active와 inactive memory를 다루는 방법을 향상시키기
page-out rate를 조절하기
서버에서 각각의 유저가 사용가능한 리소스 제한하기
불필요한 서비스 중단하기
메모리 늘리기

- Disk performance tuning
workload가 sequential 때문이라면 더 빠른 disk controller를 설치한다. workload가 random 때문이라면 drive를 추가한다.
RADI환경에서는 disk drive를 추가한다. 하드웨어 RAID를 사용한다.
striping없는 logical volume을 사용하는 것보다 striping있는 logical volume을 사용하는 것을 고려해라.
네트워크상의 다른 시스템으로 프로세싱 넘기기 - Offload processing to another system in the network (users, applications, or services).
더 많은 램을 추가하기

- Network performance tuning
네트워크 카드의 설정이 router와 switch 설정과 잘 맞는지 확인(frame size)
subnet 조작하기
더 빠른 네트워크 카드 사용하기
적절한 IPv4 TCP 커널 파라메터 튜닝하기
네트워크 카드 바꾸고 성능 측정하기
네트워크 카드를 추가하고 바인딩하기

- Changing kernel parameters
kernel parameter에 대한 정보는 /proc(or /proc/sys)에 저장된다.
sysctl 사용
  예: > sysctl /proc/sys/kernel/kernel.shmmax
  reboot후 설정 사라짐. /etc/sysctl.conf에 위 내용 넣어두면 계속 적용

- Tuning the processor subsystem
프로세스의 priority를 변경 - renice
CPU affinity
  프로세스를 특정 CPU에서만 돌도록 하기
    irq 19를 3번째 CPU에 할당
    > echo 03 > /proc/irq/19/smp_affinity
  SMT(symmetric multi-threading)시스템에서는 물리 CPU가 인터럽트를 처리하도록 하기
NUMA(Non-Uniform Memory Architecture) 시스템
  NUMA지원이 없는 애플리케이션이 병목점이 될 수 있다. numastat(numactl 패키지)로 확인

- Tuning the vm subsystem
swap 설정
  메모리 페이지 스왑하기 - /proc/sys/vm/swappiness(값을 크게하면 swap이 더 잘 일어나게 된다.)
  pdflush daemon이 얼마나 자주 flush를 하는지 설정 - /proc/sys/vm/dirty_background_ratio(값을 크게하면 flush가 더 잘 일어나게 된다.)
  애플리케이션에 의해 만들어진 dirty page를 디스크로 flush하는 비율 설정 - /proc/sys/vm/dirt_ratio(file system cache의 비율 설정)
Swap partition
  보통의 스왑 파티션은 물리 메모리의 두배
  스왑 파티션을 여러개 만드는 것이 성능을 향상시킬 수 있다.
    순차적 사용, 여러개 동시에 사용
  스왑 파티션은 가장 빠른 드라이브에 설정한다.
HugeTLBfs
  TLB(Translation Lookaside Buffer)의 크기를 늘린다. - /proc/sys/vm/nr_hugepages
    TLB - a small cache used for storing virtual-to-physical mapping information
  /proc/meminfo로 hugetlb page의 정보를 볼 수 있다.

- Tuning the disk subsystem
Hardware 고려사항
  disk I/O가 중요한 시스템: file, print, database server
  disk I/O가 중요하지 않은 시스템: email, web server
  RAID로 엮은(software and hardware RAID) drive를 통해 성능을 향상 시킬 수 있다.
  파티션 나누기
    보안을 향상시킨다.
    data integrity를 향상시킨다.
    새로운 인스톨이나 업그레이드 시 다른 파티션에 영향을 주지 않을 수 있다.
    효율적인 백업 가능
I/O elevator
  elevator 선택하기
    Synchronous file system access
      anticipatory elevator - least throughput and the highest latency
      CFQ, NOOP, deadline은 비슷하게 좋으나 I/O 사이즈가 16kb가 넘어가면 CFQ와 NOOP가 좋음
    Complex disk subsystems
      NOOP elevator
    Database systems
      seek-oriented 특성때문에 deadline elevator가 좋다.
    Virtual machines
      virtualization layer가 필요한 작업을 한다.
    CPU bound applications
      NOOP elevator
    Simple ATA or SATA disk subsystems
      anticipatory elevator
  nr_requests
    > echo 64 > /sys/block/sdb/queue/nr_requests
    disk subsystem과 I/O 특성에 따라 다르게 해줄 필요가 있다.
      nr_requests의 값 별로 I/O 사이즈에 따른 throughput 측정
  read_ahead_kb
    > echo 64 > /sys/block/<disk_subsystem>/queue/read_ahead_kb
    large streaming read의 경우 read ahead buffer의 크기를 증가시키면 성능 향상이 올 수 있다.
    random I/O operation의 경우는 별로 효과가 없을 것이다.
  file system 선택하기
    적은 I/O request의 경우 ReiserFS가 적합하고 매우 큰 파일 시스템과 매우 큰 I/O 사이즈에서는 XFS와 JFS가 좋다. Ext3는 좋은 multiprocessor scalability를 제공하면서 적은 I/O request에 적합하기 때문에 이들의 중간점이라 볼 수 있다.
    JFS, XFS: high-end data warehouses, scientific workloads, large SMP servers, or streaming media servers
    ReiserFS, Ext3: file, web, mail
    Ext2는 synchronous file system acccess시 좋음. data integrity보다 성능이 우선시 되는 경우 선택한다. asynchronous file system의 경우는 ReiserFS가 Ext3보다 좋다.
    I/O priority
      CFQ I/O elevator에서 제공하는 process에 priority를 할당하는 기능
      ionice를 사용
        idle, best-effort, real time
    Access time updates
      linux file system이 저장하는 파일의 시간정보를 저장하지 않음으로서 성능향상을 줄 수 있다.
    Journaling mode 선택하기
      mode 변경방법
        > mount -o data=writeback /dev/sdb1 /mnt/mountpoint
        또는 /etc/fstab에서 변경가능
          /dev/sdb1 /testfs ext3 defaults,data=writeback 0 0
      data=journal
        file data와 metadata를 저널링한다.
      data=ordered(default)
        metadata만 저널링한다.
      data=writeback
        특별히 적은 I/O사이즈의 경우 Ext3의 성능을 향상시킨다.
        I/O 사이즈가 증가하면 writeback의 효과는 줄어든다.
        write의 경우 성능향상이 있고 read의 경우 별 효과가 없다.
    Block sizes
      작은 파일을 많이 다룬다면 작은 block size가 좋다.
      많은 파일을 많이 다룬다면 큰 block size가 좋다.
      하지만 여러 벤치마크를 보면 block size의 변경으로 실제 성능향상을 보기는 쉽지 않다. 그러므로 디폴트인 4K로 두는 것이 일반적으로 좋다.
      hardware RAID가 사용되는 경우 array의 stripe size가 성능에 매우 큰 영향을 미친다.
- Tuning the network subsystem
네트워크 트래픽
  netstat, tcpdump, ethereal을 사용하여 정보 획득
  고려사항:
    Transaction throughput requirements (peak, average)
    Data transfer throughput requirements (peak, average)
    Latency requirements
    Transfer data size
    Proportion of send and receive
    Frequency of connection establishment and close or number of concurrent connections
    Protocol (TCP, UDP, and application protocol such as HTTP, SMTP, LDAP, and so on)
speed and duplexing
  NIC의 속도 확인
  네트워크 컴포넌트(switch or hub)와 NIC의 관계 확인
MTU size
  Maximum Transmission Units
  > ifconfig eth0 mtu 9000 up
  모든 네트워크가 큰 MTU를 지원하지는 않는다.
Network buffer 증가시키기
  memory resources
    초기 TCP memory
      /proc/sys/net/ipv4/tcp_mem
    receive socket memory
      /proc/sys/net/core/rmem_default
      /proc/sys/net/core/rmem_max
    send socket memory
      /proc/sys/net/core/wmem_default
      /proc/sys/net/core/wmem_max
    option memory buffer
      /proc/sys/net/core/optmem_max
  window size 조정
    BDP(bandwidth delay product)로 최적의 window size 값을 알아올 수 있다.
      BDP = Bandwidth(bytes/sec) * Delay(or round trip time)(sec)
    tcpdump로 변경 내용 확인
TCP/IP tuning
  IP와 ICMP tuning
    spoofing attack 막기
      > sysctl -w net.ipv4.conf.eth0.accept_source_route=0
      > sysctl -w net.ipv4.conf.lo.accept_source_route=0
      > sysctl -w net.ipv4.conf.default.accept_source_route=0
      > sysctl -w net.ipv4.conf.all.accept_source_route=0
    지정된 머신이 아닌 곳에서의 redirect 막기
      > sysctl -w net.ipv4.conf.eth0.secure_redirects=1
      > sysctl -w net.ipv4.conf.lo.secure_redirects=1
      > sysctl -w net.ipv4.conf.default.secure_redirects=1
      > sysctl -w net.ipv4.conf.all.secure_redirects=1
    ICMP redirect 막기
      > sysctl -w net.ipv4.conf.eth0.accept_redirects=0
      > sysctl -w net.ipv4.conf.lo.accept_redirects=0
      > sysctl -w net.ipv4.conf.default.accept_redirects=0
      > sysctl -w net.ipv4.conf.all.accept_redirects=0
    router가 아닌 경우 redirect 보내지 않기
      > sysctl -w net.ipv4.conf.eth0.send_redirects=0
      > sysctl -w net.ipv4.conf.lo.send_redirects=0
      > sysctl -w net.ipv4.conf.default.send_redirects=0
      > sysctl -w net.ipv4.conf.all.send_redirects=0
    broadcast ping과 smurf 공격 무시하기
      > sysctl -w net.ipv4.icmp_echo_ignore_broadcasts=1
    icmp 패킷이나 ping 무시하기
      > sysctl -w net.ipv4.cimp_echo_ignore_all=1
    router에 의한 invalid response 무시하기
      > sysctl -w net.ipv4.icmp_ignore_bogus_error_responses=1
    IP fragment를 합치는데 사용되는 메모리 설정
      > sysctl -w net.ipv4.ipfrag_low_thresh=262144
      > sysctl -w net.ipv4.ipfrag_high_thresh=393216
  TCP tuning
    TIME_WAIT socket 다시 사용하기
      > sysctl -w net.ipv4.tcp_tw_reuse=1
      > sysctl -w net.ipv4.tcp_tw_recycle=1
    tcp_fin_timeout 값 줄이기
      FIN-WAIT-2에서 소켓을 가지고 있는 시간
      > sysctl -w net.ipv4.tcp_fin_timeout=30
    동작중이지 않은 소켓 연결 끊는 시간 줄이기
      > sysctl -w net.ipv4.tcp_keepalive_time=1800
    backlog connections queue값 올리기
      > sysctl -w net.ipv4.tcp_max_syn_backlog=4096
    TCP SYN cookies는 필요할 때만 키기
      > sysctl -w net.ipv4.tcp_syncookies=1
      커널이 CONFIG_SYNCOOKIES로 컴파일되어야 함
      Dos와 DDos를 막아주기는 하지만 성능에 영향을 미침
  TCP options tuning
    selective acknowledgment 막기
      > sysctl -w net.ipv4.tcp_sack=0
      > sysctl -w net.ipv4.tcp_dsack=0
    TCP timestamp 막기
      > sysctl -w net.ipv4.tcp_timestamps=0
      backend system의 경우 굳이 time stamp 필요없음
    window scaling 막기
      > sysctl -w net.ipv4.tcp_window_scaling=0
      high network load에서는 window scaling이 좋지 않음
Netfilter
  packet filtering capability와 network security를 향상시키지만 예측가능하지 않은 행동을 유발할 수 있다.
  영향을 끼치는 요인
    Number of rules
    Order of rules
    Complexity of rules
    Connection tracking level (depends on protocols)
    Netfilter kernel parameter configuration
Offload configuration
  ethtool 사용
    > ethtool -k eth0
packet queue의 크기 늘리기
  /proc/sys/net/core/netdev_max_backlog
transmit queue length 늘리기
  > ifconfig eth1 txqueuelen 2000
  large, homogeneous data transfer를 수행하는 high-speed 연결에 적합
인터럽트 줄이기
  network interface의 인터럽트를 물리 CPU에 할당하면 성능 향상을 얻을 수 있다.
  interrupt number 알아내기
    > ifconfig eth1
  인터럽트의 CPU affinity 설정하기
    > echo 02 > /proc/irq/169/smp_affinity

- sysctl tutorial

http://www.frozentux.net/ipsysctl-tutorial/ipsysctl-tutorial.html

- 참고

https://access.redhat.com/knowledge/docs/en-US/Red_Hat_Enterprise_Linux/6/html/Performance_Tuning_Guide/index.html

Flask - Quickstart 요약

- 가장 간단한 웹앱을 만들어 보자.

# hello.py

from flask import Flask
app = Flask(__name__)

@app.route('/')
def hello_world():
    return 'Hello World!'

if __name__ == '__main__':
    app.run()

위와 같이 입력하고 command line에서 아래와 같이 입력한다.
> python hello.py

브라우저에서 http://127.0.0.1:5000에 접속하면 'Hello World!'를 볼 수 있다.

접속 URL을 컴퓨터의 ip로 바꾸고 싶으면 app.run부분을 아래와 같이 바꾸면 된다.

=> app.run(host='0.0.0.0')

디버그 모드를 키고 싶으면 아래와 같이 한다.

=> app.run(debug=True)

'/'의 요청시 hello_world() 함수가 호출되는 것은 @app.route에 의해 이루어진다.

위에서처럼 고정된 URL이 아닌 필요에 따라 변하는 URL의 경우 매칭시키고 싶으면 아래와 같이 하면 URL에서 <username> 부분이 함수의 username 파라메터로 넘어온다.

@app.route('/<username>')
def show_user_profile(username):
    return 'User %s' % username

들어오는 값을 아래와 같이 변환해 줄 수도 있다.

@app.route('/<int:post_id>')
def show_post(post_id):
    return 'Post %d' % post_id

변환해주는 값에는 아래의 3가지가 있다.
int : 정수로 변환
float: 실수로 변환
path: 마지막 '/'도 포함하는 path

- routing rule

* 마지막에 '/'가 있는 경우:
예) '/projects/'
'/projects'로 요청하면 flask는 '/projects/'로 redirect한다.

* 마지막에 '/'가 없는 경우:
예) '/projects'
'/projects/'로 요청하면 없는 페이지로 에러 발생

지금까지는 url을 함수로 매핑시켜주는 @app.route를 살펴봤다. 반대도 가능할까? url_for()를 사용하면 된다. 첫번째 파라메터는 함수의 이름이고 두번째부터는 URL에서의 변경부분이다. 없는 두번째 파라메터는 query parameter가 된다.

url_for('hello_world') => /
url_for('username', username='soo') => /username/soo
url_for('username', query='soo') => /username?query=soo

- HTTP method에 대한 처리

@app.route('/', methods=['GET', 'POST'])
def login():
    if request.method == 'POST':
        do_post_job()
    else:
        do_get_job()

디폴트는 GET이다.

- static 파일은 패키지에 static 디렉토리를 만들어서 거기에 넣어두면 /static으로 접근가능하다.

* static/style.css라는 파일이 있으면 아래와 같이 접근 가능

url_for('static', filename='style.css')

- flask는 Jinja2 템플릿 엔진을 사용한다. 물론 원하면 다른 엔진을 사용해도 된다.

패키지 안에 templates 디렉토리를 만들고 html 파일을 넣어둔다.
코드에서는 아래와 같이 접근 가능하다.

templates/hello.html 이 있는 경우

@app.route('/hello/')
@app.route('/hello/<name>')
def hello(name=None):
    return render_template('hello.html', name=name)

hello.html은 아래와 같을 것이다.

<!doctype html>
<title>Hello from Flask</title>
{% if name %}
  <h1>Hello {{ name }}!</h1>
{% else %}
  <h1>Hello World!</h1>
{% endif %}

html에서의 name은 render_template에 name argument로 넘겨준 값이 사용된다.

- 클라이언트가 보낸 데이타에 대한 처리를 위해 flask는 request object를 사용한다.

- URL에서 query parameter(?key=value)에 대한 처리는 아래와 같이 한다.

request.args.get('key', '')

- 파일 업로드하기
HTML form에서 enctype="multipart/form-data"로 해주어야 함

from flask import request

@app.route('/upload', methods=['GET', 'POST'])
def upload_file():
    if request.method == 'POST':
        f = request.files['the_file']
        f.save('/var/www/uploads/uploaded_file.txt')
    ...

업로드된 파일은 메모리나 임시 디렉토리에 저장되므로 save()함수를 사용하여 원하는 위치에 저장한다.
클라이언트쪽에서 사용했던 파일 이름을 알고 싶으면 f.filename을 사용하면 된다. 또는 좀 더 확실하게 알고 싶으면 secure_filename(f.filename)을 사용한다.

- Cookies

* 쿠키 읽기
request.cookies를 사용

from flask import request

@app.route('/')
def index():
    username = request.cookies.get('username')
    # use cookies.get(key) instead of cookies[key] to not get a
    # KeyError if the cookie is missing.

* 쿠키 저장하기
response object의 set_cookie()함수를 사용

from flask import make_response

@app.route('/')
def index():
    resp = make_response(render_template(...))
    resp.set_cookie('username', 'sun')
    return resp

- redirect하고 싶으면 redirect()함수를, 바로 종료하고 싶으면 abort()함수를 사용한다.

from flask import abort, redirect, url_for

@app.route('/')
def index():
    return redirect(url_for('login'))

@app.route('/login')
def login():
    abort(401)
    this_is_never_executed()

- 에러 페이지를 커스터마이즈하고 싶으면 app.errorhandler를 사용한다.

from flask import render_template

@app.errorhandler(404)
def page_not_found(error):
    return render_template('page_not_found.html'), 404

- Response object
a. 정상적인 response object가 함수로부터 리턴하면 이것이 바로 넘어간다.
b. string이 함수로부터 리턴하면 response object를 만들고 이것의 data로 string을 넘긴다.
c. tuple을 넘길 수 있는데 다음과 같은 형태가 되어야 한다. (response, status, headers)
d. 앞의 세 종류가 아니면 리턴 값을 response object로 변환한다.

- Session
session object를 통해 값을 가져오고 저장하고를 할 수 있다. session에는 아래의 예에서 처럼 secret key가 필요하다.

from flask import Flask, session, redirect, url_for, escape, request

app = Flask(__name__)

@app.route('/')
def index():
    if 'username' in session:
        return 'Logged in as %s' % escape(session['username'])
    return 'You are not logged in'

@app.route('/login', methods=['GET', 'POST'])
def login():
    if request.method == 'POST':
        session['username'] = request.form['username']
        return redirect(url_for('index'))
    return '''
        <form action="" method="post">
            <p><input type=text name=username>
            <p><input type=submit value=Login>
        </form>
    '''

@app.route('/logout')
def logout():
    # remove the username from the session if it's there
    session.pop('username', None)
    return redirect(url_for('index'))

# set the secret key.  keep this really secret:
app.secret_key = 'A0Zr98j/3yX R~XHH!jmN]LWX/,?RT'

- 로그가 필요하면 app.logger를 사용한다.

app.logger.debug('A value for debugging')
app.logger.warning('A warning occurred (%d apples)', 42)
app.logger.error('An error occurred')

- 구글 앱 엔진에 flask를 사용한 앱을 올리고 싶으면 아래의 내용 참조하라.
https://github.com/kamalgill/flask-appengine-template