Web Proxy #6 : Caching Proxy

캐싱을 구현해야하는 CS:APP Proxy Lab의 마지막 단계이다. LRU라는 알고리즘을 제시한 요구조건을 그대로 검색해보니 Double Linked List와 Hash Table을 병행 사용하는 형태를 제안하길래 그걸 그대로 적용한 내용을 풀어본다.

2025.05.07 - [구현하기] - Tiny Web Server 개발기록 #5 : 멀티쓰레딩 Proxy

Tiny Web Server 개발기록 #5 : 멀티쓰레딩 Proxy

개념을 먼저 짚기

캐시 시스템을 만들라고 합니다. 캐싱이 뭐죠?

클라이언트가 프록시를 통해 서버에게 연결하면 서버가 주는 무언가가 있다. 프록시는 자체적으로 이걸 저장해둔다. 클라이언트가 이걸 요청하면 프록시에 이게 있는지 먼저 보고, 없는 경우에만 끌어온다. 이게 캐싱의 기본 루틴이다.

 

 

마냥 저장을 할 순 없으니, 자주 사용된 것을 남겨두고, 상대적으로 자주 사용되지 못한 애들은 삭제될 수 있는 여지가 점점 높아진다. 이걸 정확히 어떻게 표현하면 좋을지 잘 모르겠는데, 새로운 아이템이 들어와서 기존 캐시에서 정리 해야 하는 시점에서, 제일 사용률이 낮아서 맨 끝에 있는 아이템이 제거된다. 이것이 LRU 알고리즘 형태이며, 조금 검색하니 이중 연결 리스트와 해시 테이블 결합 형태가 제일 일반적이었다.

여기서 캐시는 전역 변수 형태로 선언하도록 할 것이다.

 

LRU를 만들어오래요

주의 할 것은 해시 테이블을 만들 때 Chaining이지만 여기서 Chaining의 구현 기법도 Linked List이기 때문에 이 부분을 헷갈리면 안된다. 

Double Linked List의 head, tail은 실질적인 삽입, 삭제에만 사용되는 포인터이다. 실제 탐색은 해시 테이블을 통해서 이루어진다. 

캐시를 구현하기 위한 다양한 구조체 구성

typedef struct Item {
  char *url;
  void *content;

  size_t size;  
  
  struct Item *prev; 
  struct Item *next;
} Item;

typedef struct HashNode {
  char *key;
  Item *value;
  struct HashNode *next;
} HashNode;

typedef struct
{
  HashNode **buckets;
  size_t bucketcount;
} HashTable;

typedef struct 
{
  Item *head, *tail;
  size_t totalSize;
  size_t capacity;
  HashTable *map;
} LRUcache;

 

캐시 초기화

void init_cache(LRUcache *cache, size_t capacity)
{
  cache->head = cache->tail = NULL;
  cache->totalSize = 0;
  cache->map = hashT_create();
  cache->capacity = capacity;
}

cache에 해당하는 구조체 LRUcache에 오해가 없도록 전부 다 이쁘게 초기화 해준다.

 

 

캐시에 아이템 추가하기

void addItem(LRUcache *cache, Item *item)
{
  item->prev = NULL;
  item->next = cache->head;

  if(cache->head) cache->head->prev = item;
  cache->head = item;
  if (!cache->tail) cache->tail = item;

  hashT_put(cache->map, item->url, item);

  cache->totalSize += item->size;
}

아이템을 머리 부분에 추가하는 함수이다. 이 부분은 일반적인 이중 연결 리스트의 형태이지만, 도중에 hashT_put 함수를 볼 수 있다 : 얘는 해시 테이블에 아이템을 추가하는데, 아랫 줄에서 좀 더 자세하게 다뤄보겠다.

 

 

캐시에 아이템 제거하기

