Gorrilla是Facebook在2015年在VLDB發(fā)表的論文Gorilla: A Fast, Scalable, In-Memory Time Series Database
中介紹的內(nèi)存型時(shí)序數(shù)據(jù)庫(kù)，并在github公布了其開(kāi)源實(shí)現(xiàn)Beringei。當(dāng)前最流行的時(shí)序數(shù)據(jù)庫(kù) InfluxDB的數(shù)據(jù)壓縮算法，也參考了 Gorrila的相關(guān)實(shí)現(xiàn)。

本文將以論文為主線，結(jié)合具體的開(kāi)源代碼實(shí)現(xiàn)淺析Gorrilla的設(shè)計(jì)。原論文闡述具體實(shí)現(xiàn)的章節(jié)包括Time series compression、In-memory data structures、On disk structures和Handling failures共4個(gè)小節(jié)，本文也將按照這個(gè)順序進(jìn)行展開(kāi)。

時(shí)序數(shù)據(jù)壓縮

數(shù)據(jù)格式

Gorrilla存儲(chǔ)的數(shù)據(jù)是一個(gè)三元組：字符串類(lèi)型的key，64bit的整形時(shí)間戳，雙精度的浮點(diǎn)數(shù)數(shù)值。每個(gè)時(shí)序數(shù)據(jù)點(diǎn)（又稱time series）由時(shí)間戳和當(dāng)時(shí)對(duì)應(yīng)的數(shù)據(jù)點(diǎn)值（在Gorrilla中稱為measurement）組成。利用時(shí)序數(shù)據(jù)點(diǎn)在時(shí)間軸上具備的較強(qiáng)相關(guān)性，可以實(shí)現(xiàn)較好的數(shù)據(jù)壓縮效果。針對(duì)整數(shù)類(lèi)型時(shí)間戳和浮點(diǎn)數(shù)類(lèi)型的值，Gorrilla采用了不同的壓縮算法。壓縮后的數(shù)據(jù)（包括時(shí)間戳和數(shù)據(jù)值）以block的形式組織，block包含的數(shù)據(jù)段按照時(shí)間范圍進(jìn)行劃分。

時(shí)間戳壓縮

block的header和第一個(gè)時(shí)序數(shù)據(jù)點(diǎn)
每個(gè)block的header存儲(chǔ)block完整的起始時(shí)間戳t_-1。每個(gè)block的對(duì)應(yīng)的時(shí)間窗口是2小時(shí)，其起始時(shí)間按照兩小時(shí)對(duì)齊；緊跟header之后的是第一個(gè)時(shí)序數(shù)據(jù)點(diǎn)，第一個(gè)時(shí)序數(shù)據(jù)點(diǎn)的時(shí)間信息用實(shí)際的戳t₀與t_-1的差異(delta)來(lái)表示。對(duì)應(yīng)到圖中則是

t_-1=March 24,2015 02:00:00
t₀=March 24,2015 02:00:00
delta=62

block的第一個(gè)時(shí)序數(shù)據(jù)點(diǎn)之后的數(shù)據(jù)點(diǎn)
(a) 計(jì)算時(shí)間戳的delta的delta
D = (t_n - t_n-1) - (t_n-1 - t_n-2)
(b) 如果 D = 0，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用1個(gè)比特位0表示；
(c) 如果 D 屬于[-63,64]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用2個(gè)比特位10和7個(gè)比特位的 D 表示；
(d) 如果 D 屬于[-255,256]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用3個(gè)比特位110和9個(gè)比特位的 D 表示；
(e) 如果 D 屬于[-2047,2048]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用4個(gè)比特位1110和12個(gè)比特位的 D 表示；
(e) 其他，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用4個(gè)比特位1111和32個(gè)比特位的 D 表示；

