服务器准备

10.96.115.40 mq-01 broker-a
10.96.83.21 mq-02 broker-b
10.96.83.21 mq-02 broker-a-s
10.96.115.40 mq-01 broker-b-s
10.96.83.21、10.96.115.40 mq-01、mq-02 nameserver、console

代码准备

采用的是源码编译,

1
2
3
4
5
6
7
8
9

git clone https://github.com/apache/rocketmq.git

cd rocketmq

mvn -Prelease-all -DskipTests clean install -U

cp -rf distribution/target/rocketmq-4.5.2/rocketmq-4.5.2/  {workdir}/rocketmq-4.5.2

cd {workdir}/rocketmq-4.5.2

启动nameserver

1

nohup sh bin/mqnamesrv &

启动borker

很贴心的为我们准备了配置的模板2m-2s-async、2m-2s-sync、2m-noslave

• 10.96.115.40是broker-a、broker-b-s
• 10.96.83.21是broker-b、broker-a-s

10.96.115.40的操作

broker-a的配置

1
2
3
4
5
6
7
8
9
10
11

namesrvAddr=10.96.115.40:9876;10.96.83.21:9876    //所关联的namesrv地址
brokerClusterName=TestCluster     //集群名称
brokerName=broker-a
brokerId=0                                                 //0代表主
deleteWhen=04
fileReservedTime=48
brokerRole=ASYNC_MASTER             //角色
flushDiskType=ASYNC_FLUSH           //异步刷盘
storePathRootDir=/home/xiaoju/logs/rocketmqlogs/store  
storePathCommitLog=/home/xiaoju/logs/rocketmqlogs/store/commitlog  //日志存放目录
listenPort=10900

broker-b-s的配置

1
2
3
4
5
6
7
8
9
10
11
12

namesrvAddr=10.96.115.40:9876;10.96.83.21:9876
brokerClusterName=TestCluster
brokerName=broker-b
brokerId=1
deleteWhen=04
fileReservedTime=48
brokerRole=SLAVE
flushDiskType=ASYNC_FLUSH
listenPort=10910   //更改端口号，同一台机器上两个broker不可采用同一端口

storePathRootDir=/opt/logs/rocketmqlogs/store  
storePathCommitLog=/opt/logs/rocketmqlogs/store/commitlog

启动broker

1
2
3

cd {workdir}/rocketmq-4.5.2
nohup sh bin/mqbroker -c /home/xiaoju/rocketmq-4.5.2/conf/2m-2s-async/broker-a.properties &
nohup sh bin/mqbroker -c /home/xiaoju/rocketmq-4.5.2/conf/2m-2s-async/broker-b-s.properties &

10.96.83.21的操作

broker-b的配置

1
2
3
4
5
6
7
8
9
10
11

namesrvAddr=10.96.115.40:9876;10.96.83.21:9876
brokerClusterName=TestCluster
brokerName=broker-b
brokerId=0
deleteWhen=04
fileReservedTime=48
brokerRole=ASYNC_MASTER
flushDiskType=ASYNC_FLUSH
storePathRootDir=/home/xiaoju/logs/rocketmqlogs/store  
storePathCommitLog=/home/xiaoju/logs/rocketmqlogs/store/commitlog
listenPort=10900

broker-a-s的配置

1
2
3
4
5
6
7
8
9
10
11

namesrvAddr=10.96.115.40:9876;10.96.83.21:9876
brokerClusterName=TestCluster
brokerName=broker-a
brokerId=1
deleteWhen=04
fileReservedTime=48
brokerRole=SLAVE
flushDiskType=ASYNC_FLUSH
listenPort=10910
storePathRootDir=/opt/logs/rocketmqlogs/store
storePathCommitLog=/opt/logs/rocketmqlogs/store/commitlog

启动broker

1
2
3

cd {workdir}/rocketmq-4.5.2
nohup sh bin/mqbroker -c /home/xiaoju/rocketmq-4.5.2/conf/2m-2s-async/broker-b.properties &
nohup sh bin/mqbroker -c /home/xiaoju/rocketmq-4.5.2/conf/2m-2s-async/broker-a-s.properties &

启动rocketmq-console

一个springboot工程

1

git clone https://github.com/apache/rocketmq-externals.git

mqadmin常用命令

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

