0%

计数器及其应用

一个计数器很平凡,一组计数器却很伟大。上市公司的财报,会计的复式记账,其计算最终归结为计数器;《增长黑客》里说的数据化运营,无论分析的角度多么复杂,其计算最终依然归结为计数器。道家说:一生二、二生三、三生无穷。计数器就是这个能生无穷的一。

功能定义

计数器简单来说,就是实现 incr("key", delta) 逻辑。举个例子incr("长安十二时辰", 1),表示电视剧《长安十二时辰》的播放数加1。一个语义完备的计数器应该包含如下几个操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
interface Counter {

long incr(String key, long delta);

long incrIfLessThan(String key, long delta, long ceilingMark);

long decr(String key, long delta);

long decrIfMoreThan(String key, long delta, long floorMark);

Long get(String key);

boolean exists(String key);

boolean resetIfExisted(String key);

}

这么一个平淡朴实的东西,似乎让人提得起兴趣?下面说说它的应用场景,我们可能就会刮目相看了。

应用场景

计数器在互联网领域的应用非常之广泛,比如:

  • PV统计: 使用incr(String key, long delta);decr(String key, long delta);方法。

    • 门户网站某个页面的阅读数量。视频网站某个视频的播放数量。图片分享网站某个图片点赞数量等。
    • CTR动态调权:百度和Google给用户展示预测点击率最高的广告,如果用户没点击,则CTR下降,如果点击了,则CTR上升。其中CTR就是点击次数除以展示次数,点击和展示都是计数器。这个模型因为有了正/负反馈机制,从《控制论》角度说就具备智能了。今天的抖音,快手,滴滴,外卖的智能推荐或调度,简单来说都是基于这种计数器基础,借助深度学习,对海量标签,进行隐形搜索排名的结果。
      google-ctr
  • 撞线控制: 使用incrIfLessThan(String key, long delta, long ceilingMark);decrIfMoreThan(String key, long delta, long floorMark);方法。

    • 广告投放的日预算控制,广告主当天累计花销达到日预算阈值时,则需要暂停广告投放。
    • 广告投放的频次控制,依据The Three Hit Theory,一个广告创意应该不多不少得给潜在消费者看3次——少了,消费者记不住;多了,消费者厌烦,广告主还浪费广告位投放费。其中“多了不再投放”就需要计数器来控制。
    • 电商促销的“低价限购”,每人只限购2件,又或者免运费促销,前多少单免运费。
    • CDN调度,当把一个用户的视频播放请求,调度到某个CDN节点时,应该对该节点的剩余产能(比如带宽)进行扣减。
    • 风控领域,为了防止机器暴力破解用户密码,往往会在输入密码时,下发一个验证码图片,以区分人类和机器。但是每次输入验证码对用户体验有损,折中的办法是,只当短时间内,错误密码出现三次以上时,才下发验证码。
  • 复式记账: 大家都知道会计领域普遍使用复式记账,这个记账的账本,从程序设计的角度看,它的本质是一组计数器的事务或说一组事务性的计数器。简单解释下这个概念。假设我们去沃尔玛买东西,买了40元面包、30元牛奶、80元车用玻璃水,累计150元,用了一张30元的优惠券,再用微信付了120元。复式记账的一个特点就是把一切都看成账户,不仅优惠券是账户、微信是账户,而且连实物的面包、牛奶和玻璃水都可以是账户。于是这笔账可以记录为:

面包账户 牛奶账户 玻璃水账户 优惠券账户 微信账户
+40 +30 +80 -30 -120

这条记账的各账户变动的总和为零,且必须原子性,需要全部执行才算成功,否则失败就全不执行。写成事务的伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
transaction.start();
try {
incr("面包账户", 40);
incr("牛奶账户", 30);
incr("玻璃水账户", 80);
decr("优惠券账户", 30);
decr("微信账户", 120);
transaction.commit();

} cache(Exception e) {
transaction.rollback();
}

看到这,我们不禁发出感叹:

