Symbol

在前面几篇文章中我们介绍了Scope，通过Scope可以使得我们共享相同的stats前缀，例如下面两个stats，

这两个stats可以共享cluster.http1_cluster.前缀，尽管如此还是无法避免一些字符串的冗余，在前面的文章中我们提到，每一个线程都会创建一个Scope，也就是说相同的Scope会出现在多个线程中，这些Scope共享Metrics，但是Scope内部保存的stats前缀就会存在多份，造成浪费。此外如果像下面这两个stats一样的话就没办法共享前缀了。

带来的问题就是会造成大量字符串的冗余，带来内存上的浪费，上图中的两个stats其实是可以共享字符串upstream_rq_total、cluster等。因此Envoy中为了优化内存的使用引入了SymbolTable。将stats按照.号分割，每一段被称为一个Symbol，相同的字符串则共用同一个Symbol，其定义如下。

using Symbol = uint32_t;

有了Symbol后，凡是需要存放stats name的地方都可以替换成Symbol，避免直接存字符串带来内存上的浪费。而stats name到Symbol的转换则需要依靠下面两个Map来完成映射。

struct SharedSymbol {
    SharedSymbol(Symbol symbol) : symbol(symbol), ref_count(1) {}
    Symbol symbol_;
    // 记录Symbol被引用的次数，当引用次数为0的时候才会删除
    uint32_t ref_count_;
};

// Bitmap implementation.
// The encode map stores both the symbol and the ref count of that symbol.
// Using absl::string_view lets us only store the complete string once, in the decode map.
// 根据stats name查询对应的symbol

using EncodeMap = absl::flat_hash_map<absl::string_view, SharedSymbol, StringViewHash>;

// 根据symbol查询对应的stats name
using DecodeMap = absl::flat_hash_map<Symbol, InlineStringPtr>;
EncodeMap encode_map_ GUARDED_BY(lock_);
DecodeMap decode_map_ GUARDED_BY(lock_);

通过EncodeMap可以根据stats name查询对应的Symbol，而通过DecodeMap则可以根据Symbol查询对应的stats name，这里用InlineStringPtr来表示stats name，这个类型还是很有意思的，可以先来看下它的定义。

using InlineStringPtr = std::unique_ptr<InlineString>;
class InlineString : public InlineStorage {
public:
  static InlineStringPtr create(absl::string_view str) {
    return InlineStringPtr(new (str.size()) InlineString(str.data(), str.size()));
  }
  std::string toString() const { return std::string(data_, size_); }
  absl::string_view toStringView() const { return absl::string_view(data_, size_); }
  size_t size() const { return size_; }
  const char* data() const { return data_; }

private:
  InlineString(const char* str, size_t size);

  uint32_t size_;
  char data_[];
};

其实就是std::string的简易版本，不同的地方就是这里使用了柔性数组，相比于使用char* data来说更优，这种技巧被称为struct hack，更具体的介绍可以看这篇文章What is importance of struct hack in c?。接着我们来看下一个stats name到底是如何转换为Symbol。

SymbolTable::StoragePtr SymbolTableImpl::encode(absl::string_view name) {
  Encoding encoding;
  // 将stat按照.号切割成一个个token，然后放到Encoding中
  addTokensToEncoding(name, encoding);
  // 接着创建一个Storage存储stats编码后的内容
  auto bytes = std::make_unique<Storage>(encoding.bytesRequired());
  encoding.moveToStorage(bytes.get());
  return bytes;
}

将stats name传递给addTokensToEncoding进行encoding
encoding后的内容会存在Encoding类中，然后分配一块存储Storage
将encoding后的内容放到Storage中

一个Storage就是一个uint_8的数组，addTokensToEncoding方法会将stats name按照.号切割成一个个token，然后通过Encoding来做编码。

  using Storage = uint8_t[];
  using StoragePtr = std::unique_ptr<Storage>;

首先来看下addTokensToEncoding方法的实现。

void SymbolTableImpl::addTokensToEncoding(const absl::string_view name, Encoding& encoding) {
  if (name.empty()) {
    return;
  }

  // We want to hold the lock for the minimum amount of time, so we do the
  // string-splitting and prepare a temp vector of Symbol first.
  const std::vector<absl::string_view> tokens = absl::StrSplit(name, '.');
  std::vector<Symbol> symbols;
  symbols.reserve(tokens.size());

  // Now take the lock and populate the Symbol objects, which involves bumping
  // ref-counts in this.
  {
    Thread::LockGuard lock(lock_);
    for (auto& token : tokens) {
      symbols.push_back(toSymbol(token));
    }
  }

  // Now efficiently encode the array of 32-bit symbols into a uint8_t array.
  for (Symbol symbol : symbols) {
    encoding.addSymbol(symbol);
  }
}

