
ํค์๋: djb2 ํด์, ํด์โฏ+โฏ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ(LRU), ReaderโWriter Lock, MAX_CACHE_SIZE, MAX_OBJECT_SIZE
1. ์ ๋ณ๋์ ์บ์๊ฐ ํ์ํ๊ฐ?
- ํ๋ก์ ์๋ฒ์์ ์ธ๋ฉ๋ชจ๋ฆฌ ์บ์ฑ์ด๋? ๋์ผ ๊ฐ์ฒด ์ฌ์์ฒญ ์, ์ค๋ฆฌ์ง ์๋ฒ๋ฅผ ๊ฑฐ์น์ง ์๊ณ ๋ฐ๋ก ๋ฉ๋ชจ๋ฆฌ์์ ์ ๊ณตํ๋ ๊ฒ์ ๋๋ค.
- ์ ํฌ ์ด๋ฒ 8์ฃผ์ฐจ ์น ํ๋ก์ ๋ฉ์ ์บ์ฑ ๋ถ๋ถ์ ์๊ตฌ์กฐ๊ฑด์ ์๋์ ๊ฐ์ต๋๋ค.
- ์ธ๋ฉ๋ชจ๋ฆฌ๋ก ๋ค์ค ์ฝ๊ธฐ, ๋จ์ผ ์ฐ๊ธฐ ๋ณด์ฅ → ์ฌ์ค์ ๋ฉํฐ์ค๋ ๋ฉ ๊ตฌํ์ด ๊ฐ์
- LRU ์ ์ฑ ์ผ๋ก ๊ฐ์ฅ ์ค๋๋ (๋๋ ์ง์ ๋ ์ฉ๋์ ๋ง์ถ ๋๊น์ง) ๊ฐ์ฒด ์๋ ํด์ถ
- ์ ๊ฐ์ธ์ ์ผ๋ก ๋ชฉํํ์๋ ์ถ๊ฐ ์กฐ๊ฑด์ ์๋์ ๊ฐ์ต๋๋ค.
- ๊ท๋ชจ๊ฐ ์ปค์ ธ๋ ๋น ๋ฅธ ์๋ต์ ๋ณด์ฅํ๊ธฐ ์ํด O(1) ํ์
- ์๋ต ํค๋๊น์ง ํต์งธ๋ก ์บ์ (์ฌ์ ์ก ์ ์์ ๋์ผํ ์๋ต ๊ฐ๋ฅํ๋๋ก)
์ผ๋ฐ์ ์ธ ํ์ต์ ์ํ ์์ค์์๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ์ ๋๋ก ์บ์๋ฅผ ๊ตฌํํ ์ ์๊ฒ ์ง๋ง, O(1) ํ์์ ์ํด์๋ ๊ฒฐ๊ตญ ๋ฆฌ์คํธ๋ง์ผ๋ก๋ ์ด๋ ต๋ค๋ ๊ฒฐ๋ก ์ ๋ค๋ค๋์ต๋๋ค.
2. ์ djb2 ํด์ + ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ธ๊ฐ?
O(1)์ ์์ธ์ ์ํด์๋ ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก๋ ์๋ฉ๋๋ค. ์๋ํ๋ฉด URI ์กฐํ ์ ์์์๋ถํฐ ์ ํ ํ์์ด ๋ถ๊ฐํผํ๊ธฐ ๋๋ฌธ์ ๋๋ค. ๊ฒฐ๊ตญ ๋ด๋ฆฐ ๊ฒฐ๋ก ์, ๋ฐ๋ก, URI ์์ธ์๋ ํด์ํ ์ด๋ธ์ ์ด์ฉํ๊ณ , LRU ์ ์ฑ ์ enforce์๋ ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ด์ฉํ๋ ๊ฒ์ ๋๋ค.
3์ ๋น๊ต: ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ vs. ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ vs. ํด์ ๊ฒฐํฉ ๊ตฌ์กฐ
๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ | ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ | ํด์ ํ ์ด๋ธ + ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ | |
URI ํ์ ์๋ | O(n) (์ ํ ํ์) | O(n) (์ ํ ํ์) | O(1) |
์์ ๋ ธ๋ ์ถ๊ฐ | O(n) (์ด์ ๋ ธ๋ ์ถ์ ํ์) | O(1) | O(1) |
์์ ๋ ธ๋ ์ ๊ฑฐ | O(n) (์ด์ ๋ ธ๋ ์ถ์ ํ์) | O(1) | O(1) |
LRU ์ ๋ฐ์ดํธ (1๊ฑด) | O(n) | O(1) | O(1) |
๋ฉ๋ชจ๋ฆฌ ์ค๋ฒํค๋ | ๋ฎ์ | ์ค๊ฐ | ๋์ (prev + next + ํด์ ์ฒด์ด๋) |
๊ตฌ์กฐ ๋ณต์ก๋ | ๋งค์ฐ ๋จ์ | ๋จ์ | ์ค๊ฐ ์ด์ |
ํด์ ์ถฉ๋ ์ฒ๋ฆฌ | N/A | N/A | ์ฒด์ด๋ (h_next) ์ฌ์ฉ |
์ ํฉํ ์ฌ์ฉ์ฒ | ํ์ต, ํ ์คํธ, ์๋ฒ ๋๋ ๋ฑ | ์ค์ ๊ท๋ชจ ์บ์ | ์์ฒ ๊ฑด ์ด์์ ๊ณ ์ฑ๋ฅ ์บ์ |
๋ณด์๋ค์ํผ ํด์ ํ ์ด๋ธ + ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์์ธ, ์ถ๊ฐ, ์ ๊ฑฐ, LRU ์กฐ์ ์ ๋ถ O(1)์ ๋๋ฉ๋๋ค.
3. ์ ์ญ ์บ์ ๊ตฌ์กฐ์ฒด ๊ฐ์
ํฌ์คํธ ์๋จ ๊ทธ๋ฆผ์ ๋ค์ ์ฐธ๊ณ ํ ์ ์์ต๋๋ค.
#define HASH_SIZE 9029
typedef struct cache_entry {
char uri[MAXLINE]; // Key
char content*; // Value - malloc()๋ก ํ ๋นํ์ฌ ์ฌ์ฉํ ๊ฒ!
int size; // Value์ ์ฌ์ด์ฆ
struct cache_entry* prev; // LRU์ prev
struct cache_entry* next; // LRU์ next
struct cache_entry* hnext; // ํด์ ๋ฒํท์ next (ํด์ ์ถฉ๋ ๋์)
} cache_entry_t;
typedef struct {
cache_entry_t* head; // ๊ฐ์ฅ ์ต๊ทผ(R)
cache_entry_t* tail; // ๊ฐ์ฅ ์ค๋๋(L)
cache_entry_t* table[HASH_SIZE]; // ํด์ ๋ฒํท
size_t total_bytes;
pthread_rwlock_t lock;
} cache_t;
3.1. cache_entry_t - ๊ฐ๋ณ ์บ์ ํญ๋ชฉ ๊ตฌ์กฐ
cache_entry_t๋ ํ๋์ URI์ ํด๋นํ๋ ์ฝํ ์ธ ๊ฐ์ฒด๋ฅผ ์ ์ฅํ๋ ๊ตฌ์กฐ์ฒด๋ก, URI์ content๋ฅผ key-value ํํ๋ก ๋ณด๊ดํ ์ ์์ต๋๋ค. ์ด์ ๋ํด prev ๋ฐ next๋ LRU ๋ฆฌ์คํธ ๋ด ์์น๋ฅผ ํํํฉ๋๋ค. ์ต๊ทผ ์ฌ์ฉ๋ ํญ๋ชฉ์ ๋ฆฌ์คํธ์ ์(head)์ผ๋ก ์ด๋ํ๊ณ , ์ค๋๋ ํญ๋ชฉ์ ๋ค(tail)๋ก ๋ฐ๋ ค๋๊ฒ ๋ฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ผ๋ก ํด์ ๋ฒํท์์ ์ถฉ๋์ด ๋ฐ์ํ์ ๋, ๊ฐ์ ์ธ๋ฑ์ค์ ์ํธ๋ฆฌ๋ค์ ๋จ์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ๋ฌถ๊ธฐ ์ํ hnext ํฌ์ธํฐ๊ฐ ์์ต๋๋ค. ์ด ๋๋ถ์ ํ๋์ ํด์ ์ฌ๋กฏ์ ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ ํํ๋ก ์ฌ๋ฌ ํญ๋ชฉ์ด ๋ค์ด์ฌ ์ ์๊ณ , ํด์ ์ถฉ๋์ ๋์ํ๊ฒ ๋ฉ๋๋ค.
3.2. cache_t - ์ ์ญ ์บ์ ์ปจํธ๋กค๋ฌ ๊ตฌ์กฐ
cache_t๋ ์ ์ฒด ์บ์ ์์คํ ์ ํต์ ํ๋ ์ปจํธ๋กค ๊ตฌ์กฐ์ฒด์ ๋๋ค. table[HASH_SIZE]๋ ํด์ ํ ์ด๋ธ๋ก, ๊ฐ ์ฌ๋กฏ์๋ cache_entry_t*๊ฐ ๋ค์ด๊ฐ๋ฉฐ, ์ ์ธ๊ธํ ๋ฐ์ ๊ฐ์ด ์ถฉ๋ ์ hnext ์ฒด์ด๋์ผ๋ก ์ด์ด์ง๋๋ค. HASH_SIZE๋ ํด์ ์ถฉ๋์ ์ค์ด๊ธฐ ์ํด ์์(็ด ๆฐ)๋ก ์ก๋ ๊ฒ์ด ์ผ๋ฐ์ ์ด๋ฉฐ, ํ ์คํธ ๋ชฉ์ ์ผ๋ก ์์ ๊ฐ์ ๋ฃ์ ์๋ ์์ต๋๋ค. ์ฌ์ง์ด 1๋ ๊ฐ๋ฅํฉ๋๋ค.
๊ตฌ์ฑ์์ | ์์ธ |
---|---|
ํด์ ํ ์ด๋ธ | ํค→์ํธ๋ฆฌ๋ก์ O(1) ํ์ (์๋) |
table[HASH_SIZE] | ํด์ ํ
์ด๋ธ. ์ด๋, table[i]๋ ํด์๊ฐ์ด i์ธ URI๋ค์ ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ์ด์ด์ฃผ๋ ์ฒด์ธ์ ์์์ ์ ๊ฐ๋ฆฌํค๋ฉฐ, ๊ฐ๊ฐ์ cache_entry_t*๋ก ์ฐ๊ฒฐ๋จ. ์ถฉ๋ ์ hnext๋ฅผ ๋ฐ๋ผ ์ด์ด์ง (=ํด์ ์ฒด์ด๋). |
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ | LRU ์ญ์ & “moveโtoโfront”๋ฅผ O(1)๋ก |
hnext | ๊ฐ์ ๋ฒํท ๋ด ์ฒด์ด๋ (ํด์ ์ถฉ๋ ๋์) |
RWโLock | ๋์์ฑ ๋ณด์ฅ์ ์ํ ์บ์ ์กฐํ ์ rdlock, ์ฝ์ /์ญ์ ์ wrlock |
4. djb2 ํด์ ์๊ณ ๋ฆฌ์ฆ
static int hash_uri(const char *uri) {
unsigned int hash = 5381;
for (int c = *uri++; c; c = *uri++)
hash = ((hash << 5) + hash) + c; // hash * 33 + c
return hash % HASH_SIZE;
}
- ๊ฐ๊ฒฐ + ๋ถ์ฐ์ฑ ๋ชจ๋ ํ๋ณด → ์ค๋ฒํค๋๊ฐ ํฌ์ง ์์ผ๋ฉฐ ์์ ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
- HASH_SIZE๋ฅผ ์์๋ก ์ก์ ๊ณฑ์ ํด์์ ๋ถํฌ์ฑ์ ๊ทน๋ํํ ์ ์์ต๋๋ค.
- ๋ฌธ์์ด์ด ๊ธด ๊ฒฝ์ฐ์๋ ํด์ ๊ฒฐ๊ณผ์ ํธ์ค์ด ์ ์ด ๊ณ ๋ฅด๊ฒ ๋ฒํท์ ๋ถํฌ๋๋ ํน์ง์ ๊ฐ์ง๋๋ค.
4.1. ์ฑ๋ฅ
hash_uri() ์์ฒด๋ URI์ ๊ธธ์ด์ ์ํ์ฌ O(n)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ค. ๋ค๋ง, ์๋์ ๊ฐ์ด ์ํ์๊ฐ ์์ฒด๊ฐ ์๋ ์งง์ ๋ฟ๋๋ฌ ์บ์๋ ํญ๋ชฉ์์๋ ๋ฌด๊ดํ๋ค๋ ์ ์์ O(1)๋ก ๊ฐ์ฃผ๋ ์ ์์ต๋๋ค. ์๋๋ ๊ฐ๊ฐ 1์, 1000์์ ๋๋คํ ๋ฌธ์์ด์ ๋ฃ์ด 1๋ฐฑ๋ง ํ ํด์๊ฐ์ ๊ณ์ฐํ์ ๋์ ์ํ ์๊ฐ์ ๋๋ค.
1000์์ ๋ฌธ์์ด์ 1๋ฐฑ๋ง ํ ์ํ ์๊ฐ์ด ์ฝ 670 ms๋ผ๋ฉด, 1ํ๋น ์ํ ์๊ฐ์ 0.00067 ms (=0.67 μs)๋ก ๋ณผ ์ ์์ต๋๋ค.
5. ์บ์ ์ฐ์ฐ ํ๋ฆ
5.1. ์กฐํ (cache_get)
cache_get(uri)
โโ> rdlock ์ฒด๊ฒฐ
โโ> ํด์ ๋ฒํท ํ์ (O(1)) → hnext ์ฒด์ด๋
โโ> Miss → ์๋ฒ ์ฐ๊ฒฐ → ์๋ต → rdlock ํด์ → ํจ์ ๋ง์นจ
โโ> Hit? → rdlock ํด์ → wrlock ์ฒด๊ฒฐ → move_to_front() → wrlock ํด์ → ํจ์ ๋ง์นจ
- Reader lock์ด๊ธฐ์ ์ฌ๋ฌ ํด๋ผ์ด์ธํธ๊ฐ ๋์์ ์กฐํํด๋ ๋ฌด๋ฐฉํฉ๋๋ค.
- ๋จ, move_to_front๋ ์ฐ๊ธฐ ์ฐ์ฐ์ด๋ผ wrlock์ผ๋ก ์น๊ฒฉ๋ฉ๋๋ค (์ด ๊ณผ์ ์์ ๋ฝ ์น๊ฒฉ์ผ๋ก ์ธํ ๋ ์ด์ค ์ปจ๋์ ๋์ฒ ํ์).
- ์บ์ ๋ฏธ์ค ์ ์๋ฒ ์ฐ๊ฒฐ์ ํตํด ์๋ต์ ๋ฐ์์ cache_put๋ฅผ ํธ์ถํฉ๋๋ค.
5.2. ์ฝ์ (cache_put)
cache_put(uri, content)
โโ> wrlock ํ๋
โโ> ํด์ ํ
์ด๋ธ์์ URI ์กด์ฌ ํ์ธ (O(1))
โโ> ํ์์ LRU tail์์ evict (O(1))
โโ> ์ entry๋ฅผ malloc๋ก ์์ฑ → ํด์ ๋ฒํท ๋งจ์ ๋ฐ ๋ฆฌ์คํธ head์ ์ฝ์
โโ> total_bytes ์
๋ฐ์ดํธ
โโ> wrlock ํด์
- ์ฝ์ ์ ์ ์ฒด ๊ณผ์ ์ wrlock์ ์ฒด๊ฒฐํ ์ฑ ์ํ๋ฉ๋๋ค.
6. ๋ง์น๋ฉฐ
- djb2 ํด์ ํ ์ด๋ธ๋ก ํ์ ์๋๋ฅผ, ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก LRU ์ ์ฑ ์ ์ฉ์ ํจ์จ์ฑ์ ๊พํ์์ต๋๋ค.
- ์ค์ ์์๋ ์บ์ ๋ง๋ฃ ์๊ฐ(TTL), ์์ถ ์ ์ก ๋ฑ์ ๋์๋ ํ์ํ๋ฉฐ, ์บ์ ํํธ/๋ฏธ์ค๋ฅผ ๋ก๊น ํ์ฌ ๋ฉํธ๋ฆญ์ผ๋ก ๋ถ์์ ํตํด ์ฑ๋ฅ ํฅ์์ ๊พํ ์ ์์ ๊ฒ์ ๋๋ค.
- ์ด๋ฌํ LRU ์บ์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์น ํ๋ก์ ๊ณผ์ ์ ์ ์ฉํ์ฌ ์๋์ ๊ฐ์ด ์ ์ ํ ๊ฒฐ๊ณผ๋ฅผ ๋ฌ์ฑํ์์ต๋๋ค.
7. ๊ตฌํ ์์
์์๋๋ก cache.h ๋ฐ cache.c์ ๋๋ค.
#ifndef __CACHE_H__
#define __CACHE_H__
#include "csapp.h"
#include <signal.h>
#include <assert.h>
#define MAX_CACHE_SIZE (1<<20) // 1๋ฉ๊ฐ
#define MAX_OBJECT_SIZE (100<<10) // 100ํฌ๋ก
// #define HASH_SIZE 9029 // ์ค์ฌ์ฉ ์๋ ํฐ ์ซ์
#define HASH_SIZE 13 // ์์๋ก ์ถฉ๋ ์ต์ํ
#define HASH_VAL 5381l // djb2 ์๊ณ ๋ฆฌ์ฆ ์ต์ ํ ๊ฐ
// ํ๋์ ์บ์ ๊ฐ์ฒด
typedef struct cache_entry {
char uri[MAXLINE]; // ์บ์๋ ์์ฒญ URI (key)
char* content; // ์ค์ ๋ฐ์ดํฐ ==> ์ฌ๊ธฐ์ malloc()ํ์ฌ ์ธ ๊ฒ.
int content_length;
struct cache_entry* prev; // LRU ์ด์ ๋
ธ๋
struct cache_entry* next; // LRU ๋ค์ ๋
ธ๋
struct cache_entry* h_next; // ํด์ ํ
์ด๋ธ ๋ด ์ฒด์ด๋
} cache_entry_t;
// ์บ์ ์ ์ฒด ๊ตฌ์กฐ
typedef struct {
cache_entry_t* head; // LRU ๋ฆฌ์คํธ์ head (๊ฐ์ฅ ์ต๊ทผ)
cache_entry_t* tail; // LRU ๋ฆฌ์คํธ์ tail (๊ฐ์ฅ ์ค๋๋จ)
cache_entry_t* hashtable[HASH_SIZE]; // ํด์ ๋ฒํท ==> ์ด ์ฌ์ด์ฆ ๋๋ฌธ์ ์คํ๋ฉ๋ชจ๋ฆฌ์ ๋ฃ์ง ๋ง ๊ฒ!!
size_t total_cached_bytes; // ํ์ฌ ์ด ์บ์๋ ๋ฐ์ดํธ ์
pthread_rwlock_t ptrwlock; // ๋์ ์ ๊ทผ ์ ์ด (read-write lock)
} cache_t;
// === ์บ์ ๊ด๋ จ API ===
void cache_init(cache_t* cache);
void cache_deinit(cache_t* cache); // ์บ์ ์ ์ฒด์ ๋ฉ๋ชจ๋ฆฌ ํด์
cache_entry_t* cache_lookup(cache_t* cache, const char* uri, const int use_lock, const int update_lru); // O(1) ํ์ - TODO: pthread_rwlock_unlock() ์ด๋์ ํ ์ง ๋์ค์ ๊ฒฐ์ ํ ๊ฒ!
void cache_insert_unmanaged(cache_t* cache, const char* uri, const char* buf, int size); // ์ฝ์
void cache_evict_policy_unmanaged(cache_t* cache, int required_size); // ํ์์ LRU ์ ๊ฑฐ
inline int cache_size(cache_t* cache); // ํ์ฌ ์ด ์บ์ ๋ฐ์ดํธ ์
void cache_remove(cache_t* cache, const char* uri); // ๋ช
์์ ์ญ์ - URI๋ก
void cache_remove_by_entry_unmanaged(cache_t* cache, cache_entry_t* entry); // ๋ช
์์ ์ญ์ - cache_entry_t๋ก
void debug_print_cache(cache_t* cache); // LRU ์์๋๋ก ์ถ๋ ฅ (๋๋ฒ๊น
)
// ์ดํ ํจ์๋ค์ ์ฃผ์์ cache.c ์ฐธ์กฐ.
int cache_get(cache_t *cache, const char *uri, char *buf_out, int *size_out);
void cache_put(cache_t *cache, const char *uri, const char *buf, int size);
#endif /* __CACHE_H__ */
#include "csapp.h"
#include "cache.h"
#include <pthread.h>
/* ์ ์ญ ์ํ */
// (๋น)
/* ์ ํธ๋ถ */
/**
* hash_uri - djb2 ์๊ณ ๋ฆฌ์ฆ์ผ๋ก intํ ํด์๊ฐ ๋ฐํ
* ์ถ์ฒ: https://stackoverflow.com/questions/64699597/how-to-write-djb2-hashing-function-in-c
*/
static int hash_uri(const char* uri) {
unsigned long hash = HASH_VAL;
for (int c = *uri++; c != '\0'; c = *uri++)
hash = ((hash << 5) + hash) + c;
return hash % HASH_SIZE;
}
/**
* move_to_front - ํด๋น ์บ์๋ฅผ ๋งจ ์์ผ๋ก
* ์ค์! ๋ฝ์ ์ฌ๊ธฐ์ ๊ด๋ฆฌ๋์ง ์์!
*/
static void move_to_front_unmanaged(cache_t* cache, cache_entry_t* entry) {
// ์ผ๋ฆฌ ๋ฆฌํด - ์ด๋ฏธ ๋งจ ์์ด๋ฉด
if (cache->head == entry)
return;
// 1. ๊ธฐ์กด ์์น์์ entry ์ ๊ฑฐ
if (entry->prev)
entry->prev->next = entry->next;
else
cache->head = entry->next;
if (entry->next)
entry->next->prev = entry->prev;
else
cache->tail = entry->prev;
// 2. entry๋ฅผ head๋ก ์ฝ์
entry->prev = NULL;
entry->next = cache->head;
if (cache->head)
cache->head->prev = entry;
cache->head = entry;
if (cache->tail == NULL)// ๋ฆฌ์คํธ์ ์๋ฌด๊ฒ๋ ์๋ค
cache->tail = entry;
}
/**
* evict_lru - ํด๋น ์บ์๋ฅผ ํด์ถ
* ์ค์! ๋ฝ์ ์ฌ๊ธฐ์ ๊ด๋ฆฌ๋์ง ์์!
*/
static void evict_lru_unmanaged(cache_t* cache) {
cache_entry_t* entry = cache->tail;
if (entry)
cache_remove_by_entry_unmanaged(cache, entry);
}
/* ๊ตฌํ๋ถ */
/**
* cache_init - ์บ์ ์ ์ฒด ์ฒด๊ณ ์ด๊ธฐํ
*/
void cache_init(cache_t* cache) {
cache->head = NULL;
cache->tail = NULL;
cache->total_cached_bytes = 0;
memset(cache->hashtable, 0, sizeof(cache->hashtable)); // ํด๋น ํฌ์ธํฐ์์ sizeof(cache->hashtable)๋งํผ์ 0(NULL)๋ก ์ด๊ธฐํ.
pthread_rwlock_init(&cache->ptrwlock, NULL);
}
/**
* cache_deinit - ์บ์ ์ ์ฒด ์ฒด๊ณ ๋ง์ (๋ฝ ํฌํจ)
*/
void cache_deinit(cache_t *cache) {
pthread_rwlock_wrlock(&cache->ptrwlock);
cache_entry_t *curr = cache->head;
while (curr) {
cache_entry_t *next = curr->next;
free(curr->content);
free(curr);
curr = next;
}
cache->head = NULL;
cache->tail = NULL;
cache->total_cached_bytes = 0;
memset(cache->hashtable, 0, sizeof(cache->hashtable));
pthread_rwlock_unlock(&cache->ptrwlock);
pthread_rwlock_destroy(&cache->ptrwlock);
}
/**
* cache_get - ์บ์์์ URI์ ํด๋นํ๋ ๊ฐ์ฒด๋ฅผ ์ฐพ๊ณ , ์กด์ฌํ ๊ฒฝ์ฐ buf_out์ ๋ณต์ฌํจ
* ๋ด๋ถ์ ์ผ๋ก ๋ฝ์ ํ๋ํ๋ฉฐ, LRU ์
๋ฐ์ดํธ๋ ์ํํจ.
*
* @param uri ์์ฒญํ URI
* @param buf_out ์บ์๋ ์ฝํ
์ธ ๊ฐ ๋ณต์ฌ๋ ๋ฒํผ
* @param size_out ์ฝํ
์ธ ๊ธธ์ด
* @return ์ฑ๊ณต(1), ์คํจ(0)
*/
int cache_get(cache_t *cache, const char *uri, char *buf_out, int *size_out){
cache_entry_t* entry;
// Read lock์ผ๋ก lookup๋ง ์งํ
pthread_rwlock_rdlock(&cache->ptrwlock);
entry = cache_lookup(cache, uri, 0, 0); // NO internal lock, NO LRU ์
๋ฐ์ดํธ.
if (!entry) {
pthread_rwlock_unlock(&cache->ptrwlock);
return 0;
}
// ์ฝํ
์ธ ๋ณต์ฌ
memcpy(buf_out, entry->content, entry->content_length);
*size_out = entry->content_length;
pthread_rwlock_unlock(&cache->ptrwlock);
// LRU ์ด๋์ ๋ณ๋์ wrlock์์ ์ํ
// ๋ฝ ์น๊ฒฉ ๋ฌธ์ ๋ ์์ง๋ง, rdlockํด์ →wrlockํ๋ ์ด ์ฌ์ด์ ๋ด์ฉ์ด ๋ฐ๋๋ฉด ๋ฌธ์ ์์ง๋ ์์
pthread_rwlock_wrlock(&cache->ptrwlock);
move_to_front_unmanaged(cache, entry);
pthread_rwlock_unlock(&cache->ptrwlock);
return 1; // ์ฐพ์ผ๋ฉด 1
}
int cache_get_v1(cache_t *cache, const char *uri, char *buf_out, int *size_out){
pthread_rwlock_wrlock(&cache->ptrwlock);
cache_entry_t* entry = cache_lookup(cache, uri, 0, 0); // LRU ์
๋ฐ์ดํธ๋ cache_get์์ ์ง์ .
int result = 0; // 1 ์ฐพ์; 0 ์์.
if(entry){
memcpy(buf_out, entry->content, entry->content_length);
*size_out = entry->content_length;
move_to_front_unmanaged(cache, entry);
result = 1;
}
pthread_rwlock_unlock(&cache->ptrwlock);
return result;
}
/**
* cache_put - ์บ์์ ์ ๊ฐ์ฒด ์ ์ฅ
* ๋ด๋ถ์์ ์ง์ ์ฝ๊ธฐ ๋ฝ ์ฌ์ฉ!
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param uri: ์์ฒญ URI (key)
* @param buf: ์๋ต ๋ณธ๋ฌธ (payload)
* @param size: ์๋ต ๋ณธ๋ฌธ ํฌ๊ธฐ
* @return void
*/
void cache_put(cache_t *cache, const char *uri, const char *buf, int size) {
if (size > MAX_OBJECT_SIZE)
return;
pthread_rwlock_wrlock(&cache->ptrwlock);
cache_insert_unmanaged(cache, uri, buf, size);
pthread_rwlock_unlock(&cache->ptrwlock);
}
/**
* cache_insert_unmanaged - buf๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ์ ์บ์ ์์ฑ, ๋ฆฌ์คํธ ๊ฐฑ์
* ์ค์! ๋ฐ๋์ ์ธ๋ถ์์ ๋ฝ ๊ด๋ฆฌ!
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param uri: ์์ฒญ URI (key)
* @param buf: ์๋ต ๋ณธ๋ฌธ (payload)
* @param size: ์๋ต ๋ณธ๋ฌธ ํฌ๊ธฐ
* @return void
*/
void cache_insert_unmanaged(cache_t* cache, const char* uri, const char* buf, int size){
// ์ผ๋ฆฌ ๋ฆฌํด - ์ฌ์ด์ฆ ๋ง๋ ๊ฒฝ์ฐ๋ง
if (size > MAX_OBJECT_SIZE)
return;
// ์ด์ ๊บผ ์์ผ๋ฉด ์ญ์
cache_entry_t* entry = cache_lookup(cache, uri, 0, 0);
if (entry != NULL){
cache_remove_by_entry_unmanaged(cache, entry);
entry = NULL;
}
// ํด์ถ ์ ์ฑ
cache_evict_policy_unmanaged(cache, size);
// ์ ๊ฐ์ฒด ์์ฑ
cache_entry_t* new_entry = Malloc(sizeof(cache_entry_t));
strcpy(new_entry->uri, uri);
new_entry->content = Malloc(size);
memcpy(new_entry->content, buf, size);
new_entry->content_length = size;
new_entry->prev = NULL;
new_entry->next = NULL;
new_entry->h_next = NULL;
// ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ
new_entry->next = cache->head;
if (cache->head)
cache->head->prev = new_entry;
cache->head = new_entry;
if (cache->tail == NULL)
cache->tail = new_entry;
// ํด์ ํ
์ด๋ธ ์ฒด์ด๋
int hashed_index = hash_uri(uri);
new_entry->h_next = cache->hashtable[hashed_index];
cache->hashtable[hashed_index] = new_entry;
// ์ฌ์ด์ฆ
cache->total_cached_bytes += size;
}
/**
* cache_remove_by_entry_unmanaged - entry๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ํด๋น ์บ์ ๊ฐ์ฒด๋ฅผ ์ ๊ฑฐ
* ์ค์! ๋ฐ๋์ ์ธ๋ถ์์ ๋ฝ ๊ด๋ฆฌ!
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param entry: ํด๋น ์บ์ ๊ฐ์ฒด์ ํฌ์ธํฐ
* @return void
*/
void cache_remove_by_entry_unmanaged(cache_t* cache, cache_entry_t* entry){
assert(entry != NULL);
// ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ์ ๊ฑฐ
if (entry->prev)
entry->prev->next = entry->next;
else
cache->head = entry->next;
if (entry->next)
entry->next->prev = entry->prev;
else
cache->tail = entry->prev;
// ํด์ ์ฒด์ด๋(๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ)์์ ์ ๊ฑฐ
int hashed_index = hash_uri(entry->uri);
cache_entry_t* curr = cache->hashtable[hashed_index];
cache_entry_t* prev = NULL;
while(curr){
if(curr == entry){
if (prev)
prev->h_next = curr->h_next;
else
cache->hashtable[hashed_index] = curr->h_next;
break;
}
prev = curr;
curr = curr->h_next;
}
cache->total_cached_bytes -= entry->content_length;
free(entry->content);
free(entry);
}
/**
* cache_lookup - uri ๊ธฐ๋ฐ์ผ๋ก ์บ์์์ ํ์
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param uri: ์์ฒญ URI (key)์ ํฌ์ธํฐ
* @param internal_lock: internal_lock 1์ด๋ฉด ๋ฝ์ ๋ด๋ถ์์ ๊ด๋ฆฌ. 0์ด๋ฉด ์ธ๋ถ์์ ๊ด๋ฆฌ.
* @param update_lru: update_lru 1์ด๋ฉด LRU ์
๋ฐ์ดํธ, 0์ด๋ฉด ์ํจ. (cache_insert์์๋ ์ด๊ฑธ ์ฐ๋๋ฐ ๊ฑฐ๊ธฐ์ LRU ์
๋ฐ์ดํธ๋ฅผ ์ ํ๊ฒ ๋?)
* @return void
*/
cache_entry_t* cache_lookup(cache_t* cache, const char* uri, const int internal_lock, const int update_lru){
if (internal_lock)
pthread_rwlock_wrlock(&cache->ptrwlock);
// ํด์๊ฐ ๊ตฌํจ ==> ํด์ ํ
์ด๋ธ ==> ํด์ ์ฒด์ด๋ ์์.
cache_entry_t* entry = cache->hashtable[hash_uri(uri)];
while (entry && strcmp(entry->uri, uri) != 0) // ํด์ ์ฒด์ด๋์ ๋๊น์ง - entry๊ฐ NULL์ฌ๋ ํ์ถ
entry = entry->h_next;
// ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ prev/next๋ ํด์ ์ฒด์ด๋ ๋ฆฌ์คํธ์ ์ฌ์ค์ ๋ณ๊ฐ๋ก ์๋.
if (entry && update_lru)
move_to_front_unmanaged(cache, entry);
if (internal_lock)
pthread_rwlock_unlock(&cache->ptrwlock);
return entry;
}
/**
* cache_remove - uri ๊ธฐ๋ฐ์ผ๋ก ์บ์์์ ์ ๊ฑฐ
* ๋ฝ์ ๋ด๋ถ์์ ์ง์ ๊ด๋ฆฌ!
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param uri: ์์ฒญ URI (key)์ ํฌ์ธํฐ
*/
void cache_remove(cache_t* cache, const char* uri) {
pthread_rwlock_wrlock(&cache->ptrwlock);
cache_entry_t* entry = cache->hashtable[hash_uri(uri)];
while (entry && strcmp(entry->uri, uri) != 0)
entry = entry->h_next;
if (entry != NULL)
cache_remove_by_entry_unmanaged(cache, entry);
pthread_rwlock_unlock(&cache->ptrwlock);
}
/**
* cache_evict_policy_unmanaged - ์ ์ฑ
๊ธฐ๋ฐ์ผ๋ก ํด์ถ
* ์ค์! ์๋ ๋ฝ์ ๊ด๋ฆฌํ์ง ์์!
*
* @param cache: ์บ์ ํฌ์ธํฐ
* @param required_size: ์ง๊ธ ๋ฃ์ผ๋ ค๋ ํฌ๊ธฐ
*/
void cache_evict_policy_unmanaged(cache_t* cache, int required_size) {
while (cache->total_cached_bytes + required_size >= MAX_CACHE_SIZE){
if (cache->tail == NULL) break; // ์บ์๊ฐ ๋น์๋๋ฐ๋ ๊ณต๊ฐ์ด ๋ถ์กฑํ ๊ฒฝ์ฐ
evict_lru_unmanaged(cache);
}
}
/**
* cache_size - ์บ์ ํฌ๊ธฐ
*
* @param cache: ์บ์ ํฌ์ธํฐ
*/
inline int cache_size(cache_t* cache){
return cache->total_cached_bytes;
}
/**
* debug_print_cache - ๋๋ฒ๊น
ํจ์
*
* @param cache: ์บ์ ํฌ์ธํฐ
*/
void debug_print_cache(cache_t* cache) {
pthread_rwlock_rdlock(&cache->ptrwlock);
printf("====== Cache Current State ======\n");
printf("Total cached bytes: %zu\n", cache->total_cached_bytes);
cache_entry_t* curr = cache->head;
while (curr != NULL) {
printf("URI: %-60s | Size: %d bytes\n", curr->uri, curr->content_length);
curr = curr->next;
}
printf("========== End of Cache =========\n");
pthread_rwlock_unlock(&cache->ptrwlock);
}
8. ์คํ: ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ vs. ํด์ ํ ์ด๋ธ + ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ
๊ฐ๋จํ ์น์๋ฒ์ ์์ ๊ฐ์ด 15-30 KB์ ํ์ผ์ 51๊ฐ ๋ฐฐ์น (์ด 1.1MB)ํ์ฌ ์ด๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ์บ์ ์ฑ๋ฅ์ ์ธก์ ํ์์ต๋๋ค. LRU ์ ์ฑ ์งํ์ ์ํด ์บ์ ์ ์ฒด ์ฉ๋์ 1 MB๋ก ์ก์์ต๋๋ค. ํด์ ๋ฒํท์ ์ฌ์ด์ฆ๋ 13์ ๋๋ค.
์๋ '๋๋ณด๊ธฐ'๋ ์คํ์ ์ฌ์ฉ๋ Python ์คํฌ๋ฆฝํธ๋ก, 1ํ๋น 50๊ฐ์ ๋ฌด์์ ๋ฆฌํ์คํธ๋ฅผ ํ๋ก์์ ์ก์ ํฉ๋๋ค. ์ด๋ฅผ 10ํ ๋ฐ๋ณตํ์ฌ ๊ฐ ํ๋น ์ํ์๊ฐ๊ณผ ์ ์ฒด ์ํ์๊ฐ์ ์ธก์ ํฉ๋๋ค.
#!/usr/bin/python3
import requests
import time
import random
# ์ค์
PROXY_ADDR = "http://localhost:49877" # Web proxy server ์ฃผ์
TINY_SERVER_ADDR = "http://localhost:49876" # Tiny Web Server ์ฃผ์
TEST_FILES = [f"a{num:02d}.smi" for num in range(1, 101)] # a01.smi ~ a100.smi
REQUESTS_PER_ITER = 50
NUM_ITERATIONS = 10
def fetch_via_proxy(filename):
url = f"{TINY_SERVER_ADDR}/{filename}"
proxies = {"http": PROXY_ADDR, "https": PROXY_ADDR}
start = time.perf_counter()
try:
response = requests.get(url, proxies=proxies)
elapsed = time.perf_counter() - start
status = response.status_code
except Exception as e:
elapsed = -1
status = f"ERR({e})"
return elapsed, status
def run_random_requests():
print(f"{'Iteration':<10} {'Time (s)':>10}")
overall_start = time.perf_counter()
for it in range(1, NUM_ITERATIONS + 1):
iter_start = time.perf_counter()
for _ in range(REQUESTS_PER_ITER):
fname = random.choice(TEST_FILES)
elapsed, status = fetch_via_proxy(fname)
if status == 404:
continue # 404๋ ์คํต
iter_time = time.perf_counter() - iter_start
print(f"{it:<10} {iter_time:>10.5f}")
total_time = time.perf_counter() - overall_start
print(f"\n{'Total':<10} {total_time:>10.5f}")
if __name__ == "__main__":
run_random_requests()
์ํ ๊ฒฐ๊ณผ๋ ์๋์ ๊ฐ์ต๋๋ค.
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๊ธฐ๋ฐ ์บ์ | ํด์ ํ ์ด๋ธ + ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ ๊ธฐ๋ฐ ์บ์ |
frk2@frks2:~/webproxy-lab/tiny/cache_test$ ./bench.py Iteration Time (s) 1 0.09251 2 0.07936 3 0.07183 4 0.08544 5 0.07964 6 0.07714 7 0.06997 8 0.07782 9 0.07047 10 0.06802 Total 0.77245 |
frk2@frks2:~/webproxy-lab/tiny/cache_test$ ./bench.py Iteration Time (s) 1 0.08368 2 0.06967 3 0.06667 4 0.06375 5 0.06676 6 0.06346 7 0.05940 8 0.05956 9 0.06615 10 0.06116 Total 0.66050 |
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๊ตฌ์กฐ๊ฐ ์ฝ 0.77์ด, ๊ทธ๋ฆฌ๊ณ ํด์ ํ ์ด๋ธ์ ์ ์ฉํ ๊ตฌ์กฐ๊ฐ ์ฝ 0.66์ด์ ์ํ์๊ฐ์ ๋ณด์์ต๋๋ค (๊ธฐ์กด ๋๋น 86%).
'IT > ๊ธฐํ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
SF UI Display ํฐํธ (OTF) (0) | 2025.05.11 |
---|---|
Ubuntu์ APT๋ก Firefox Developer Edition ์ค์น (0) | 2025.05.10 |
C์ธ์ด๋ก ํ์ฑํ๊ธฐ (0) | 2025.05.07 |
Pintos ์๋ฃ ์ทจํฉ (0) | 2025.04.22 |
WSLg Ubuntu 24.04.1 LTS์์ GUI ์ฐฝ์ด ๋จ์ง ์๊ฑฐ๋ ์ฅ์๊ฐ ๊ธฐ๋ค๋ ค์ผ๋ง ๋ฐ ๋ (0) | 2025.04.16 |
์๋์ฐ 11 "์ฐฝ์ ๋๋๊ทธํ ๋๋ง๋ค ์์ ๋ญ ๋จ๋ ๊ทธ๊ฑฐ" ๋นํ์ฑํํ๊ธฐ (0) | 2025.04.04 |
์๋์ฐ 11 ๋ ธํธ๋ถ ์ฝํ์ผ๋ฟ ํค ๋นํ์ฑํ/๋์ฒดํ๊ธฐ (0) | 2025.02.19 |
์๋ ํ์ธ์.
ํฌ์คํ ์ด ์ข์๋ค๋ฉด "์ข์์โค๏ธ" ๋๋ "๊ตฌ๋ ๐๐ป" ํด์ฃผ์ธ์!