[네트워크] 캐싱(Caching)

캐싱

1. 캐시 저장소 설계: 캐시로 사용할 저장소를 설계해야 합니다. 이는 메모리, 디스크, 데이터베이스 등 다양한 형태로 구현될 수 있습니다. 일반적으로는 메모리나 디스크 기반의 저장소를 사용하여 데이터를 저장합니다.
2. 요청 검사: 클라이언트로부터의 요청을 받았을 때, 해당 요청이 캐시에 저장된 데이터에 대한 요청인지 확인해야 합니다. 이를 위해 요청된 리소스의 고유 식별자(예: URL)를 사용하여 캐시 저장소에서 검색합니다.
3. 캐시 데이터 전달: 캐시에 저장된 데이터가 있는 경우, 해당 데이터를 클라이언트에게 전달합니다. 이를 위해 클라이언트로부터의 요청을 처리하는 핸들러에서 캐시 데이터를 반환하면 됩니다.
4. 원격 서버 요청: 캐시에 저장된 데이터가 없거나 캐시 유효기간이 만료된 경우, 원격 서버에 데이터를 요청합니다. 이를 위해 프록시 서버는 클라이언트의 요청을 원격 서버에 전달하고, 응답을 받아옵니다.
5. 캐시 데이터 저장: 원격 서버로부터 받은 응답 데이터를 캐시 저장소에 저장합니다. 이때, 데이터의 고유 식별자(예: URL)를 키로 사용하여 데이터를 저장합니다. 필요에 따라 캐시의 유효기간을 설정하여 일정 시간 동안 유효하도록 관리할 수도 있습니다.
6. 캐시 데이터 관리: 캐시 데이터의 크기를 제한하거나, 오래된 데이터를 자동으로 삭제하여 캐시의 용량을 관리해야 합니다. 이를 위해 LRU(Least Recently Used) 등의 알고리즘을 사용하여 데이터를 관리할 수 있습니다.

 

캐싱 구조체 in C언어

• 연결 리스트(Linked List) 형태

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

typedef struct web_object_t {
    char path[MAXLINE];
    int content_length;
    char *response_ptr;
    struct web_object_t *prev, *next;
} web_object_t;

web_object_t *find_cache(char *path);
void send_cache(web_object_t *web_object, int clientfd);
void read_cache(web_object_t *web_object);
void write_cache(web_object_t *web_object);

extern web_object_t *rootp;
extern web_object_t *lastp;
extern int total_cache_size;

#define MAX_CACHE_SIZE 1049000
#define MAX_OBJECT_SIZE 102400

 

캐시 검색

web_object_t *find_cache(char *path) {
    if (!rootp)
        return NULL;
    web_object_t *current = rootp;
    while (strcmp(current->path, path)) {
        if (!current->next)
            return NULL;

        current = current->next;
        if (!strcmp(current->path, path))
            return current;
    }
    return current;
}

 

클라이언트에게 캐시 전송

void send_cache(web_object_t *web_object, int clientfd) {
    char buf[MAXLINE];
    sprintf(buf, "HTTP/1.0 200 OK\r\n");
    sprintf(buf, "%sServer: Tiny Web Server\r\n", buf);
    sprintf(buf, "%sConnection: close\r\n", buf);
    sprintf(buf, "%sContent-length: %d\r\n\r\n", buf, web_object->content_length);
    Rio_writen(clientfd, buf, strlen(buf));

    Rio_writen(clientfd, web_object->response_ptr, web_object->content_length);
}

 

최근에 쓰인 캐시를 루트로 옮김

void read_cache(web_object_t *web_object) {
    if (web_object == rootp)
        return;

    if (web_object->next) {
        web_object_t *prev_objtect = web_object->prev;
        web_object_t *next_objtect = web_object->next;
        if (prev_objtect)
            web_object->prev->next = next_objtect;
        web_object->next->prev = prev_objtect;
    } else {
        web_object->prev->next = NULL;
    }

    web_object->next = rootp;
    rootp = web_object;
}

 

캐시에 저장

