队列二级取模方案的数学陷阱及其优化的理论和实践稿件

1、队列二级取模方案的数学陷阱及其优化的理论和实践山西项目组 张大朋 2010/8/1摘要由于电信业务的特点，电信类软件系统所面临的任务压力都比较大。为了能够快速处理大量任务，通常会采用多进程+多线程的方式来进行并发处理。这时候对各进程和各线程的任务分配是必不可少的工作，采用取模的方法对原始任务进行分解处理是简单可行的一种方案。利用这种方法将原始任务序列进行1次取模任务分配时，我们可以很容易确定分配结果是均匀公平的。由于人类固有的思维惯性，大部分人会把这种均匀性分配的认识推广到2次取模分配上，然而事实并非如此，这里存在一个巨大的陷阱，而这个陷阱和分配的进程数与线程数存在着确定的数学关系。本文在通过

2、对这些数量关系研究的基础上，给出了一些推论，并给出了自己的推导证明，希望这些推论可以让我们在日后timer优化及相似事情的处理上避开一些逻辑陷阱。事件背景在日常的维护工作中，发现电信业务存在一个典型的特点：每个月的月初和月末的几天里，是业务受理高峰，这比平时要高出很多。系统中流动的业务数据量也在这几天内急速飙升至最高值，并经常刷新纪录。因此这些时段也最能考验我们的软件系统的受压能力，而大部分情况下，我们系统中负责业务处理的timer都会瘫痪掉，造成系统大量压单，我们最繁忙的工作就是不断重起这些timer应用程序。本月月末，依然未能幸免，状态机timer压单严重。我们保持5个进程不变，把每个进程

3、的线程数由原来的7个提高到10个，期望通过提高并发处理能力来缓解业务压力。但是第2天，我们并未看到预期的效果，而状态机timer压单量已经飙升至15000，成为历史最高点。这时候，项目经理在对timer滚动输出的日志中敏锐的发现到系统中存在好多线程在空跑，进一步检查数据库心跳，发现果然很多线程在执行空的循环，在巨大的任务压力面前居然还有线程不干活，真是可恶。项目经理立刻意识到是昨天调整线程数造成的，当把这个问题提出来后，我们感觉到线程数10这个数字存在问题，凭直觉建议改用素数，于是我们把线程数从10调成13，结果发现所有线程都在工作了，在对数据的监控中，我们也感觉到了状态机处理速度在加快。初步

4、分析为了后续说明的方便，这里对状态机timer的任务分配机制进行简单的介绍。状态机Timer的主要任务是对业务定单对应流程实例的状态的转换，以驱动流程流转。在一个定单的流程实例生成时，流程实例的主键proc_inst_id由数据库sequence生成，作为流程实例的唯一标识。同时会将该主键对状态机timer的进程数取模，取模结果记入流程实例的subarea_no字段，作为将来状态机timer进程任务分配的依据。进程从0开始编号，n个进程，编号依次为0、1、2、 n-1，0号进程只处理subarea_no为0的流程实例，依此类推。每个进程分配到相应的任务数据后，会根据配置文件中的线程数参数，并发

5、出m个线程来分摊处理这些任务数据，每个线程拥有一个线程号作为自身标示，线程号从0开始，一直到m-1，线程的任务分配是在每个线程提取数据时完成的，线程在提取数据时，同样拿proc_inst_id对线程数取模，每个线程只处理余数等于自身线程号的那批数据。现在我们来分析一下前面说的5个进程、10个线程的组合为什么会导致很多线程为空，是偶然还是必然？前面说过，状态机处理的目标是一堆流程实例记录，而流程实例可以由主键proc_inst_id唯一标示，我们不妨将这一堆任务抽象为一堆由proc_inst_id组成的数字序列，序列中的每个数字标识其对应的任务。现在我们给每个进程分配任务，不妨假设有z个数据、n

6、个进程、每个进程对应m个线程，现在n=5，m=10。由于proc_inst_id是由数据库sequence生成，因此它是一个步长为1的等差数列，考虑到各种因素的干扰，导致最后状态机每次提取到的数据并不严格是一个等差数列，但是从宏观上看，不影响我们这里等差数列的假设，因为大部分情况下是。为了演示的方便，我们把这个数列向前平移，变为一个初值为1、步长为1的等差数列，显然这个动作也不会影响我们的取模分配。那么我们开始给进程分配任务，将这个等差数列对n=5取模，因为步长为1，所以每个proc_inst_id取模结果必然顺次落到0、1、2、3、4上，这样每个proc_inst_id就归属于对应的0、1、

