秒杀系统在各种业务场景里面都会出现。对于电商公司商品秒杀会涉及到:会场、排期、招商、C端(商详店详)、金融等中台或业务线的通力合作,系统本身也会涉及到网关、风控、基础设施(db,cache,容器)多个环节。但是如果现在仅仅考虑1个固定商品的秒杀一天就一个固定场次,不涉及支付(0元就可以秒),用户限购1个,这样市场或营销的场景,现在看一下如何短平快实现一个高并发支持实现简单快捷的秒杀系统。

图里面的系统简单起见都认为已经有了,不需要再进行考虑了。

1. 开始具体的的设计
数据库一张表名字叫buy:
字段:id, item_id,user_id,number(秒杀序号)
uniq key: item_id,user_id
uniq key: item_id, number

2. 秒杀接口(登陆态必须):
input :userid,itemid
output: 是否秒杀成功

3. 核心逻辑

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
26
27
28
29
30
31
32
    /**
     * -1无库存
     * @param userId 用户id
     * @param itemId 商品id
     * @param stock  商品库存
     * @return
     */
    public long buyNow(long userId, long itemId, long stock) {

        String nowNo = jedis.get(String.format("buynow_%d",itemId));
        if (nowNo != null && Long.valueOf(nowNo) >= stock) {
            // 没有库存了
            return  -1;
        }
        if(jedis.pfadd(String.format("buynow_u_%d",itemId),String.valueOf(userId)) > 0) {
            // 这个uid没来过
            long byno = jedis.incr(String.format("buynow_%d",itemId));
            if (byno <= stock) {
                // 获取到购买序号了

                // 插入表格返回id,插入失败返回null
                Long id = buyDao.insert(userId,itemId,byno);
                if (id !=null ) {
                    // 记录数据库成功
                    return id;
                }
               
            }
        }
        // 没有抢到
        return  -1;
    }

上面的逻辑主要看当前号是否已发放完了,没发放完,给没来过的用户发号。里面用到了hyperloglog和string两个redis的数据类型。但是需要这个kv系统是可靠的。
如果库存很小的情况下方法基本没有瑕疵,库存大的话,有些用户没来过会判断已经来过了。不会给他号。不过还好足够简单了。

家里网上太慢了,项目依赖的snapshot包太多了,本地编译太费劲了,如何搞
修改 settings.xml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<profile>
    <id>default</id>
    <repositories>
        <repository>
            <id>central</id>
            <url>http://central</url>
            <releases>
                <enabled>true</enabled>
            </releases>
            <snapshots>
                <enabled>true</enabled>
                <!--<updatePolicy>always</updatePolicy>-->
                <!-- 此处设置永不更新 -->
                <updatePolicy>never</updatePolicy>  
            </snapshots>
        </repository>
    </repositories>
</profile>

此时 快速编译一下:

mvn package -nsu -Dmaven.test.skip=true
# 如果只使用这个命令是没什么效果的,settings.xml里面如果不改,致此处还会不停的从远程检查。

强制更新一下snapshot 并编译一下
mvn package -U -Dmaven.test.skip=true

其他的更新策略,也可以尝试一下
The frequency for downloading updates – can be “always”, “daily” (default), “interval:XXX” (in minutes) or “never” (only if it doesn’t exist locally).

参考文档: http://maven.apache.org/ref/3.5.0/maven-settings/settings.html

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
26
package thread;

public class DeamonTest {

    public static void main(String[] args) {

        Runnable runnable = new Runnable() {
            public void run() {
                try {
                    Thread.sleep(10000);
                } catch (InterruptedException e){

                }
                System.out.println("thread exit");
            }
        };

        Thread thread = new Thread(runnable);
        thread.setDaemon(true);
        thread.start();
        System.out.println("main exit");
    }
}

输出:
main exit

基于jdk1.8 和 linux讨论:

1. java中两类线程:deamon 和 非deamon,调用start之前 thread.setDaemon(false); 可以设置是否为daemon进程,默认为false。 如果调用的不是start函数而是run函数,就是同步执行runable的具体方法了。
2. main函数 属于非deamon
3. main函数退出后,如果有非deamon线程,jvm不会退出要等待非deamon线程退出。 如果只有deamon线程,jvm会直接退出
4. java的线程实现是 Thread调用native的start0方法进行实现(Java Native Interface)。这个方法最终调用了操作系统API实现。java线程对应的是一个真实的操作系统线程。
5. java.lang.Thread.State 里面定义了:NEW, RUNNABLE, (BLOCKED, WAITING,TIMED_WAITING), TERMINATED 六种进程状态,实际操作系统里面的定义可以不一样,由于跨平台特性java需要适配系统线程状态定义。