void deleteItem(LRUcache *cache)
{
  Item *vic = cache->tail;
  if(!vic) return;

  cache->tail = vic->prev;
  if (cache->tail) cache->tail->next = NULL;
  else cache->head = NULL;

  hashT_remove(cache->map, vic->url);

  cache->totalSize -= vic->size;
  free(vic->content);
  free(vic->url);
  free(vic);
}

아이템을 제거한다. 물론 tail에 대해서만 제거하니 별 특별한 건 없다. hashT_remove 는 아래에서 자세하게 다룬다. 여기서는 특별한 게 없고 free를 아이템 내부의 구성 부터 확인한다.  

 

아이템을 이중 연결 리스트 첫 번째로 이동 시키기

void moveToHead(LRUcache *cache, Item *item)
{
  if (cache->head == item) return;

  if (item->prev) item->prev->next = item->next;
  if (item->next) item->next->prev = item->prev;
  if (cache->tail == item) cache->tail = item->prev;

  item->next = cache->head;
  cache->head->prev = item;
  cache->head = item;
  item->prev = NULL;
}

LRU 알고리즘 상 사용된 아이템은 맨 앞으로 옮겨져서 삭제 우선순위를 낮추어 주는게 필요하다. 이 코드를 통해 효과를 볼 수 있다.

 

 

아이템 실제 배치하기  | put

void placeItem(LRUcache *cache, const char *url, const char *contents, size_t size)
{
  Item *exist = hashT_get(cache->map, url);

  if(exist)
  {
    cache->totalSize -= exist->size;
    free(exist->content);
    exist->size = size;
    exist->content = Malloc(size);
    memcpy(exist->content, contents, size);
    cache->totalSize += size;
    moveToHead(cache, exist);
  }
  else
  {
    Item *item = malloc(sizeof(Item));
    item->url = strdup(url);
    item->size = size;
    item->content = Malloc(size);
    memcpy(item->content, contents, size);

    while(cache->totalSize + size > MAX_CACHE_SIZE)
    {
      deleteItem(cache);
    }
    addItem(cache, item);
  }
}

아이템이 있냐 없냐에 따라 내용이 다소 달라진다. 음.. 달리 언급할게 없다..

 

 

아이템 정보 가져오기 | get

char *getItem(LRUcache *cache, const char *url)
{
  Item *item = hashT_get(cache->map, url);
  if(!item) return NULL;

  moveToHead(cache, item);
  return item->content;
}

해시 테이블에 대한 장점인 O(1)을 적극 활용하는 내용이다. hashT_get 은 이제 슬슬 설명하겠다.

---

Hash Table 구현

Hash Table 생성 및 초기화

HashTable *hashT_create()
{
  HashTable *ht = malloc(sizeof(HashTable));
  ht->bucketcount = HASH_BUCKET_COUNT;
  ht->buckets = calloc(ht->bucketcount, sizeof(HashNode *));
  return ht;
}

해쉬 테이블을 초기화한다.

 

 

Hash 함수 | DJA2

static unsigned long hash_func(const char *str)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
    {
      hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

알려진 해쉬 함수인데, 문자열을 변환시키는 함수로 알려져있다. hash << 5는 31.

 

 

Hash Table 아이템 배치 | put

void hashT_put(HashTable *ht, const char *key, Item *value)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  HashNode *node = ht->buckets[h];

  for(; node; node = node->next)
  {
    if (strcmp(node->key, key) == 0)
    {
      node->value = value;
      return;
    } 
  }

  node = malloc(sizeof(HashNode));
  node->key = strdup(key);
  node->value = value;
  node->next = ht->buckets[h];
  ht->buckets[h] = node;
}

해쉬 함수를 이용하여 h를 정하면 해당 위치에 아이템을 배치하고자 시도한다. 막 엄청 특이한건 없고 정의에 충실하다.

 

 

Hash Table 아이템 가져오기 | get

Item *hashT_get(HashTable *ht, const char *key)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  for(HashNode *node = ht->buckets[h]; node; node = node->next)
  {
    if(strcmp(node->key, key) == 0)
      return node->value;
  }
  return NULL;
}