查看帮助：
# sh mqadmin <command> -h
查询Producer的网络连接情况：
# sh mqadmin producerConnection -n localhost:9876 -g <producer-group> -t <producer-topic>
查询Consumer的网络连接情况：
# sh mqadmin consumerConnection -n localhost:9876 -g <consumer-group>
查询Consumer的消费状态：
# sh mqadmin consumerProgress -n localhost:9876 -g <consumer-group>

查询消息是否发送成功
获取指定Topic：
# sh mqadmin topicList -n localhost:9876 | grep <topicName>
查看Topic状态：
# sh mqadmin topicStatus -n localhost:9876 -t <topicName>
根据offset获取消息：
# sh sh mqadmin queryMsgByOffset -n localhost:9876 -b <broker-name> -i <queueId> -o <offset> -t <topicName>
根据offsetMsgId查询消息：
# sh sh mqadmin queryMsgById -n localhost:9876 -i <offsetMsgId>

查询消息是否被消费成功
查询消息详情：
# sh mqadmin queryMsgById -i {MsgId} -n {NameServerAddr}
查看Consumer Group订阅了哪些TOPIC：
# sh mqadmin consumerProgress -g <ConsumerGroup> -n <NameServerAddr>

查询TOPIC被哪些Consumer Group订阅了
没有查询特定TOPIC订阅情况，只能查询所有后再过滤：
# sh mqadmin statsAll -n <NameServerAddr> | grep <TOPIC>
返回结果：#Topic #Consumer Group #InTPS #OutTPS #InMsg24Hour #OutMsg24Hour

关闭nameserver和所有的broker:
# sh mqshutdown namesrv
# sh mqshutdown broker

查看所有消费组group:
# sh mqadmin consumerProgress -n 192.168.23.159:9876
查看指定消费组（kevinGroupConsumer）下的所有topic数据堆积情况：
# sh mqadmin consumerProgress -n 192.168.23.159:9876 -g kevinGroupConsumer
查看所有topic :
# sh mqadmin topicList -n 192.168.23.159:9876
查看topic信息列表详情统计
# sh mqadmin topicstatus -n 192.168.23.159:9876 -t myTopicTest1
新增topic
# sh mqadmin updateTopic –n 10.96.115.40:9876;10.96.83.21:9876 –c TestCluster –t <TopictName>
删除topic
# sh mqadmin deleteTopic –n 10.45.47.168:9876 –c DefaultCluster –t ZTEExample

通过hash算法产生短网址

要点：

1. 选择冲撞小、高效的的hash函数，MurmueHash算法。有32bit和128bit，短连接我们可以选择32bits,求原始地址的hashCode
2. 进一步缩短网址：网址我们一般会采用a-zA-Z0-9等62个字符，我们可以通过除法、并且取模来生成网址，见代码
3. 解决Hash冲突，将原始地址和短连接地址保存起来（redis or mysql）等，当我们发现短连接已经存在并且和原始地址一致可直接返回，如果存在，且和原始地址不一致我们可以加一些额外字段,比如当前的纳秒数等等作为计算hash的种子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class ShortUrlGenerator {

    private static char[] charArray = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray();

    public static String genaratorCode(String input) {

        int code = Math.abs(MurmurHash.murmurhash3_x86_32(input, 0, input.length(), 0));

        List<Integer> list = new ArrayList<>();

        StringBuilder sb = new StringBuilder();
        while (code > 0) {
            //取模
            sb.append(charArray[code % charArray.length]);
            //整除
            code = code / charArray.length;
        }

        return sb.toString();
    }
}

通过自增ID

• 对比上面的方式，对于相同的网址，我们会产生不同的短连接，但是会减少判重的次数（数据库的交互）
• 自增ID是全局的，肯定要加锁，为了增加并发我们可以同时用多个发号器来解决，类似分库分表的思想。

路由匹配

精确匹配

按照从大到小的数组排序，用二分法查找时间复杂度大大减少

前缀匹配

用字典树的方式解决，不过字典树这次是按照分隔符“/”来进行分割，同一级别按照大小顺序进行分组，用俩分法进行匹配

包含通配符的模糊匹配

将url分组，没有通配符的优先匹配复杂度O(logn)
有通配符的用回溯算法匹配

Disruptor是java内存级的消息队列，堪称java中性能最高的队列，在java的并发篇中提到过，本文主要讲解在算法方面是如何做到的。

