3) Look-aside cache 구현하기

- 과제명
Look-aside cache 구현하기

- 캐시: 자주 사용되는 데이터 값을 미리 복사해놓는 임시 저장소.

속도 향상을 위해 사용하며, 다음과 같은 상황에서 사용된다.

원본 데이터보다 빠르게 접근한다.
같은 데이터에 반복적으로 접근한다.
변하지 않는 데이터를 주로 사용한다.

- 캐싱 전략: 캐시로 사용할 때 어떻게 배치하는가가 시스템 성능에 큰 영향을 준다.

Look-Aside: 데이터를 찾을 때 우선 캐시에서 찾고, 데이터가 있다면 캐시에서 데이터를 가져오는 전략.
- 만약 캐시에 데이터가 없어 Cache Miss가 발생한다면, 앱은 DB에서 데이터를 가져온 뒤 캐쉬에 넣어주는 작업을 진행한다.
- 이 구조는 캐시가 다운되더라도 DB에서 데이터를 가져올 수 있다.
- DB에서 캐시로 미리 데이터를 넣어주는 것을 Cache Warming이라고 부른다.
Read Through
Write Through
Write Back
Write Around

- 파레토 법칙: 8:2의 법칙. 전체 결과의 80%는 전체 원인의 20%에서 발생한다는 현상. 일부만 저장해도 대부분의 데이터를 케어할 수 있다.

더 자세히: https://yoongrammer.tistory.com/101

- 문제 설명
우리는 수업 시간에 look-aside cache에 대해 배워본 바 있습니다. 이제 직접 look-aside cache를 구현해서 캐시 의 작동 원리에 대해 이해해봅시다.

- 요구 사항
주어진 client.c, server.c, cache.c, util.h를 수정해서 look-aside cache를 완성하세요.
코드를 작성해서 distributed key-value stores를 구현하세요.
이번 과제에서는 오직 읽기 요청/답신만이 존재한다고 가정합니다. 서버에서는 데이터가 미리 준비되어 있습니다.
서버에서는 읽기 요청을 받으면 해당 요청을 처리한 후에 답장을 클라이언트로 보냅니다.
클라이언트는 읽기 요청을 보낸 후, 캐시 노드 혹은 서버로부터 답장을 받으면 이에 대해 적절한 처리를 수행합니다.

- util.h

#include <arpa/inet.h>
#include <netinet/in.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <signal.h>
#include <arpa/inet.h>
#include <netinet/in.h>
#include <stdbool.h>
#include <time.h>