해쉬 테이블 기반 탐색이니 O(1)이다.

 

Hash Table 아이템 제거

void hashT_remove(HashTable *ht, const char *key)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  HashNode *node = ht->buckets[h];
  HashNode *prev = NULL;

  while (node)
  {
    if(strcmp(node->key, key) == 0)
    {
      if(prev) prev->next = node->next;
      else ht->buckets[h] = node->next;
      free(node->key);
      free(node);
      return;
    }
    prev = node;
    node = node->next;
  }
}

해당 아이템이 연결 리스트에서 제거되면 이어서 호출된다.

 

Hash Table 메모리 해제

void hashT_destroy(HashTable *ht)
{
  for (size_t i = 0; i < ht->bucketcount; i++)
  {
    HashNode *node = ht->buckets[i];
    while (node)
    {
      HashNode *next = node->next;
      free(node->key);
      free(node);
      node = next;
    }
  }
  free(ht->buckets);
  free(ht);
}

테이블 자체를 제거한다.

 

본문 변경 점

pthread_mutex_t cache_mutex;
LRUcache cache;

전역 변수로 두 가지가 추가되었다. 뮤텍스는 쓰레드간의 동기화를 위해 cache 접근에 대해 필요한 내용인데, 당장 설명하기엔 좀 논할게 많아서, 그냥 진짜 접근 할 때 잠깐 열리는 문 정도로 생각하면 좋다.

cache는 전역 변수로 선언하여 사용해야 그 의도에 맞다. 모든 쓰레드가 공통된 캐시를 사용해야 하기 때문.

init_cache(&cache, MAX_CACHE_SIZE);
  pthread_mutex_init(&cache_mutex, NULL);

두 변수는 main에서 초기화된다.

realTask 에서 변경 점이 있다 :

void *realTask(int client_fd)
{
...

...
  
 
 parseURI(uri, hostname, port, path);
    
    pthread_mutex_lock(&cache_mutex);
    char *cached = getItem(&cache, uri);
    pthread_mutex_unlock(&cache_mutex);
    if(cached)
    {
      Rio_writen(client_fd, cached, strlen(cached));
      return;
    }
  
...

  while ((n = Rio_readnb(&server_rio, response_buf, MAXBUF)) > 0)
  { 
    Rio_writen(client_fd, response_buf, n);
  }

  pthread_mutex_lock(&cache_mutex);
   placeItem(&cache, uri, response_buf, strlen(response_buf));
  pthread_mutex_unlock(&cache_mutex);


...
}

cached를 감지해서 hit/miss 여부를 감지하고, mutex_lock/unlock 구문이 추가 되었다. 이렇게하면 Proxy Lab Step 3에 맞는 구현을 진행 할 수 있다.

 

아래는 코드 전문이다. || https://github.com/pwerty/webproxy_lab_docker 에서 webproxy-lab/proxy.c 와 내용 동일.

#include <stdio.h>
#include <string.h>
#include "csapp.h"

/* Recommended max cache and object sizes */
#define MAX_CACHE_SIZE 1049000
#define MAX_OBJECT_SIZE 102400

#define HASH_BUCKET_COUNT 1024

/* You won't lose style points for including this long line in your code */
static const char *user_agent_hdr =
    "User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.3) Gecko/20120305 "
    "Firefox/10.0.3\r\n";
// Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/135.0.0.0 Safari/537.36

typedef struct Item {
  // 1. 키 식별자
  char *url;                    // 해시 테이블의 키로 사용할 내용, url-uri 계열을 사용
  
  // 2. 데이터 저장
  void *content;                // 캐시된 콘텐츠 (응답 데이터)
  size_t size;                  // 콘텐츠의 크기
  
  // 3. 이중 연결 리스트 포인터
  struct Item *prev;       // prev ptr
  struct Item *next;       // next ptr
  
} Item;

