# 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 ![](https://i.imgur.com/1SmTRW0.png =500x) 以上是示意圖，Coarse-Grained(粗質)的意思是，整個資料結構共享一個 lock，例如圖中綠色的 CPU(或是thread)要修改其中的某個node，就要把整個資料結構都 lock 住，但這會導致平行化毫無意義，因為其他的 thread 要等這個 thread 所有操作完成才能再操作。 #### Fine-grained Locking ![](https://i.imgur.com/PUD9Kce.png =600x) 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)
Last changed by  
 
蔡宇軒
1507
Published on HackMD