Immutable

2015-12-21

抢占式操作系统并发编程中有利的做法, 可以减少需要锁的情况, 减少串行代码占比

Amdahl定律: S=1/(1-a+a/n)
其中，a为并行计算部分所占比例，n为并行处理结点个数。
当1-a=0时，(即没有串行，只有并行)最大加速比s=n；
当a=0时（即只有串行，没有并行），最小加速比s=1；
当n→∞时，极限加速比s→ 1/（1-a），这也就是加速比的上限。
例如，若串行代码占整个代码的25%，则并行处理的总体性能不可能超过4。
这一公式已被学术界所接受，并被称做“阿姆达尔定律”，也称为“安达尔定理”(Amdahl law)。

Immutable variables

为的是保证状态一致性,比如一个数据结构,日期{Year, Month, Day}
如果它不是Immutable的话,
例如:

Date date = new Date(2015, 1, 31);
date.setYear(2015);
date.setMonth(2);
date.setDay(29);

那么,当CPU执行到date.setMonth(2);之后进程被抢先,
其他进程读这个date变量的时候就会读到一个非法的值{2015, 2, 31}
即中间状态被暴露给了外部,产生了bug
所以现在C#,Java等语言的Date或DateTime类型都是Immutable的,

Java好像曾经有过setMonth之类的函数,现在虽然还有,
但是改到了Calendar里,Calendar里根据日历信息保证日期是合法的,返回一个Immutable的新DateTime
关键还是Immutable,如果只是放到Calendar里把2月31日改成3月1日的话,还是有中间状态被外部看到

即任何对Date的更新都必须返回一个正确的Date,
如果只是直接更新一个内部值如月份得到的值可能就不正确(不一致),
即使后面还有一个setDay函数,执行后可以得到正确的值,但是过程中不正确的值可能被并发进程读到所以不行
而如果不想让不正确的中间状态对其他进程可见,一个好的做法就是用Immutable变量,
这样就像数据库的事务一样,其他进程能看到的要么是之前的{2015,1,31},要么是最后的正确结果{2015,2,29}

erlang的消息机制把一个erlang进程封装成一个类似Date这样的Immutable数据结构,
其他进程看不到消息处理过程中的数据中间状态,
因为消息是按队列一个一个地顺序处理的,想要取值的消息(同步调用,call)也是按消息队列的
例子是Date内部的值出现冲突(2月和31日的冲突)问题,
而视野放到一个更大的范围就会发现Date之上的数据结构里,可能也有相同的问题,
比如某产品的出厂日期按业务来说不可能是这个日子,但是更新了产品Id之后更新日期之前这个时间窗里,暴露给其他进程的整体信息就是这样一个冲突了的信息
所以我们需要把整个状态(可能很大,很多字段)都做成Immutable的?
改一点点都要把所有字段全都copy一遍?引发巨大的性能的问题?
其实不需要全部copy, 假如数据结构是State: {A, B, C, Date}这样的,
更新的那一点点假如是Date,那么重新创建一个Date,
然后A, B, C与这个新的Date的引用串起来得到一个新State引用,ok
另外, String类也是Immutable的, String类的对象完全可能很大很大, 但是不影响它成为Immutable对象.

那么小到比如一个Int(往往Long, Double就已经不保证原子性了)呢,不像Date这样有内部数据结构了,需要变量不可变吗?
int a = 1;
a = a + 1;
这样有问题吗?
临时计算变量(函数内用完就扔)没问题,业务状态变量(即可以被外部看到)就有问题了

曾经出过一个这样的问题,有一个购买物品的功能,
扣钱的操作是通过更新gen_server的state来做的,而给物品奖励是通过更新进程字典的值来做的,
结果有一次出了bug,物品奖励给完之后扣钱之前erlang进程崩掉了
(或被catch住后面的扣钱代码没有执行也是一样的结果),
于是在进程terminate时将物品奖励写到了DB里,而扣钱的操作没有成功(因为state没有更新,相当于rollback了)
即给了玩家物品却没扣钱

如果物品奖励不是通过进程字典而和扣钱一样是通过state的话,物品奖励也不会给,就不会有这个问题出现,
这就是事务逻辑的好处
从本质上讲,进程字典的操作跳过了事务的逻辑,相当于实时commit,
然而其他数据因为异常都rollback了, 这就是问题所在
上例的
int a = 1;
a = a + 1;
如果a是业务状态变量(比如说酒店住宿天数,直接关系到收费),那么也等同于此处的进程字典更新

归根结底是不能出现不一致的状态
无论是外部逻辑看到不正确的中间状态还是自毁长城实时commit导致不一致的状态

更新前的状态a,在更新完成的状态b出现之前,外部能看见的应该一直是a
(更严格的做法是,状态a-状态b的变化过程中外部想要取值只能等,因为变化过程中取旧值相当于插队了)

插队什么情况下会引发什么后果,能举个例子吗?