1) 基数统计(非精确去重统计) HyperLogLog, 统计一下数字

1
for ((i=0; i<200; i++)) { echo $i;   echo "pfadd goodhyperloglog $i" | redis-cli; } ; echo "pfcount goodhyperloglog" | redis-cli

在 Redis 里面,每个 HyperLogLog 键最坏情况下只需要花费 12k bytes ,就可以计算接近 2^64 个不同元素的基数
参考:redis#hyperloglog

2)Bitmaps 不是一个真实的数据类型,只是在String类型上定义的一系列的位操作。string是二进制安全的,最大长度512M,能存储2^32个bit位。参考redis#bitmap

1
for ((i=0; i<200; i++)) { echo $i;   echo "setbit bitkey $i 1" | redis-cli; } ; echo "bitcount bitkey" | redis-cli

这两个数据类型都可以用来做去重的统计,一个非精确快速 hyperloglog (单个计数器时间复杂度 O(1)),另外一个精确 bitcount 时间复杂度o(n)

消息的传递常系统规设计中都依赖MQ,目前MQ中间件常用的有RabbitMq、roketmq、kafka、zeromq、activeMq,咱们这里面先忽略mq的顺序性保障 ,重点讨论mq的上下游(producer、consumer)的消息顺序性保障如何实现。

如果这么设想的话,问题会变得简单些。 假定消息中间件的消息顺序性是可以保障的(消息中间件假定kafka: 一个topic下可以有多个partition, partition内的顺序可保障,消息可以多次消费)

首先来看一下 consumer的消息顺序性保障

1) 如果是一个topic 一个partition,partition中消息本来就是顺序的, 下游consumer的消费业务时延【可忽略】:一个线程就能搞定,此时是最简单的一种情况,直接单线程消费就能保障消息的时序性。

2) 如果是一个topic 一个partition,partition中消息本来就是顺序的,下游consumer的消费业务时延【不可忽略】:此时一个线程消费不过来了,容易照成业务堆积了。此时如何保障消息的顺序性?

假定业务场景:消息中存储的是用户的积分变动,且用户间消息无业务依赖。消息中有userid,此时用userid做hash,拆分成多个桶,每个桶对应一个线程进行处理此时即可保障单用户消息的时序性,利用业务特性提升consumer的并发消费能力。

具体操作:consumer启动x个线程(或进程)每个线程都消费当前partition所有的消息,如果这个消息的 userid%x=自己的序号就处理这条消息,否则就跳过(这里面可以进一步用一致性hash考虑consumer的可靠性)。

此场景再次扩展,如果某个hash下面存在热点如何处理: 如果业务特性允许可以进行二次hash。

看一下MQ的顺序性保障

1)刚才假定consumer只消费一个partition,如果当前mq的吞吐量不够如何处理
基于以上讨论mq单个partition的顺序性是能够保障的。此时可以考虑刚才consumer的处理方式,根据业务独立特性将消息进行分桶,不同的消息(或者按照某维度进行拆分)进入不同的partition。

此时高吞吐量的场景下:在mq以及下游consumer的消息的时序和时延都能够得到很好的保障。

此时利用各种hash将消息进行拆分,利用并发提高整体消息系统在mq和consumer的消息处理能力。
但是有些业务的对时序和时延的要求是不一样的以上方案只能解决部分场景下的问题。

producer的顺序性保障
如果源头消息的产生就不是顺序的下游如何处理都不不靠谱(此处太绝对)。因此消息源头如何保障顺序性至关重要。但是细想这个问题好像比上面的两个环节要更复杂。

1) 第一种情况 一个消息源头: 此时producer 是一个线程,线程内处理业务是顺序的产生的消息是本身自带顺序性,直接投放到MQ是没有问题的,hash投放到多个partition也是可以的,此时顺序是可以保证的。

2)第二种情况,多个消息源头: 此时producer 是多个线程。 单个线程内处理消息产出的顺序是顺序的,多个线程间的消息产出顺序不可保证。

例如:一个A线程修改一条数据,产生一条消息。 另外一个线程B修改同一条数据产生一条消息。 在全局时间空间里面,A发生在B前面。但是没法保证A消息一定先于B消息投放到MQ的同一个partition。这个场景就比较复杂了,中间实现的各种细节如果再考虑到这个问题就更加复杂了。

这个场景如何处理:

