↓ Skip to main content
111qqz’s blog
  1. Posts/

redis学习笔记

·1304 words·3 mins
工程 Redis
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

最近在做一个智能算力的项目，其中需要用到redis维护某个全局的时间窗口

资料
#

复杂数据结构的表示方式
#

学习过程中唯一让我迷惑的是一个嵌套的数据结构要如何表示。比如我想表示一个key为string, value为List的Hash 按照c++的语法，也就是一个

1std::unordered_map<std::string,std::vector<int>>

但是我发现，在redis中我无法设置value的数据类型

后来发现，redis这种kv存储其实所有的key是在同一个空间的，不存在嵌套关系

嵌套关系是根据相同的string名称来间接进行的 也就是说：hash的value是一个string，这个string是list的key名称

hash: hash_key_name-> value_key_name list: value_key_name ->list

原子性
#

redis单个命令是原子操作，但是有的时候需要执行多个命令完成一个操作 比如典型的 Read-Modify-Write 操作，这种操作为了保证原子性通常有两种办法 其一是使用incr/hincrby 等命令，把多个命令合成一个 其二是使用lua script，用以实现更复杂的逻辑

性能优化
#

以我遇到的具体问题举例说明吧

有一个队列，队列中的元素是不断变化的，想知道这个队列中所有元素的和。队列元素的增加：当一个请求到来时，就往队列中添加元素。可能同时到来上百个请求。队列元素的删除：按照时间删除，当请求到来超过一定时间后，自动删除。说白了就是想维护一个时间窗口，并查询窗口中元素之和。

最初考虑过使用redis expire命令来实现自动过期的策略，但是由于expire的key没办法直接把sum也对应删除掉，因此没有选择这个方案。

于是转而考虑使用一个list来维护请求队列，从右边加入元素，左边删除元素。维护窗口的时候按照时间戳进行删除

当请求量增大时，发现耗时逐渐变慢，于是开始分析可能的性能瓶颈

使用evalsha替代eval
#

Lua script 每次会把脚本发送到server执行，script没有变化，因此每次传送的开销也是没必要的。

使用evalsha替代eval。

O(n)复杂度的操作
#

目前的实现中有三个O(n)复杂度的操作，分别是取队列中元素、删除其中过期的元素的key、在队列中清除这些元素

代码如下

 1
 2         local queue_name = redis.call("hget",KEYS[1],"queue")
 3         local sum_value = redis.call("hget",KEYS[1],"sum_value")
 4         local sum_quota = redis.call("hget",KEYS[1],"sum_quota")
 5         local queue = redis.call("lrange",queue_name,0,-1)
 6         local cnt = 0
 7         local need_deleted = {}
 8         for i=1,#queue do
 9           local time_stamp = redis.call("hget",queue[i],"timestamp")
10           if (ARGV[2]-time_stamp<=tonumber(ARGV[1])) then break end
11           cnt = i
12           local quota = redis.call("hget", queue[i],"quota")
13           local value = redis.call("hget",queue[i],"value")
14           sum_value = sum_value-value
15           local quota = redis.call("hget",queue[i],"quota")
16           need_deleted[i] = queue[i]
17           sum_quota = sum_quota - quota
18          end
19          redis.call("del",unpack(need_deleted))
20          redis.call("hmset",KEYS[1],"sum_quota",sum_quota,"sum_value",sum_value)
21          redis.call("ltrim",queue_name,cnt,-1)
22          return cnt

其中删除操作考虑过使用unlink替代del，发现反而更慢了。参考 Is the UNLINK command always better than DEL command?，原因需要进一步确认

但是另外的lrange和ltrim命令基本没有改进的空间，只有想办法减少操作的元素个数

每次把队列中所有元素取出来作为候选集是完全没必要的

队列中的元素是按照到来的时间单调排列的，只有一个小范围内的元素是可能过期的。 比如如果更新间隔是100ms，那我每次只选取120ms（比100ms稍大的值）的请求数作为候选集来删除 可以大大减少每次要操作的元素个数

异步操作
#

不管是向队列中加入元素，还是删除过期元素，都没有必要使用同步操作等待redis server返回结果

big key
#