7、2、3、4号进程的任务队列里，为了演示方便，我们取z=100来看看进程任务分配的结果：0: 5 1015202530354045505560657075808590951001:1 61116212631364146515661667176818691962:2 71217222732374247525762677277828792973:3 81318232833384348535863687378838893984:4 9141924293439444954596469747984899499注：1代表一号进程，其后代表它的任务队列和我们想象中的一样，任务被5个进程平均分配了，接下来我们再

8、对每个进程的10个线程进行任务分配。首先一点必须想明白，0号进程各线程的分配结果与其它进程的各线程的分配结果是一致的，这里的一致是指结果呈现出来的分布情况。现在以0号进程各线程的分布为例，如下：00:10203040506070809010001:02:03:04:05:515253545556575859506:07:08:09:注：05代表0号进程的第5号线程，其后是它的任务队列从上图可以看出来，0号进程的全部任务只是平分给了0号线程和5号线程，其它8个线程都没有分配到任务，恐怖吧。同理我们可以推断1号进程只有1号线程和6号线程分到了任务，其它以此类推。如此看来，把7个线程提高到10个线程

9、，线程总数增加到5*10=50个，比5*7=35个增加了15个，但是有效工作线程却变成了5*2=10个，比原来的5*7=35反而减少了25个！而空跑的线程依然会消耗cpu资源，依然会连接数据库提取数据，虽然没有提到。下面我们来分析一下，为什么会造成这个结果。在对进程的任务分配时，没有问题，一个步长为1的等差数列对5取模分配的结果是均匀的，5个进程平分了这些任务。这时候，有一个规律：0号进程的任务队列上都是5的倍数，记为5x+0（x=1，2，3，z/5）；1号进程的任务队列上都是5的倍数加1，记为5x（x=1，2，3，z/5）；以此类推。我们以0号进程为例，进行线程的任务分配，这等价于拿5的倍数

10、序列5x+0（x=1，2，3，z/5）来对10取模运算，可以看到结果只有两个0和5，对应的序列为5x（x=1，3，5，z/5）和5x（x=2，4，6，z/5），这里最后的z/5一个是奇数一个是偶数，没有太大影响。可以看出这个序列要么能被10整除从而归集到0号线程，要么不能被10整除能被5整除而归集到5号线程上。我们再讨论1号进程各线程的任务分配规律。1号进程的任务队列为5x+1（x=1，2，3，z/5），对10取模。同样10=5*2，固定x为偶数（2，4，6，），得到序列为5x+1（x=2，4，6，z/5）=10x+1（x=1，2，3，）这些对10取模的结果必然都是1，其它数字组成的序列5x+

11、1（x=1，3，5，z/5）对10取模的结果必然是5+1=6。因此，1号进程的任务最终都只平分给了1号和6号线程。继续对2号进程的各线程分配任务。2号进程的任务队列为5x+2（x=1，2，3，z/5），因此任务分配公式为5x+2（x=1，2，3，z/5） mod 10，可以得到下面结果：故，得到2号进程的任务只平分给了2号线程和7号线程。同样的道理，可以推广到3号进程、4号进程。看来，“5个进程、10个线程”的组合导致大量线程空跑是必然的结果了。当我们把进程数调成5个、线程数调成13个，发现每个线程都在工作了，每个线程的任务队列里都有数据了。但是这儿还有一个问题：这种搭配最后的分配结果是均匀的

12、么？有没有最佳的进程数与线程数的组合呢？均匀分配到底和进程数与线程数有没有必然的关系呢，如果有那是怎样的关系呢？抱着这些疑问，我对这个数量关系进行了一些研究，并得到了一些令我激动的结论，现在和大家分享交流一下。理论为了叙述不致混乱，这里给出本文的几个定义，在以后的论述中，会引用这里的定义： 定义1：初值为1、步长为1的等差数列，记为Q定义2：对Q第1次取模任务分配时，称为“将Q一级取模分配”，若模数为n，则称“将Q对n一级取模分配”；同样的，将Q对n一级取模分配之后，再将各结果队列对m进行取模任务分配，称为“将Q二级取模分配，一级模数为n，二级模数为m”定义3：将Q对n一级取模分配，分配结果各

