使用缓存优化数据请求

上一篇场景之后,事情还没有完。

我有一堆struct obj对象(数量级可能为千级), 客户端需要频繁拉取这些信息中的一部分去显示(比如,当切换标签页时)。

由于这一操作可能会很频繁,而struct obj对象并不算小,如果每一次都重新拉取全部数据,有点让人不舒服,而且对流量也是一种很大的浪费。因此就琢磨着怎么去优化整个过程,以使在此过程中使数据传输量最小。

第一反应,肯定就是对整个列表加一个version字段,每当有obj对象改变时,version加1,当客户端进行拉取时,拿着他本地存储的version值向服务端要列表,如果服务端的version没有比客户端version更新,则直接返回空即可(ps.之所以最开始想到这个办法,是因为有先例 :D)。

但是仔细分析一下整个场景,就会发现这个方法并不太适用这些场景。

一方面,所有obj对象共享着同一个version字段,就意味着只要有任何一个obj对象变动,version字段都会自增。因此理论上obj对象越多,version就变动越频繁,当obj多到一定程度,version机制基本上就形同虚设。

另一方面,由于客户端只需要拉取所有obj对象中的一部分,所有的obj对象共享同一个version也显得有些太过浪费。因此这个方案很容易就被放弃了。

另一种解决方案是,客户端在本地实现一个cache模块,当cache为空时向服务器拉取所需信息。此后再切换标签, 直接从本地cache模块取数据。只有当通过本地cache进行操作(如:通过某按钮根据cache中的obj对象的状态,向服务器发送请求)失败时,再清空本地cache重新从服务端获取。

然而,这种方案有另外一个坏处,就是用户每隔一段时间必然要出现一次错误。对用户来讲似乎不太友好。

经过仔细思考之后,对方案一和方案二进行了综合。来同时去除两种方案的所带来的弊端。

首先将版本号与每一个obj对象进行关联,这样就可以精确指示出某一个对象是否比客户端新。

再将拉取列表命令拆分成两条命令,pull_list和pull_info。

在客户端需要拉取列表时(比如切换标签页), 直接调用pull_list,而pull_list返回一个item列表。item结构体如下:

struct item {
int id;
int version;
};

可以看出这个item极其简单,就算是频繁拉取,数据量也还可以接受。

客户端依然会在本地维护一个cache, 而这个cache的数据结构可能类似于std::unordered_map<int, struct obj>一样的数据结构。

当客户端收到pull_list的回应之后,拿着item列表去cache中查询,确认cache中是否存在这些数据。如果数据存在,则检查服务端返回obj对象的version字段是否比cache中新,如果较新则从cache中删除些obj对象。

然后拿着cache不存在或失效的id列表使用pull_info命令向服务器请求数据。由于在相对短时间段内不可能所有obj对象都会有状态改变。因此,在客户端频繁拉取信息时,cache必然有极高的命中率,这也意味着会极大的节省数据流量开销。

此外,此方案还存在一个问题,那就是列表是随时动态变化的,而其中的obj对象还会随着某些特殊的操作或时间的流逝而消亡。

那么客户端如何才能感知这些变化, 并从cache中删除这些已经不存在的obj对象呢。

遗憾的是,客户端似乎真的没有办法来感知这些变化。

为了解决这个问题,我们做了一个约定,假设客户端一次拉取的列表为N,当客户端cache中obj对象的个数大于2N时,就意味着cache中至少有一半对象可能都已经消亡了(ps.只是有可能)。这时侯直接把cache清空,然后从新开始cache。

BTW, 其实约定为2N实为无奈之举,按我最初的想法,应该是用一个类似weak table的数据结构来cache。这样当内存不够时,可以由GC来自动释放这些内存,来保证客户端依然能够顺利流畅的运行。在Java中可以用WeakHashTable来代替,可遗憾的是在C#中并无此类型数据结构。

使用lua过程中需要注意事项

最近一段时间写了不少lua代码,由于这一次的代码量比以往都多,因此也就遇到了以前没有遇到问题, 需要说明的是,这就是一篇lua问题大集合, 并不涉及其他。

先说说遇到的问题及解决方案。

在lua中没有多余的数据结构,全靠一张表,这也是他简洁的根本所在。

当索引为全为数字时即可当数组使用,然而需要注意的是lua假设数组的索引一定是连续的,在此基础上lua尽可能快的优化了取数据长度的算法,因此lua对‘#’操作符的描述是“当table[i]不为nil, 而table[i+1]为nil时,则数组的长度为i”.