会计之美:计算机直到遇见大数据才催生了列式存储,会计上的复式记账却早就蕴含了列式存储的思想,早到1千多年前的威尼斯商贸中心时期。当我们用微信,花10元,买了个面包。多数人会想微信账户少了10元,极少有人能把面包也作为一个账户。这个观念上的突破,美丽至极! 它一下子把任何一笔交易的记账变成了多账户间的转账,且和恒等于零,具有自纠错能力。更重要的是从代数系统的角度,它统一了元运算,统一到一个简单的计数器,接着记账被定义为一组计数器的事务,然后再套上会计准则,就可以描述一切的商业活动。瞬间有种道家所说的“一生二,二生三,三生万物”的感觉。这里的一就是计数器,二就是一组计数器的事务,三就是会计准则,万物就是一切商业活动

什么是会计准则呢?简单理解就是实际的会计中,不会把面包、牛奶等真当做一个账户,而要遵循一些约定俗成的分类和操作规则,比如面包和牛奶都归为维持劳动力再生产的原材料,把玻璃水归为低值易耗品,把微信归为现金,把优惠券姑且当做其他应收款吧(笔者并不严格懂会计分录),这笔账则记为:

原材料 低值易耗品 现金 其他应收款
记账 +70 +80 -120 -30
备注 40元面包和30元牛奶 玻璃水 微信支付 优惠券

如果紧接着用支付宝,买了牛腩和西红柿,记明细账会是:

面包账户 牛奶账户 玻璃水账户 牛腩账户 西红柿账户 优惠券账户 微信账户 支付宝账户
+40 +30 +80 -30 -120
+30 +5 -35

这么看来,账本便是一个稀疏矩阵:横看是业务流水,记录每笔交易或说业务事件;竖看是账户变动,记录账户变迁史和当前账面值,前者像是录像机录制的一段视频,后者像是照相机抓拍的一张照片,或者说前者的视频就是后者一系列不同时间定格的瞬间串联起来的动图。

另外,从账本的账户是否可随时新增的角度,可分为“自由账本”和“标准账本”。前者是随着记账的需要,可以随时新增账户;而后者则是记账前,就预先明确了账户,过程中几乎不增加。

两类实现

一般来说,计数器实现分两大类:

  • 实时计数
    • 应用层实现
    • Redis实现
    • MySQL实现
  • 流式计数:简单说就是先顺序写日志,再快速回放日志计数。为什么要这样?因为高并发场景下,实时计数会有损性能,阻塞写入端。在写入端,先写日志,用的是磁盘的顺序写操作,速度很快,关键不在应用层产生资源竞争;然后在读取端,重放日志,开始计数,并提供在线读取。这样绕了一圈,自然无法实时计数,但多数场景下,我们只需要准实时计数。

并发计数原理

在并发环境下需要考虑两处Lost Update的情况。

  • 累加不丢失:在计算机内部,执行一次累加,需要执行3步:先从内存中读取变量到寄存器;再通过运算器对寄存器累加;后把寄存器的最新值写入内存变量。

    • 错误的并发时序:由于并发控制不当,Tb覆盖掉了Ta累加的中间结果。这就叫Lost Update
    时序 备注 Ta Tb
    0 初始值:key = 10
    1 Ta读取key值 GET a <= key;
    2 Tb读取key值 GET b <= key;
    3 Ta加法计算 ALU a = a + 2;
    4 Tb加法计算 ALU b = b + 3;
    5 中间值:key = 12 SET key <= a;
    6 最终值:key = 13 SET key <= b;
    • 正确的并发时序:Tb在Ta的基础上再累加,就不会丢失。
    时序 备注 Ta Tb
    0 初始值:key = 10
    1 Ta读取key值 GET a <= key;
    2 ALU a = a + 2;
    3 中间值:key = 12 SET key <= a;
    4 GET b <= key;
    5 ALU b = b + 3;
    6 最终值:key = 15 SET key <= b;

  • 空置不丢失

    • 错误的并发时序:由于并发控制不当,Tb覆盖掉了Ta累加的中间结果。这就叫Lost Update
    时序 备注 Ta Tb
    0 初始值:key = null
    1 GET a <= key;
    if (a == null)
    2 GET b <= key;
    if (b == null)
    3 中间值:key = 2 SET key <= 2;
    4 最终值:key = 3 SET key <= 3;
    • 正确的并发时序:
    时序 备注 Ta Tb
    0 初始值:key = null
    1 GET a <= key;
    if (a == null): TRUE
    2 中间值:key = 2 SET key <= 2;
    3 GET b <= key;
    (b == 2) != null
    4 ALU b = b + 3;
    5 最终值:key = 5 SET key <= 5;