A)假设:消息产生都是对mysql数据库具体数据的变更,此时将mysql的binlog订阅到MQ里面即可。这个方法利用了将多源变成了单源,这种场景只是特例,系统中存在组件能够提供顺序性的消息刚好又和消息相关。

B)假设:消息的产生就是在业务层应用内的具体线程里面产出:此时再加个假设条件消息在具体线程里面产生时带的顺序标记(当前时间)是靠谱的。

有些场景是不靠谱的这个地方咱们简单说一下:如果触发某个函数会产生一条消息,函数完成了线程被挂起了,挂起5分分钟,当线程继续运行的时候获取当前时间作为顺序标识,完成消息的制造,此时顺序标记就是不靠谱的(为了能更好的抽象思考这个问题这个场景咱们先忽略)

此时我们已经有了线程内的具体时序标识,只要按照这个标识的先后顺序投递到MQ下游的消息顺序性就能保证了。但是保证先后顺序是很困难的,为什么这么说呢。按照目前MQ中间件提供的能力,其困难点主要在于有序投递,而有序投递目前MQ的中间件是不负责的。

此时假定我们有n个线程能够产生具有可靠顺序标记的消息,然后消息发送到某个消息排序缓存中,然后顺序的投递到MQ好像就能解决这个难题。但是得有这样一个消息排序缓存。直接想比较难,但是如果是个时序优先级的队列就好思考了,但是这个队列缓存未排好序的不能读。如下图:

以上讨论假定了很多因素(系统间的交互幂等,异常)只是为了聚焦时序本身。当然以上设计也是有很多问题的,假如某个app的消息发送不到缓冲区,为了保证时序性。我们是暂停消费还是丢弃(能保证时序)直接继续向下(保证时延小),还是直接下游消费等待上游app恢复后继续(消费者是否能接受这个延迟)。

看场景处理问题
两个名词(时序,时延),四个象限:

时序:代表消息的顺序性保障。
时延:代表消息从产生到被消费的时间间隔。
这里面具体的场景具体分析,但是同时保证这两项非常困难。以上场景的诸多假设把问题抽象简单了,但是实际场景中producer本来就有n个,而且一个producer又可能有n个线程。线程间的顺序要保证,然后所有producer的顺序要保证还是非常有挑战的。

当然,未来这些都能解决。


空间映射&编码

  1. 墨卡托模型: http://cdn.hujiulong.com/geohey/blog/mercator/play.html
  2. Geohash 是一种地理编码,由 Gustavo Niemeyer 发明的。它是一种分级的数据结构,把空间划分为网格。Geohash 属于空间填充曲线中的 Z 阶曲线(Z-order curve)的实际应用。
  3. s2 参考文档 https://github.com/halfrost/Halfrost-Field/blob/master/contents/Go/gospatialsearch.md

空间索引的方法

Lucene的方法:

  1. 2D空间下的索引:
    1. geo_point :前缀索引 可以解决附近点和区域内点的搜索
    2. geo_sharp : 形状索引的实现。 Tessellation Decomposition + Block K Dimensional Trees (Bkd),三角拆分+blockKDtree
  2. 3D空间下的索引

    1. XYShape for Spatial…in Lucene 8.2+ Tessellating & Indexing Virtual Worlds

  3. lucene geo索引原理参考文档

    1. https://www.slideshare.net/elasticsearch/geospatial-advancements-in-elasticsearch
    2. https://portal.opengeospatial.org/files/?artifact_id=90337

索引涉及的数据结构和发展

  • 空间数据库中最基本的查询
    1. 正交范围查询(range query)
    2. 窗口查询(window query): 在二维坐标数据中,窗口查询是一个坐标对齐矩形,查询目标是数据库中的落在矩形内所有点。
      • 支持窗口查询的的多维点索引结构有: k-d B-tree hB-tree Bkd-tree R-tree