對(duì)生產(chǎn)環(huán)境的時(shí)序數(shù)據(jù)進(jìn)行采樣后，選擇了一組比較合適的各個(gè)時(shí)間范圍區(qū)間的劃分。對(duì)于固定時(shí)間間隔的時(shí)間點(diǎn)，只需要1個(gè)比特位即可表示。用Facebook的一段生產(chǎn)數(shù)據(jù)集進(jìn)行了驗(yàn)證，該壓縮方法可以取得較好的壓縮效果。
從Beringei中摘取了一段經(jīng)過(guò)簡(jiǎn)化，保留了主要邏輯的代碼如下：

struct {
  int64_t bitsForValue;
  uint32_t controlValue;
  uint32_t controlValueBitLength;
} static const timestampEncodings[4] = {{7, 2, 2}, //如果 D 屬于[-63,64]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用2個(gè)比特位10和7個(gè)比特位的 D 表示
                                        {9, 6, 3}, //如果 D 屬于[-255,256]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用3個(gè)比特位110和9個(gè)比特位的 D 表示
                                        {12, 14, 4}, //如果 D 屬于[-2047,2048]區(qū)間，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用4個(gè)比特位1110和12個(gè)比特位的 D 表示
                                        {32, 15, 4}}; //其他，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用4個(gè)比特位1111和32個(gè)比特位的 D 表示

bool TimeSeriesStream::appendTimestamp(
    int64_t timestamp,
    int64_t minTimestampDelta) {

  if (data_.empty()) {
    // Store the first value as is
    // 首個(gè)時(shí)間點(diǎn)存儲(chǔ)時(shí)間園值
    BitUtil::addValueToBitString(
        timestamp, kBitsForFirstTimestamp, data_, numBits_);
    prevTimestamp_ = timestamp;
    prevTimestampDelta_ = kDefaultDelta;
    return true;
  }

  if (deltaOfDelta == 0) {
    // 如果 D = 0，則該數(shù)據(jù)點(diǎn)的時(shí)間戳用1個(gè)比特位0表示
    prevTimestamp_ = timestamp;
    BitUtil::addValueToBitString(0, 1, data_, numBits_);
    return true;
  }

  // 循環(huán)用于判斷值屬于哪個(gè)區(qū)間
  for (int i = 0; i < 4; i++) {
    if (absValue < ((int64_t)1 << (timestampEncodings[i].bitsForValue - 1))) {
      // 控制位
      BitUtil::addValueToBitString(
          timestampEncodings[i].controlValue,
          timestampEncodings[i].controlValueBitLength,
          data_,
          numBits_);

      // Make this value between [0, 2^timestampEncodings[i].bitsForValue - 1]
      // 數(shù)據(jù)位
      int64_t encodedValue = deltaOfDelta +
          ((int64_t)1 << (timestampEncodings[i].bitsForValue - 1));

      BitUtil::addValueToBitString(
          encodedValue, timestampEncodings[i].bitsForValue, data_, numBits_);
      break;
    }
  }
  
  // 保存當(dāng)前值為下一次調(diào)用時(shí)的前值
  prevTimestamp_ = timestamp;
  prevTimestampDelta_ = delta;

  return true;
}

值壓縮

Gorilla限制值的類(lèi)型為雙精度浮點(diǎn)數(shù)。根據(jù)Facebook已有的數(shù)據(jù)分析，大部分的時(shí)序數(shù)據(jù)點(diǎn)相對(duì)于其鄰近點(diǎn)并不會(huì)有顯著變化，這一特點(diǎn)使得可以實(shí)現(xiàn)高效的數(shù)據(jù)壓縮。相近的浮點(diǎn)數(shù)的符號(hào)、指數(shù)和尾數(shù)的開(kāi)頭幾位都會(huì)是相同的。為了利用這一特性，將當(dāng)前值與前值進(jìn)行異或計(jì)算得到中間值，并對(duì)中間值按照如下方式進(jìn)行編碼：

