時(shí)間格式

因?yàn)閤dag的文件存儲(chǔ)命名使用了時(shí)間戳，需要先描述時(shí)間戳的格式。

1. 時(shí)間戳

   xdag用的時(shí)間戳是一個(gè)64位的int值，分為兩部分。

   1. 尾部低10位

      表示秒以下的單位育灸，最小單位是1/1024秒，注意作者在這里用的是二進(jìn)制運(yùn)算昵宇，所以用1024去分割秒磅崭。

   2. 剩余的高54位

      UTC秒。注意瓦哎，實(shí)際中用不到54位砸喻。

2. 時(shí)間片

   xdag用64秒做為一個(gè)時(shí)間片，假設(shè)t為時(shí)間戳杭煎，則 t>>16 (先右移10位去秒恩够，再右移6位) 為時(shí)間片序號，代碼中每次取時(shí)間片都是用這種方式羡铲。

storage目錄結(jié)構(gòu)

一個(gè)典型的存儲(chǔ)目錄結(jié)構(gòu)：

image-20190819132213748.png

1. 文件命名

   除了0級目錄名固定為storage外蜂桶，1到3級目錄和block文件的命名均與時(shí)間戳有關(guān)。

   假設(shè)一個(gè)block的時(shí)間戳16進(jìn)制為：XX1-XX2-XX3-XX4-XX5-XX6-XX7-XX8也切，則這個(gè)block會(huì)被存儲(chǔ)在名為storage/XX1XX2XX3/XX4/XX5/XX6.dat的文件中扑媚，因?yàn)橥ǔ?code>XX1XX2都是0（目前秒的部分只需要32位就夠了腰湾，而這里實(shí)際有54位），所以我們看到的實(shí)際文件名路徑一般為storage/XX3/XX4/XX5/XX6.dat疆股，但是注意费坊，隨著時(shí)間的推移，1級目錄名出現(xiàn)XX1XX2XX3的形式是正確的旬痹。但在目前的代碼實(shí)現(xiàn)上附井，只允許出現(xiàn)XX3，不允許出現(xiàn)XX1XX2XX3两残，所以后續(xù)都假設(shè)只有XX3一種形式永毅。

2. 目錄存儲(chǔ)

   因?yàn)槲募拿玫氖且粋€(gè)字節(jié)的16進(jìn)制字符表示，所以理論上人弓，任何一個(gè)目錄下的子目錄或者文件個(gè)數(shù)沼死，最多只能有256個(gè)。文件名反映了對上級時(shí)間段的256分割崔赌。

   1. 3級目錄下的block文件意蛀，最多可以有256個(gè)，每個(gè)文件包含了一個(gè)時(shí)間片內(nèi)所有的block存儲(chǔ)（64秒內(nèi)）健芭。
   2. 1县钥、2、3級目錄中的目錄數(shù)吟榴，也是只能最多256個(gè)魁蒜。
   3. 0級目錄只有固定的一個(gè)storage囊扳。

block文件結(jié)構(gòu)

一個(gè)block文件（XX6.dat）吩翻，存儲(chǔ)了一個(gè)XX6時(shí)間片（64秒）內(nèi)所有收到的block，按順序把二進(jìn)制放進(jìn)去锥咸，個(gè)數(shù)不限狭瞎，理論上這個(gè)文件可以無限大（除了受到文件系統(tǒng)限制）。

格式：block1-struct-binary | block2-struct-binary | ... | blockN-struct-binary搏予。

sums文件

1. sums文件格式

   sums.dat存儲(chǔ)了當(dāng)前目錄下所有block（或者目錄）的數(shù)據(jù)摘要結(jié)果熊锭。

   sum文件固定為4K大小，文件被等分為256個(gè)部分雪侥，存儲(chǔ)當(dāng)前目錄下256個(gè)文件（目錄）各自的sum計(jì)算結(jié)果碗殷。每個(gè)等分16字節(jié)，等于struct xdag_storage_sum的大小速缨。

   struct xdag_storage_sum {
       uint64_t sum;   // 8字節(jié)
       uint64_t size;  // 8字節(jié)
   };
   

   每個(gè)block（目錄）在sum在文件中的存儲(chǔ)索引锌妻，就是block文件名的值（轉(zhuǎn)為十進(jìn)制后）。

   拿9d/sums.dat文件舉例旬牲，這個(gè)文件的第138等分處仿粹，存儲(chǔ)的是9d/8a.dat文件的sum計(jì)算結(jié)果（直接存儲(chǔ)了xdag_storage_sum結(jié)構(gòu)體）搁吓，因?yàn)?6進(jìn)制的8a等于十進(jìn)制的138。

2. sum計(jì)算方式

   每個(gè)位置實(shí)際存儲(chǔ)的就是xdag_storage_sum結(jié)構(gòu)體的二進(jìn)制內(nèi)容吭历，下面說明如何計(jì)算堕仔。

   以9d/8a.dat文件的sum計(jì)算舉例，在9d/sums.dat文件的第138個(gè)位置晌区，存儲(chǔ)了一個(gè)下面的結(jié)構(gòu)體摩骨。

   struct xdag_storage_sum {
       uint64_t sum;
       uint64_t size;
   };
   

   size：8a.dat文件中所有block的字節(jié)總和，實(shí)際上就是文件大小朗若，之所以這樣描述仿吞，是因?yàn)榇a是這樣寫的，這是直觀意圖捡偏，但不排除未來這兩者不再相等唤冈。

   sum：把block文件按照8字節(jié)分割，每個(gè)8字節(jié)作為一個(gè)64位int疊加到sum银伟，原始代碼：s.sum += ((uint64_t *)(buf + i))[j];你虹。這里的目的是為了做摘要后在多結(jié)點(diǎn)間對比數(shù)據(jù)差異，碰撞概率上比hash大彤避，有一定瑕疵傅物。

3. 1/2/3級目錄sum計(jì)算

   以3級目錄舉例，3級目錄中sums.dat文件中的存儲(chǔ)結(jié)構(gòu)與block目錄的sums.dat文件存儲(chǔ)模式一致琉预，只不過把block的位置換成了目錄的位置董饰。

   以9d目錄舉例，則6c/sums.dat文件中的第157位置存儲(chǔ)的是9d目錄的sum結(jié)果圆米，因?yàn)?6進(jìn)制9d等于十進(jìn)制157卒暂。

   9d目錄的xdag_storage_sum結(jié)構(gòu)體計(jì)算方法比較簡單，就是把9d/sums.dat中256個(gè)xdag_storage_sum結(jié)構(gòu)體的相同字段簡單求和娄帖。9d-xdag_storage_sum.size = sum(9d/sums.dat.size)也祠，sum字段類似。

   1近速、2級目錄的sum計(jì)算方法一樣诈嘿。