kdtree 的发展:

  1. K-d tree 1975 Jon Louis Bentley 发明(https://en.wikipedia.org/wiki/K-d_tree)

    1. k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点,节点右边的子树代表在超平面右边的点。选择超平面的方法如下:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样,超平面可以用该x值来确定,其法线为x轴的单位向量。

    2. 基本结构&构建:

      • 有很多种方法可以选择轴垂直分割面( axis-aligned splitting planes ),所以有很多种创建k-d树的方法。 最典型的方法如下:
        1. 随着树的深度轮流选择轴当作分割面。(例如:在三维空间中根节点是 x 轴垂直分割面,其子节点皆为 y 轴垂直分割面,其孙节点皆为 z 轴垂直分割面,其曾孙节点则皆为 x 轴垂直分割面,依此类推。)
        2. 选择的轴的具体座标的中位数作为作为分割面,同时该点放入子树。
      • 这个方法产生一个平衡的k-d树每个叶节点的高度都十分接近。但是平衡的树不一定所有场景都是最佳的
    3. 支持:最近邻查询和范围查询
    4. kdtree的主要问题:
      • 因为k-d树是多维排序的,做到平衡比较复杂。不能使用树旋转技术来平衡它们,因为这可能会破坏不变量
      • 平衡K-D树的几种算法:divided k-d tree, pseudo k-d tree, k-d B-tree, hB-tree and Bkd-tree
    5. 制约和限制:
      • 维度灾难:在高维空间中,k-d树叶并不能做很高效的* 最邻近搜索。一般的准则是:在k维情况下,数据点数目N应当远远大于2^k时,k-d树的最邻近搜索才可以很好的发挥其作用
  2. K-D-B-tree (k-dimensional B-tree) k-d-b-tree的目标是提高平衡k-d树的搜索效率,同时提高b-tree面向块的存储以优化外部内存访问

    • J. T. Robinson. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10–18, 1981
    • https://en.wikipedia.org/wiki/K-D-B-tree
    • 原文: http://www.csee.usf.edu/~tuy/Literature/KDB-SIGMOD81.pdf
    • 也有简称kdtree的

    • 与k-d树类似,k-d-b树组织k维空间中的点,对于范围搜索和多维数据库查询等任务非常有用。k-d-b树通过比较单个域中的元素将空间划分为两个子空间。以二维b树(二维k-d-b树)为例,空间的细分方式与k-d树相同:仅使用其中一个域或轴中的一个点,在这种情况下,所有其他值都小于或大于当前值,并分别落在拆分平面的左侧和右侧。 与k-d树不同,每个半空间不是自己的节点。相反,与b-树一样,k-d-b-树中的节点存储为页,树存储指向根页的指针。

    • kdbtree基本结构
      todo: https://en.wikipedia.org/wiki/K-D-B-tree

  3. Bkd-tree 是 kd-tree 的扩展 2003发明

    • 参考文档:https://users.cs.duke.edu/~pankaj/publications/papers/bkd-sstd.pdf

  4. hB-tree

    1. http://www.cs.bu.edu/fac/gkollios/cs591/hb-tree.pdf

空间数据分割树

  • R树 R*树 R+树 X树 M树 线段树 可持久化线段树 希尔伯特R树 优先R树

  • R-tree 1984 Antonin Guttman 发明 (https://en.wikipedia.org/wiki/R-tree https://zh.wikipedia.org/wiki/R%E6%A0%91) 在空间索引应用上非常典型也非常成功。最典型的应用就是:附近两公里的餐厅这样的查询

  • R树也是平衡树(所以所有叶子节点都在同一深度)。它把数据按(内存)页存储,是为磁盘存储设计的(跟数据库的做法相同)。每一页可以存储不超过一个上限的条目,这个上限一般用M表示。R树会在除根节点以外的节点上维持数据条目不小于最小条目数

Elastic search中空间索引和lucene映射历史

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    ? Lucene 8.2+      XYShape for Spatial... Tessellating & Indexing Virtual Worlds
Elasticsearch 7.0 bundles Lucene 8
2019326日 - Elasticsearch 6.7.0, based on Lucene 7.7.0.
2019-2-4              6.6.0   Integrate Lucene's LatLonShape (BKD Backed GeoShapes) as default geo_shape
Elasticsearch 6.5.0, based on Lucene 7.5.0.
Elasticsearch 6.4.0, based on Lucene 7.4.0.
2018年6月13日 Elasticsearch 6.3.0, based on Lucene 7.3.0.
Elasticsearch 6.2.0, based on Lucene 7.2.1.
                                     6.6+      "triangle" encoding(Bkd-tree)
                                     pre 6.6   terms/postings encoding
Elasticsearch 5.4.1, based on Lucene 6.5.1.
Elasticsearch 5.4.0, based on Lucene 6.5.0.
Elasticsearch 5.3.3, based on Lucene 6.4.2.
Elasticsearch 2.4.0, based on Lucene 5.5.2.

elastic search 7.4 Geo 相关支持情况

  • Geo query(https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-queries.html)
  • ElasticSearch支持两种类型的地理数据:支持纬度/经度对的地理点域和支持点、线、圆、多边形、多多边形等的地理形状域。
  • 支持的查询类型:

    1. 地理框查询(geoboundingbox)
      • 查找具有落在指定矩形中的地理点的文档。(支持经纬度查询数组、字符串、或geohash编码构建的矩形区域进行查询)
    2. 地理距离查询(geo_distance)
      • 查找地理点位于中心点指定距离内的文档。
    3. 地理多边形查询(geo_polygon)
      • 查找指定多边形内具有地理点的文档。
    4. 地理图形查询(geo_shape)
      • 查找具有与指定的地理形状相交、包含或不相交的地理形状的文档。
      • 能够过滤带有geo_shap类型字段的索引
      • 查询支持直接给的一个形状也支持在另外一个索引里面定义的形状。
      • 空间关系运算符:
        1. intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
        2. DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
        3. within-返回其geo_shape字段位于查询几何体中的所有文档。
        4. contains-返回其geo_shape字段包含查询几何图形的所有文档。注意:这只支持使用递归前缀树策略[6.6]
  • Shap query(https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-shape-query.html)

    1. 查询带有shap类型的索引
    2. 和geo_shape类型查询很像,shap query 用 GeoJSON 或 Well Known Text (WKT)表征形状。
    3. 支持的空间关系运算:
      1. intersects-(默认)返回其geo_shape字段与查询几何体相交的所有文档。
      2. DISJOINT-返回其geo_shape字段与查询几何图形没有任何共同点的所有文档。
      3. within-返回其geo_shape字段位于查询几何体中的所有文档。

es lbs 查询实例

  • 场景:查询当前点在可服务区域里面的所有doc并按照直线距离排序。 poi_zone 代表可服务区域 , poi_point 代表服务提供方所在位置。
  • 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
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    DELETE /shapes


    PUT /shapes
    {
        "mappings": {
            "properties": {
                "poi_zone": {
                    "type": "geo_shape"
                },
                "poi_point": {
                    "type": "geo_point"
                }
            }
        }
    }


    PUT /shapes/_doc/deu
    {
        "poi_zone": {
            "type": "polygon",
            "coordinates" : [
              [[116.402508,39.947163], [116.414653,39.94697], [116.414869,39.940083], [116.40276,39.939972],[116.402508,39.947163]]
            ]
        },
        "poi_point":{
          "lon":116.408401,
          "lat":39.943734
        }

    }

    PUT /shapes/_doc/deu2
    {
        "poi_zone": {
            "type": "polygon",
            "coordinates" : [
              [[116.409443,39.947136], [116.420043,39.946997], [116.420043,39.945615], [116.409443,39.945587],[116.409443,39.947136]]
            ]
        },
        "poi_point":{
          "lon":116.414096,
          "lat":39.946513
        }
    }

    GET /shapes/_search

    GET /shapes/_search
    {
        "query":{
            "bool": {
                "must": {
                    "match_all": {}
                },
                "filter": {
                    "geo_shape": {
                        "poi_zone":  {
                            "relation": "intersects",
                            "shape": {
                              "coordinates": [116.409766,39.946389],
                              "type": "point"
                            }
                        }
                    }

                }
            }
        },
        "sort": [{
                "_geo_distance": {
                    "poi_point": {
                        "lon": 116.413503,
                        "lat": 39.946776
                    },
                    "unit": "km",
                    "order": "asc"
                }
            }]
    }

仔细想想这个问题还是挺有意思的。如图即将见到方法:

client相对服务器的时间偏差是:
offset = ((t1-t0)+(t2-t3))/2 如何理解呢,这个假设网络往返时间是相同的(实际情况仅同一网络内可以这么理解,广域网不会一样)。 t1-t0 是 网络延迟+时间差别 t2-t3 是 负的网络延迟+时间差别 两个合起来 除2就是时间差距了。
另外:网络延迟
delay = (t3-t0) – (t2-t1) 除去服务器的处理时间。

关于时间偏差如下示例:

1
2
3
4
5
6
7
8
9
10
        timeline->
server: 0  1  2  3  4  5  6  7  8
client: 1  2  3  4  5  6  7  8  9

clock synchronization:
c          2
s             2  3
c                   5

offset: -1=((2-2) + (3-5))/2

utc 是 tai(基于铯133的物理计时(购买原子钟可以联系我))的协调时间 会有闰秒, 每年的年中 6.30 和 12.31 是采用行政的方式加1秒,地球是转速的变慢的所已会加1秒。
闰秒的存在会使得同步差别更大。集群里面有些地方是要注意这个问题的,但是有折中的解决的办法。
另外代码时间相关的需要考虑到个闰秒的影响。

参考:
关于NTP,你需要知道的一切: https://www.jianshu.com/p/8096c0477230
wiki: https://en.wikipedia.org/wiki/Network_Time_Protocol
Raspberry Pi与GPS构建NTP服务器: https://blog.csdn.net/xiaohu50/article/details/78731534
Time synchronization with a Garmin GPS: https://www.lammertbies.nl/comm/info/GPS-time.html

FSA
FSA:确定无环有限状态接收机(Deterministric acyclic finite state acceptor, FSA) tire-tree就是这种

(构建工具http://examples.mikemccandless.com/fst.py)

FST

fst: Finite State Transducers(有限状态传感器)

(构建工具http://examples.mikemccandless.com/fst.py)
图中输入框里面 单词代表输入 后面的数字代表状态
用单词遍历这个有向无环图,初始状态是0,遇到的数字就累加上,到达终点节点的话就是对应的结果状态,如果没有到达终点代表咱们这里不支持这个输入
红色的边代表可优化存储的边 a large reduction of the FST size(实际实现中它的到达节点就是它的下一个节点,这个和实际存储实现由很大关系 )
加粗的边代表下个节点是终结(这个地方注意 黑色的有加粗的 红色的也有 0/1 g/1 这两条边都是加粗的)

构建方法:
输入的词是有序的(有序的构建的是最小树),添加词,再添加词(锁定部分边有些是不会动的边了 可以锁定了)调整未锁定的边,同时调整里面的数值让输出是目标值。再添加的时候有些边又可以锁定了,然后调整其他未锁定的。
输出状态可以是数字大于等于0的整数:每个路,经边的值加和。
输出状态可以是文本:每个路,经过的值得合并,下面以上图为例 Lucene 的fst为例进行说明

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
目的是使用1维的byte数组将状态变化全部保存起来

上图拉伸变形后

    c  a  t
    d  e e p
       o g s
    e  g g

  镜像后得到(镜像是和插入顺序相关)
c   d  e   g   g
       o   g   s
       e   e   p
           a   t

从后到前依次填入到byte里面
fst的bytes字段
#一行10个byte 10进制

 0    116  15   97    6   112   15    101  6   1  
 115  31   1    103   23  1     111   23   8   101
 0    103  15   103   6   6     101   22   20  2
 100  16   4    1     99  16


#转换arc为字母 标记状态
 (0)  [t]  15   [a]   6    [p]  15    [e]   6       <1>  
 [s]  31   <1>  [g]   23   <1>  [o]   23    {8}     [e]
 0    [g]  15   [g]   6    <6>  [e]   22    {20}    <2>
 [d]  16   {4}  <1>   [c]  16


lucene 的arc 标记位8个bit定义了6个标记
BIT_FINAL_ARC = 1 << 0;       表示此边的目标节点是否为可接受状态
BIT_LAST_ARC = 1 << 1;       表示此边是节点的最后一条边,此边后面的内容就是下一个节点了。一个节点的所有边按顺序写入到bytes中,只有最后一条边被标记为BIT_LAST_ARC
BIT_TARGET_NEXT = 1 << 2;   表示此边应用了target_next优化,bytes中的下一个Node就是此边的目标节点
BIT_STOP_NODE = 1 << 3;     表示此边的目标节点是-1,已经遍历到了FST的末尾。
BIT_ARC_HAS_OUTPUT = 1 << 4;  表示此边有输出
BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5;  则该ARC需要存储output信息。
BIT_MISSING_ARC = 1 << 6;  表示此边的目标节点有输出(final output)


flag=16,二进制为 ‭00010000‬ 。
第三位为BIT_TARGET_NEXT=0,因此有目标节点target;
第五位为BIT_ARC_HAS_OUTPUT=1,因此有输出符号output

flag=22, 二进制为‭ 00010110‬ 。
第二位BIT_LAST_ARC=1,说明这是节点的最后一条边;
第三位BIT_TARGET_NEXT=1,因此不需要存储target,其目标节点为下一个节点 往前找就可以了;
第五位为BIT_ARC_HAS_OUTPUT=1,因此有输出符号output


用的时候从后往前查找  比如查找  do
 (0) 代表结束
 []  代表arc
 <>  代表输出
 {}  代表目标跳转
 纯数字  代表flag

应用场景:

1.搜索功能的sug模块: tire-tree和 fst均可作为底层数据结构,实现产品效果是一样的,查询效率相同都是 o(length(queryword))。但是fst的索引构建相较tire的复杂,tire的使用的内存较多,不能共享尾部。对于中文sug来转化为拼音和拼音前缀的Tire很浪费内存。【这个地方重点是压缩率】sug不用这些结构也是可以的(提前构建好用hashmap也可以)
2.Lucene的 term和 doc id的映射就是用的fst。
3.拼写检查

lucence fst使用示例

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public static void main(String[] args) throws Exception {
        /*
        参考文档
        http://lucene.apache.org/core/8_2_0/core/org/apache/lucene/util/fst/package-summary.html
         */

        String inputValues[] = {"cat", "deep", "do", "dog", "dogs", "egg",};
        long outputValues[] = {1, 2, 3, 4, 5, 6};


        PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
        Builder<Long> builder = new Builder<Long>(FST.INPUT_TYPE.BYTE1, outputs);
        IntsRefBuilder scratchInts = new IntsRefBuilder();
        for (int i = 0; i < inputValues.length; i++) {
            BytesRef bb = new BytesRef(inputValues[i]);
            System.out.println(bb.toString());
            builder.add(Util.toIntsRef(bb, scratchInts), outputValues[i]);
        }
        FST<Long> fst = builder.finish();

        System.out.println(fst.toString());


        //find-----------------------------------
        BytesRef xx = new BytesRef("cat");
        System.out.println("-------------");
        System.out.println("search result:"+Util.get(fst, xx));


        System.out.println("-------------");
        System.out.println("foreach fst:");
        //foreach-------------------------------
        IntsRefFSTEnum<Long> fstEnum = new IntsRefFSTEnum<Long>(fst);
        IntsRefFSTEnum.InputOutput<Long> inputOutput;
        BytesRefBuilder scratch = new BytesRefBuilder();
        while ((inputOutput = fstEnum.next()) != null) {
            String input = Util.toBytesRef(inputOutput.input, scratch).utf8ToString();
            System.out.println(input + "\t" + inputOutput.output);
        }

        //sug-------------------------------------
        System.out.println("-------------\nsug result:");
        String forsug = "do";

        BytesRef bytesRef = new BytesRef(forsug);
        IntsRef input = Util.toIntsRef(bytesRef, new IntsRefBuilder());
        FST.Arc<Long> arc = fst.getFirstArc(new FST.Arc<Long>());
        FST.BytesReader fstReader = fst.getBytesReader();
        for (int i = 0; i < input.length; i++) {
            if (fst.findTargetArc(input.ints[input.offset + i], arc, arc, fstReader) == null) {
                System.out.println("can not find ...");
                return;
            }
        }
        System.out.println(arc.toString());

        //"do" find top 5 shortest path
        Util.TopResults<Long> results = Util.shortestPaths(fst, arc, PositiveIntOutputs.getSingleton().getNoOutput(), new Comparator<Long>() {
            @Override
            public int compare(Long o1, Long o2) {
                return o1.compareTo(o2);
            }
        }, 5, false);
        BytesRefBuilder bytesRefBuilder = new BytesRefBuilder();
        for (Util.Result<Long> result : results) {
            IntsRef intsRef = result.input;
            System.out.println( forsug + Util.toBytesRef(intsRef, bytesRefBuilder).utf8ToString());
        }

    }

其他字典树:

Array/List 使用二分法查找,不平衡
HashMap/TreeMap 性能高,内存消耗大,几乎是原始数据的三倍
Skip List 跳跃表,可快速查找词语,在lucene、redis、Hbase等均有实现。相对于TreeMap等结构,特别适合高并发场景(Skip List介绍)
Trie 适合英文词典,如果系统中存在大量字符串且这些字符串基本没有公共前缀,则相应的trie树将非常消耗内存(数据结构之trie树)
Double Array Trie 适合做中文词典,内存占用小,很多分词工具均采用此种算法(An Implementation of Double-Array Trie : https://linux.thai.net/~thep/datrie/datrie.html)
Ternary Search Tree 三叉树,每一个node有3个节点,兼具省空间和查询快的优点(https://en.wikipedia.org/wiki/Ternary_search_tree)
Finite State Transducers (FST) 一种有限状态转移机,Lucene 4有开源实现,并大量使用

FST的开源实现

1. OpenFst, an open-source library for FST operations.
2. Stuttgart Finite State Transducer Tools, another open-source FST toolkit
3. java FST Framework, an open-source java FST Framework capable of handling OpenFst text format.
4. Vcsn, an open-source platform (C++ & IPython) platform for weighted automata and rational expressions.
5. Finite State Morphology–The Book XFST/ LEXC, a description of Xerox’s implementation of finite-state transducers intended for linguistic applications.
6. FOMA, an open-source implementation of most of the capabilities of the Xerox XFST/ LEXC implementation.

【one more thing】

利用Lucene的开源工具实现了一个小的中文sug的demo:sugdemo

参考资料:

lucene字典实现原理——FST https://www.cnblogs.com/bonelee/p/6226185.html
关于Lucene的词典FST深入剖析 http://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
https://blog.csdn.net/zx2011302580235/article/details/88594342
fst wiki https://en.wikipedia.org/wiki/Finite-state_transducer

  • 最大内存
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    [work@xxxxx ~]$ ./redis/bin/redis-cli
    #最大可使用的内存是多少
    127.0.0.1:6379> config get maxmemory
    1) "maxmemory"
    2) "0"
    127.0.0.1:6379> config set maxmemory 100mb  #设置100M
    OK
    127.0.0.1:6379> config set maxmemory 0   #设置不限制
    OK
    127.0.0.1:6379> config get maxmemory
    1) "maxmemory"
    2) "0"    #在64位操作系统下不限制内存大小,在32位操作系统下最多使用3GB内存
  • 内存淘汰策略
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    127.0.0.1:6379> config get maxmemory-policy
    1) "maxmemory-policy"
    2) "noeviction"  #默认的redis内存淘汰策略,满了以后就放不进去了
    127.0.0.1:6379> config set maxmemory-policy allkeys-lru
    OK
    127.0.0.1:6379> config get maxmemory-policy
    1) "maxmemory-policy"
    2) "allkeys-lru"


    #noeviction(默认策略):对于写请求不再提供服务,直接返回错误(DEL请求和部分特殊请求除外)
    #allkeys-lru:从所有key中使用LRU算法进行淘汰
    #volatile-lru:从设置了过期时间的key中使用LRU算法进行淘汰
    #allkeys-random:从所有key中随机淘汰数据
    #volatile-random:从设置了过期时间的key中随机淘汰
    #volatile-ttl:在设置了过期时间的key中,根据key的过期时间进行淘汰,越早过期的越优先被淘汰
    #当使用volatile-lru、volatile-random、volatile-ttl这三种策略时,如果没有key可以被淘汰,则和noeviction一样返回错误
  • 当前状态
  • 1
    2
    #基础监控返回内容参考 https://redis.io/commands/info
    127.0.0.1:6379> info
  • 数据持久化
  • 1
    2
    3
    4
    127.0.0.1:6379> save  #同步dump rdb文件,生产环境是禁用,导致阻塞
    OK
    127.0.0.1:6379> bgsave #异步
    Background saving started
  • 慢日志
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    127.0.0.1:6379> SLOWLOG LEN   #慢日志的长度
    (integer) 9
    127.0.0.1:6379> SLOWLOG GET 1  #获取一条慢日志
    1) 1) (integer) 8
       2) (integer) 1569908358
       3) (integer) 33015
       4) 1) "save"
    127.0.0.1:6379> SLOWLOG RESET  #慢日志重置,内存中的reset后永久丢失
    OK
  • 运维工具
  • Redis实用监控工具一览

    聊聊redis的监控工具

    1) opcache缓存的问题。如果开启了opcache缓存,关闭了脚本检查opcache.validate_timestamps=0,修改代码会生效吗?如果不生效需要怎么办?

    opcache.validate_timestamps boolean
    如果启用,那么 OPcache 会每隔 opcache.revalidate_freq 设定的秒数 检查脚本是否更新。 如果禁用此选项,你必须使用 opcache_reset() 或者opcache_invalidate() 函数来手动重置 OPcache,也可以 通过重启 Web 服务器来使文件系统更改生效。

    opcache.revalidate_freq integer
    检查脚本时间戳是否有更新的周期,以秒为单位。 设置为 0 会导致针对每个请求, OPcache 都会检查脚本更新。如果 opcache.validate_timestamps 配置指令设置为禁用,那么此设置项将会被忽略。

    【注意】如果禁用此选项,你必须使用 opcache_reset() 或者 opcache_invalidate() 函数来手动重置 OPcache,也可以 通过重启 Web 服务器来使文件系统更改生效。重启php-fpm或nginx都是没有用的,缓存存储到共享内存里面的,不清除共享内存,缓存是不会被清理的。
    如果修改源代码一直不生效,就差删除文件了,可以排查一下这个设置。

    2)php.ini修改后php-fpm子进程如果异常退出了,会加载最新配置吗?
    不会pm = dynamic本身就支持动态子进程的,如果子进程重新创建使用新配置就乱套了。

    参考文档:
    https://www.php.net/manual/zh/opcache.configuration.php#ini.opcache.revalidate-freq