typedef struct HashNode {
  char *key;
  Item *value;
  struct HashNode *next;
} HashNode;

typedef struct
{
  HashNode **buckets;
  size_t bucketcount;
} HashTable;

typedef struct 
{
  Item *head, *tail;
  size_t totalSize;
  size_t capacity;
  HashTable *map;
} LRUcache;

void deleteItem(LRUcache *cache);
void addItem(LRUcache *cache, Item *item);
void init_cache(LRUcache *cache, size_t capacity);
void placeItem(LRUcache *cache, const char *url, const char *contents, size_t size);
char *getItem(LRUcache *cache, const char *url);
HashTable *hashT_create();
void hashT_put(HashTable *ht, const char *key, Item *value);
Item *hashT_get(HashTable *ht, const char *key);
void hashT_remove(HashTable *ht, const char *key);
void hashT_destroy(HashTable *ht);
static unsigned long hash_func(const char *str);


void init_cache(LRUcache *cache, size_t capacity)
{
  cache->head = cache->tail = NULL;
  cache->totalSize = 0;
  cache->map = hashT_create();
  cache->capacity = capacity;
}

void addItem(LRUcache *cache, Item *item)
{
  item->prev = NULL;
  item->next = cache->head;

  if(cache->head) cache->head->prev = item;
  cache->head = item;
  if (!cache->tail) cache->tail = item;

  hashT_put(cache->map, item->url, item);

  cache->totalSize += item->size;
}

void deleteItem(LRUcache *cache)
{
  Item *vic = cache->tail;
  if(!vic) return;

  cache->tail = vic->prev;
  if (cache->tail) cache->tail->next = NULL;
  else cache->head = NULL;

  hashT_remove(cache->map, vic->url);

  cache->totalSize -= vic->size;
  free(vic->content);
  free(vic->url);
  free(vic);
}

void moveToHead(LRUcache *cache, Item *item)
{
  if (cache->head == item) return;

  if (item->prev) item->prev->next = item->next;
  if (item->next) item->next->prev = item->prev;
  if (cache->tail == item) cache->tail = item->prev;

  item->next = cache->head;
  cache->head->prev = item;
  cache->head = item;
  item->prev = NULL;
}

void placeItem(LRUcache *cache, const char *url, const char *contents, size_t size)
{
  Item *exist = hashT_get(cache->map, url);

  if(exist)
  {
    cache->totalSize -= exist->size;
    free(exist->content);
    exist->size = size;
    exist->content = Malloc(size);
    memcpy(exist->content, contents, size);
    cache->totalSize += size;
    moveToHead(cache, exist);
  }
  else
  {
    Item *item = malloc(sizeof(Item));
    item->url = strdup(url);
    item->size = size;
    item->content = Malloc(size);
    memcpy(item->content, contents, size);

    while(cache->totalSize + size > MAX_CACHE_SIZE)
    {
      deleteItem(cache);
    }
    addItem(cache, item);
  }
}

char *getItem(LRUcache *cache, const char *url)
{
  Item *item = hashT_get(cache->map, url);
  if(!item) return NULL;

  moveToHead(cache, item);
  return item->content;
}

HashTable *hashT_create()
{
  HashTable *ht = malloc(sizeof(HashTable));
  ht->bucketcount = HASH_BUCKET_COUNT;
  ht->buckets = calloc(ht->bucketcount, sizeof(HashNode *));
  return ht;
}


static unsigned long hash_func(const char *str)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
    {
      hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

void hashT_put(HashTable *ht, const char *key, Item *value)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  HashNode *node = ht->buckets[h];

  for(; node; node = node->next)
  {
    if (strcmp(node->key, key) == 0)
    {
      node->value = value;
      return;
    } 
  }

  node = malloc(sizeof(HashNode));
  node->key = strdup(key);
  node->value = value;
  node->next = ht->buckets[h];
  ht->buckets[h] = node;
}


