Envoy源码分析之Stats符号表

简介: # Symbol 在前面几篇文章中我们介绍了`Scope`,通过`Scope`可以使得我们共享相同的`stats`前缀,例如下面两个stats, ![share-scope.jpg](https://ata2-img.cn-hangzhou.oss-pub.aliyun-inc.com/db6cfdfa57dd322f79dd87c89b354dff.jpg) 这两个stats可

Symbol

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

share-scope.jpg

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

scope.jpg

带来的问题就是会造成大量字符串的冗余,带来内存上的浪费,上图中的两个stats其实是可以共享字符串upstream_rq_totalcluster等。因此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;
}
  1. 将stats name传递给addTokensToEncoding进行encoding
  2. encoding后的内容会存在Encoding类中,然后分配一块存储Storage
  3. 将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);
  }
}
  1. absl::StrSplit(name, '.')切割stats name
  2. symbols.push_back(toSymbol(token)) 每一个stat name通过toSymbol转换为Symbol存起来
  3. encoding.addSymbol(symbol) 将所有的Symbol添加到Encoding中进行编码

`toSymbol的实现依赖上文中提到的EncodeMap表,stats的每一段都要去查询这个Map,如果已经存在就直接返回对应的Symbol否则就创建一个SymbolSymbol本质上就是一个递增的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

encoding.jpg

最后一个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;
}

storage.jpg

到此为止一个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_;
};

StorageStatName最终会被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-new.jpg

最后我们来讲一下如何将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。转换的过程如下:

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

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

stats-decoding.jpg

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

目录
相关文章
|
3月前
|
存储 缓存 监控
GitlabCI学习笔记之五:GitLabRunner pipeline语法之cache
GitlabCI学习笔记之五:GitLabRunner pipeline语法之cache
|
6月前
|
缓存 安全 网络协议
Envoy中Wasm Filter相关概念解释
本文旨在介绍Envoy中Wasm Filter相关概念,让用户对相关架构有更加深入的了解,可以快速开发出自己的Wasm插件。 阿里云服务网格(Service Mesh,简称ASM)提供一个全托管式的服务网格平台,兼容社区Istio开源服务网格,用于简化服务的治理,包括服务调用之间的流量路由与拆分管理、服务间通信的认证安全以及网格可观测性能力,从而极大地减轻开发与运维的工作负担。 ASM支持Wasm插件。
188 2
|
6月前
|
安全 数据安全/隐私保护
SAP ABAP Gateway 系统接口 /IWBEP/IF_MGW_APPL_SRV_RUNTIME 的作用介绍
SAP ABAP Gateway 系统接口 /IWBEP/IF_MGW_APPL_SRV_RUNTIME 的作用介绍
|
存储 JavaScript API
39 # events 模块的实现原理
39 # events 模块的实现原理
33 0
|
缓存 Kubernetes 安全
kubernetes indexer源码解析
kubernetes indexer是实现了多索引的本地缓存,在实现思路,特别在代码可复用方面,值得我们学习借鉴
132 0
kubernetes indexer源码解析
|
Java API 开发者
Gateway全局过滤使用方法|学习笔记
快速学习Gateway全局过滤使用方法
|
Rust Kubernetes Go
为Envoy编写WASM Filter并部署到服务网格ASM中使用
## 简介 Envoy是一个高性能、可编程的L3 / L4和L7代理,被服务网格ASM作为数据面的代理使用。Envoy的连接和流量处理的核心是网络过滤器(Network Filter),该过滤器一旦融合进滤器链(Filter Chain),就可以实现用于访问控制、数据或协议转换、数据增强、审计等高级功能。通过添加新的过滤器Filter,可以用来扩展Envoy的已有功能集。当前有两种方法可以添加新
2161 0
为Envoy编写WASM Filter并部署到服务网格ASM中使用
|
存储 网络协议 前端开发
Envoy源码分析之Stats基础
# 简介 Envoy官方文档中提到`One of the primary goals of Envoy is to make the network understandable`,让网络变的可理解,为了实现这个目标Envoy中内置了`stats`用于统计各类网络相关的指标,Envoy没有选择使用`Prometheus`SDK,而是选择自己实现了`stats`,[目的是为了适配Envoy的线
1615 0
Envoy源码分析之Stats基础
|
存储 缓存 安全
Envoy源码分析之Stats Scope
# Scope 在上一篇文章中提到Envoy中通过`Scope`来创建`Metrics`,为什么要搞一个`Scope`的东西出来呢?`Scope`诞生的目的其实是为了更好的管理一组`stats`,比如关于集群的`stats`,这类`stats`的名称有个特点就是都是以`cluster.`作为前缀,那么可以以`cluster.`来创建一个`Scope`,这样就可以通过这个`Scope`来管理
1093 0
|
负载均衡 算法 安全
Envoy源码分析之Load balancing基础
# 什么是Load balancing? > Load balancing is a way of distributing traffic between multiple hosts within a single upstream cluster in order to effectively make use of available resources. There are man
1353 0