absl::StrSplit(name, '.')切割stats name
symbols.push_back(toSymbol(token)) 每一个stat name通过toSymbol转换为Symbol存起来
encoding.addSymbol(symbol) 将所有的Symbol添加到Encoding中进行编码

`toSymbol的实现依赖上文中提到的EncodeMap表，stats的每一段都要去查询这个Map，如果已经存在就直接返回对应的Symbol否则就创建一个Symbol。Symbol本质上就是一个递增的uin32_t类型的整数。

Symbol SymbolTableImpl::toSymbol(absl::string_view sv) {
  Symbol result;
  auto encode_find = encode_map_.find(sv);
  // If the string segment doesn't already exist,
  if (encode_find == encode_map_.end()) {
    InlineStringPtr str = InlineString::create(sv);
    auto encode_insert = encode_map_.insert({str->toStringView(), SharedSymbol(next_symbol_)});
    ASSERT(encode_insert.second);
    auto decode_insert = decode_map_.insert({next_symbol_, std::move(str)});
    ASSERT(decode_insert.second);

    result = next_symbol_;
    newSymbol();
  } else {
    result = encode_find->second.symbol_;
    ++(encode_find->second.ref_count_);
  }
  return result;
}

在EncodeMap表中查询不到stats的时候，就会进行分配，直接返回next_symbol_，这是预先分配好的一个Symbol，接着通过newSymbol进行下一个Symbol的预分配。

// Symbol pool
std::stack<Symbol> pool_

void SymbolTableImpl::newSymbol() EXCLUSIVE_LOCKS_REQUIRED(lock_) {
  if (pool_.empty()) {
    next_symbol_ = ++monotonic_counter_;
  } else {
    next_symbol_ = pool_.top();
    pool_.pop();
  }
  // This should catch integer overflow for the new symbol.
  ASSERT(monotonic_counter_ != 0);
}

分配的时候先看下Symbol pool中是否有释放的Symbol，没有的话就递增来创建一个新的Symbol，当我们一个stats name不再使用的时候会被释放掉，对应的Symbol也会被释放，最终会存放在Symbol pool中。这个分配机制和Linux内核中的inode分配机制其实是类似的。最后来看下最重要的Symbol的encoding实现。

static const uint32_t SpilloverMask = 0x80;
static const uint32_t Low7Bits = 0x7f;
std::vector<uint8_t> vec_;

void SymbolTableImpl::Encoding::addSymbol(Symbol symbol) {
  // UTF-8-like encoding where a value 127 or less gets written as a single
  // byte. For higher values we write the low-order 7 bits with a 1 in
  // the high-order bit. Then we right-shift 7 bits and keep adding more bytes
  // until we have consumed all the non-zero bits in symbol.
  //
  // When decoding, we stop consuming uint8_t when we see a uint8_t with
  // high-order bit 0.
  do {
    if (symbol < (1 << 7)) {
      vec_.push_back(symbol); // symbols <= 127 get encoded in one byte.
    } else {
      vec_.push_back((symbol & Low7Bits) | SpilloverMask); // symbols >= 128 need spillover bytes.
    }
    symbol >>= 7;
  } while (symbol != 0);
}

整个编码的过程类似于UTF-8编码，会根据Symbol本身的值大小来决定是使用多少个字节来存储，如果是小于128的话，那么就按照一个字节来存储，如果是大于128那么就会进行切割。首先通过和Low7Bits相与拿到低7位，然后和SpilloverMask相或将最高位设置为1。这里有个疑问为什么是小于128就用单字节存储呢?这里为什么不是256呢?，vec_的类型其实是uint8_t的，完全可以用来存储256。但是这里只用到了低7位，最高的那一位是用来表示这个Symbol是否是多个字节组成，还是一个字节组成的。如果是0就表示这个Symbo是一个单字节的。所以当包含多个字节的时候，需要和SpilloverMask相或将最高位设置为1来表示是多字节表示的Symbol。

最后一个stat name被编程成了一个std::vector<uint8_t>，编码的目的其实还是为了节约内存，原来需要一个Symbol表示一个stats name的一部分，现在可能只需要一个uint8_t就可以完成。最后通过Encoding::moveToStorage方法将整个std::vector<uint8_t>存放到Storage中。

class Encoding {
    ......
  private:
      std::vector<uint8_t> vec_;
};

constexpr uint64_t StatNameSizeEncodingBytes = 2;
constexpr uint64_t StatNameMaxSize = 1 << (8 * StatNameSizeEncodingBytes); // 65536

static inline uint8_t* writeLengthReturningNext(uint64_t length, uint8_t* bytes) {
  ASSERT(length < StatNameMaxSize);
  // 取length的低二位存到Storage中，一个stats name的大小最大使用2个字节来表示，也就是最多65535
  *bytes++ = length & 0xff;
  *bytes++ = length >> 8;
  return bytes;
}

uint64_t SymbolTableImpl::Encoding::moveToStorage(SymbolTable::Storage symbol_array) {
  // 拿到vec_成员的大小，
  const uint64_t sz = dataBytesRequired();
  // Storage的前两个字节是用来存储大小的信息
  symbol_array = writeLengthReturningNext(sz, symbol_array);
  if (sz != 0) {
    memcpy(symbol_array, vec_.data(), sz * sizeof(uint8_t));
  }
  vec_.clear(); // Logically transfer ownership, enabling empty assert on destruct.
  return sz + StatNameSizeEncodingBytes;
}

到此为止一个stat name被编码成了一个Storage，这个Storage可以被用来构造成StatName结构，但是不拥有Storage只是对其引用。在使用stats name的地方就可以使用StatName结构了，无论stats name多大，都只占用一个uint_8*的指针大小。

class StatName {
public:
    .....
private:
  // 指向Storage中的unit8_t[]，前两个字节表示sats name的大小。
  const uint8_t* size_and_data_;
};

Storage和StatName最终会被StatNameStorage来管理，StatName内部的size_and_data_指向的就是StatNameStorage内部存放的Storage。

class StatNameStorage {
public:
  // 通过SymbolTable.encode对stats name进行编码，最后存到Storage中
  StatNameStorage(absl::string_view name, SymbolTable& table);
  StatNameStorage(StatName src, SymbolTable& table);
  .......
private:
  SymbolTable::StoragePtr bytes_;
};

StatNameStorage::StatNameStorage(absl::string_view name, SymbolTable& table)
    : bytes_(table.encode(name)) {}

// 拷贝构造，StatName并不拥有storage，所以这里需要拷贝一份。
StatNameStorage::StatNameStorage(StatName src, SymbolTable& table) {
  const uint64_t size = src.size();
  bytes_ = std::make_unique<SymbolTable::Storage>(size);
  src.copyToStorage(bytes_.get());
  table.incRefCount(statName());
}

一个StatNameStorage对应一个Storage, 一个StatName引用一个Storage，但是两者是独立的，没办法从StatNameStorage产生一个StatName，因此有了StatNamePool来管理这两者。

class StatNamePool {
public:
  explicit StatNamePool(SymbolTable& symbol_table) : symbol_table_(symbol_table) {}
  ~StatNamePool() { clear(); }
  StatName add(absl::string_view name);
  uint8_t* addReturningStorage(absl::string_view name);
private:
  SymbolTable& symbol_table_;
  std::vector<StatNameStorage> storage_vector_;
};

uint8_t* StatNamePool::addReturningStorage(absl::string_view str) {
  storage_vector_.push_back(Stats::StatNameStorage(str, symbol_table_));
  return storage_vector_.back().bytes();
}

StatName StatNamePool::add(absl::string_view str) { return StatName(addReturningStorage(str)); }

有了StatNamePool后就可以非常方便的使用StatName了。

// Example usage:
 StatNamePool pool(symbol_table);
 StatName name1 = pool.add("name1");
 StatName name2 = pool.add("name2");
 uint8_t* storage = pool.addReturningStorage("name3");
 StatName name3(storage);

通过StatNamePool管理的stats是一个个独立的，每一个stats占用一个Storage，通过一个StoragePtr指针指向分配的Storage。那么有没有办法将多个stats存储在一个Storage里面呢，那就是StatNameList。

void SymbolTableImpl::populateList(const absl::string_view* names, uint32_t num_names,
                                   StatNameList& list) {
  RELEASE_ASSERT(num_names < 256, "Maximum number elements in a StatNameList exceeded");

  // First encode all the names.
  size_t total_size_bytes = 1; /* one byte for holding the number of names */

  STACK_ARRAY(encodings, Encoding, num_names);
  for (uint32_t i = 0; i < num_names; ++i) {
    Encoding& encoding = encodings[i];
    addTokensToEncoding(names[i], encoding);
    total_size_bytes += encoding.bytesRequired();
  }

  // Now allocate the exact number of bytes required and move the encodings
  // into storage.
  auto storage = std::make_unique<Storage>(total_size_bytes);
  uint8_t* p = &storage[0];
  *p++ = num_names;
  for (auto& encoding : encodings) {
    p += encoding.moveToStorage(p);
  }

  // This assertion double-checks the arithmetic where we computed
  // total_size_bytes. After appending all the encoded data into the
  // allocated byte array, we should wind up with a pointer difference of
  // total_size_bytes from the beginning of the allocation.
  ASSERT(p == &storage[0] + total_size_bytes);
  list.moveStorageIntoList(std::move(storage));
}

populateList方法的目的就是通过Storage来存储多个stats name，它使用Storage的第一个字节来存储stats name的个数，接着将stats name一个个进行encoding成Storage，追加到最终的Storage后。

class StatNameList {
public:
    .....
private:
  .....
  SymbolTable::StoragePtr storage_;
};

最后我们来讲一下如何将Storage转换为对应的stats name。

std::string SymbolTableImpl::toString(const StatName& stat_name) const {
  return decodeSymbolVec(Encoding::decodeSymbols(stat_name.data(), stat_name.dataSize()));
}

SymbolVec SymbolTableImpl::Encoding::decodeSymbols(const SymbolTable::Storage array,
                                                   uint64_t size) {
  SymbolVec symbol_vec;
  Symbol symbol = 0;
  for (uint32_t shift = 0; size > 0; --size, ++array) {
    uint32_t uc = static_cast<uint32_t>(*array);

    // Inverse addSymbol encoding, walking down the bytes, shifting them into
    // symbol, until a byte with a zero high order bit indicates this symbol is
    // complete and we can move to the next one.
    symbol |= (uc & Low7Bits) << shift;
    if ((uc & SpilloverMask) == 0) {
      symbol_vec.push_back(symbol);
      shift = 0;
      symbol = 0;
    } else {
      shift += 7;
    }
  }
  return symbol_vec;
}

decodeSymbols会将Storage转换成一个SymbolVec，因为一个Storage可以包含多个Symbol。转换的过程如下:

每次从Storage中拿一个uint8_t，然后转换为uint32_t，因为Symbol的类型就是uint32_t
接着通过和Low7Bits相或拿到低7位的值
判断SpilloverMask位是否是0，如果是0那就是一个完整的Symbol直接放到SymbolVec即可
如果是1表示，Symbol是多字节组成，还要继续组装，再次读取一个uint8_t，然后取低7位，这个时候，需要向左移动7位，因为Symbol的每一个部分都是7位组成，依次排放的。

下面这张图就是一个多字节的Symbol进行decoding的过程。

将Storage转换为SymbolVec后，还需要通过上文中提到的DecodeMap来反查Symbol对应的name。最后将所有的name通过"."合并起来就成了最终的stats name。

std::string SymbolTableImpl::decodeSymbolVec(const SymbolVec& symbols) const {
  std::vector<absl::string_view> name_tokens;
  name_tokens.reserve(symbols.size());
  {
    // Hold the lock only while decoding symbols.
    Thread::LockGuard lock(lock_);
    for (Symbol symbol : symbols) {
      name_tokens.push_back(fromSymbol(symbol));
    }
  }
  return absl::StrJoin(name_tokens, ".");
}

总结

本文讲解了Envoy中是如何通过SymbolTable的方式来实现内存优化的，提高内存的利用率，SymbolTable实现的关键点有四个，第一个就是将stats name通过"."号拆成一个个token，充分的让相同的token共享同一份存储。第二个就是将token映射到Symbol，方便encoding。第三个就是通过Encoding模块对多个Symbol进行编码，减少引用的成本。第四个就是通过Storage来管理编码后的内容，使用开始的二个字节来存储编码后内容的大小，避免了额外使用一个数据成员来存储。

Envoy源码分析之Stats符号表

Symbol

总结

热门文章

最新文章

相关电子书