第一個(gè)時(shí)序數(shù)據(jù)點(diǎn)的值存儲(chǔ)原值；
若中間值為0，則存儲(chǔ)1個(gè)比特位0；
若中間值不為0，則存儲(chǔ)1個(gè)比特位1，計(jì)算中間值首尾的0的數(shù)量；
3.1 若首0和尾0的數(shù)量均不小于前值，則存儲(chǔ)1個(gè)比特位0（表示需要使用前值的有效位數(shù)信息）。將中間值按照前值的有效位進(jìn)行截取，先去掉前值的尾0數(shù)量個(gè)尾0，再去掉前值首0數(shù)量個(gè)首0，然后存儲(chǔ)（因此恢復(fù)時(shí)需要知道前值的首尾0個(gè)數(shù)）；
3.2 否則，存儲(chǔ)1個(gè)比特位1（表示不需要使用前值的有效位數(shù)信息）。并用5個(gè)bit位存儲(chǔ)首0個(gè)數(shù)，隨后用6個(gè)bit存儲(chǔ)有效位的長(zhǎng)度，最后存儲(chǔ)有效位；

采用這樣的壓縮方法，可以有效壓縮Facebook的生產(chǎn)數(shù)據(jù)樣本。但需要注意的是，當(dāng)查詢的時(shí)間范圍較小時(shí)，由于值的解壓縮可能依賴前值，通常需要讀取更多的數(shù)據(jù)以得到期望的時(shí)間段的時(shí)序數(shù)據(jù)。
從Beringei中摘取了一段經(jīng)過(guò)簡(jiǎn)化，保留了主要邏輯的代碼如下：

void TimeSeriesStream::appendValue(double value) {

  // 若中間值為0，則存儲(chǔ)1個(gè)比特位0
  if (xorWithPrevius == 0) {
    BitUtil::addValueToBitString(0, 1, data_, numBits_);
    return;
  }

  // 若中間值不為0，則存儲(chǔ)1個(gè)比特位`1`
  BitUtil::addValueToBitString(1, 1, data_, numBits_);

  if (leadingZeros >= previousValueLeadingZeros_ &&
      trailingZeros >= previousValueTrailingZeros_ &&
      previousBlockInformationSize < expectedSize) {
    // Control bit for using previous block information.
    // 否則，存儲(chǔ)1個(gè)比特位`1`（表示不需要使用前值的有效位數(shù)信息）
    BitUtil::addValueToBitString(1, 1, data_, numBits_);

    // 否則，存儲(chǔ)1個(gè)比特位`1`（表示不需要使用前值的有效位數(shù)信息）。并用5個(gè)bit位存儲(chǔ)首0個(gè)數(shù)，隨后用6個(gè)bit存儲(chǔ)有效位的長(zhǎng)度，最后存儲(chǔ)有效位
    uint64_t blockValue = xorWithPrevius >> previousValueTrailingZeros_;
    BitUtil::addValueToBitString(
        blockValue, previousBlockInformationSize, data_, numBits_);

  } else {
    // Control bit for not using previous block information.
    // 若首0和尾0的數(shù)量均不小于前值，則存儲(chǔ)1個(gè)比特位`0`（表示需要使用前值的有效位數(shù)信息）
    BitUtil::addValueToBitString(0, 1, data_, numBits_);

    // 將中間值按照前值的有效位進(jìn)行截取，先去掉前值的尾0數(shù)量個(gè)尾0，再去掉前值首0數(shù)量個(gè)首0，然后存儲(chǔ)（因此恢復(fù)時(shí)需要知道前值的首尾0個(gè)數(shù)）
   // 存儲(chǔ)前值的首0個(gè)數(shù)
    BitUtil::addValueToBitString(
        leadingZeros, kLeadingZerosLengthBits, data_, numBits_);
  
    // 存儲(chǔ)有效位
    BitUtil::addValueToBitString(
        // To fit in 6 bits. There will never be a zero size block
        blockSize - kBlockSizeAdjustment,
        kBlockSizeLengthBits,
        data_,
        numBits_);

    uint64_t blockValue = xorWithPrevius >> trailingZeros;
    BitUtil::addValueToBitString(blockValue, blockSize, data_, numBits_);

    // 存儲(chǔ)當(dāng)前值，下一次調(diào)用時(shí)作為前值
    previousValueTrailingZeros_ = trailingZeros;
    previousValueLeadingZeros_ = leadingZeros;
  }

  previousValue_ = *p;
}

