Proxy-lab

In this lab, you will write a simple HTTP proxy that caches web objects.
- 출처 : http://csapp.cs.cmu.edu/3e/proxylab.pdf

프록시(Proxy)란 브라우저(Web browser)와 서버(end server) 간의 'middleman'.
브라우저의 응답을 받아 서버에게 넘겨주고(forward), 서버의 응답을 다시 브라우저에게 보내준다(send).

프록시는,

1. 서버에 대한 방화벽(firewall)의 역할을 수행할 수 있다.
2. 브라우저를 익명화(anonymize)할 수 있다. 브라우저를 식별할 수 있는 정보를 서버에게 넘기지 않음으로써.
3. 서버의 응답을 캐시(cache)함으로써 클라이언트의 요청을 효율적으로 처리할 수도 있다.

Proxy-lab에서는 가장 우리에게 가장 basic한 proxy를 만들고, 2단계에 걸쳐 개선하도록 주문한다.

Part I: Implementing a sequential web proxy

1. "프록시의 기본 정의 : 클라이언트와 서버 사이의 요청/응답을 매개하는 역할. 클라이언트의 요청을 서버에게 전달하고, 서버의 응답을 클라이언트에게 되돌려준다."
   에 충실한 구현을 일단 하면 된다. HTTP/1.0 버전의 GET method 요청만을 처리할 수 있으면 된다. 나머지(POST method 등)는 optional.

2. 클라이언트의 요청이 valid한지를 확인해야 한다. 자세하게 설명되어 있지는 않으나, 구체적으로는 요청 라인, 헤더가 HTTP 프로토콜의 포맷에 맞는지를 확인해야 한다
   : 요청 라인(method, URI, version), 헤더(header-name: header-data).

Part II: Dealing with multiple concurrent requests

1. 기존의 sequential proxy는 iterative server 처럼 하나의 요청을 처리하는 동안 다른 요청 시도를 들을 수 없다. 따라서 동시에 여러개의 요청에 응답할 수 있는 proxy로 개선한다. pthread를 이용해 동시성 구현을 할 수 있다.

Part III: Caching web objects

1. 아주 간단한 캐싱을 하는 프록시로 개선한다.
   캐싱 가능한 웹 object 크기 (MAX_OBJECT_SIZE)가 정해져 있고, 캐시된 object들의 크기 합은 다시 MAX_CACHE_SIZE를 넘을 수 없도록 구현한다

2. LRU(Least-recently-used) 삭제 정책(eviction policy)을 적용하여 구현한다.

3. 캐시 접근이 '스레드세이프'(여러스레드에서 동시에 접근해도 프로그램이 안전해야 함) 하도록 구현해야 한다.

구현 이슈

rio_readnb vs rio_readn

Proxy가 서버에서 받은 응답의 contents(body)를 자신이 가지고 있는 버퍼(해당 응답의 크기만큼 malloc으로 할당 했다)에 잠시 넣어두고, 다시 클라이언트에게 전달하는 과정이 있다. 서버와 연결된 socket에서 proxy의 버퍼로 read 할 때, 사용할 수 있는 함수가 두 가지 : rio_readn(), rio_readnb() 있었는데, rio_readnb()를 사용하면 응답이 문제 없이 클라이언트에게 전달되었지만, rio_readn()를 사용하면 산발적으로 완전하지 못한 응답이 전달되는 현상이 있었다. 원인을 찾고자 많은 고민과 시도를 했다.

RIO (Robust I/O)
가장 먼저 위에서 언급된 함수의 상위 패키지인 RIO package의 특성을 뜯어봤다.
기본 I/O 함수인 ssize_t read(int fd, void *buf, size_t n) 은 fd의 현재 파일 위치에서 최대 n 바이트를 메모리 위치 buf로 복사하고, 자신이 실제로 전송한 바이트 수를 리턴한다. 리턴 값 -1은 에러를, 0은 EOF를 의미한다.
주의할 점은 '최대 n' 바이트라는 점. 즉, 우리가 read() 에게 요청한 n 보다 적은 양을 읽어줄 수도 있다는 것이다. 책에서는 이를 short count가 발생했다고 정의한다. 이에 대해서는 세가지 정도의 원인이 있는데, 아래와 같다 :

