# Concurrent and Rapid Dictionary
contributed by <`f74034067`>, <`catpig1630`>, <`rex662624`>, <`e94046165`>
## 預期目標
* 基於 [prefix search](https://hackmd.io/giJnGUwMQGqS9bNcLcF1Lw)，導入 Bloom Filter ，實作快速字串搜尋機制。如果字串根本不存在於資料庫中，我們根本不需走訪 ternary search tree;
* 需要支援多個 thread ，讓多個使用者能同時查字典;
* 注意處理某個使用者新增 word 的同時其他使用者也要可以同時搜尋;
## 何謂 Bloom Filter
當我們要在大量的資料中搜尋一個字串時，最簡單的方式就是每一個走過一次，這樣時間複雜度會是 O(n) 。
而 Bloom Filter 就是利用一個 n bits 的 table ，不走訪資料結構就能透過這個 table 預測字串是不是在這個資料結構內。而這樣時間複雜度就變為了 O(1)。
這樣的應用其實很常見。例如在社群網站 facebook ，在搜尋欄鍵入名字時，能夠在20億註冊用戶中很快的找到結果，甚至是根據與使用者的關聯度排序。
### 實作方式
首先，建立一個 n bits 的 table，並將每個 bit 初始化為 0。
我們所有的字串 set 表示為 S = {x~1~ ,x~2~ ,x~3~...,x~n~ }， Bloom Filter 會使用 k 個不同的 hash function，每個 hash function 轉換後的範圍都是 0 ~ n-1 (為了能夠對應上面建立的 n bits table)。而對每個 S 內的 element x~i~，都需要經過 k 個 hash function ，一一轉換成 k 個 index。轉換過後，table 上的這 k 個 index 的值就必須設定為 1。(注意到所以這裡可能會有同一個 index 被多次設定為 1 的狀況)
Bloom Filter 這樣的機制，是會有錯誤機率的。若今天想要找一個字串 x 在不在 S 中，這樣的資料結構只能保證某個 x~1~ 一定不在 S中，但沒辦法 100% 確定某個 x~2~一定在 S 中。因為會有誤判( false positive )的可能。
此外，資料只能夠新增，而不能夠刪除，試想今天有兩個 string x~1~ , x~2~經過某個 hash function h~i~ 轉換後的結果 h~i~(x~1~)=h~i~(x~2~) ，若今天要刪除x~1~ 而把 table 中 set 的 1 改為 0，豈不是連 x~2~ 都受到影響了 ?
### 錯誤率計算
首先假設我們的所有字串 set S 裡面有 n 個字串， hash 總共有 k 個，Bloom Filter 的 table 總共 m bits。我們會判斷一個字串存在於 S 內，是看經過轉換後的每個 bits 都被 set 了，我們就會說可能這個字串在 S 內。但試想若是其實這個字串不在 S 內，但是其他的 a b c 等等字串經過轉換後的 index ，剛好把我們的目標字串轉換後的 index 包含了，就造成了誤判這個字串在 S 內的情況。
如剛剛所述，Bloom Filter 有錯誤機率，而我們開發程式時可能必須把錯誤機率回報給使用者，因此以下將證明錯誤率公式。
當我們把 S 內的所有字串，每一個由 k 個 hash 轉換成 index 並把 table[index] 設為 1，而全部轉完後， table 中某個 bits 仍然是 0 的機率是 $(1-\dfrac{1}{m})^{kn}$ 。
其中$(1-\dfrac{1}{m})$是每次 hash 轉換後，table 的某個 bits 仍然是 0 的機率 。因為我們把 hash 轉換後到每個 index (而這個 index 會被 set )的機率視為相等(每人$\dfrac{1}{m}$)，所以用 1 減掉即為不會被 set 的機率。我們總共需要做 kn 次 hash，所以就得到答案$(1-\dfrac{1}{m})^{kn}$ 。
由$(1-\dfrac{1}{m})^{m}≈e^{-1}$特性，$(1-\dfrac{1}{m})^{kn}=((1-\dfrac{1}{m})^{m})^{\frac{kn}{m}}≈(e^{-1})^{\frac{kn}{m}}≈e^{-\frac{kn}{m}}$
以上為全部的字串轉完後某個 bit 還沒有被 set 的機率。
因此誤判的機率=全部經由 k 個 hash 轉完後的 k bit 已經被其他人 set 的機率:
轉完後某個 bit 被 set機率 : $1-e^{-\frac{kn}{m}}$，因此某 k bit 被 set機率 : ==$(1-e^{-\frac{kn}{m}})^k$==
### 如何選參數值( k (多少個不同 hash )、 m ( table size 的大小))
**如何選 k 值(要多少個不同hash):**
我們必須讓錯誤率是最小值，因此必須讓$(1-e^{-\frac{kn}{m}})^k$的值是最小。先把原式改寫成$(e^{k\ ln(1-e^{-\frac{kn}{m}})})$，我們只要使${k\ ln(1-e^{-\frac{kn}{m}})}$最小，原式就是最小值。可以看出當 $e^{-\frac{kn}{m}}=\dfrac{1}{2}$ 時，會達到最小值。因此 ==$k=ln2\dfrac{m}{n}$== 即能達到最小值。
[Bloom Filter calculator](https://hur.st/bloomfilter/?n=5000&p=3&m=&k=45)、[Bloom Filter calculator 2](https://krisives.github.io/bloom-calculator/) 這兩個網站可以透過設定自己要的錯誤率與資料的多寡，得到 k 和 m 值。
### 在 prefix search 導入 bloom filter 機制
[這是暫時找到的 dictionary file](https://stackoverflow.com/questions/4456446/dictionary-text-file)，裡面總共有36922個詞彙 **(太小，後面必須找更大的詞彙集，否則推測難以體現效能)**。透過上面的網址知道當我們容許5%錯誤(0.05)時，table size=230217，k=4。
看懂[ bloom filter c code ](http://sircmpwn.github.io/2016/04/12/How-to-write-a-better-bloom-filter-in-C.html)，並試著導入原來程式。並先用原來的 cities.txt 檔案做測試以評估正確性。
首先，這裡選用了兩種 hash ，`jenkins` 和`djb2`，另外 murmur3 hash 也是一個不錯的選擇，這裡主要是選用夠 uniform 的即可。
```clike=
unsigned int djb2(const void *_str)
{
const char *str = _str;
unsigned int hash = 5381;
char c;
while ((c = *str++)) {
hash = ((hash << 5) + hash) + c;
}
return hash;
}
unsigned int jenkins(const void *_str)
{
const char *key = _str;
unsigned int hash=0;
while (*key) {
hash += *key;
hash += (hash << 10);
hash ^= (hash >> 6);
key++;
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
```
再來宣告我們的 Bloom filter 主體，這裡是用一個 structure 包住，裡面共有三個元素：
`func` 是用來把我們的 hash function 做成一個 list 串起來，使用這個方法的用意是方便擴充。若我們今天要加進第三個 hash function，只要串進 list ，後面在實做時就會走訪 list 內的所有 function。
`bits` 是我們的 filter 主體，也就是 table 。 size 則是 table 的大小。
```clike=
typedef unsigned int (*hash_function)(const void *data);//宣告成function pointer形式
typedef struct bloom_filter * bloom_t;
struct bloom_hash {
hash_function func;
struct bloom_hash *next;
};
struct bloom_filter {
struct bloom_hash *func;
void *bits;
size_t size;
};
```
以下是 bloom filter 實做主體，以下是主要的程式碼：
首先在 `bloom_create` 的部份，可以看到我們把兩個 hash function 透過`bloom_add_hash` 加入了結構中。
再來 `bloom_add` 裡面是透過對目標字串 `item` 套用 hash ，並把 hash 產生的結果 module size (第20行)，這樣才會符合 table size 。最後第21行把產生的 bit 設定為 1 。
最後`bloom_test`就是去檢驗使用者輸入的 `item` 是不是在結構當中。與 add大致上都相等，只是把 bit 設定為1的部份改為檢驗是不是 1，若是任一個 bit 不是 1 ，我們就可以說這個結構裡面沒有這個字串。
這樣的實做，讓我們可以在 bloom_create 初始化完，接下來要加入字串就呼叫 bloom_add ，要檢驗字串就呼叫 bloom_test，不需要其他的操作。
```clike=
bloom_t bloom_create(size_t size)
{
bloom_t res = calloc(1, sizeof(struct bloom_filter));
res->size = size;
res->bits = malloc(size);
//加入hash function
bloom_add_hash(res, djb2);
bloom_add_hash(res, jenkins);
return res;
}
void bloom_add(bloom_t filter, const void *item)
{
struct bloom_hash *h = filter->func;
uint8_t *bits = filter->bits;
while (h) {
unsigned int hash = h->func(item);
hash %= filter->size;
bits[hash] = 1 ;
h = h->next;
}
}
bool bloom_test(bloom_t filter, const void *item)
{
struct bloom_hash *h = filter->func;
uint8_t *bits = filter->bits;
while (h) {
unsigned int hash = h->func(item);
hash %= filter->size ;
if (!(bits[hash])) {
return false;
}
h = h->next;
}
return true;
}
```
再來是 main 改的部份(這裡是去修改 test_ref.c檔案):
這裡需要改的地方是 add 和 find 功能 (雖然 delete 其實會失去效用，如同文內`何謂 Bloom Filter`-`實做方式`所說，但程式碼並未刪除。)
首先 find 功能修改：
```clike=
...
t1 = tvgetf();
//用bloom filter去判斷是否在 tree 內
if (bloom_test(bloom,word)==1) {
//version1:bloom filter偵測到在裡面就不走下去了
t2 = tvgetf();
printf(" Bloomfilter found %s in %.6f sec.\n",word, t2 - t1);
printf(" Probability of false positives:%lf\n",pow(1 - exp(-(double)HashNumber /(double) ((double)TableSize /(double) idx)), HashNumber));
// version2:bloom filter偵測到在裡面,就去走tree(防止偵測錯誤)
t1 = tvgetf();
res = tst_search(root, word);
t2 = tvgetf();
if(res)
printf(" ----------\n Tree found %s in %.6f sec.\n", (char *) res, t2- t1);
else
printf(" ----------\n %s not found by tree.\n", word);
} else
printf(" %s not found by bloom filter.\n", word);
break;
```
由以上程式碼可以看到，第11行會先用 bloom filter 去判斷是否在結構內，如果不在的話就不用走訪，直接進入 else 部份。如果在的話，我先印出 bloom filter 找到的時間，還有錯誤機率，然後真的去走訪看是不是在 tree 裡面。
而根據我的參數是 TableSize 5000000(五百萬)，hashNumber=2(總共兩個hash)，及用原來的 cities 數量為 259112 ，算出來(理論上)錯誤率約為 0.009693 ，也就是不到 1%。
以下是 add 的部份：
```clike=
...
/* FIXME: insert reference to each string */
if(bloom_test(bloom,Top)==1)//已經被filter偵測存在，不要走tree
res=NULL;
else//否則就去走訪tree加入,並加入bloom filter
{
bloom_add(bloom,Top);
res = tst_ins_del(&root, &p, INS, REF);
}
t2 = tvgetf();
if (res) {
idx++;
Top += (strlen(Top) + 1);
printf(" %s - inserted in %.10f sec. (%d words in tree)\n",(char *) res, t2 - t1, idx);
} else
printf(" %s - already exists in list.\n", (char *) res);
if(argc>1 && strcmp(argv[1],"--bench")==0)//a for auto
goto quit;
break;
```
以上程式碼可以看到，第3行的部份會先偵測要加入的字串是否在結構中，若是回傳 1 表示 bloom filter 偵測在結構中，已經重複了。因此會把 res 設為 null，這樣下方第12行的判斷自然就不會成立。如果偵測字串不在結構中，會跑進第5行的 else 加入結構還有 bloom filter 當中。
至此，基本 bloom filter 已經導入完畢。
## 導入 multi-threading
因為我們要支援多個使用者可以執行不同功能，所以我想必須要把程式分成 Server 端和 Client 端，一次開一個 Server ，就可以支援不同的 Client 連上。
首先主要的程式運作模式是，先開啟一個 server 程式，然後 server會透過 socket 去監聽有沒有 client 要來連，若是連上了，server 就用 thread 去服務這個 client ，然後 main thread 繼續監聽有沒有 client 。
因為所有 thread ，共享程式的 heap 部份，所以要查詢的資料存在 global variable ，讓所有 thread 共同存取。細部的功能部份，是透過 send 和 recv 一問一答，例如 server 去問 client 要什麼加入什麼字串，client 就回答。
以下將逐步講解程式碼：
### 用 Socket 讓 Server 能夠服務多個 Client
首先，我們讓 Server 和每個 Client ，透過 Socket 相連通訊。
#### Server 端
首先以下程式碼是在 Server 中，設定好 Socket 的 IP 、Port 等初始化動作。
```clike=
sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd == -1) {
printf("Fail to create a socket.");
}
//socket的連線
//提供socket訊息
struct sockaddr_in serverInfo,clientInfo;
socklen_t addrlen = sizeof(clientInfo);
bzero(&serverInfo,sizeof(serverInfo));//初始化
serverInfo.sin_family = PF_INET;//sockaddr_in為Ipv4結構
serverInfo.sin_addr.s_addr = inet_addr("127.0.0.1");//IP
serverInfo.sin_port = htons(59487);//port
//綁定server在socket上
bind(sockfd,(struct sockaddr *)&serverInfo,sizeof(serverInfo));
```
再來，放一個`while(1)`表示 main thread 不斷監聽有沒有 Client 要連上，第3行的 `listen()` 就是去查看有沒有 Client要連結上。
在第20行的部分用`accept()`，就會去真的接受這個 Client ，這裡把回傳的值儲存於`forClientSockfd`中，因為每個 Client 都有自己的通話管線，這裡就好像是管線的編號一樣，想傳訊息給這個 Client 就要透過這個 Socket 。
最後連上這個 Client 之後，就建立一個新 thread ，進去`thread_function()`中做各自的操作。並在第30行用 `thread_join` 表示等所有人做完再結束。(但是這裡其實是執行不到，因為 main thread 會不斷在 while 中監聽有沒有 client 要連，直到使用者按 ctrl+c )。
```clike=
while(1) {
//監聽有沒有client來
listen(sockfd,10000);
//增加新的client,要把舊的data移到新allocate的地方
int temp[num];
pthread_t ptemp[num];
int i;
for(i=0; i<num; i++) {
temp[i]=forClientSockfd[i];//先用temp存放剛剛的
ptemp[i]=thread[i];
}
//重新allocate array(記得把num+1)
forClientSockfd = malloc(sizeof(int)*(num+1));
thread = malloc(sizeof(pthread_t)*(num+1));
for(i=0; i<num; i++) {
forClientSockfd[i]=temp[i];//還原剛剛備份的data
thread[i]=ptemp[i];
}
forClientSockfd[num] = accept(sockfd,(struct sockaddr*)&clientInfo,&addrlen);
int ptr = num;
if(pthread_create( &(thread[num]), NULL, thread_function,(void*)&ptr)!=0) {
printf("thread create failed");
}
threadid=thread[num];
num++;
}
pthread_join(threadid,NULL);
```
#### Client 端
Client 的部分就比較簡單，只要設定好之後，用 `connect()` 連上 Server即可。
```clike=
sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd == -1) {
printf("Fail to create a socket.");
}
//連線socket
struct sockaddr_in info;
bzero(&info,sizeof(info));
info.sin_family = PF_INET;
info.sin_addr.s_addr = inet_addr("127.0.0.1");
info.sin_port = htons(59487);
int err = connect(sockfd,(struct sockaddr *)&info,sizeof(info));
if(err==-1) {
printf("Connection error");
}
```
### 2.Multi-thread
上面 Client 連上 Server 之後，Server 會建立新的 Thread 去服務這個 Client，然後 Main thread 會繼續在 while 迴圈內看有沒有 Client 要連上。
以下演示 find 功能的運作，其他功能的設計都大同小異。
#### Server 端
以下是於 thread function 內的部分程式碼，也就是每個服務 Client 的新 thread 各自都要做以下的事，與 Client 做對答。
首先，將所有動作包在 while 裡面，每一輪 while 代表著一次完整的動作。第6行會先把上面2~5行要問 client 的問題傳送給他。然後第7行接收 client 要求作的選項。
例如 client 要做 f 選項，就會進到第11行。然後第14行 Server 再傳問題問 Client 要 find 什麼字串並在下一行接收。之後下面的動作就是做 Bloom filter 版本的 find ，並把結果回傳給Client。
```clike=
while(1) {
sprintf(message,"%s","\nCommands:\na add word to the \
tree\nf find word in tree\ns search words matching \
prefix\nd delete word from the tree\nq quit, \
freeing all data\n\nchoice: ");
send(forClientSockfd[localindex],message,sizeof(message),0);//把上面的message傳給client
recv(forClientSockfd[localindex],inputBuffer,sizeof(inputBuffer),0);//receive client 要執行什麼選項
...省略
else if(strcmp(inputBuffer,"f")==0) {
char word[WRDMAX] = "";
sprintf(message,"%s","find word in tree:");
send(forClientSockfd[localindex],message,sizeof(message),0);
recv(forClientSockfd[localindex],inputBuffer,sizeof(inputBuffer),0);//從client拿到要找的word
printf("Get from thread %d :%s\n",localindex,inputBuffer);
sprintf(word,"%s",inputBuffer);
rmcrlf(word);
t1 = tvgetf();
//用bloom filter去判斷是否在 tree 內
if (bloom_test(bloom,word)==1) {//如果bloom filter有找到
//version1:bloom filter偵測到在裡面就不走下去了
t2 = tvgetf();
sprintf(message," Bloomfilter found %s in %.6f sec.\n Probability of false positives:%lf\n" \
,word, t2 - t1,pow(1 - exp(-(double)HashNumber /(double) ((double)TableSize /(double) idx)), HashNumber));
// version2:bloom filter偵測到在裡面,就去走tree(防止偵測錯誤)
t1 = tvgetf();
res = tst_search(root, word);
t2 = tvgetf();
if(res) { //如果bloom filter有找到且tree也有找到
//這裡因為要把字串收集在char * message裡面,所以用strcat串起來
char * temp =malloc(128);
sprintf(temp," ----------\n Tree found %s in %.6f sec.\n", (char *) res, t2- t1);
strcat(message,temp);
free(temp);
} else { //如果bloom filter有找到但是tree沒有找到
char * temp =malloc(128);
sprintf(temp," ----------\n %s not found by tree.\n", word);
strcat(message,temp);
free(temp);
}
//把字串收集好後一次傳送，以免大量傳送造成的i/o負擔
send(forClientSockfd[localindex],message,sizeof(message),0);
} else { //bloom filter沒找到
sprintf(message," %s not found by bloom filter.\n", word);
send(forClientSockfd[localindex],message,sizeof(message),0);
}
}
```
#### Client 端
Client 端的部分，也是在 while 迴圈裏面繞，每一輪 while 就代表一次完整的對答，也就表示了做完一次完整的工作。
例如首先第2行會先接到 Server 詢問要做什麼指令，若這次我要做 find 指令，就會在第6行回答 server，server 這時就會回要 find 什麼字串(第16行接收 server 問題，並在第17行印出)。第19行就會回答 server 要加入的字串， server 做完一連串 find 動作後，Client 就會接收結果並印出來(第20 21行)。
```clike=
while(1) {
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//先接到要求的訊息
printf("%s",receiveMessage);
scanf(" %s",message);
send(sockfd,message,sizeof(message),0);//送出request
if(strcmp(message,"a")==0) {//如果自己送出的request==a
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收add what word?
printf("%s\n",receiveMessage);
scanf(" %s",message);
send(sockfd,message,sizeof(message),0);//送出要add什麼字
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收是否add成功
printf("%s\n",receiveMessage);
} else if (strcmp(message,"f")==0) {
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);
printf("%s\n",receiveMessage);
scanf(" %s",message);
send(sockfd,message,sizeof(message),0);//送出要find什麼字
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收find結果
printf("%s\n",receiveMessage);
}
```
## 將本來的城市檔案改成字典檔
### 程式開發
這個部份需要做的改動是，在 client 用 find option，也就是找特定的字時，輸出有沒有找到這個字，如果有找到要連解釋一起輸出。另外也要改 add option ，改成加入字串的同時，也要鍵入這個字串的解釋。其他部份就不用改變。
讀檔時，把單字和解釋分開存，單字用 ternary tree 存，解釋用 array 儲存，而 ternary tree 的 leaf 會儲存這個單字解釋的index
```clike=
while (fgets(line,1024,fp) != NULL) {
if(line[0] == '\n')
continue;
//單字存入Top,解釋存入array
sscanf(line, "%s %[^\t\n]", Top, explain[count]);
char *p = Top;
/* insert reference to each string */
//把array的index傳入做ternary tree的function裡
if (!tst_ins_del(&root, &p, INS, REF,count)) {//沒有insert成功
fprintf(stderr, "error: memory exhausted, tst_insert.\n");
fclose(fp);
return 1;
} else { //有insert 進資料結構，因此也要加入bloom filter
bloom_add(bloom,Top);
}
//完成一個單字index+1
count ++;
idx++;
Top += (strlen(Top) + 1);
}
```
find 單字時用一個全域變數儲存 find 的單字解釋的 index ，然後再一起把單字和解釋 send 給 client 端
```clike=
void *tst_search(const tst_node *p, const char *s)
{
const tst_node *curr = p;
while (curr) { /* loop over each char in 's' */
int diff = *s - curr->key; /* calculate the difference */
if (diff == 0) { /* handle the equal case */
if (*s == 0){ /* if *s = curr->key = nul-char, 's' found */
explain_index = curr->index; /*儲存單字解釋的index
return (void *) curr->eqkid; /* return pointer to 's' */
}
s++;
curr = curr->eqkid;
} else if (diff < 0) /* handle the less than case */
curr = curr->lokid;
else
curr = curr->hikid; /* handle the greater than case */
}
return NULL;
}
```
``` clike=
sprintf(temp," ----------\n Tree found %s in %.6f sec.\n%s\n%s\n", (char *) res, t2- t1,(char *) res,explain[explain_index]);
strcat(message,temp);
```
至於 add option 是 client 端先傳送單字到 server 端，接下來等 user 打完解釋後把解釋送到 server 端
``` clike=
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收add what word?
printf("%s\n",receiveMessage);
scanf(" %s",message);
send(sockfd,message,sizeof(message),0);//送出要add什麼字
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收what is it's explanation?
printf("%s\n",receiveMessage);
scanf(" %[^\t\n]",message);
send(sockfd,message,sizeof(message),0);//送出字的解釋
recv(sockfd,receiveMessage,sizeof(receiveMessage),0);//接收是否add成功
printf("%s\n",receiveMessage);
```
至於 server 就是把接收到的單字存到 ternary tree 中，而解釋存到 array 中
### sizeof(pointer) v.s. sizeof(array)
在這裡我們忽略掉了一個基本的概念:
我們在傳送訊息時，是用 `send(forClientSockfd[localindex],message,sizeof(message),0);`，這裡的第二個和第三個 argument 分別是儲存訊息的字串，後面接的是要傳送出去的 byte 大小。
但我們發現最多只能傳出 8 byte 的訊息，是因為我們用 `char* message = malloc(1024);`來宣告，而 sizeof(message) ，就會是這個指標所佔的記憶體大小，也就是 8 byte。解決方式就是把宣告方式變成 `char message[1024]`。
這裡設計實驗釐清一下概念，考慮以下程式碼:
```clike=
#include <stdio.h>
#include <stdlib.h>
struct str {
int a; int b; int c; int d; int e;
};
int main(void)
{
int * x = malloc(sizeof(int)*2);
int y[2];
printf("sizeof(x): %d\n", sizeof(x));
printf("sizeof(y): %d\n", sizeof(y));
printf("sizeof(*x): %d\n", sizeof(*x));
printf("sizeof(*y): %d\n", sizeof(*y));
printf("---------------\n");
struct str *a = malloc(sizeof(struct str)*2);
struct str b[2];
printf("sizeof(a): %d\n", sizeof(a));
printf("sizeof(b): %d\n", sizeof(b));
printf("sizeof(*a): %d\n", sizeof(*a));
printf("sizeof(*b): %d\n", sizeof(*b));
return 0;
}
```
output:
```
sizeof(x): 8
sizeof(y): 8
sizeof(*x): 4
sizeof(*y): 4
---------------
sizeof(a): 8
sizeof(b): 40
sizeof(*a): 20
sizeof(*b): 20
```
首先 `sizeof(x)` 和 `sizeof(a)` 不難理解，是 pointer 的大小，也就是一個address，8byte。`sizeof(y)` 和 `sizeof(b)` ，因為他們是 array，所以是整個array 的記憶體大小。
接下來 `sizeof(*a)` 和 `sizeof(*x)`，會是指標指向的記憶體區塊之第一個 item 之型態大小。前者的第一個元素是一個 20 byte 的 structure ，而後者是一個 int(4Byte)。
最後 `sizeof(*b)` 和 `sizeof(*y)` ，也會是第一個元素大小，分別是 20 和 4 byte 。
## thread safe
### 程式開發
因為有些 thread 會寫資訊進結構，有些 thread 會從結構中讀資料出來，要達成 thread safe 就要對資料做一些保護，我們用到的是 read write lock。pthread 本身就已經有 read write lock的功能，以下將介紹呼叫方式與行為。
首先，在 pthread 用 read write lock 的方式是:
```clike=
pthread_rwlock_t tree_lock;
int main(int argc, char **argv)
{
pthread_rwlock_init(&tree_lock, NULL);
......
pthread_rwlock_wrlock(&tree_lock);
//這一行放要保護的資料結構
pthread_rwlock_unlock(&tree_lock);
......
pthread_rwlock_rdlock(&bloom_lock);
//這一行放要保護的資料結構
pthread_rwlock_unlock(&bloom_lock);
```
首先第一行是宣告 lock ，在第五行做初始化，然後第7行如果要用 write lock ，就要呼叫`pthread_rwlock_wrlock()`。若是要用 read lock ，就要呼叫`pthread_rwlock_rdlock()`。
而 read write lock 的行為是: 如果有 writer 要寫入資料到資料結構，就要用 write lock 鎖住，這時候任何其他 thread 都不能再進來使用這個資料結構，因為若是其他 thread 再 access ，就可能有錯誤。而若是 reader 要寫入資料結構，所有的 writer 都不能進來使用，但是其他 reader 還是可以使用資料結構，因為他們只有讀值，對資料結構沒有寫入。
:::warning
參考 [Concurrent Hash Tables](https://parsa.epfl.ch/courses/cs206/slides/L09-Hashs.pdf)，提出正確的 read/write lock 機制
:notes: jserv
:::
### 不同的 lock 機制
#### Coarse-Grained Locking
以上是示意圖，Coarse-Grained(粗質)的意思是，整個資料結構共享一個 lock，例如圖中綠色的 CPU(或是thread)要修改其中的某個node，就要把整個資料結構都 lock 住，但這會導致平行化毫無意義，因為其他的 thread 要等這個 thread 所有操作完成才能再操作。
#### Fine-grained Locking
Fine-grained 就可以解決上面的問題，因為一個元素自己本身就用一個 lock(實作方法是把本來的資料結構多一個 lock 元素，每個 node 自己有專屬的lock)。如上圖，如果紅色的 thread 要用 node a 和 head 的話，就獲取他們兩個的lock就好，因此這樣藍色的 thread 如果還要對node c、node d 做操作，就不需要等紅色 thread 操作完。
#### Lock-free Lists
這種避免資料錯誤的方法，沒有用到 lock ，所有的 thread 還是能同時存取所有資料，但還是能保證資料正確。
一個典型的方法是: [CAS](https://en.wikipedia.org/wiki/Compare-and-swap)(compare-and-swap)
實作程式碼如下:
```clike=
bool compare_and_swap(int *accum, int *dest, int newval)
{
if (*accum == *dest) {
*dest = newval;
return true;
} else {
*accum = *dest;
return false;
}
}
......
//使用:
int accum =目前的 data//先備份一次，後來的備份都會在第7行的部分
while(！compare_and_swap(暫存的變數 address，要修改的 data address，修改後的值));
```
compare_and_swap() 的 parameter，accum 是備份的舊數據，dest 是要修改的數據位置，newval 是新值。
主要的概念為，當備份的舊 data，與要修改的 data 進行比較時，如果相等(進入第4行)，則證明共享數據沒有被修改，替換成新值，然後繼續往下運行。如果不相等(第7行)，說明共享數據已經被修改，放棄已經所做的操作，然後重新執行剛才的操作，這裡注意到第7行要重新備份舊值，下次再執行這個 function 才會是正確的。
這裡注意到 function 裡面都要是 atomic 做完，因為試想一個 thread1 通過 if，另一個 thread 也在這時通過 if(因為這時 thread1 還沒修改值)並把值修改了，然後 thread1 這時才修改值。就造成了 thread1 先進到 if， thread2 後來才進入，但是最後修改的卻是 thread1 。
## 目前程式已知問題：
1. **情境：** 如果 server 開啟後，有多個 client 連上的情況下，若是某一個 client 沒有正常用 q 離開而是直接用`ctrl+c`離開，則 server 也會直接關掉。就算再次打開 server 與 client ，client 都會 connect error。這個情況就算用 make clean 再重新 make 也無法解決。但是去加上一些無關緊要的 code ，例如在某行多加上一個分號，然後重新 make ，就可以恢復運作。(或是隔一段時間再開 server ?)
**解決方法：** 需要加上 signal handler 去改變 client 的 ctrl+C 行為，讓它可以先關掉 socket 再正常離開。
2. **情境：** 連續 send ，例如 server send 一次，沒有 receive動作就直接在 send 一次 ，會導致傳出去的字串有問題。
**解決方法：(已解決)** 在連續 send 中間加入一個 dummy 的 receive ，但應該要去找有什麼可以讓 socket buffer flush 的方式。
3. **情境：** prefix search 因為傳送的資料量可能會非常大(例如我們想找以 R 為開頭的所有字)，這樣要傳給 client 的 buffer size只設 1024 可能會不夠，但是宣告太大，例如測試過宣告 5120 的陣列，在 free 的時候會造成越界導致 core dumped 。不 free 又將會造成 memory leak 。
**解決方法：(已解決)**：分段傳送，buffer快滿時就先傳出去
1.server 端：在尋找字串的同時，在迴圈內同時加上`if(strlen(message)>999)`就去 send ，也就是快要超過 1024 時就先把目前累積的資料的傳出去，並把陣列清空重新累積，然後還要加上如果是找到最後一輪的話，就算沒有快超過 buffer 也要把資料傳出去。也就是變成`if(strlen(message)>999||i==sidx-1)`
2.client 端：用一個while迴圈一直接收訊息，如果不是接收到`"Server send over"`就繼續接收。所以相對的剛才的 server 要在迴圈跑完，找到所有的字串後送出`"Server send over"`。
4. **情境：** 發現本來 prefix search 程式就有的問題，如果要尋找以"A"為prefix的字串會 core dumped，這應該是因為有一個變數LMAX設成 1024 導致最多只能傳 suggest[0]~suggest[1023] 。
## 改進方向
* 比照 [linux-list](https://github.com/sysprog21/linux-list)，允許透過 `make check` 執行內建的 unit test 或 test suite
* 引入 stress test，檢驗各種邊界狀況
* 透過 [mutrace](https://github.com/leventov/mutrace) 一類的工具追蹤 lock contention: http://0pointer.de/blog/projects/mutrace.html
* client-server 程式需要檢查連線狀況並給予清楚的訊息 (如使用 `perror`)，當首度連線失敗時，client 可嘗試用 fork + execve 建立 server process 以重新連線
## reference
* [StarDict](http://ossacc.moe.edu.tw/uploads/datafile/ezgo7_win/ezgo_win/_stardict.html)
* [Bloom Filter 影片解說](https://www.youtube.com/watch?v=bEmBh1HtYrw)
* [Bloom Filter](https://blog.csdn.net/jiaomeng/article/details/1495500)
* [dictionary file 下載處](https://stackoverflow.com/questions/4456446/dictionary-text-file)
* [murmur3 hash](https://github.com/PeterScott/murmur3)
* [Jenkins' One-at-a-Time hash](https://stackoverflow.com/questions/114085/fast-string-hashing-algorithm-with-low-collision-rates-with-32-bit-integer)
* [sizeof](http://applezu.netdpi.net/2014/02/blog-post_22.html)
* [不同 read write lock 的圖片](http://fileadmin.cs.lth.se/cs/education/eda015f/2013/herlihy4-5-presentation.pdf)
Sign in with Wallet
Connect another wallet