这个场景中的big key就是这个队列了 那么实际上也完全没必要使用一个大的queue 可以根据时间戳拆成多个小的queue来操作

Related

[施工中] levelDB 代码阅读笔记 06 iterator

·1164 words·3 mins
工程 Leveldb
接口 # 一个ABC，后面会继承这个类做各种实现 clean up function # 代码比较好懂，唯一让我感到疑惑的是 clean up function 这部分 1 2 // FIXME: 不太理解为什么需要很多个clean up function 3 // Cleanup functions are stored in a single-linked list. 4 // The list's head node is inlined in the iterator. 5 struct CleanupNode { 6 // True if the node is not used. Only head nodes might be unused. 7 bool IsEmpty() const { return function == nullptr; } 8 // Invokes the cleanup function. 9 void Run() { 10 assert(function != nullptr); 11 (*function)(arg1, arg2); 12 } 13 14 // The head node is used if the function pointer is not null. 15 CleanupFunction function; 16 void* arg1; 17 void* arg2; 18 CleanupNode* next; 19 }; 20 CleanupNode cleanup_head_; 21}; 从 table/iterator.cc 的析构函数中，可以看到在iterator析构的时候会依次调用多个clean up function

levelDB 代码阅读笔记 05 arena

·1286 words·3 mins
工程 Leveldb
arena是levelDB中的内存池实现 接口 # 没有太多好说的，都非常直观。补了些注释 1 2class Arena { 3 public: 4 Arena(); 5 6 Arena(const Arena&) = delete; 7 Arena& operator=(const Arena&) = delete; 8 9 ~Arena(); 10 11 // Return a pointer to a newly allocated memory block of "bytes" bytes. 12 char* Allocate(size_t bytes); 13 14 // Allocate memory with the normal alignment guarantees provided by malloc. 15 char* AllocateAligned(size_t bytes); 16 17 // Returns an estimate of the total memory usage of data allocated 18 // by the arena. 19 size_t MemoryUsage() const { 20 return memory_usage_.load(std::memory_order_relaxed); 21 } 22 23 private: 24 char* AllocateFallback(size_t bytes); 25 char* AllocateNewBlock(size_t block_bytes); 26 27 // Allocation state 28 // alloc_ptr_ 表示下一个可用的位置 29 char* alloc_ptr_; 30 size_t alloc_bytes_remaining_; 31 32 // Array of new[] allocated memory blocks 33 // 需要注意，vector中每一个元素都是一段内存块(memory, block) 34 std::vector<char*> blocks_; 35 36 // Total memory usage of the arena. 37 // 38 // TODO(costan): This member is accessed via atomics, but the others are 39 // accessed without any locking. Is this OK? 40 std::atomic<size_t> memory_usage_; 41}; 分配策略 # 代码可说的不多，主要想讲讲分配策略

levelDB 代码阅读笔记 04 filter

·2552 words·6 mins
工程 Leveldb
FilterPolicy接口 # 1 2class LEVELDB_EXPORT FilterPolicy { 3 public: 4 virtual ~FilterPolicy(); 5 6 // Return the name of this policy. Note that if the filter encoding 7 // changes in an incompatible way, the name returned by this method 8 // must be changed. Otherwise, old incompatible filters may be 9 // passed to methods of this type. 10 virtual const char* Name() const = 0; 11 12 // keys[0,n-1] contains a list of keys (potentially with duplicates) 13 // that are ordered according to the user supplied comparator. 14 // Append a filter that summarizes keys[0,n-1] to *dst. 15 // 16 // Warning: do not change the initial contents of *dst. Instead, 17 // append the newly constructed filter to *dst. 18 virtual void CreateFilter(const Slice* keys, int n, 19 std::string* dst) const = 0; 20 21 // "filter" contains the data appended by a preceding call to 22 // CreateFilter() on this class. This method must return true if 23 // the key was in the list of keys passed to CreateFilter(). 24 // This method may return true or false if the key was not on the 25 // list, but it should aim to return false with a high probability. 26 virtual bool KeyMayMatch(const Slice& key, const Slice& filter) const = 0; 27}; 其中CreateFilter的含义是从n个key生成一个 std::string. 生成的std::string可以包含n个key的信息(类似于生成了一个全集) 从而后续判断某个key是否在其中。