总有人说写的时候用一个进程统一写ets，读的时候从外面读ets没问题
但是
如果读出来的数据只是print看一下，那么没问题
如果读出来的数据还要用于判断或计算，那么用ets可能会有问题
举例,ets里存了一个counter
两个进程读出来都是0，都+1，得到结果1，把1发给一个单独的进程（写该ets的专用进程），写进入一个1,bug了
所以说用一个进程统一写也不一定ok
至少更新也得在本进程处理,此时不应对外开放一个单独的写接口，
比如信箱里堆了好多+1的消息
另一个进程直接ets读了个0，然后通过写接口，把那N个+1的消息更新出来的N又给覆盖成了1
所以进程暴露出来的写接口,都必须是保证一致性的写接口

另例,排行榜如果读ets的话,
假如有一个活动,结束时(timer驱动)发奖,读ets取到第一名给奖励,
然而此时排行榜进程(所谓唯一专门写ets的进程)有一条消息正在处理,处理完写完ets第一名应该是另一个人,
怎么办?奖励发错人了,而且往往排行榜有查看功能,此时明明白白可以看到第一名是谁,错得无可辩驳

另例,打BOSS,
如果直接读ets觉得有BOSS,进去以后发现没有BOSS(管理进程里攒着掉血的消息,处理完的时候BOSS已经死了)
如果不想遇见这种情况(根据业务不同,可能会有问题,比如进去这件事本身有代价如需要买票),就得call管理进程,
否则管理进程一时忙的话,多卖出去N多票,引发许多麻烦

所以用于重要判断的地方,还是不能插队读ets,而要call进程

另例说明别的问题
比如ets存玩家Id对应的团队Id
玩家进程读自己是哪个队的，如果玩家进程更新自己的团队Id都是call调用的话，
这样能保证玩家进程自己看不到自己对应的旧的团队Id
因为call会阻塞玩家进程，等阻塞解除后，那边的ets也已经更新完了
但是这个保证并不容易, 比如被团长踢出团队就保证不了
(此时玩家可能不在线, 即无法通过玩家进程修改, 只能由玩家进程以外的进程更新玩家id对应的团队id),
根本原因是ets里玩家id对应的记录并不是只有玩家进程会更新,即本质上一条数据不止一个进程写,
而且玩家进程以外的其他进程还是可以插队ets看到旧的团队Id

当我报名参加一个活动时取ets告诉活动进程我的团队Id，但是团队进程信箱里有一条踢我的消息，
辛辛苦苦打完之后，活动进程通知团队进程发奖，这时没有我的奖，辛苦了一场为什么没有奖，
但是如果用call取也有可能刚call完就被踢了，结果也一样
那怎么办，世界好复杂
那么，被踢不能就这么算了，要通知活动进程，团队解散更要通知
也许报名时把人员对应的团队id存上才是正解，发奖的时候按照报名时的名单给奖励,
但同时也要考虑团队解散的情况, 可能发奖时要取团队名称什么的,取不到也有问题
也许正确做法就是，代码写成奖励尽量给，实在给不了就算了

当ets的数据间或两(多)个ets间存在一致性关联时,
专门的进程统一更新这个(这些)ets也保证不了其他进程读到一致的数据,
因为更新了一个还没更新另一个的时候会被外面看到,这就不仅仅是插队的问题了
仍然是中间状态被外面看见的大问题

感觉进程间以及进程和ets间的复杂关系必须画图，加文字说明特殊情况以及特殊考虑

Immutable variables again

考虑下例:

void Safe(string s)
{
    if (!SecurityCheck(s)) { throw new SecurityException(); }
    Dangerous(s);
}

Safe函数检查字符串s是否安全(比如用户是否允许访问该表或有没有注入式攻击的代码等),
如果字符串不是Immutable的,聪明的攻击者先传一个安全的字符串,检查过了以后,将字符串s改成一个不安全的就得手了
(怎么改?由于s只是一个地址,而且是别的地方传过来的全局变量,找到其他并发赋值的地方给一个不安全的值即可)
于是Immutable的
第一个好处是: 对一个值,以前得出的结论未来仍然正确,这样写代码才有自信
第二个好处是: 可以复用,
当需要构造多个大对象时,里面可以都用同一个小对象(即复用),
以后某一处要改的话,另创建一个对象换掉就可以了,不影响其他大对象
而如果不是Immutable的话就不能复用,因为万一一处被改了,所有的地方都变掉了(引用类型只是记了一个地址而已嘛),
所以如果不是Immutable的话就得copy多份
考虑这一点,Immutable并不比Mutable性能差

原子性

什么是原子性,即不可分割,即没有中间状态,
要么全完成,要么都不完成,没有中间状态(不正确的状态,比如ATM扣了余额没出钱).

加锁方案的缺点

加锁导致代码串行化,存在Amdahl定律提示的性能问题
解锁之前出bug,解锁的代码没有执行到,锁一辈子死锁
需要加锁的地方可能很多处,一处漏掉就会有bug,防不胜防

参考链接

书: OReilly.Becoming.Functional
https://blogs.msdn.microsoft.com/ericlippert/2011/05/26/atomicity-volatility-and-immutability-are-different-part-one/
https://blogs.msdn.microsoft.com/ericlippert/2011/05/31/atomicity-volatility-and-immutability-are-different-part-two/
https://blogs.msdn.microsoft.com/ericlippert/2011/06/16/atomicity-volatility-and-immutability-are-different-part-three/