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 namesymbols.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来管理编码后的内容，使用开始的二个字节来存储编码后内容的大小，避免了额外使用一个数据成员来存储。