1. EOF를 읽기 중에 만났을 때.
   20바이트만 가지고 있는 파일의 현재 파일 위치에서 50바이트를 한 번에 읽으려 한다면, 당연히 read는 50이 아닌 20을 리턴할 것이고, 이 때 short count가 발생했다고 말할 수 있다.

2. 터미널에서 텍스트 줄을 읽을 때.
   만약 열린 파일이 터미널과 연결되어 있으면, 각 read()는 한 번에 한 개의 텍스트 줄을 전송할 것이다. 어플리케이션이 read()에게 요청한 크기가 이 텍스트 줄의 크기보다 컸다면, short count가 발생했다고 말 할 수 있다.

3. 네트워크 소켓을 읽거나 쓸 때.
   열린 파일이 네트워크 소켓이라면, 내부 버퍼링 제약(커널에서 관리되는 내부 소켓 버퍼가 존재한다)과 긴 네트워크 지연시간 때문에 read()와 write() 호출 시 short count가 발생할 수 있다.

실제로, 디스크 파일을 읽을 때는 EOF를 제외하고는 short count가 발생하지 않을 것이다. 그리고 디스크 파일에 쓸 때는 절대로 short count를 만나지 않을 것이다. 하지만 3번의 경우와 같이, 네트워크 소켓에 관련된 I/O에 대해서는 short count가 발생할 수 있고, 이는 곧 어플리케이션에서 '요청한 크기' 만큼의 I/O가 불가능해지는 것이므로 안정된 프로그램이라고 할 수 없을 것이다. 따라서 이러한 short count 상황에 굴하지 않는 견고한(robust) I/O를 구현한 것이 RIO 패키지와 그 함수들이다.

앞서 언급한 이슈를 맞닥드렸을 때, 나와 팀원들은 rio_readn()함수가 RIO 패키지 함수임에도 불구하고, 어딘가 모르게 short count에 대응하지 못하고 있다고 가정하고서 문제해결을 시도했다. 하지만 구체적인 함수 구현 내용을 확인한 결과, rio_readn(), rio_readnb() 함수 모두 응용프로그램이 요청한 'n'만큼을 읽어들일 때까지 read()를 반복적으로 호출해 주고 있음에는 틀림이 없었다.

결국 나중에 찾은 원인은, 응답 body를 read 하기 전에 header를 읽을 때 사용했던 readlineb()에 있었다.

RIO에서 제공하는 read함수는 버퍼를 사용하는 함수와 사용하지 않는 함수로 나뉠 수 있다.
버퍼를 사용하는 함수 :

• ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen)
• ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n)
• 각 함수의 내부에서 실제로 read할 때 사용되는 함수
  • static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)

버퍼를 사용하지 않는 함수 :

• ssize_t rio_readn(int fd, void *usrbuf, size_t n)
• 각 함수의 내부에서 실제로 read할 때 사용되는 함수
  • ssize_t read(int fd, void *vuf, size_t n) : 표준 I/O 함수

버퍼를 사용하는 함수에서 주목해야 할 점은, 1. 각 함수들의 내부에서 또하나의 RIO 패키지 함수인 rio_read()를 호출한다는 것과, 2. 함수들이 서로 rio_t라는 구조체를 공유한다는 것이다.

1. rio_read()는 리눅스read() 함수의 버퍼형 버전이다. 7번 라인을 보면, 매 read() 호출마다 rio_buf의 버퍼 크기(항상 RIO_BUFSIZE)만큼 읽어와서 rio_buf를 꽉 채워둔다. 그리고 자신을 부른 함수가(또는 어플리케이션이) 요청한 크기인 n만큼 버퍼에서 떼서 주는 형식이다. 따라서 항상 버퍼가 비워지는 것이 아니므로, 버퍼에서 어디까지 읽어서 전달했는지 기억할 수 있는 포인터 rio_bufptr이 필요하다. 2. rio_t구조체를 공유하는 함수들은 결국 이 rio_bufptr를 공유하게 되는 것이다. rio_t 구조체는 하나의 소켓에 대해 초기화되므로, 하나의 소켓에 대해 버퍼를 사용하는 함수들끼리는 서로 번갈아가며 호출되어도 문제가 생기지 않는다.

