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总结

Symbol

总结

继续阅读

Apache (You don't have permission to access / on this server.）

debian9升级4.9.0内核到4.19.2内核过程

centOS7 配置 vsftpd 虚拟用户及权限Vsftpd配置虚拟用户及权限

linux-svn卸载与安装

vsftp虚拟多用户多权限一键部署脚本

Ubuntu14.04 LTS下安装mongodb

Nginx服务优化（1）——隐藏版本号、修改用户与组、网页缓存时间、日志切割、连接超时一、隐藏版本号二、修改用户与组三、配置Nginx网页缓存时间四、实现Nginx日志分割五、配置Nginx实现连接超时六、补充关于时间日期的命令

httpd服务的部署、启动、配置和简单优化一、部署二、启动三、配置文件

配置网页内容访问

手动安装Intel network I217-LM网卡的Linux驱动

禁止ubuntu系统弹出报错界面

Ubuntu Linux下Apache的配置文件

samba服务器的功能

【Linux】UDP广播报文接收速率问题

Linux设备模型（中）之上层容器

PowerPC平台 Linux移植三