应用层实现

如果用Java描述,一个参考实现是 mydk#ConcurrentCounter.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private ConcurrentHashMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();

@Override
public Long increaseAndGet(String key, int delta) {
AtomicLong c = map.get(key);
if (c == null) {
c = new AtomicLong(0L);

// 用ConcurrentHashMap的putIfAbsent做到空置不丢失
AtomicLong pre = map.putIfAbsent(key, c);

// 乐观锁概念:如果冲突了,能检测出来,再勘正即可。
if (pre != null) {
c = pre;
}
}
// 用AtomicLong做到累加不丢失
return c.addAndGet(delta);
}

当然如果我们真需要在应用层计数,这里还是推荐专门的metrics库:

1
2
3
4
5
<dependency>
<groupId>io.dropwizard.metrics</groupId>
<artifactId>metrics-core</artifactId>
<version>3.1.2</version>
</dependency>

它的好处是有配套的报表,包括日志的、CSV的、MBean的。还有开源生态,比如推送到Influxdb,可以支持多个维度的展开;再跟Grafana整合,可以可视化地制作各种绚丽的报表,而且能自动刷新实时监控。还可以配置各种阈值和智能检测,并对异常波动进行告警和推送。

1
2
3
4
5
6
7
8
9
MetricRegistry metricRegistry = new MetricRegistry();

String videoKey = MetricRegistry.name(CounterDemo.class, "vv", "长安十二时辰");

// get or add counter for the specified name
Counter videoView = metricRegistry.counter(videoKey);

// 并发计数
videoView.inc();

Redis实现

Redis默认就支持计数器操作,包括INCRBYHINCRBY等操作:

1
2
3
4
5
6
7
8

# 如果 key 不存在,那么 key 的值会先被初始化为 0 ,然后再执行 INCRBY 命令
redis 127.0.0.1:6379> INCRBY KEY_NAME INCR_AMOUNT

# Hincrby 命令用于为哈希表中的字段值加上指定增量值
redis 127.0.0.1:6379> HINCRBY KEY_NAME FIELD_NAME INCR_BY_NUMBER
redis> HINCRBY myhash field 1
(integer) 6

另外Redis还支持事务,也就是说,可以用Redis瞬间建设一个会计账本。如果一个账本的科目不多,用HINCRBY即可。其中KEY_NAME表示账本名称,FIELD_NAME表示账本内的科目名称。

之前沃尔玛购物的例子:

1
2
3
4
5
6
7
8
9
10
11
12
transaction.start();
try {
incr("面包账户", 40);
incr("牛奶账户", 30);
incr("玻璃水账户", 80);
decr("优惠券账户", 30);
decr("微信账户", 120);
transaction.commit();

} cache(Exception e) {
transaction.rollback();
}

就可以用Redis实现为:

1
2
3
4
5
6
7
8
redis 127.0.0.1:6379>
redis> MULTI
redis> HINCRBY 购物账本 面包科目 40
redis> HINCRBY 购物账本 牛奶科目 30
redis> HINCRBY 购物账本 玻璃水科目 80
redis> HINCRBY 购物账本 优惠券科目 -30
redis> HINCRBY 购物账本 微信科目 -120
redis> EXEC