RIO input functions are thread-safe (Section 12.7.1) and can be interleaved arbitrarily on the same descriptor. For example, you can read some text lines (rio_readlineb()) from a descriptor, then some binary data (rio_readn()), and then some more text lines (rio_readlineb()).
- 출처 : CSAPP 10.5 - Robust Reading and Writing with the RIO Package

하지만, rio_readn()은 버퍼를 사용하지 않는 함수이기에, rio_t 구조체를 공유하지 않는다. 그저 한 소켓에 대한 바로 이전의 읽기 호출의 끝지점에서 부터 read한다. 그래서 rio_readlineb()를 한 이후에, rio_readn()를 호출하면, 실제 어플리케이션이 전송받은 데이터 바로 이후의 데이터부터 읽는 것이 아니라, 버퍼를 사용한 rio함수가 읽어들였던 버퍼의 끝 데이터에서부터 읽어들이게 된다. 바로 이 과정에서 응답 body가 불완전하게 구성되었던 것이었다.

패키징이 된 함수를 활용하는 것은 간편하고, 실용적이고, 효율적일 수 있지만, 내부적인 구조를 전혀 모르는 채로 programming voodoo를 해서는 안될 일임을 이번 이슈를 통해 절실히 느꼈다.

LRU implementation

먼저, cache object를 포함한 구조체들을 node로 가지는 Doulbly Linked List를 구현했다.
그리고 그 리스트를 LIFO 방식으로 관리하도록 했다. 각 cache node는 요청 URI string field로 식별되며, 클라이언트의 요청에 대한 cache가 있는지 확인할 때 list의 각 node를 선형적으로 탐색한다.

1. cache object가 사용되었다면, hit된 cache object를 list의 top으로 끌어 올린다.

2. 서버로부터의 새로운 응답을 cache하고자 할 때 MAX_CACHE_SIZE를 초과하는 상황이라면,
   list의 끝에 있는 (top으로부터 가장 멀리 있는) node를 삭제하고, 새로운 cache object를 list에 추가한다.

3. sentinel node를 사용하여 노드의 삽입과 삭제 시의 포인터들의 갱신을 용이하게 했다.

배경지식

클라이언트-서버 모델

• 한 개의 서버 프로세스, 한 개 이상의 클라이언트 프로세스
• 연산의 가장 기본 단위는 트랜잭션 (요청 - 응답)
• 클라이언트와 서버는 프로세스임.

네트워크

• 네트워크는 단지 또 다른 I/O 디바이스.
• LAN : Local Area Network
• Ethernet : 가장 대중적인 LAN 기술
• Ethernet segment : 호스트들이 허브로 연결되어있는 네트워크 단위
  호스트 - 어댑터 / 허브 - 포트
  허브는 각 포트에서 수신한 비트를 다른 모든 비트로 복사. 그래서 모든 호스트는 모든 비트를 볼 수 있음.
• Ethernet adapter : 어댑터의 비휘발성 메모리에 저장된 고유한 48비트 주소.
• frame : LAN에서 전송 단위
  header bit : source, destination, 프레임 길이
  data bit : data
• bridged ethernet : 다수의 이더넷 세그먼트가 연결된 LAN
  어떤 호스트가 어떤 포트에서 도달 가능한지 장기간에 걸쳐 학습.
  선택적으로 하나의 포트에서 다른 포트로 프레임을 복사.
• router : 네트워크간 연결을 구성하는 특별한 컴퓨터
  각 라우터는 자신이 연결되는 각 네트워크에 대해 어댑터(포트)를 가짐.
• WAN : Wide Area Network
  라우터를 통해 연결된 네트워크 모임.
