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