Item *hashT_get(HashTable *ht, const char *key)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  for(HashNode *node = ht->buckets[h]; node; node = node->next)
  {
    if(strcmp(node->key, key) == 0)
      return node->value;
  }
  return NULL;
}

void hashT_remove(HashTable *ht, const char *key)
{
  unsigned long h = hash_func(key) % ht->bucketcount;
  HashNode *node = ht->buckets[h];
  HashNode *prev = NULL;

  while (node)
  {
    if(strcmp(node->key, key) == 0)
    {
      if(prev) prev->next = node->next;
      else ht->buckets[h] = node->next;
      free(node->key);
      free(node);
      return;
    }
    prev = node;
    node = node->next;
  }
}

void hashT_destroy(HashTable *ht)
{
  for (size_t i = 0; i < ht->bucketcount; i++)
  {
    HashNode *node = ht->buckets[i];
    while (node)
    {
      HashNode *next = node->next;
      free(node->key);
      free(node);
      node = next;
    }
  }
  free(ht->buckets);
  free(ht);
}


void *task(void *fd);
void *realTask(int client_fd);
void format_http_header(char *client_rio, char *path, char *hostname, char *other_header);
void read_requesthdrs(rio_t *rp, char *host_header, char *other_header);
void get_filetype(char *filename, char *filetype);

pthread_mutex_t cache_mutex;
LRUcache cache;

int main(int argc, char **argv)
{
  int listenfd, connfd;
  char hostname[MAXLINE], port[MAXLINE];
  socklen_t clientlen;
  struct sockaddr_storage clientaddr;

  init_cache(&cache, MAX_CACHE_SIZE);
  pthread_mutex_init(&cache_mutex, NULL);

  if(argc != 2)
  {
    fprintf(stderr, "usage: %s <port>\n", argv[0]);
    exit(1);
  }

  listenfd = Open_listenfd(argv[1]);
  while (1)
  {
    int *connfd_ptr = Malloc(sizeof(int));
    *connfd_ptr = Accept(listenfd, (SA *)&clientaddr, &clientlen);
    pthread_t pthr;
    pthread_create(&pthr, NULL, task, connfd_ptr);
  } 
}



void *realTask(int client_fd)
{
  struct stat sbuf;
  char buf[MAXLINE], method[MAXLINE], uri[MAXLINE], version[MAXLINE];
  char hostHeader[MAXLINE], otherHeader[MAXLINE];
  char hostname[MAXLINE], path[MAXLINE], port[MAXLINE];
  char request_buf[MAXLINE], response_buf[MAXLINE];
  int server_fd, flag;
  ssize_t n;
  rio_t client_rio, server_rio;
  

  Rio_readinitb(&client_rio, client_fd);
  Rio_readlineb(&client_rio, buf, MAXLINE);
  printf("Request Headers:\n");
  printf("%s", buf);
  sscanf(buf, "%s %s %s", method, uri, version);
  
  

 parseURI(uri, hostname, port, path);
    // 대충 이 언저리에서 uri를 바탕으로 캐시 접근이 필요해보인다.
    
    pthread_mutex_lock(&cache_mutex);
    char *cached = getItem(&cache, uri);
    pthread_mutex_unlock(&cache_mutex);
    if(cached)
    {
      Rio_writen(client_fd, cached, strlen(cached));
      return;
    }
  
  read_requesthdrs(&client_rio, hostHeader, otherHeader); // read HTTP request headers
    // HTTP 1.1->HTTP 1.0으로 변경 

  format_http_header(request_buf, path, hostname, otherHeader);

  server_fd = Open_clientfd(hostname, port);
  Rio_writen(server_fd, request_buf, strlen(request_buf));
  Rio_readinitb(&server_rio, server_fd);


  while ((n = Rio_readnb(&server_rio, response_buf, MAXBUF)) > 0)
  { 
    Rio_writen(client_fd, response_buf, n);
  }

  pthread_mutex_lock(&cache_mutex);
   placeItem(&cache, uri, response_buf, strlen(response_buf));
  pthread_mutex_unlock(&cache_mutex);


  Close(server_fd);
  //Close(client_fd);
  return NULL;
}