• internet : LAN과 WAN들로부터 만들 수 있는 총체적 네트워크
  서로 호환되지 않는 네트워크들끼리 연결되어 있지만 데이터 전송이 가능
  어떻게? ⬇️
  호스트 또는 라우터에서 돌고있는, 미리 약속된 방법(protocol)을 구현해놓은 소프트웨어를 통해.
• internet protocol : 호스트들과 라우터들이 데이터를 전송하기 위해서 어떻게 협력할지를 약속해놓은 것.
  • Naming Scheme : 서로 다른 LAN은 호스트에 주소를 설정하는 방법이 서로 다름. internet protocol은 호스트의 주소를 위한 통일된 포맷을 정의.
  • delivery mechanism : 서로 다른 네트워킹 기술은 비트 인코딩 방법 / 프레임 내에 패키징하는 방법이 서로 다르다. internet protocol은 packet이라는 비연속적 단위로 묶는 통일된 방법을 정의.
    packet = header(source, destination, size) + data
    보통 LAN의 frame(header+data)에서 data 부분이 internet packet.

글로벌 IP Internet

• 글로벌 IP Internet : internet에 대한 가장 유명하고 성공적인 구현.
• 미리 약속된 방법은 TCP/IP 를 사용.
  TCP 는 IP위에 구현된 복잡한 프로토콜. 프로세스들 간에 '안전한 완전 양방향' 연결을 제공.
• 클라이언트와 서버는 socket interface와 Unix I/O 함수를 사용해 통신함
• IP는 아래의 속성을 가짐
  • Naming Scheme : basic naming scheme
  • delivery mechanism : datagram(packet)
• Internet은 다음과 같은 특징을 갖는, 전 세계의 호스트의 집합
  • 호스트는 32bit IP 주소를 갖는다.
    IP 주소의 집합은 Internet Domain Name 집합에 매핑된다.
  • 하나의 인터넷 호스트의 프로세스는 '연결'을 통해 다른 인터넷 호스트의 프로세스와 통신할 수 있다.

IP 주소

• IP 주소는 unsigned int (32bit).
• 네트워크 바이트 순서는 '빅엔디안'
  • 빅 엔디안 : 최상위 바이트(높은 자리수에 해당하는 바이트)부터 메모리에 쓴다.(사람이 읽는 방식과 동일) 디버그가 편하다.
  • 리틀 엔디안 : 최하위 바이트부터 메모리에 쓴다. 하위 바이트들만 필요할 때 편하다.

도메인

• 도메인 이름들의 집합은 IP 주소 집합으로 매핑되어 있음. 사람들이 읽고 쓰기 편하게.

• 하나의 도메인 이름은 계층 구조를 가지고 있다.

  • First-level domain names : com, edu, gov, org, net 등등
  • Second-level domain names : ICANN인정 대행사가 획득한 domain name에 해당.
  • 이 아래 단계의 도메인 레벨은 그 도메인을 가진 조직이 자유롭게 생성 가능.

• 일반적인 경우, 다수의 도메인 이름들은 다수의 IP주소로 매핑될 수 있다. (로드 밸런싱 등의 이유)

소켓

• 클라이언트와 서버는 연결을 통해서 바이트 스트림을 주고받는 형식으로 통신.
• 소켓이란
  • 커널의 관점: 소켓은 통신을 위한 끝점.
  • 어플리케이션의 관점: 소켓은 해당 식별자를 가지는 열린 파일
• 하나의 소켓은 IP주소와 16bit int port번호로 이루어 짐.

• 소켓 인터페이스에서 소켓은 active socket, listening socket 으로 나뉠 수 있다.
  socket()으로 소켓 식별자(파일)을 만들면, 일단 기본적으로는 항상 active socket이다.
  이 상태에서 해당 소켓에 대해 connect()를 하면 active socket으로서 서버에 연결할 수 있다.