当我们把记账理解为一组计数器的事务,这个观念突破后,Redis就可以实现一个多账本,可自定义科目的记账系统:Redis的transaction binlog就是它的流水账,当前的存储数据稍做汇总计算,就是资产负债表。

如果我们再调整下,用kafka来单纯的业务事件,业务事件就是采购、生产和销售环节的各种业务事件,比如用户下订单或退货等。kafka的消费侧,可以用MySQL记录流水过程,同时用Redis记录账户结果。一个简单,且实用的,支持多账本和可自定义科目的记账中台就浮出水面了

MySQL实现

在MySQL中实现,需要首先定义一张表,假设为:

1
2
3
4
5
CREATE TABLE `counter` (
`item_id` varchar(20) COLLATE utf8_unicode_ci NOT NULL,
`count` bigint(20) NOT NULL,
PRIMARY KEY (`item_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

我们用于一个存储过程实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
DELIMITER $$
DROP PROCEDURE IF EXISTS `proc_counter`;
CREATE PROCEDURE `proc_counter` (in item_id varchar(20),in incr bigint(20), out count bigint(20), out action INT)
BEGIN
DECLARE found bigint(20);
DECLARE dupli INT default 0;
DECLARE CONTINUE HANDLER FOR 1062 SET dupli=1;
START TRANSACTION;
SELECT c.count INTO found from `counter` as c where c.item_id =item_id;
IF found is null then
INSERT INTO `counter` VALUES (item_id, incr);
if dupli=0 then
set action=1;
else
UPDATE `counter` as c SET c.count=c.count+incr where c.item_id=item_id; set action=2;
end if;
set count=incr;
else
UPDATE `counter` as c SET c.count=c.count+incr where c.item_id=item_id;
set action=3;
SET count=found+incr;
END IF;
COMMIT;
END
$$

存储过程的方法签名:

类型 含义
输入参数
$item_id varchar(20) 计数对象Key
$incr bigint(20) 本次计数增量
输出参数
$count bigint(20) 本次计数完成后,
计数器当前取值。
$action INT 取值枚举:{1,2,3}
$action=1 表示第一次计数,且无并发冲突,
返回的$count是真实数值;
$action=2 表示第一次计数,但出现并发冲突,
返回的$count是过期数值;
$action=3 表示非第一次计数,
返回的$count是累加后的计数器取值。

上述代码需要略微解释的是语句:

1
2
3
> DECLARE dupli INT default 0;
> DECLARE CONTINUE HANDLER FOR 1062 SET dupli=1;
>

它定义了一个异常捕:对于MySQL抛出的ErrorCode=1062异常,也就是插入操作时的主键冲突,采取的行为是CONTINUE继续执行,而不是EXIST退出,继续执行SET dupli=1。这样当我们插入一个新的item_id的时,如果没有主键冲突,则dupli等于0;否则,主键冲突时,dupli会等于1。这就是空置不丢失乐观锁实现。

而对于“累加不丢失”,使用的是SET c.count=c.count+incr,具体的是:

1
UPDATE `counter` as c SET c.count=c.count+incr where c.item_id=item_id;

当“where c.item_id=item_id”记录存在时,UPDATE一个存在的主键是会触发行锁的,也就是“悲观锁”实现。

多维变种与流式计数

前面讨论的计数器,都是KV结构的,但实际应用中,我们往往还需要多维变种。还拿前面的例子incr("长安十二时辰", 1),它的一级分类是电视剧,二级分类是悬疑剧,如果我们还要统计分类播放数呢?设计个点分层级计数器,逻辑上它可以变换成多个普通计数器的事务:

1
2
3
4
5
6
7
8
9
10
11
12
13
incrHierarchy("电视剧.悬疑剧.长安十二时辰", 1) {
transaction.start();
try {
incr("电视剧.悬疑剧.长安十二时辰", 1);
incr("电视剧.悬疑剧", 1);
incr("电视剧", 1);
transaction.commit();

} catch(Exception e) {
transaction.rollback();
}

}

我们把点分层级看做一个树,上面实现逻辑就是层级追溯策略。

更进一步,如果我们还想知道它的时空分布呢?时间上,比如每天播放量,当然时间也可以有层级,比如“年.季.月.周.天”;空间上,比如每个城市播放量,当然时间上也可以有层级,比如“国家.区域.省份.城市”。由于时间和空间,两者没有交叠,我们把这种多维变种叫做正交分解计数器。逻辑上也可以变成多个普通计数器的事务:

1
2
3
4
5
6
7
8
9
10
11
12
13
incrOrthogonality("长安十二时辰", 1, new String[] {"2019/08/09", "北京"}) {
transaction.start();
try {
incr("长安十二时辰", 1); // 时空组合=00
incr("长安十二时辰.北京", 1); // 时空组合=01
incr("长安十二时辰.2019/08/09", 1); // 时空组合=10
incr("长安十二时辰.2019/08/09.北京", 1); // 时空组合=11
transaction.commit();

} catch(Exception e) {
transaction.rollback();
}
}

这种基于组合展开的策略本质上是空间换时间的优化策略。

层级与正交

我们综合下刚才的点分层级正交分解,从内容、时间和地域三个维度,考察一次播放行为,触发的一组计数器的事务

内容 时间 地域 语义
0 0 0 总播放量:不限内容不限时间不限地区从创办以来的总播放量
0 0 1 各地域的播放量
再按地域层级追溯:
全国.北京
全国
0 1 0 各日期的播放量
再按日期层级追溯:
2019.Q3.M08.2019/08/09
2019.Q3.M08
2019.Q3
2019
0 1 1 地域和日期的组合:2*4=8
全国.北京&2019.Q3.M08.2019/08/09
全国.北京&2019.Q3.M08
全国.北京&2019.Q3
全国.北京&2019
全国&2019.Q3.M08.2019/08/09
全国&2019.Q3.M08
全国&2019.Q3
全国&2019
1 0 0 各内容的播放量
再按内容层级追溯:
电视剧.悬疑剧.长安十二时辰
电视剧.悬疑剧
电视剧
1 0 1 内容和地域的组合:3*2=6
电视剧.悬疑剧.长安十二时辰&全国.北京
电视剧.悬疑剧.长安十二时辰&全国
电视剧.悬疑剧&全国.北京
电视剧.悬疑剧&全国
电视剧&全国.北京
电视剧&全国
1 1 0 内容和日期的组合:3*4=12
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08.2019/08/09
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08
电视剧.悬疑剧.长安十二时辰&2019.Q3
电视剧.悬疑剧.长安十二时辰&2019
电视剧.悬疑剧&2019.Q3.M08.2019/08/09
电视剧.悬疑剧&2019.Q3.M08
电视剧.悬疑剧&2019.Q3
电视剧.悬疑剧&2019
电视剧&2019.Q3.M08.2019/08/09
电视剧&2019.Q3.M08
电视剧&2019.Q3
电视剧&2019
1 1 1 内容、日期和地域的三维组合:3 * 4 * 2 = 24
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08.2019/08/09&全国.北京
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08.2019/08/09&全国
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08&全国.北京
电视剧.悬疑剧.长安十二时辰&2019.Q3.M08&全国
电视剧.悬疑剧.长安十二时辰&2019.Q3&全国.北京
电视剧.悬疑剧.长安十二时辰&2019.Q3&全国
电视剧.悬疑剧.长安十二时辰&2019&全国.北京
电视剧.悬疑剧.长安十二时辰&2019&全国
电视剧.悬疑剧&2019.Q3.M08.2019/08/09&全国.北京
电视剧.悬疑剧&2019.Q3.M08.2019/08/09&全国
电视剧.悬疑剧&2019.Q3.M08&全国.北京
电视剧.悬疑剧&2019.Q3.M08&全国
电视剧.悬疑剧&2019.Q3&全国.北京
电视剧.悬疑剧&2019.Q3&全国
电视剧.悬疑剧&2019&全国.北京
电视剧.悬疑剧&2019&全国
电视剧&2019.Q3.M08.2019/08/09&全国.北京
电视剧&2019.Q3.M08.2019/08/09&全国
电视剧&2019.Q3.M08&全国.北京
电视剧&2019.Q3.M08&全国
电视剧&2019.Q3&全国.北京
电视剧&2019.Q3&全国
电视剧&2019&全国.北京
电视剧&2019&全国

交叉转正交

刚才的《长安十二时辰》,我们归类为悬疑剧,但也有人归类为古装剧,实际上它的确是古装悬疑剧。这就是说,现实中有些分类的类型似乎不是正交的,而是交叉的,会存在一些电视剧,既属于A,又属于B。

这是因为“内容”可以进一步细分成多个正交的维度,比如:

  • 故事题材:悬疑、情感、偶像、军旅
  • 故事时间:古代(古装)、近代(年代)、现代
  • 制作产地:内地、香港、台湾、日本、韩国、美国

按道理上述三个都是内容的三个不同维度,但是人类往往更习惯把“故事题材”和“故事时间”统称为“类型”,而“产地”却会保持独立的维度。这是为什么呢?因为产地既可以跟故事题材,🈶可以跟故事时间,进行完全的组合展开,比如“内地&悬疑”,“韩国&偶像”。但是“故事题材”与“故事时间”只能部门的组合展开: 比如“古装&悬疑”、“古装&情感”;但是“古装&偶像”这个组合似乎就很少了,能想起来的《寻秦记》能算得上是;而“古装&军旅”就特别古怪了,因为军旅剧基本跟近代或现代绑定的,不太可能在古代,或者即便理论上可行,商业上拍古代军旅也不卖座。人类大脑会天然过滤掉这种不太可能存在的组合,于是简化出类型,但同时埋下一个坑,刚开始会简单的合并为类型包括“悬疑”和“古装”等,直到某天遇到了《长安十二时辰》,人类大脑才恍然大悟:“哦,原来还存在既是悬疑,又是古装的情况”。

组合/存在性 悬疑 情感 偶像 军旅
古代(古装) TRUE TRUE FALSE FALSE
近代(年代) TRUE TRUE TRUE FALSE
现代 TRUE TRUE TRUE TRUE

依据上表,把“故事题材”和“故事时间”两个维度合并成一个“类型”,取值范围是 {古装悬疑, 古装情感, 近代悬疑, 近代情感, 近代偶像, 现代悬疑, 现代情感, 现代偶像, 现代军旅}。简单说就是把FALSE组合排除了,从而把两个维度合并成一个维度。

总结下维度间的关系,从集合论的角度,就三种:层级、正交和交叉。如下图所示:

image-20190811115609839

它们与全集U的作用关系,如下图(假设最外层虚线边框为全集U):

image-20190811121812751

其中“交叉覆盖集” {A, B, C} 可以通过交叉切割的形式转化为 “正交划分集” {A-C, A∩C, B-C, B∩C, C-A-B}。

这个Partition算法的一个示意图描述:

image-20190811124211959

伪代码描述:

image-20190811124328353

形式化描述与流式计数

前面讲了一个观看行为,单从内容、时间、地域三个维度展开,就需要触发 1+2+4+3+(24)+(23)+(43)+(24*3) = 60个计数器同时计数。在海量网站,这么多计数器,并发资源竞争就是大概率事件,势必会阻塞写入端。前面提到工业界普遍做法是,写入端只写日志,而且顺序写,然后消费端回放日志,在回放的时候再计数。这就叫流式计数。开源实现可以用Kafka写日志流,用Flume消费Kafka来回放日志,并在回放过程中过滤和计数,并把结果存储在Redis列式存储中。包括诸如Spark等主流流式计算,这些技术都很成熟。这两需要提及的有两点:一个是形式化描述,另一个是SQL化查询

  • 形式化描述指的是如何在写日志的时候,就通过形式化的语法刻画出未来流式计算的语义,从而把程序自动化下来,而不用每次依据业务再写。

比如业务事件日志描述为:

1
VV=1  品类: 电视剧.古装悬疑剧.长安十二时辰, 时间: 2019.Q3.M08.2019/08/09, 地域: 全国.北京, 产地: 内地  [ {品类, 时间, 地域}, {产地, 时间, 地域} ]

上述这条形式化日志,包含3个部分:

  1. 指标序列: VV=1,指标是VV,增量是1。如果这次观看产生了0.1元的收入,也可以增加一个指标,形如 VV=1, GMV=0.1
  2. 点分层级维度序列:比如品类维度,被描述为点分层级的语法 品类: 电视剧.古装悬疑剧.长安十二时辰。我们有4个维度,于是写成品类: 电视剧.古装悬疑剧.长安十二时辰, 时间: 2019.Q3.M08.2019/08/09, 地域: 全国.北京, 产地: 内地,跟前面一样,多个维度间用逗号隔离。
  3. 正交分解组合分组: 品类、时间和地域,这3个维度是可以正交分解,并组合的,于是把它们放一组,描述为{品类, 时间, 地域}。而产地、时间和地域,它们3还可以组合成另一个分组,描述为{产地, 时间, 地域},这里假设我们不需要计算“品类和产地”的组合,否则我们可以只定义一个分组,然后它含有4个维度,比如 { 品类, 产地, 时间, 地域 } 。

需要提醒的是,按分组进行计数的时候,需要排除重复的组合。比如在第一个分组 { 品类, 时间, 地域 },时间和地域两个组合时会被计算一次;而 { 产地, 时间, 地域 }分组下,时间和地域两个组合一起又会被计算一次。但显然它只能累加一次。如下图所示,排除中间重叠的重复计算区:

image-20190811153557268

  • SQL化查询指的是基础的计数器完成计数后,有一部分的查询就是单一计数就能直接返回结果的,比如“北京&电视剧”的播放量,又或者是“全国&悬疑剧”的播放量。但是如果查询“北上广的电视剧播放量”呢,它可以拆解为“北京&电视剧”+“上海&电视剧”+“广州&电视剧”的累加和。本着把简单留给使用方,把复杂留给实现方的原则,自然会思考对使用方提供SQL标准语法的查询,然后内部实现时,进行SQL解析,生成执行计划,涉及多个组合的,则分别从Redis上查询,然后汇总。这个思想就是开源软件Apache Kylin采用的加速思想。

总结回顾

最后我们总结下,我们从一个简单的计数器开始,发现它的应用场景却很广泛,广告、CDN调度、电商等领域都有它的身影,尤其是会计的复式记账,让我们对有了全新的认识。比如账是一个稀疏矩阵,账是一组计数器的事务。接着探讨了它的常见实现,应用层、Redis和MySQL。最后更加深入的探讨了多维变种——点分层级、正交分解和交叉覆盖。给出了将交叉覆盖转变为正交分解的Partition算法,然后基于层级和正交可以形式化地描述一个业务事件:

1
VV=1, GMV=0.1  品类: 电视剧.古装悬疑剧.长安十二时辰, 时间: 2019.Q3.M08.2019/08/09, 地域: 全国.北京, 产地: 内地  [ {品类, 时间, 地域}, {产地, 时间, 地域} ]

这个业务事件可以被一个统一的流式计算框架计算和查询。这个形式化描述的厉害之处在于,它实现了数据埋点和数据分析的双重自助,传统模式下埋完点后,需求方还得跟计算方跨部门沟通。

image-20190811234331171

如上图所示,在一个组织中,数据有个非常重要的特性——三权分离,它极大的阻碍了数据的应用,如何破解?一个数据体系应该强IO:不仅要有强大的计算能力,而且要有强大的交换能力。比如上图说的丰富的导入,丰富的导出。

而这个形式化描述,能够自助的解决数据采集、数据加工和数据应用三权分离的融合问题。