void read_requesthdrs(rio_t *rp, char *host_header, char *other_header){
    char buf[MAXLINE];
  
    host_header[0]='\0';
    other_header[0]='\0';
  
    while(Rio_readlineb(rp, buf, MAXLINE) > 0 && strcmp(buf, "\r\n")){
      //buf에 남은 자리가 있고, buf가 "\r\n"으로 마지막에 도달하지 않았으면 계속 읽음
      if(!strncasecmp(buf, "Host:",5)){
        //Host만 따로 저장해주면 되서? 
        strcpy(host_header, buf);
      }
      else if(!strncasecmp(buf, "User-Agent:", 11)||!strncasecmp(buf, "Connection:", 11)||!strncasecmp(buf, "Proxy-Connection:", 17)){
        //얘들은 버림
        continue;
      }else{
        //그 외의 헤더는 다른곳에 저장해둠 
        strcat(other_header, buf);
      }
    }
  }

void format_http_header(char *client_rio, char *path, char *hostname, char *other_header){
    sprintf( client_rio,
    "GET %s HTTP/1.0\r\n"
    "Host: %s\r\n"
    "%s"
    "Connection: close\r\n"
    "Proxy-Connection: close\r\n"
    "%s"
    "\r\n",
    path, hostname, user_agent_hdr, other_header);
  }
  

void parseURI(char *uri, char *hostname, char *port, char *path)
{
    char *hostBegin, *hostEnd, *portBegin, *pathBegin;
    int hostLen, portLen, pathLen;

    hostBegin = strstr(uri, "//");
    if (hostBegin != NULL)
        hostBegin += 2;
    else
        hostBegin = (char *)uri;
    // hostbegin, 즉 본격적인 위치를 확인해야함. //의 시작 위치니 //를 스킵한 위치로 던져주는 것
    
    pathBegin = strchr(hostBegin, '/');
    if(pathBegin != NULL)
    {
        hostEnd = pathBegin;
        pathLen = strlen(pathBegin);
        strncpy(path, pathBegin, pathLen);
        path[pathLen] = '\0';
    }
    else
    {
        hostEnd = hostBegin + strlen(hostBegin);
        path[0] = '\0';
    }
    // http://www.naver.com/ << 즉, hostbegin은 //를 이미 넘어간 상태에서 다음 /를 찾는 것이다.

    portBegin = strchr(hostBegin, ':');
    if (portBegin != NULL && portBegin < hostEnd)
    {
        hostLen = portBegin - hostBegin;
        strncpy(hostname, hostBegin, hostLen);
        hostname[hostLen] = '\0';

        portBegin++;
        portLen = hostEnd - portBegin;
        strncpy(port, portBegin, portLen);
        port[portLen] = '\0';
    }
    else
    {
        hostLen = hostEnd - hostBegin;
        strncpy(hostname, hostBegin, hostLen);
        hostname[hostLen] = '\0';
        port[0] = '\0';
    }
    // 포트 번호 탐색.
}

void *task(void *connfd)
{
    int fd = *((int *)connfd);
    free(connfd);
    Pthread_detach(pthread_self());
    realTask(fd);
    Close(fd);
}
// 1차 구현 완료
// 2차 목표, 멀티쓰레딩 프로젝트
  // 뭐가 어떻게 흘러가느냐?
  // 클라이언트의 연결 발생에 대해 디스크립터를 쥐어주고 새로운 쓰레드를 만든다.
    // 해당 쓰레드는 할 일을 하는데, 할 일을 할때 써야할 rio는 공통된 rio를 사용하게 끔한다.