并发任务分配问题

这是在工作中遇到的实际问题和解决过程。问题已经被抽象成并发任务的分配问题。

问题

如果有 n 组数据均分给 m 个处理器处理,那么每个处理器分到的数据是 \(\lceil \frac{n}{m} \rceil\) 。如果n组数据的类型有差异,其中有a组是一类数据,剩余 n-a 组是另一类数据。只有同类数据才能被一次性处理,那么该如何分配?

这个问题在现实中是存在的。比如HTTP并发请求处理一些数据。数据被批量送来,但类型不一样。为了节省耗时,我们希望并发处理这些不同的数据。并发数是确定好的。现在需要计算每个请求处理的数量,以便我们能给每一个请求打包数据。

求解

n 组数据交给 m 个处理器处理,每个处理器最多分到 \(\lceil \frac{n}{m} \rceil\) 组数据,这是毫无疑问的。如果 n 组数据中有a组是一类数据,n-a组是另一类数据。同类数据必须分配到同一个处理器。那么a类数据得到的处理器的数量是 \(\lceil \frac {a} {\lceil \frac{n}{m} \rceil} \rceil \),b类得到的处理器的数量是 \(\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil \)。我们现在其实需要考虑它们总共需要的处理器数量和m的关系。原有的m个处理器是否满足这种需求?如果不满足,需要多少个处理器才能满足?

即,求 \(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \) 和 m的关系。

对于上面的问题,我们的存在一些已知的前提条件:

  1. m, m 为正整数
  2. \(n \leq m\)

根据上面已知的条件,我们可以得出一些引理:

  1. \(\lceil \frac {n}{m} \rceil \geq \frac {n}{m} \)
  2. \( \lceil \frac {n}{m} \rceil \leq \frac {n}{m} + \frac {m-1}{m} \)

因此,容易得出\(( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \geq \lceil \frac {n}{\lceil \frac {n}{m} \rceil} \rceil \geq m \)

即数据类型分成两种的时候所需要的处理器数量是大于等于m的,原先的处理器个数可能不够用了。那么多少才够用?这是现在需要考虑的问题。

容易得出,\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil ) \leq \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \)

根据上面的引理可以得出 \( \lceil \frac {am}{n}\rceil + \lceil \frac {(n-a)m} {n} \rceil \leq \frac {am}{n} + \frac {n-1}{n} + \frac {(n-a)m} {n} + \frac {n-1}{n} = n+2-\frac{2}{n} \)

由已知条件可以知道,\( ( \lceil \frac {a}{\lceil \frac{n}{m} \rceil} \rceil +\lceil \frac {n-a} {\lceil \frac{n}{m} \rceil} \rceil )\) 是正整数,因此可以将 \( n+2-\frac{2}{n} \)向下取整为\(n+1\)。

即需要n+1个处理器才能满足要求。

因此遇到这种问题的时候,要么增加一个处理器,要么计算每个处理器能处理的数量的时候在原先处理器数量减一的基础上计算。

布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法

引言

在介绍布隆过滤器之前我们首先引入几个场景。

场景一

在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0。但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿?

有人说, 将这个key的值置为0存入缓存不就行了吗?这是确实是一种解决方案。当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存。不过这样做的缺点也很明显:浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中,我们需要设置很多黑名单内容。比如一个邮件系统,我们需要设置黑名单用户,当判断垃圾邮件的时候,要怎么去做。比如爬虫系统,我们要记录下来已经访问过的链接避免下次访问重复的链接。

在邮件很少或者用户很少的情况下,我们用普通数据库自带的查询就能完成。在数据量太多的时候,为了保证速度,通常情况下我们会将结果缓存到内存中,数据结构用hash表。这种查找的速度是O(1),但是内存消耗也是惊人的。打个比方,假如我们要存10亿条数据,每条数据平均占据32个字节,那么需要的内存是64G,这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路,查询的速度是O(1),消耗内存特别小呢?前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态(是或者不是,存在或者不存在),那么对于所存的数据完全可以用位来表示。数据本身则可以通过一个hash函数计算出一个key,这个key是一个位置,而这个key所对的值就是0或者1(因为只有两种状态),如下图:

(更多…)

你可能还喜欢下面这些文章

设计模式:观察者模式介绍与应用场景

简短描述在观察者模式中,有一个主题和几个观察者,主题状态改变之后会通知到所有的观察者。现实中的观察者模式观察者模式和现实世界很好对应。比如我和我的朋友们购买了今年一年的报纸,每次报社印刷了今天的报纸之后就会往我这里送。在这个系统里面,“报社“是一个主题,“我和我的朋友们”就是一个观察者,当“报社”生产报纸之后,“我和我的朋友们”都能收到这份报纸。根据上面的描述,我们很容易写出一个观察者模式。首先定义一个报社作为主题,然后定义一些用户作为观察者。不过在此之前,我们先定义主题和观察者的接口,毕竟我们是面向接口编程。定义一个主题接口namespace ds\observer\contract;/**

设计模式:装饰器模式介绍和应用

简短描述当前有一个功能完善的对象,如果我们想要给这个对象添加一个新的职责,那么我们可以用一个新的类去装饰它来实现对原有对象职责的扩展。新的类称为“装饰者”,原有的对象称为“被装饰者”。这种模式被称为装饰器模式。现实生活中的装饰器模式装饰器模式在现实生活中的例子简直太多了。比如我开了一个奶茶店,卖的是普通的奶茶。现在我想引入一个叫珍珠奶茶的商品,我要怎么做呢?我是不是需要升级一下我的制作奶茶的机器,让它支持珍珠奶茶的做法?但这种成本估计比较高,说不定还没原来做奶茶的机器好用呢!实际上我只需要买一个能做“珍珠”的机器就行!把“珍珠”放进奶茶不就成了珍珠奶茶。原有的做奶茶的机器依然可以稳定地制作做奶