循环队列

JAVA原生多采用ArrayBlockingQueue，注：LinkedBlockingQueue无界队列当消费者消费能力不足会导致OOM。
而Disruptor采用的这种方式本质上是循环队列，在插入、删除等不会出现数据的搬移操作。并且所有数据都已经初始化好减少gc的成本

无锁操作

生产时候会去检查是否有空位，如果没有会用cas一直询问，消费时候会去判断队列是否为空，为空就一直判断。

解决伪缓存

不在这里讨论啦：P,用的是缓存填充法。

搜索引擎分为如下四个部分

爬虫抓取

1. 利用graph的bfs方式遍历，每个url就是一个vertex,用links.bin作为bfs搜索的队列，这样支持断点续排，并且也能减少内存的使用
2. 由于网页的量巨大，我们可以用bloomfilter进行排重，这样能减少内存空间，即bloomfilter.bin
3. 保存原始网页docs_row.bin,格式是docs_id–>docs_content,docs_id由一个中心计数器生成

分析

1. 抽取文本信息：去掉网页中的标签等信息 可以理由ac自动机
2. 创建临时索引：然后对文本进行分词
   1. 创建tmp_index.bin，格式是：term_id–>doc_id
   2. 创建term_id.bin,格式是：term_id–>term （散列表）
   3. term_id通过一个中心计数器生成

索引

1. 分析网页，简历倒排索引：即term_id–>doc_id1,doc_id2,doc_id3。由于临时索引很大，我们可以采用多路归并排序（map-reduce）进行归并，index.bin
2. 记录term在倒排索引偏移量的文档term_offset.bin

如图：

查询

我们通过上面提到的文件：term_id.bin、term_offset.bin、index.bin、docs_id.bin，

1. 想通过且此获取k个term
2. 在通过term_id.bin获取term_id
3. 在通过term_offset.bin找到索引中对应的doc_id，看那个doc_id出现的次数最多就说明哪个服务客户需要就排在前面
4. 按照3的顺序在docs_id.bin查找顺序。

摘要实现原理

我们在创建临时索引时候可以将摘要和doc_ic以及term_id存入到schema.bin中，需要的时候查询出来。
网页快照可以将doc_id–>doc_row用lru的算法存入到shap_shot.bin中。

主要介绍下Redis中数据结构相关的知识点，分别是List,Set,SortSet,Hash

Redis是内存数据库（也有持久化功能）

List

zipList:

• 保存的单个数据都小于64字节;

• 存储的元素不超过512个;

  其他情况会采用双向循环链表，优点：便于处理从尾向前遍历，以及方便删除修改操作。

Hash

zipList:

• 保存的单个数据都小于64字节;

• 存储的元素不超过512个;

  其他情况会采用散列表，默认情况下装载因子大于1时候会进行库容，小于0.1时候会进行缩容，扩容方案采用延迟扩容的方案

Set

有序数组:

• 保存的单个数据都是整数；

• 存储的元素不超过512个;

  其他情况会采用散列表

SortSet

zipList:

• 保存的单个数据都小于64字节;

• 存储的元素不超过128个;

  其他情况会采用跳表+Dict

zipList解释

是加强版的数组，和数组相比：支持多种数据格式，且每个元素的长度可以不一致。比数组更节省内存的空间。redis在数据量小的时候会采用这种方案取代其他的数据结构，相当于用时间换空间，毕竟redis是内存数据库，在内存的使用上是很敏感的:P

数据的持久化

redis在磁盘存储时候会去掉原有的数据结构，以便于节省磁盘空间，当需要将数据加载到内存中时候会还原原有的数据结构。（缺点是加载时间比较长，由于redis是内存级数据库所以这点损耗可接受）

算法优化是有极限的比如说常见的三种O(NlogN)：快排、归并、堆排序。在算法上我们几乎没有优化的空间，但是在执行效率上我们可以利用计算机的并发来提高执行效率

并行排序

• 归并排序：可以将数据分成均分N组，然后每组并发的进行归并排序，最后在对这些数据进行合并。
• 快速排序：可以先扫描一遍数据，将数据按从小到大分别分到N个曹中，对应N个线程并发排序，排好即可

归并排序是先排序，后归并；快排是先分组，在排序。

并行查找