13、队列依次标记为0号队列、1号队列、号队列、n-1号队列定义4：对于定义3中的各分配结果队列，如果不为空队列，则对应的队列编号称为归集点。显然，对于模数n，归集点只能是0、1、2、n-1中的若干个定义5：将两个归集点对应队列的编号之差，称为“归集点的间隙”定义6：自然数n与m的最小公倍数记为gb(n,m)，最大公约数记为gy(n,m)为了论述的简洁，这里对原始问题进行了相关处理：处理1：设定n<m，这是从经验来看的，一般来说进程总数会小于每个进程的线程数，这个设定会在本文的后续部分消解掉。处理2：将任务数列看成一个严格的初值为1、步长为1的等差数列，这个设定会在本文的后续部分消解掉。下面给

14、出这类问题的几条结论，然后对部分结论进行了推理证明：公理：在对数列Q进行任意数取模分配时，结果都是均匀的，即0号队列、1号队列、号队列、n-1号队列，各队列中的数据量相差不超过1。这个无需证明，是显然的事情。推论1：将Q二级取模分配，一级模数为n，二级模数为m。则一级分配结果的0号队列在二级取模分配时以gb(n,m)为最小周期向外扩散；并且均匀在gy(n,m)的各倍数（不大于m）点上，即归集点为x* gy(n,m)，其中x=0，1，m/gy(n,m)。证明：易得1级分配结果的0号队列为Q0=nx(x=1,2,3,z/n)n与m的最大公约数是gy(n,m)令n= a* gy(n,m)，m= b*

15、 gy(n,m)，其中，a与b互质，a、b是自然数从而有Q0= a* gy(n,m)*x(x=1,2,3,z/n)我们将x从1开始，逐渐增大，可以看到Q0在对m取模的结果情况：当x=1，n<m n mod m = a* gy(n,m)这里可以看到取模结果为gy(n,m)的整倍数，为n本身当x=2，2n mod m= 2a* gy(n,m)这里可以看到取模结果为2n，依然是gy(n,m)的整倍数当x=，使得*n>m时，有*n > m *a* gy(n,m) >b* gy(n,m)*a>b不妨设*a=b+c，这里c是一个自然数*n=*a* gy(n,m)=(b+c)