內(nèi)存數(shù)據(jù)結(jié)構(gòu)

Gorrila內(nèi)存數(shù)據(jù)結(jié)構(gòu)

TSmap

TSmap即Timeseries Map，由一個(gè)vector和map組成，均作為時(shí)序數(shù)據(jù)的索引使用。vector元素位指向時(shí)間序列的智能指針(shared_ptr)；map以時(shí)間序列的名稱作為key（大小寫(xiě)敏感但是保留大小寫(xiě)），指向時(shí)間序列的智能指針作為value。vector可以提供較好的范圍查詢能力，map提供較好的點(diǎn)查詢能力。
使用智能指針避免了范圍查詢時(shí)的大量數(shù)據(jù)拷貝。在刪除時(shí)間序列數(shù)據(jù)的索引vector時(shí)，只需要將這片連續(xù)內(nèi)存標(biāo)記為dead，并將其歸還給內(nèi)存池，以等待下一次內(nèi)存分配重用。
為了實(shí)現(xiàn)并發(fā)訪問(wèn)，每個(gè)TSmap用一個(gè)讀寫(xiě)鎖保護(hù)訪問(wèn)索引vector和map，同時(shí)每個(gè)時(shí)間序列由一個(gè)自旋鎖保護(hù)其訪問(wèn)。Facebook認(rèn)為每個(gè)時(shí)間序列的寫(xiě)入吞吐量不會(huì)太高，因此自旋鎖并不會(huì)因?yàn)樽x寫(xiě)產(chǎn)生太強(qiáng)的沖突。
Beringei中，TSmap對(duì)應(yīng)的實(shí)現(xiàn)叫做BucketMap，摘取了一段實(shí)現(xiàn)范圍掃描和特定key查詢的代碼如下：

// Get all the TimeSeries.
void BucketMap::getEverything(std::vector<Item>& out) {
  out.reserve(tableSize_);
  folly::RWSpinLock::ReadHolder guard(lock_);
  out.insert(out.end(), rows_.begin(), rows_.end());
}

BucketMap::Item
BucketMap::getInternal(const std::string& key, State& state, uint32_t& id) {
  folly::RWSpinLock::ReadHolder guard(lock_);

  state = state_;
  if (state_ >= UNOWNED && state_ <= READING_KEYS) {
    // Either the state is UNOWNED or keys are being read. In both
    // cases do not try to find the key.
    return nullptr;
  }

  const auto& it = map_.find(key.c_str());
  if (it != map_.end()) {
    id = it->second;
    return rows_[id];
  }

  return nullptr;
}

ShardMap

ShardMap使用vector存儲(chǔ)TSmap的指針（unique_ptr)。

std::vector<std::unique_ptr<BucketMap>> data_;

Timeseries

timeseries是直接存儲(chǔ)時(shí)序數(shù)據(jù)點(diǎn)的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，包括保存最近一個(gè)時(shí)間窗口數(shù)據(jù)的熱數(shù)據(jù)塊（open block）以及保存更早時(shí)間窗口數(shù)據(jù)的冷數(shù)據(jù)塊（open block）。熱數(shù)據(jù)塊是一個(gè) append-only 的字符串結(jié)構(gòu)。每個(gè)數(shù)據(jù)塊的時(shí)間窗口都是2個(gè)小時(shí)，熱數(shù)據(jù)塊的時(shí)間窗口過(guò)期后，會(huì)開(kāi)啟一個(gè)新的熱數(shù)據(jù)塊，并將過(guò)期的熱數(shù)據(jù)塊設(shè)置為冷數(shù)據(jù)塊。熱數(shù)據(jù)塊轉(zhuǎn)變?yōu)槔鋽?shù)據(jù)塊過(guò)程中，所有數(shù)據(jù)會(huì)進(jìn)行一次拷貝以減小內(nèi)存碎片。因?yàn)闊釘?shù)據(jù)塊會(huì)因?yàn)槿萘康淖兓?jīng)常進(jìn)行內(nèi)存再分配，通過(guò)數(shù)據(jù)拷貝可以在總體上減少內(nèi)存碎片。
與常規(guī)數(shù)據(jù)庫(kù)有所不同的是，數(shù)據(jù)的讀取是直接拷貝數(shù)據(jù)塊到RPC調(diào)用的數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的解壓是由客戶端完成的。