因此如果table = {1, nil, 2, 3}, 那么使用#table得到的结果会是1.因为table[1]不为nil, 而table[1+1]为nil。其实这一点在”Programming in Lua”是有明确说明的,只不过在写代码时我忘记了。

如果想删除数组中的元素而又保证#table的正确性,可以使用table.remove函数来删除指定位置的值,table.remove所做的事情其实就是把所有元素向前移动一位,因此在使用table.remove时一定要估算好移动元素带来的开销是否超出了预期。如果超出了预期就要考虑其他方案,而其他方案也与‘#’引起的问题没有关系了。

‘#’的语义带来的麻烦还不仅仅于此。考虑下面一段代码:

        function test1(...)
                local param = {...}
                local p1, p2, p3, p4 = table.unpack(param)
        end

当调用test(1, nil, 2, 3)之后,得到的结果是p1 = 1, p2 = nil, p3 = nil, p4 = nil。

之所以这样是因为table.unpack(param) 等价于table.unpack(param, 1, #param), 而’#’的语义导致了#param得到的结果是1,所以table.unpack其实只unpack出了第一个值而已。

即然存在此类问题,显然也存在着解决方案。lua的table库中提供了一个函数table.pack。table.pack(…)与{…}惟一不一样的地方就是,table.pack会自动识别…中有几个参数,并把这个值赋给返回的表中的”n”字段。

所以上述代码要想支持传递nil就必须改成如下:

        function test1(...)
                local param = table.pack(...)
                local p1, p2, p3, p4 = table.unpack(param, 1, param.n)
        end

再说说优化问题。

3R在很多文章上都有提到,就不再多说什么了,但是对于Reuse需要注意的是,并不是所有的值都值得Reuse,需要考虑这个表的Reuse的代价有多大。

考虑一个表从产生到销毁的过程(不包含对元表的__gc函数的调用过程)。

local xx = {} 就代表着要构造一个新表,这就代表要调用malloc, 当这个表不再被使用时,就会被gc回收free掉。

如果我们可能重用xx表,那么就可以省去malloc/free的开销,要知道malloc的开销是相当大的。

但是这里需要注意的一个问题是,xx已经有了预分配槽位,假设之前xx表中被设置过xx[1]~xx[100]个数据,那么就意味着重用xx表后,向xx[1]~xx[100]的位置赋值是是不会触发malloc进行扩容的。

之所以说这是一个问题而不是一个优点,是因为在不同的情况下,这种重用有时有利有时有害。这取决于被重用的xx表的用途,如果xx几乎是固定大小,那么显然这种不需要扩容就是有利的,反之如果xx大部分情况下都很小,就会浪费很多空间。

当重用的表是一个模块的upvalue时,还需要考虑的是当你为这个表的每一个槽位都赋为nil的代价与构造一个表的代价哪个更高,如果无法评估则应该选取语言更简单的模式“直接构造一个表”。

next函数常用来进行无序遍历整张表,同样你必须知道他的底层实现,才能够很好的使用它。从lua源码中可以找到next函数具体实现,当传递给next的key为nil时,事实上next函数会从table的第一个空槽位开始遍历,直接找到第一个值为非nil的key并返回。因此在使用next进行遍历时,必须对整个table中的布局做到心中有数。

考虑一种极端情况,有一个table有1M个数组空间,只有在索引接近1M时,值才不为nil,其他值都为nil,如果这时候需要频繁的调用next来遍历整个表,势必会造成程序性能急剧下降。这种情况下就需要在表的基础上构造出相应的数据结构来提高程序性能,比如记录第一个非nil的起始索引。

在lua中有很多基本库和函数是存在于_ENV表中,比如table库,math库等,如果调用这些函数很频繁,可以考虑将函数局部化,能显著提高程序性能。

下面对比一下两段代码,和编译后的OPCODE

--使用全局函数
local tbl = {}
for i = 1, 100 do
        table.insert(tbl, i)
end
--OPCODE
main <a.lua:0,0> (12 instructions at 0x7fc748c043f0)
0+ params, 8 slots, 1 upvalue, 5 locals, 4 constants, 0 functions
	1	[1]	NEWTABLE 	0 0 0
	2	[3]	LOADK    	1 -1	; 1
	3	[3]	LOADK    	2 -2	; 100
	4	[3]	LOADK    	3 -1	; 1
        --for i = 1, 100 do
	5	[3]	FORPREP  	1 5	; to 11
	6	[4]	GETTABUP 	5 0 -3	; _ENV "table"
	7	[4]	GETTABLE 	5 5 -4	; "insert"
	8	[4]	MOVE     	6 0
	9	[4]	MOVE     	7 4
	10	[4]	CALL     	5 3 1
	11	[3]	FORLOOP  	1 -6	; to 6
        -- end
	12	[5]	RETURN   	0 1

--全局函数局部化

local tinsert = table.insert
local tbl = {}
for i = 1, 100 do
        tinsert(tbl, i)
end
--OPCODE
main <b.lua:0,0> (13 instructions at 0x7fb5a94043f0)
0+ params, 9 slots, 1 upvalue, 6 locals, 4 constants, 0 functions
	1	[1]	GETTABUP 	0 0 -1	; _ENV "table"
	2	[1]	GETTABLE 	0 0 -2	; "insert"
	3	[2]	NEWTABLE 	1 0 0
	4	[3]	LOADK    	2 -3	; 1
	5	[3]	LOADK    	3 -4	; 100
	6	[3]	LOADK    	4 -3	; 1
        -- for i = 1, 100 do
	7	[3]	FORPREP  	2 4	; to 12
	8	[4]	MOVE     	6 0
	9	[4]	MOVE     	7 1
	10	[4]	MOVE     	8 5
	11	[4]	CALL     	6 3 1
	12	[3]	FORLOOP  	2 -5	; to 8
        -- end
	13	[5]	RETURN   	0 1

对比可以看出使用局部变量tinsert代替table.insert之后在for循环内少了两条对table的操作(GETTABUP, GETTABLE) 效率大概提高了10%

当语言内置操作和标准库一样时,应该优先选择语言内置操作。其实这很好理解语言内置操作执行一起一般比调用标准库要生成更少的OPCODE,在功能一样的情况下一般OPCODE数目越少,应该就越高效才对。
在循环100W次的情况下table[#table+1]=i要比table.insert(table, i)快30%左右。

btw, 在看lvm.c的过程中,越来越觉得脚本语言是比C/C++更高层次的抽象,不过也只有这样才能达到简少代码的目的。然而高层次抽象就意味着我们失去了很多优化的能力。

lua gc的使用

主流的垃圾回收一般都是基于引用计数和标记清除算法.

从内存占用量上来讲, 引用计数无疑是有优势的, 当引用计数为0时, 直接就会将相应的对象清除, 典型的应用就是C++的智能指针. 但是基于引用计数的gc有一个坏处, 它无法解决循环引用问题. 如果A引用B会导致B的引用计数+1, B引用A也会导致A的引用计数+1, 这样A,B对象永远也不会删除. 记得在OC中似乎使用了弱引用来解决这个问题, 但总感觉这样会给代码中埋下坑.

标记清楚算法可以完美的解决循环引用问题, 其做法是从root遍历所有可达的指针, 然后将不可达的区域回收. 这样即使A和B循环引用, 只是没有其他对象来引用A和B, 那么A和B对象即是不可达. 此时A和B对象即可删除. 但是标记清除算法有一个致命缺陷, 就是在gc时需要停顿整个程序来进行mark-sweep.

最近抽了点时间研究了下go语言, 果然可能是由于太年轻, go也有这个坑. 在搜索资料时发现很多人都在吐槽go的gc部分, go的主要应用领域就是服务器部分,然而据说go的gc会造成不可预知的停顿,这对于服务器来讲是非常致命的.

看到这, 我突然非常担心lua也有此问题, 而在silly中也是以lua来写上层逻辑的, 很担心lua中的gc是否也会造成stop-the-world. 于是找来手册重新认真的读了一下, 发现以前对于lua的gc的工作方式太想当然了, 以致于造成了对lua的错误使用.

lua中的gc算法是采用增量标记清除算法, 通过一次执行一小步来将一次完整的gc时间分摊在每一步上, 提高了整个程序的实时性.(具体如何做的,还要等看完源码才知道:D)

在lua中是分为手动gc和自动gc的.

通过设置垃圾收集器间歇率和垃圾收集器步进倍率来控制自动gc的运行方式.

有某些特殊的条件下, 如果我们需要手动控制gc的时机, 这时就可以LUA_GCSTOP来停止自动垃圾回收器. 然后在恰当的时机手动调用LUA_GCSTEP来发起一次增量垃圾回收.

这样看来, 至少在gc的策略上, lua应该做的比go要好. 当然具体情况还是要等看完实现才能更确切的比较.

btw, 作为一门现代语言, gc已经是一个不可缺少的部件. 然而gc的问题在于, 在平时开发时完全体会不到问题, 一旦在大量数据面前就有可能会出现各种情况. 因此熟悉一门语言绝不仅仅是熟悉其语法就好了, 还必须要深刻了解该语言的Gc机制, 才能做到心中有数.