16、* gy(n,m)=b * gy(n,m)+c * gy(n,m)从而有*n mod m =( b * gy(n,m)+c * gy(n,m) mod b* gy(n,m)=0+ c * gy(n,m)= c * gy(n,m)可见，模的结果依然是gy(n,m)的整数倍。当x= gb(n,m)/n，此时Q0序列当前值为gb(n,m)/n*n= gb(n,m)，即n与m的最小公倍数，它对m取模结果必然为0这时候，如果我们继续增大x，即x=gb(n,m)/n+1，得Q0序列当前值为gb(n,m)+n于是有，(gb(n,m)+n) mod m = gb(n,m) mod m + n mod m =0

17、+n mod m =n mod m，这等价于x=1时的情形。当x = gb(n,m)/n+2，显然等价于x=2时的情形至此，可以得到结论，这种取模的结果是周期性的，并且以gb(n,m)为周期，第1个周期即为n,2n,gb(n,m)，这个周期内的数字对m取模结果决定了整个Q0序列对m的取模结果，后续的取模也只是对第1个周期的重复。另外，在回头看x=时，可以证明在第一个周期内，Q0序列值对m取模的结果都是gy(n,m)的整数倍，由于上面证明了取模的周期性，因此这里的结论也随之扩展至整个序列，因此可以证明整个Q0对m取模的结果都是gy(n,m)的整数倍。综上，推论中的两点得到证明。推论2：将Q二级取

18、模分配，一级模数为n，二级模数为m。则一级分配结果的号队列再二级取模分配，分配结果的分布情形同0号队列，归集点为(x* gy(n,m) +) mod m，其中x=0，1，m/gy(n,m)。证明：在推论1中，我们已经证明了0号队列Q0= a* gy(n,m)*x(x=1,2,3,z/n)的归集点为x* gy(n,m)。对于号队列，有Q= a* gy(n,m)*x+ (x=1,2,3,z/n ；=0,1,n-1)，不妨记作Q= Q0+ Q0 mod m = x* gy(n,m) Q mod m =( Q0+) mod m=( Q0 mod m)+( mod m)= x* gy(n,m)+ 考虑到

19、x* gy(n,m)+ 会大于m，因此这里再次对m取模，即归集点为(x* gy(n,m) +) mod m命题得证。推论3：二级取模任务分配方案的最终效果（归集点、归集间隙）只与进程数和线程数紧密相关，与原始任务序列的起始值无关，与原始任务序列的长度及结束值无关证明：此命题由推论1中的推理过程容易得到，这里就不在熬述了。此推论可以消解上面假定原始任务序列起始值为1的处理。理论应用通过以上推论，可以得出以下与实际的任务分配问题相关的实用结论：结论1：当线程数与进程数互质时，最终的线程任务分配是均匀的，各线程任务队列相差最多不超过1。单从分配均匀的角度来说，这里的分配结果都是最优的。结论2：当线程

20、数与进程数存在除1以外的公约数时，必定存在线程不会分配到任务，并且可以确定每个进程只有gb(n,m)/n个线程平分掉全部的任务。结论3：对于0号进程，只有线程数与进程数最大公约数的倍数号线程被均匀分配到任务，即归集点在最大公约数的倍数上；对于号进程，归集点比0号进程的分配结果平移结论4：线程数与进程数的最大公约数逾大，则最终的任务归集点之间的间隙逾大，归集点逾少。结论5：进程数与线程数的最小公倍数决定了最终一个取模周期中归集点的个数，进程数与线程数的最大公约数决定了最终一个取模周期中两个归集点之间的间隙。对应的公式如下： 归集点个数 =gb(n,m)/n归集点间隙 =gy(n,m)举例说明：举

21、例1：我们再回过头来看看5个进程、10个线程的组合。最大公约数是5，最小公倍数是10。应用结论2可知，采用二级取模分配，结果每个进程只有gb(5,10)/5 =10/5 =2个线程在分摊进程的任务，其它线程都在空跑；应用结论3可知，0号进程只有0号线程、5号线程上有任务队列，是归集点；1号进程只有1号线程和6号线程上有任务队列，应用结论5，可知每个进程的归集点的个数为gb(n,m)/n =10/5 =2，归集点间隙= gy(n,m) =5举例2：5个进程、13个线程的组合由于5和13互质，因此只须应用结论1，即可判定，这个分配是均匀的，每个线程都会分配到同样多的任务。也可以通过结论2或结论5得

22、到：归集点个数 =5*13/5=13，即是每个线程都是一个归集点；归集点间隙= gy(n,m) =gy(5,13)=1，即是紧挨着的。举例3：12个进程、18个线程的组合最大公约数为6，最小公倍数为36。应用结论5，得：归集点个数 =36/12=3，归集间隙是6应用结论3，知：0号进程只有0号、6号、12号线程上分配到了任务可见，一共12*18=216个线程，只有12*3=36个线程在干活，其它线程都在白白的浪费系统资源。因此如果你为了增大并发处理能力，缓解系统压力，而把5个进程13个线程的组合调整为12个进程、18个线程的组合是得不偿失的。理论扩展在上面的理论论述部分作了两个特殊处理，下面来

23、消解这两个处理。上面的假设中，把每次状态机提取到的原始任务序列假设成一个严格的步长为1的等差序列，显然和实际情况相差较大。我们不妨再回归本原，它其实就是一个无规律的无重复自然数列，经过第1次取模分配后，可以肯定，0号进程中的数据肯定都是5的倍数，1号进程中的都是5的倍数+1，依此类推。在第2次取模分配时，我们以0号进程为例，同样可以得到在5的倍数中，能被10整除的都归集在0号线程上，不能被10整除的都归集在5号线程上；同理可以推广到1号进程、2号进程的分配情况。可见，原始数据序列的杂乱不会影响第2次的取模分配，而只会影响第1次的取模分配不均匀。而从宏观来说这些不确定是可以被内部平衡掉的，因此这

24、些都不会影响上面的推理。上述结论都是在n<m的条件下得到的，对于n>=m的情况，我们也可以得出类似的结论，不过如果n=m或者n是m的倍数，那最后是每个进程在单线程作业，其它线程都在空跑了，限于篇幅，类似的结论就不再给出了。提高timer的工作效率必然给系统带来压力，本文没有考虑接口机系统负荷、应用服务器系统负荷以及最终的数据库服务的负荷。因此，在实际调优过程中仍需要谨慎考虑到各方面因素的影响。当然如果时机成熟，我们可以建立一个更大点的数学模型来研究timer应用的优化问题。总结本文仅仅从任务分配的角度研究了timer的优化问题，而且仅仅是针对文中所述的类似状态机timer所采用的二

25、级取模分配方案，进行了相关推测，并给出了证明。希望在以后的timer参数设置过程中，可以以此为基础，遵循“线程数与进程数互质”的规则，避开相应的逻辑陷阱。当然，如果开始就没有使用这种二级取模分配方案，也就不会有这个问题存在了，以上分析仅供参考，相关分析证明也难免存在不严谨的地方，欢迎批评指正。附录附录1：二级取模分配模拟程序这里给出了一个简单的模拟二级取模分配方案的程序，可以用来验证上面的结论。可以设定不同的初值、长度的数列来模拟原始任务序列；可以查看一级取模分配结果，即各进程对应的任务队列；可以查看指定进程对应线程的二级取模分配结果，即x号进程对应各线程的任务队列。package mod;i

26、mport java.util.ArrayList;import java.util.List;/* * 二级取模任务分配模拟程序 * 此类问题有一个明显特点，原始任务是一组以有序数列为特征标识的， * 因此对原始任务的分配就变成了对纯粹数据序列的分配 * * 本程序通过模拟状态机timer对进程和线程的任务分配，可以直观的看到 * 不同的进程数与线程数组合搭配后，最终任务分布的效果 * * 调节不同的进程数与线程数，来预测线程任务队列的分布情况 * author zdp * since 2010-7-29 */public class ModTest public static void m

27、ain(String args) ModTest test = new ModTest();/ 数据总量，任务总量int dataCount = 1000;/ 任务起始特征值int start = 1; /222199/ 进程数int processCount = 12;/ 线程数int threadCount = 18;/ 数据序列，任务数据的特征值，任务分配的源int dataSeq = new intdataCount;/ 进程分配结果int processData = new intprocessCount;/ 线程分配结果int threadData = new intprocess

28、CountthreadCount;/ 初始化数据源：生成连续数据序列System.out.println("初始化数据源：生成连续数据序列");dataSeq = test.initDataSourse(dataCount, start);/ 模拟一级分配：将数据总量按进程数取模分配System.out.println("一级分配：将数据总量按进程数取模分配");List xList = test.split(dataSeq, processCount);for (int i = 0; i < xList.size(); i+) List<I

29、nteger> x1 = (ArrayList) xList.get(i);processDatai = test.toArray(x1);test.print2Array(processData);/ 模拟二级分配：将各进程分到的任务量再按线程数取模分配System.out.println("二级分配：将分到的任务量再按线程数取模分配");for (int i = 0; i < processData.length; i+) List yList = test.split(processDatai, threadCount);for (int j = 0; j

30、 < yList.size(); j+) List y1 = (ArrayList) yList.get(j);threadDataij = test.toArray(y1);test.print3Array(threadData, 0);/ 打印3号进程对应全部线程的任务分配队列System.out.println("结束-");/* * 初始化数据源，原始任务数据模拟 * * param total * 任务总量 * param start * 任务起始特征值 * return */public int initDataSourse(int total, int

31、start) / 声明数据源int Z = new inttotal;for (int i = 0; i < total; i+) Zi = start+;return Z;/* * 任务分配（核心思想） 将数据序列取模放到一个二级List中 */public List split(int data, int mod) / 初始化一个二级ListList X = new ArrayList();for (int i = 0; i < mod; i+) X.add(new ArrayList();/ 将任务数组分配到相应的list中for (int i = 0; i < dat

32、a.length; i+) int index = (datai) % mod;(ArrayList) X.get(index).add(datai);/ 如此以来，X中的mod个list就分到了数据，然后并发mod个线程来对应处理return X;/ 打印二维listpublic List print2List(List X) for (int i = 0; i < X.size(); i+) System.out.println("X" + i + " =" + X.get(i);return X;/ 打印二维数组public void print2Array(int data) for (int i = 0; i < data.length; i+) System.out.print(&