磁盤(pán)數(shù)據(jù)結(jié)構(gòu)

Goriila的底層數(shù)據(jù)存儲(chǔ)是POSIX兼容的的分布式文件系統(tǒng)GlusterFS，包括3個(gè)數(shù)據(jù)副本。一個(gè)Gorrila節(jié)點(diǎn)可能包括多個(gè)shard，每個(gè)shard只包括一個(gè)數(shù)據(jù)目錄，每個(gè)數(shù)據(jù)目錄包括4種類(lèi)型的文件：key list, append-only log, complete block file, checkpoint file。

key list

key list是維護(hù)時(shí)序數(shù)據(jù)key到id的映射，這個(gè)id值是內(nèi)部數(shù)據(jù)數(shù)據(jù)的下標(biāo)。

append-only log file

每個(gè)shard包括一個(gè)append-only log file，存儲(chǔ)使用本文前文中描述的壓縮算法壓縮后的數(shù)據(jù)。Gorrila不提供ACID保證，此日志與傳統(tǒng)的write-ahead-log不同，不能完全保證數(shù)據(jù)的安全性。當(dāng)數(shù)據(jù)在緩存中超過(guò)64kB，就會(huì)觸發(fā)一次從數(shù)據(jù)從內(nèi)存flush到磁盤(pán)。在數(shù)據(jù)持久化到磁盤(pán)前，內(nèi)存中的數(shù)據(jù)可能因?yàn)楣收媳罎⒑髞G失。相對(duì)于傳統(tǒng)的write-ahead-log，用一定的數(shù)據(jù)丟失的風(fēng)險(xiǎn)，換來(lái)了更高的數(shù)據(jù)寫(xiě)入性能。

complete block file

每過(guò)兩個(gè)小時(shí)，Gorrila會(huì)復(fù)制壓縮block數(shù)據(jù)到磁盤(pán)生成complete block file。文件內(nèi)容包括兩個(gè)section：若干64kB連續(xù)的數(shù)據(jù)塊，這些數(shù)據(jù)塊的格式與內(nèi)存中的保持一致；保存了<時(shí)序key id, 數(shù)據(jù)block的指針>的數(shù)據(jù)對(duì)的列表。

checkpoint file

checkpoint file是用來(lái)標(biāo)記complete block內(nèi)存數(shù)據(jù)是否flush到磁盤(pán)的文件。當(dāng)一個(gè)complete block持久化到磁盤(pán)生成相應(yīng)文件，Gorrila會(huì)刪除相應(yīng)的日志文件。

故障處理