• 만들어진 소켓 식별자를 bind()와 listen()을 사용해 클라이언트로부터의 요청을 '들을 수 있는' listening socket으로 변환할 수 있다. 이 상태에서 해당 소켓에 대해 accept()를 호출하면, 클라이언트의 연결 요청이 listening socket에 도착하기를 기다린 후, 도착하면 그 클라이언트와의 연결이 수립된 연결 식별자(connect socket, which is active socket)를 리턴한다. listening socket과 connect socket을 분리함으로써 많은 클라이언트 요청을 동시에 처리할 수 있는 가능성이 생긴다 (이에 추가로 동시성을 구현해야 함).

• 리눅스에서 제공하는 함수인 getaddrinfo() 와 getnameinfo()를 통해 위 함수에 사용되는 인자를 안정적으로 획득할 수 있다. 이 둘은 호스트이름,주소,서비스이름,포트번호 등의 스트링정보를 sockaddr(소켓 주소 구조체)로 교환해주거나, 그 역을 수행해주는 역할을 한다.

HTTP

• HTTP - Hypertext Transfer Protocol

• 말그대로 '통신 규약'. 웹 컨텐츠라는 정보를 주고 받기 위한 약속.

• Request = request line 1줄 + request headers(0개 이상) + 빈줄 (+ request body)

  • request line = %s %s %s\r\n : method, URI, version
  • request header = %s: %s\r\n : header-name, header-data
  • empty line = \r\n

• Response = response body 1줄 + response headers(0개 이상) + 빈줄 (+ response body)

  • response line = %s %s %s\r\n : version, status-code, status-message
  • response header = %s: %s\r\n : header-name, header-data
  • empty line = \r\n
    
    

• HTTP 0.9 - 원라인 프로토콜

  • 요청 메서드가 GET만 존재한다. 원라인 프로토콜로 불렷다.
  • HTTP 헤더가 존재하지 않았다.
  • 응답이 파일 내용 자체로 구성된다. HTML 파일 이외에 다른 유형의 문서는 전송할 수 없었다.

  요청

  GET /mypage.html

  응답

  <HTML>
  A very simple HTML page
  </HTML>

• HTTP 1.0 - 확장성 만들기

  • 헤더가 추가되었다.
  • HTTP 버전을 확인할 수 있다.
  • 응답 코드를 확인할 수 있다.
  • Content-Type이 존재하여 HTML이 아닌 다른 문서도 전송할 수 있게 되었다.
  • 커넥션 하나당 요청 하나만 처리할 수 있었다.

  요청

  GET /mypage.html HTTP/1.0
  User-Agent: NCSA_Mosaic/2.0 (Windows 3.1)

  응답

  200 OK
  Date: Tue, 15 Nov 1994 08:12:31 GMT
  Server: CERN/3.0 libwww/2.17
  Content-Type: text/html
  
  <HTML>
  A page with an image
  <IMG SRC="/myimage.gif">
  </HTML>

• HTTP 1.1 - 표준 프로토콜

  • HTTP의 첫번째 표준 버전이다.
  • 지정한 timeout 동안 커넥션을 닫지 않는 persistent Connection이 도입되었다.
  • 여러 요청이 하나의 커넥션을 통해 처리할 수 있게 되었다.
  • Pipelining 기법이 도입되었다.

• Content-Length 헤더의 존재 이유.
  response body를 읽기 위해 클라이언트는 자신이 읽고 있는 스트림에서 body contents의 끝이 어디인지를 알아야 할 것이다. non-persistent한 연결의 경우, 연결이 끊기면 해당 응답이 종료된 것으로 보고, 그 끊긴 지점까지가 response body 의 끝이라고 판단하면 되겠지만, persistent한 연결의 경우 response body의 끝이 어딘지 모호해진다. 이를 위해 서버는Content-Length 헤더를 사용해 클라이언트에게 response body의 크기를 전달하므로써, 응답 헤더의 종료를 의미하는 빈줄(\r\n)이 나타난 이후의 지점부터 해당 크기를 읽을 수 있도록 만들어주는 것이다.

참고자료

• CSAPP 10장, 11장, 12장
• https://scshim.tistory.com/502
• https://stackoverflow.com/questions/27228343/what-are-the-consequences-of-not-including-a-content-length-header-in-a-server-r