// Constants
#define KEY_SIZE 16 // 사용할 KEY 크기이다. 16바이트.
#define VALUE_SIZE 16 // 사용할 VALUE 크기이다. 32바이트.
#define DATASET_SIZE 1000 // 데이터셋 크기
#define SET_SIZE 62     // 가능한 문자들의 수 (예: 영문 대소문자 + 숫자)
const char SET[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

// 가독성을 위해 메시지 타입별로 매크로를 만듬
#define READ_REQ 0
#define READ_REP 1
#define WRITE_REQ 2
#define WRITE_REP 3
#define CACHE_MISS 4

struct KVS { // key value store 구조체
    uint8_t type;  // message type
    char key[KEY_SIZE]; // key
    char value[VALUE_SIZE]; // value
} __attribute__((packed));

char* get_type(struct KVS RecvMsg){
  char* type;
  if(RecvMsg.type == READ_REQ) type ="READ_REQ";
  else if(RecvMsg.type == READ_REP) type ="READ_REP";
  else if(RecvMsg.type == WRITE_REQ) type ="WRITE_REQ";
  else type ="WRITE_REP";
  return type;
}

uint64_t hash64(const char* str) {
    uint64_t value = 0;
    while (*str) {
        value = (value * 31 + (uint8_t)*str++) & 0xFFFFFFFFFFFFFFFF;
    }


    value = (((value >> 32) ^ value) * 0xc4ceb9fe1a85ec53) & 0xFFFFFFFFFFFFFFFF;
    value = (((value >> 32) ^ value) * 0xc4ceb9fe1a85ec53) & 0xFFFFFFFFFFFFFFFF;
    value = (value >> 32) ^ value;

    return value & 0xFFFFFFFFFFFFFFFF;
}

- client.c

#include "util.h"

const char* dst_ip = "127.0.0.1"; // 하나의 host안에서 통신할 것이므로 서버주소는 localhost(i.e., 127.0.0.1)임

// 임의의 key를 생성해서 반환해줌
void generate_key(char* key) {
    uint64_t number = rand() % DATASET_SIZE;
    for (int i = 0; i < 5; ++i) number = ((number << 3) - number + 7) & 0xFFFFFFFFFFFFFFFF;
    key[KEY_SIZE - 1] = '\0';
    for (int i = KEY_SIZE - 2; i >= 0; i--) {
        int index = number % SET_SIZE;
        key[i] = SET[index];
        number /= SET_SIZE;
    }
}

int main(int argc, char *argv[]) {

  srand((unsigned int)time(NULL));  // 난수 발생기 초기화
  /* 서버 구조체 설정 */
	int SERVER_PORT = 5001;
	struct sockaddr_in srv_addr; // 패킷을 수신할 서버의 정보를 담을 소켓 구조체를 생성한다.
	memset(&srv_addr, 0, sizeof(srv_addr)); // 구조체를 모두 '0'으로 초기화해준다.
	srv_addr.sin_family = AF_INET; // IPv4를 사용할 것이므로 AF_INET으로 family를 지정한다.
	srv_addr.sin_port = htons(SERVER_PORT); // 서버의 포트번호를 넣어준다. 이 때 htons()를 통해 byte order를 network order로 변환한다.
	inet_pton(AF_INET, dst_ip, &srv_addr.sin_addr);  // 문자열인 IP주소를 바이너리로 변환한 후 소켓 구조체에 저장해준다.

  /* 소켓 생성 */
	int sock; // 소켓 디스크립터(socket descriptor)를 생성한다.
	if ((sock = socket(AF_INET, SOCK_DGRAM, 0)) < 0) { // socket()으로 IPv4(AF_INET), UDP(SOC_DGRAM)를 사용하는 소켓을 생성 시도한다.
		printf("Could not create socket\n"); // sock으로 return되는 값이 -1이라면 소켓 생성에 실패한 것이다.
		exit(1);
	}

	int n = 0;

  struct KVS SendMsg={0,}; // 송신용으로 쓸 메시지 구조체 생성 및 초기화

  struct sockaddr_in src_addr; // 패킷을 수신하였을 때, 해당 패킷을 보낸 송신자(Source)의 정보를 저장하기 위한 소켓 구조체
  socklen_t src_addr_len = sizeof(src_addr); // 수신한 패킷의 소켓 구조체 크기를 저장함. IPv4를 사용하므로 sockaddr_in 크기인 16바이트가 저장됨.
  int cnt = 0; // 패킷 5개를 전송한다.
  size_t pkt_size = 0;
  struct KVS RecvMsg = { 0, }; // 수신용으로 쓸 메세지 구조체 생성 및 초기화
	while(cnt < 5){
    printf("Request ID: %d\n",cnt++);
	printf("Sent bytes: %ld\n", sizeof(SendMsg) - VALUE_SIZE);
	SendMsg.type = READ_REQ; // 타입 READ_REQ 설정
	generate_key(SendMsg.key); // 키 생성
	printf("Type: %s Key: %s Value:\n", get_type(SendMsg), SendMsg.key); // 메세지 타입, 키 출력

	sendto(sock, &SendMsg, sizeof(SendMsg), 0, (struct sockaddr*)&srv_addr, sizeof(srv_addr)); // 소켓 통해 송신
	
	recvfrom(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, &src_addr_len); // 소켓 통해 수신

	/* 메세지 타입이 CACHE_MISS 인 경우 */
	if (RecvMsg.type == CACHE_MISS) {
		printf("Cache Miss!!\n");
		srv_addr.sin_port = htons(SERVER_PORT + 1); // port 번호 5002로 변경
		sendto(sock, &SendMsg, sizeof(SendMsg), 0, (struct sockaddr*)&srv_addr, sizeof(srv_addr));
		recvfrom(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, &src_addr_len);
	}

	/* 메세지 타입이 READ_REP인 경우 */
	if (RecvMsg.type == READ_REP) {
		/* 출력 */
		srv_addr.sin_port = htons(SERVER_PORT); // port 번호 5001로 초기화
		printf("Cache hit!!\n");
		printf("Received bytes: %ld\n", sizeof(RecvMsg));
		printf("Type: %s Key: %s value: %s\n", get_type(RecvMsg), RecvMsg.key, RecvMsg.value);
		printf("\n");
	}
	}

	close(sock); // 소켓을 닫아준다.
	return 0;
}

- cache.c

#include "util.h"

int SERVER_PORT; // 서버 포트번호

static volatile int quit = 0; // Trigger conditions for SIGINT
void signal_handler(int signum) {
	if(signum == SIGINT){  // Functions for Ctrl+C (SIGINT)
		quit = 1;
	}
}

int main(int argc, char *argv[]) {
	// 프로그램 시작시 입력받은 매개변수를 parsing한다.
	if (argc < 2) {
		printf("Input : %s port number\n", argv[0]);
		return 1;
	}

	srand((unsigned int)time(NULL));  // 난수 발생기 초기화

	signal(SIGINT, signal_handler); // SIGINT에 대한 핸들러 등록

	SERVER_PORT = atoi(argv[1]); // 입력받은 argument를 포트번호 변수에 넣어준다.

	// 서버의 정보를 담을 소켓 구조체 생성 및 초기화
	struct sockaddr_in srv_addr;
	memset(&srv_addr, 0, sizeof(srv_addr));
	srv_addr.sin_family = AF_INET;
	srv_addr.sin_port = htons(SERVER_PORT);
	srv_addr.sin_addr.s_addr = htonl(INADDR_ANY); // 0.0.0.0 i.e., 자기 자신의 IP

	// 소켓을 생성한다.
	int sock;
	if ((sock = socket(AF_INET, SOCK_DGRAM, 0)) < 0) {
		printf("Could not create listen socket\n");
		exit(1);
	}

	// 생성한 소켓에 소켓구조체를 bind시킨다.
	if ((bind(sock, (struct sockaddr *)&srv_addr, sizeof(srv_addr))) < 0) {
		printf("Could not bind socket\n");
		exit(1);
	}


	int n = 0;
  struct KVS RecvMsg={0,}; // 수신용으로 쓸 메시지 구조체 생성 및 초기화

	struct sockaddr_in src_addr; // 패킷을 수신하였을 때, 해당 패킷을 보낸 송신자(Source)의 정보를 저장하기 위한 소켓 구조체
  socklen_t src_addr_len = sizeof(src_addr);
	size_t pkt_size = 0;
	while (!quit) {
		recvfrom(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, &src_addr_len); // 소켓 수신

		/* 50% 확률 cache hit 또는 miss 발생 */
		if (rand() % 2) {
			printf("Cache Miss for key: %s\n", RecvMsg.key);
			RecvMsg.type = CACHE_MISS; // 메세지 타입 CAHCE_MISS
		}
		else {
			printf("Cache Hit for key: %s\n", RecvMsg.key);
			strcpy(RecvMsg.value, "CACHECACHECACHE"); // value 값 반환
			RecvMsg.type = READ_REP; // 메세지 타입 READ_REP
		}

		sendto(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, sizeof(src_addr)); // 소켓 송신
	}


	printf("\nCtrl+C pressed. Exit the program after closing the socket\n");
	close(sock);

	return 0;
}

- server.c

#include "util.h"

int SERVER_PORT; // 서버 포트번호
char* kv[DATASET_SIZE]; // 정적 key value stores
void init_kvs(){
  for(int i =0;i<DATASET_SIZE;i++){
		kv[i] = malloc(VALUE_SIZE);
		strcpy(kv[i], "AAAABBBBCCCCDDD");
		//printf("%s\n",kv[i]);
	}

}

static volatile int quit = 0; // Trigger conditions for SIGINT
void signal_handler(int signum) {
	if(signum == SIGINT){  // Functions for Ctrl+C (SIGINT)
		quit = 1;
	}
}

int main(int argc, char *argv[]) {
	// 프로그램 시작시 입력받은 매개변수를 parsing한다.
	if ( argc < 2 ){
	 printf("Input : %s port number\n", argv[0]);
	 return 1;
	}

	signal(SIGINT, signal_handler); // SIGINT에 대한 핸들러 등록

	SERVER_PORT = atoi(argv[1]); // 입력받은 argument를 포트번호 변수에 넣어준다.

	// 서버의 정보를 담을 소켓 구조체 생성 및 초기화
	struct sockaddr_in srv_addr;
	memset(&srv_addr, 0, sizeof(srv_addr));
	srv_addr.sin_family = AF_INET;
	srv_addr.sin_port = htons(SERVER_PORT);
	srv_addr.sin_addr.s_addr = htonl(INADDR_ANY); // 0.0.0.0 i.e., 자기 자신의 IP

	// 소켓을 생성한다.
	int sock;
	if ((sock = socket(AF_INET, SOCK_DGRAM, 0)) < 0) {
		printf("Could not create listen socket\n");
		exit(1);
	}

	// 생성한 소켓에 소켓구조체를 bind시킨다.
	if ((bind(sock, (struct sockaddr *)&srv_addr, sizeof(srv_addr))) < 0) {
		printf("Could not bind socket\n");
		exit(1);
	}

	init_kvs(); // key-value store 초기화

	int n = 0;
  struct KVS RecvMsg={0,}; // 수신용으로 쓸 메시지 구조체 생성 및 초기화

	struct sockaddr_in src_addr; // 패킷을 수신하였을 때, 해당 패킷을 보낸 송신자(Source)의 정보를 저장하기 위한 소켓 구조체
  socklen_t src_addr_len = sizeof(src_addr);
	size_t pkt_size = 0;
	while (!quit) {
		recvfrom(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, &src_addr_len); // 메시지 수신

		int index = hash64(RecvMsg.key) % DATASET_SIZE; // key값으로 index 참조
		strcpy(RecvMsg.value, kv[index]); // KVS 참조해 value 리턴
		RecvMsg.type = READ_REP; // 메세지 타입 READ_REP로 변환
		printf("Type: %s Key: %s Value: %s\n", get_type(RecvMsg), RecvMsg.key, RecvMsg.value); // 출력

		sendto(sock, &RecvMsg, sizeof(RecvMsg), 0, (struct sockaddr*)&src_addr, sizeof(src_addr)); // 메세지 송신
	}

	printf("\nCtrl+C pressed. Exit the program after closing the socket\n");
	close(sock);

	return 0;
}

'코딩 > 분산시스템 프로젝트' 카테고리의 다른 글

5) Primary-backup 구현하기 (0)	2024.06.01
4) Power of two choices 로드 밸런싱 구현하기 (0)	2024.05.24
2) Distributed key-value stores 구현하기 (0)	2024.05.17
1) UDP Echo 프로그램 만들기 (0)	2024.05.17

북극성

3) Look-aside cache 구현하기

'코딩 > 분산시스템 프로젝트' 카테고리의 다른 글

티스토리툴바

3) Look-aside cache 구현하기

'코딩 > 분산시스템 프로젝트' 카테고리의 다른 글

'코딩/분산시스템 프로젝트' Related Articles

티스토리툴바