void write_cache(web_object_t *web_object) {
    total_cache_size += web_object->content_length;

    while (total_cache_size > MAX_CACHE_SIZE) {
        total_cache_size -= lastp->content_length;
        lastp = lastp->prev;
        free(lastp->next);
        lastp->next = NULL;
    }

    if (!rootp)
        lastp = web_object;
    else {
        web_object->next = rootp;
        rootp->prev = web_object;
    }
    rootp = web_object;
}

 

캐시를 연결 리스트로 구현하는 이유?

1. 데이터의 삽입과 삭제가 효율적: 연결 리스트는 데이터의 삽입과 삭제가 상대적으로 간단하게 이루어집니다. 데이터를 캐시에 추가할 때나 삭제할 때, 연결 리스트는 단순히 노드의 연결을 조정하는 작업으로 처리할 수 있습니다. 이는 배열과 같은 다른 데이터 구조에 비해 더 효율적인 삽입과 삭제를 가능하게 합니다.
2. 데이터의 순서 유지: 연결 리스트는 데이터를 추가한 순서대로 유지합니다. 이는 LRU(Least Recently Used)와 같은 캐시 대체 알고리즘을 구현하는 데 유용합니다. 캐시의 가장 오래된 데이터를 제거하기 위해서는 캐시 내 데이터의 순서를 추적해야 하는데, 연결 리스트는 데이터를 추가한 순서대로 유지하기 때문에 이를 간편하게 처리할 수 있습니다.
3. 동적 크기 조정: 연결 리스트는 동적으로 크기를 조정할 수 있습니다. 데이터의 삽입과 삭제에 따라 리스트의 길이가 유동적으로 변경될 수 있어, 캐시의 크기가 동적으로 조절되는 상황에서 유용합니다. 이는 캐시의 효율성과 용량 관리를 개선하는 데 도움이 됩니다.
4. 효율적인 반복과 탐색: 연결 리스트는 데이터를 순차적으로 접근하고 탐색하는 데 효율적입니다. 데이터를 순차적으로 탐색하거나, 특정 데이터를 찾아야 할 때 연결 리스트는 선형 탐색을 수행하며 노드 간의 연결로 이루어진 구조이기 때문에 효율적인 반복과 탐색이 가능합니다.

위와 같은 이유로 연결 리스트는 캐시 구현에 많이 사용되며, 데이터의 삽입, 삭제, 순서 유지, 동적 크기 조정 등의 캐시 작업을 효율적으로 수행할 수 있는 데이터 구조입니다.

 

LRU 알고리즘

LRU(Least Recently Used) 알고리즘은 캐시 메모리에서 어떤 데이터를 삭제할지 결정하는 방식 중 하나입니다. LRU 알고리즘은 가장 최근에 사용되지 않은 데이터를 우선적으로 삭제하는 방식으로 동작합니다. LRU 알고리즘은 데이터의 접근 패턴을 추적하여 가장 오래 전에 사용된 데이터를 식별하고, 이를 삭제 대상으로 선택합니다. 간단히 말해, 가장 오랫동안 사용되지 않은 데이터를 삭제하여 새로운 데이터에 공간을 확보하는 방식입니다.

 

LRU 알고리즘의 구현은 일반적으로 "사용된 시간"을 추적하는 방식으로 이루어집니다. 각 데이터는 접근될 때마다 타임스탬프를 갱신하거나, 데이터에 접근한 순서를 기록하여 사용 시간을 추정합니다. 그리고 공간이 부족해질 때, LRU 알고리즘은 가장 오래된 데이터를 삭제합니다. 이러한 방식으로 LRU 알고리즘은 최근에 사용되지 않은 데이터를 삭제하므로, 상대적으로 자주 사용되는 데이터가 캐시에 유지되는 경향이 있습니다. 이는 데이터의 로컬리티(locality)를 잘 반영하고, 캐시 효율성을 높이는 데 도움이 됩니다.

 

LRU 알고리즘은 많은 캐시 기반 시스템에서 사용되며, 데이터베이스 캐싱, 웹 캐싱, 파일 시스템 캐싱 등 다양한 분야에서 적용됩니다.