Gorrila的故障處理優(yōu)先考慮單節(jié)點(diǎn)故障、不可觀測(cè)的臨時(shí)故障以及地域性的故障。對(duì)于其他故障，優(yōu)先考慮最近數(shù)據(jù)的可用性，而通過(guò)HBase等外部系統(tǒng)來(lái)處理歷史數(shù)據(jù)不可用時(shí)的歷史數(shù)據(jù)查詢。
Gorrila在不同的數(shù)據(jù)中心維護(hù)兩個(gè)完全一樣但不考慮一致性的實(shí)例級(jí)別的數(shù)據(jù)副本，以實(shí)現(xiàn)數(shù)據(jù)中心故障或分區(qū)的情況下的高可用。發(fā)往故障region副本的請(qǐng)求會(huì)透明地重定向到另一個(gè)可用的region副本。當(dāng)副本故障持續(xù)超過(guò)一分鐘，副本數(shù)據(jù)將會(huì)被刪除。在這期間，所有的請(qǐng)求都不會(huì)再發(fā)往該副本，直到副本恢復(fù)并存儲(chǔ)有超過(guò)26小時(shí)時(shí)間的數(shù)據(jù)。
在region內(nèi)部，有一個(gè)基于Paxos復(fù)制的管控系統(tǒng)叫ShardManager。當(dāng)一個(gè)節(jié)點(diǎn)故障時(shí)，ShardManager會(huì)將故障節(jié)點(diǎn)上的shard重新分配到集群內(nèi)的其他節(jié)點(diǎn)上。在shard移動(dòng)過(guò)程中，客戶端會(huì)暫存寫(xiě)入的數(shù)據(jù)。數(shù)據(jù)暫存的空間大小支持容納1分鐘的數(shù)據(jù)，1分鐘前的數(shù)據(jù)將會(huì)被丟棄以存儲(chǔ)新的數(shù)據(jù)。通常情況下，數(shù)據(jù)的移動(dòng)會(huì)在30秒內(nèi)完成。如果超過(guò)1分鐘，那么可以從另一個(gè)region副本上讀取完整數(shù)據(jù)。
當(dāng)一個(gè)shard被分配到一臺(tái)機(jī)器節(jié)點(diǎn)上后，shard會(huì)從GlusterFS上讀取所有數(shù)據(jù)，通常需要幾分鐘時(shí)間。在讀文件的同時(shí)，也會(huì)同時(shí)接收新的寫(xiě)入數(shù)據(jù)將其放入隊(duì)列中暫存起來(lái)以待后續(xù)處理。在版本升級(jí)等可控的重啟過(guò)程中，所有的數(shù)據(jù)都會(huì)被flush持久化到磁盤(pán)。當(dāng)然，在append-only log file未將全部數(shù)據(jù)flush到磁盤(pán)的場(chǎng)景中，部分?jǐn)?shù)據(jù)會(huì)丟失。Gorrila選擇這樣的權(quán)衡，以提高系統(tǒng)寫(xiě)入吞吐量。
在節(jié)點(diǎn)故障恢復(fù)過(guò)程中，shard可能只包括部分?jǐn)?shù)據(jù)，所有的請(qǐng)求都會(huì)返回一個(gè)partial標(biāo)記。當(dāng)客戶端從一個(gè)副本處得到了一個(gè)partial的結(jié)果后，可以選擇從另一個(gè)副本再次查詢。
當(dāng)然，最終Facebook也采用了HBase作為兜底方案。在所有內(nèi)存數(shù)據(jù)副本失效后，可以通過(guò)HBase進(jìn)行查詢。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

基于內(nèi)存的時(shí)序數(shù)據(jù)庫(kù)Gorilla的設(shè)計(jì)和實(shí)現(xiàn)-論文閱讀筆記

基于內(nèi)存的時(shí)序數(shù)據(jù)庫(kù)Gorilla的設(shè)計(jì)和實(shí)現(xiàn)-論文閱讀筆記

時(shí)序數(shù)據(jù)壓縮

時(shí)間戳壓縮

值壓縮

內(nèi)存數(shù)據(jù)結(jié)構(gòu)

TSmap

ShardMap

Timeseries

磁盤(pán)數(shù)據(jù)結(jié)構(gòu)

key list

append-only log file

complete block file

checkpoint file

故障處理

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

基于內(nèi)存的時(shí)序數(shù)據(jù)庫(kù)Gorilla的設(shè)計(jì)和實(shí)現(xiàn)-論文閱讀筆記

時(shí)序數(shù)據(jù)壓縮

時(shí)間戳壓縮

值壓縮

內(nèi)存數(shù)據(jù)結(jié)構(gòu)

TSmap

ShardMap

Timeseries

磁盤(pán)數(shù)據(jù)結(jié)構(gòu)

key list

append-only log file

complete block file

checkpoint file

故障處理

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av