在用散列表构建索引时候，当散列过了负载因子阈值时候会进行扩容，如果是一个大的散列表会浪费许多资源。同时也没法通过并行提高查找效率。我们可以将散列表分成N个小散列表在查找时候去N个散列表中一起查找，同时也支持对单个散列表进行扩容和缩容。

并行匹配字符串

模式串是M

• 对于一个大文本，我们可以将文本拆分为N个小文本。用N个线程并发查找。
• 由于有可能俩个小文本结尾会把模式串切分开了，我们要对每个小文本特殊处理，也就是将没个小文本的末尾M个字符和下一个文本的开头M个字符连起来2M个长度在进行匹配

并行搜索

在图的BFS搜索的问题上，我们用一个队列来进行层层搜索，我们可以采用俩个队列A、B，多线程并发处理A将扩展队列放到B中，当A空后在处理B，如此循环。

Map-Reduce实际上就是并行处理框架

衍生问题

上面提到的都是没有依赖的任务，针对有依赖的任务我们可以进行touple排序，没个依赖用一个线程并发去执行。（有依赖就进行拓扑排序）

Mysql的索引采用B+tree的结构，因为索引需要自持范围查寻、等值查询，支持快速的添加、删除，且时间复杂度不能太高，同时占用的空间不能太大。

b+tree做索引的实现原理

查询

1. 保存在文件中，采用时间换空间的思路，支持大的索引;
2. 由于节点在磁盘中，每次访问节点都需要一次磁盘的IO，所以b+tree是多叉树，有效降低了树的高度，极大减小了磁盘IO的次数提高了性能;
3. b+tree每个节点的大小都对应一个内存的PAGE_SIZE,保证每次加载只有一次磁盘IO

4. b+tree只保存索引所以，叶子节点由链表串联起来，所以支持范围查找，并且修改值不用改动索引，且索引很小。

   添加:添加如果节点超过了Page容纳的范围，就将原有节点分裂成俩个不同的节点，逐层向父级分裂知道满足需求
   删除：设置一个阈值，如果b+tree节点数量小于阈值就进行合并，如果合并后节点数超过PAGE_SIZE在和添加一样进行分裂

b+tree和b-tree的区别

1. b+tree的节点保存索引，btree保存值。
2. b+tree的叶子节点由链表串联起来。

索引的选型

索引是所有的数据存储系统的关键，直接关乎查询的效率，常用的适合做索引的数据结构有：

• 散列表：查询修改复杂度都是O(1),适合nosql的存储，如redis，memcached等，大部分索引都在内存中
• 红黑树：适合做文件系统的索引，插入、修改、查询的事件复杂度都是O(LogN)，也适合构建内存索引
• B+tree：适合构建磁盘索引，如mysql等
• 还有布隆过滤器、位图等：虽然有误判，但是我们可以选择他做二级索引，因为索引很小，且效率很高，判断下数据是否存在，如果返回存在在调用其他索引查找。

实现音乐推荐系统算法模块的思路：

1. 找到和你口味的相近的人，把他听的歌曲推荐给你
2. 找到和你听的歌曲个特征相似的跟去，把这些歌曲推荐给你

实现原理

向量的欧几里得距离

基于相似口味的人

• 把听过的某首歌看为是一个向量
• 把听过的歌进行打标（收藏、听、分享、不喜欢）计算每一首歌的向量值;
• 然后遍历所有的用户，计算向量的欧几里得距离，设定一个阈值，小于这个阈值的说明口味相近，我们将用户没听过的歌推荐给用户

基于喜欢的歌曲进行推荐

• 用户对于喜欢听的歌曲的成都进行标记
• 遍历所有歌曲，计算向量的欧几里得距离，设定一个阈值，小于这个阈值的说明歌曲受欢迎程度相似可以进行推荐。

有一下3中过滤方式

基于黑名单规律

可以制作手机号码的黑名单：

1. 利用bloomfiter来过滤手机黑名单，可能会有误判的可能
2. 将黑名单方法服务器，利用时间换空间

基于规则过滤

可以将垃圾短信的样本中出现的词进行整理，计算他们是垃圾短信的概率和不是垃圾短信的概率如果一个单词是垃圾短信的概率远远大于非垃圾短信的概率说明它是垃圾短信的词语。

基于概率过滤

利用朴素贝叶斯算法，计算词语和垃圾短信的关系