数据结构与算法-数组

数组是一种线性表结构,用连续的内存来储存一组相同类型的数据,在C语言自学数组和指针中有做过这方面的一些笔记

线性结构

线性表包括 数组 队列 链表,他们的特点就是有前后两个方向并且数据排成一条线

线性结构

连续内存

连续的内存相同的数据类型是数组的另一个特性,它构造了一个高效的特性随机访问

顺序访问:类似于链表要找到下标为3的元素,需要1->2->3一级一级往下找 O(n)
随机访问:获取起始内存地址,偏移3找到对应的值 O(1)

1
a[i]_address = base_address + i * data_type_size

性能劣势

虽然数组有随机访问访问的特性,访问时间复杂度只有O(1),但是在删除或者插入的时候有最好O(1)最差O(n)平均O(n)的时间复杂度是不高效的。

插入优化:数组若无序插入新的元素时,可以把这个元素放到数组尾部,然后再这个元素的位置上插入新元素O(1)

删除优化:合并多次删除操作,只是单纯标记删除。在内存不够或者特点情况下触发物理删除,可以减少后面元素移动次数

越界

1
2
3
4
5
6
7
8
9
10
int main(int argc, char* argv[]){
int i = 0;
int arr[3] = {0};
for(; i<=3; i++){
arr[i] = 0;
printf("hello world\n");
}
return 0;
}

上面这段代码,arr的长度是3,i<=3。说明for循环体内会进行4次操作,但是arr的最大容量为3超出了我们划分的数组容量。C语言中的变量会放在内存栈中顺序是 i,a[2],a[1],a[0]。在a[3]这次寻址中会找到对应i的内存地址赋值为0会造成死循环。(数组越界后的执行结果未决,和编程语言和编译器都有关系)

为什么数组下标为0

  1. 最早的C语言是这样,后续语言为了延续习惯
  2. 寻址是 a[n] = 起始地址+n*偏移大小 如果小标1开始就是 a[n] = 起始地址+(n-1)*偏移大小 这样会多一次计算量

溜了,睡觉。。。。

05 -06| 深入浅出索引

索引可以提高数据的查询效率,就像书的目录。其中索引设计到一部分数据结构和算法的内容,想要深入理解索引的概念那正要补补数据结构和算法了。

涉及数据结构

  • 哈希表
  • 有序数组
  • 搜索树

优缺点

数据模型|优点|缺点
:-:|:-:|:-:|:-:|
哈希表|插入和查找在没退化成链表情况下O(1)|不适合范围查找
有序数组|等值范围都适合O(long(N))|写入性能成本高
搜索树(N叉树)|读写操作O(long(N))|写入最坏时间复杂度O(n)

InnoDB主键(聚簇)索引 和非主键索引的区别

主键索引的叶子节点放的整行数据,非主键索引放的主键的值,也就是说使用非主键索引时需要再查询次主键索引树,这种方式称为回表

eg

1
2
3
4
5
6
7
8
9
mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

select * from T where k betwee 3 and 5 需要执行几次树的检索

  1. 在k索引树上找到k=3,获得 id = 300
  2. 到ID索引树上找 id = 300 取全部值

如此往复,那么怎么优化第2部的消耗能?

索引覆盖

覆盖索引对innodb表特别有用,上面讲到二级索引的值是主键索引的值所以用了覆盖索引可以减少回表查询的次数。由此可见上面的查询可改为

1
select id from T where k betwee 3 and 5

依稀记得刚开始写代码的时候老师傅书过 * 性能不如每行写出要查的值吗,当时很懵逼问了老师傅,得到的解释是查出来的内容少了网络开销也会小(糟老头子误人子弟),其实覆盖索引减少的回表次数才是主要原因

最左原则

最左原则是建立在联合索引上的,联合索引有个好处就是减少回表,但是因为B+树的数据结构形式还是会有些限制的由此有了最左原则

联合索引示意图

假设上面是一个联合索引('name',number) ID为索引保存的值,当要找到 name = abc的时候可以快速定位到位置并且遍历出所有内容,如果是 where name like ‘%a’也可以用到这个联合索引。由此可得,最左可以是最左索引中的最左N个字段,也可以是字符串索引的最左N个字符。

小技巧

  • (a,b)的联合索引,不需要单独给a加上索引。
  • 如果同时需要(a,b) 联合查询,又需要单独查询,建议以ab两个字段的大小决定先后顺序

索引下推

索引下推是 Mysql5.6后的特性,拿上面例子举例如果完成下面这条语句sql查询

1
2
mysql> select * from name like '%a' and number = 140

5.6之前的执行步骤

  1. 在联合索引的树上找到a开头的主键ID
  2. 通过主键ID找到 number 值
  3. 对比是否满足 number = 140

5.6之后的执行步骤

  1. 在联合索引的树上找到a开头的主键ID
  2. 和联合索引中的ID 对比是否满足 number = 140

如何建立高效的主键索引

主键索引是基于B+数的数据结构,在数据写入时如果非顺序写入会存在插入一个节点而移动后面节点的情况。为了避免这种情况,我们一般会使用自增保证数据的顺序写入。而且非主键索引的值是主键索引的值,创建主键索引时应尽量保证索引的短小

PHP翻转一个单向链表(图解)

最近在撸mysql发现底层很多涉及到数据结构和算法的知识点,看见有点撸不动了转过头来看算法。

链表是什么

链表与动态链表这个里面有用C完成的一部分介绍,知识刚好可以交叉。其实单这样看也是看不动的推荐我的docker环境,和打开PHP的xdebug

#完整代码实现

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
<?php

/**
* 一个链表结构
* Class ListNode
*/
class ListNode {
public $val = 0;
public $next = null;

function __construct($val)
{
$this->val = $val;
}
}

/**
* 链表尾部追加
* @param $node
* @param $val
*/
function addList($header ,$val)
{
$scan = $header;

while(!is_null($scan->next)){
$scan = $scan->next;//遍历到尾部
}

$scan->next = new ListNode($val);

}

/**
* 打印这个链表
* @param $header
*/
function seeList($header)
{
$scan = $header;
while(!is_null($scan->next)){
echo $scan->val.PHP_EOL;
$scan = $scan->next;
}
echo $scan->val.PHP_EOL;
}

/**
* 反转
* @param $header
* @return string
*/
function rev($header)
{

$re = '';

while($header){
$temp = $header->next;
$header->next = $re;
$re = $header;
$header = $temp;

}

return $re;

}


$header = new ListNode(1);
addList($header ,2);
addList($header ,3);
addList($header ,4);
seeList(rev($header));

#图解

初始化链表结构

这是最开始生成的一个一级链表结构,val是当前值 next是对应的下个节点

链表的第一次循环

第一次循环后经历了如下变化

  • $temp = $header->next; 把除第一个以外的后续节点暂存 2->3->4

  • $header->next = $re; 把上一次的$re插入$header第二个节点 1->null

  • $re = $header; $re为最终的返回值,迭代这个结果 1->null

  • $header = $temp;$header原始内容发生变化,$temp暂存内容替代,也是为下次偏移准备 2->3->4

第二次循环

链表第二次循环

变化如下

  • $temp = $header->next; 把除第一个以外的后续节点暂存 3->4

  • $header->next = $re; 把上一次的$re(1->null)插入$header第二个节点2->1->null

  • $re = $header; $re为最终的返回值,迭代这个结果

  • 继续偏移

接下来如此反复

链表反转后续

在docker下的PHP Xdebug配置

这段时间在研究算法,为了看一些算法的迭代和递归过程需要断点。这里记录下我自己在MAC docker环境下的PHP xdebug配置过程。

配置

这里跳过了安装步骤,因为docker里的xdebug难点不在扩展的安装,而在通信。

PHPxdebug原理

上图是官网上xdebug的工作原理

  • 浏览器,访问web页面服务(http协议request)
  • PHP发起基于DBGP协议的调试请求,访问IDE 9000端口
  • IDE监听端口收到请求后开始同步调试
  • 调试完成返回(http协议的response)
  • 完成一次http会话请求

由此我们可以得出,docker环境不需要为这次xdebug调试工作映射任何容器端口到物理机。但是docker必须知道物理机的IP。物理机的IP写入docker有2种方法

  1. 使用extra_hosts添加主机名映射,但是这种需要结合环境变量达到自动启动的目的(不推荐使用)
1
2
3
4
...
extra_hosts:
- dockerhost:$DOCKERHOST
...

启动需要shell

1
2
3
export DOCKERHOST=$(ifconfig | grep -E "([0-9]{1,3}\.){3}[0-9]{1,3}" | grep -v 127.0.0.1 | awk '{ print $2 }' | cut -f2 -d: | head -n1) \
&& docker-compose -f docker-compose.yml up

二. 创建本地回环别名

1
sudo ifconfig lo0 alias 10.0.1.1

mac本地回环

它的作用是创建一个类似127.0.0.1回路的别名

  • lo 回环接口
  • eth0 以太网接口
  • br0 网桥接口
  • wlan0 无线接口

设置完IP或者别名后就需要配置php扩展的debug配置了

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

#远程调试IP
xdebug.remote_host= 10.0.1.1
#请求端口
xdebug.remote_port = 9123
#约定的调试key
xdebug.idekey = PHPSTORM
#日志目录
xdebug.remote_log='/www/xdebug_php7.log'
#开启
xdebug.remote_enable = 1

配置编辑器

直接上图

设置

配置端口

设置key

php.ini配置信息选择一致

编辑调试模式

选择

编辑器的配置基本完成,下面就是测试是否可以正常调试了我们先打上断点

断点debug测试

算法中的时间复杂度

时间复杂度是衡量算法好坏的标准,这边列举一些常见的时间复杂度的级别。

复杂度 说明
O(1) 常数复杂度
O(log n) 对数复杂度
O(n) 线性时间复杂度
O(n^2) 平方
O(n^3) 立方
O(2^n) 指数
O(n!) 阶乘

算法在少量计算下没多少体现,在次数和量级增长的情况下性能也是线性增长的
时间复杂度

《图解HTTP》

这本书不是很厚,看着像一本小漫画。但是里面的知识点该讲到的都是讲到了的只是没那么深(作者的话就是更好理解),一个周末2天时间撸完的。

图解HTTP

主要知识点

  • TCP/IP
  • 状态码
  • http请求头
  • http和https的优缺点
  • 用户身份认证
  • web常见攻防

一篇250页的小册子不可能把上面的知识面面俱到,至少TCP/IP还有很大一块知识需要了解。对于自身收获比较大的是http请求头里的cache-control使用好了真的可以减少很大的服务器压力这是之前不知道的知识点,然后就是http和https的优缺点比较官方和学术的了解到了区别。

总的来说,讲得不细但是该有的都有。不枯燥值得投入时间阅读

03 | 事务隔离:为什么你改了我还看不见?

这篇主要是记录了事务操作的几个隔离级别,为了方便解释和记忆会以表格的形式来归纳总结。事务的隔离级别和特性都是非常有趣的东西

事务的特性

ACID

  • 原子性
  • 一致性
  • 隔离性
  • 持久性

隔离性和隔离级别

当多个事务同时发生时就会出现脏读,不可重复读幻读,为了解决这些问题有了隔离级别这个概念。标准隔离级别和区别见下表

隔离级别 描述
读未提交 事务未提交就可以被其他事务读了
读提交 事务提交后变更其他事务才能看到
可重复读 启动时的数据在执行过程中看的一致,其他事务不可读
串行化 会加读写锁,后访问的事务必须等待前者先完成

#一张图区分隔离级别

事务A 事务B 读未提交 读提交 可重复读 串行化
启动事务查询得到值1 启动事务
查询得到值1
将1改成2
查询得到V1 2 1 1 1
提交事务B
查询得到V2 2 2 1 1
提交事务A
查询得到V3 2 2 2 2

#事务中的视图创建

在事务执行时数据库里面会创建一个视图的概念,具体如下

读未提交 读提交 可重复读 串行化
- sql执行时创建 事务启动时 直接加锁

#事务的隔离实现

  1. 事务如何实现回滚

比较形象一点,类似于git。每次修改都会有次commit记录修改内容即回滚版本,这样保证了所有事务可以正常回滚就是数据库的多版本并发控制(MVCC)

  1. 事务日志的删除时机

在没有更早的回滚日志时会删除事务日志,这样就意味着长事务会存在很多老的事务视图,会占用大量的存储空间

事务的启动方式

还有点内容,需要结合百度看下什么名堂

02 | 日志系统:一条SQL更新语句是如何执行的?

这边会介绍MySQL中的两种更新日志,binlog和InnoDB的redo log,这两块是MySQL比较重要也跑不掉的两个知识点。

binlog

介绍

binlog主要是数据库server层的东西在
mysql基础架构 有讲到server层和储存引擎层的一些关系。binlog给MySQL带来了crash-safe的能力(crash-safe这块DBA接触的比较多也比较偏运维,简单来说我的理解就是保证已提交事务数据依然存在,未提交事务自动回滚。其实单库还好主从同步的时候可以避免一些链路中断的情况)

启用

修改配置文件 mysql.cnf

1
2
3
4
5
6
7
8
9
10
11
#第一种方式
#开启binlog日志
log_bin=ON
#binlog日志的基本文件名
log_bin_basename=/var/lib/mysql/mysql-bin
#binlog文件的索引文件,管理所有binlog文件
log_bin_index=/var/lib/mysql/mysql-bin.index

#第二种方式,等同于上面三行
log-bin=/var/lib/mysql/mysql-bin
binlog_format = row #行的日志格式

查看binlog是否正常启用

1
show variables like '%log_bin%';

binlog的几种数据格式

格式 格式介绍 优点 缺点
STATEMENT(SBR) 记录每一句sql语句 日志量相对较小 必须记录上下文UUID等随机函数哦豁
ROW(RBR) 行的复制 每一条记录记录更安全,每一行修改更高效,数据恢复更方便 日志量大
MIXED 上面的混合 系统决定用行或段,数据量大小由sql决定 -

redo log

介绍

redo log 是InnoDB引擎的日志,它实现了Write-Ahead Logging(WAL)技术,顾名思义它是预写入日志,保证了即使异常重启数据也不会丢失(crash-safe)。它可以设置文件大小与文件个数,比如一个文件1G一共4个redo log文件,它会在满足一定规律后进行刷盘操作checkpoint。InnoDB的事物也是依赖于redo logundo log进行的。

binlog 和 redo log的差异

名称|引擎|大小|
:-:|:-:
redo log|InnoDB|循环写入刷入磁盘
binlog|mysql server层|累加

一条update语句在日志中的操作

1.执行器先找引擎取ID=2的一行,引擎直接用搜索树找到这条数据,如果在内存中直接返回没在磁盘中读入内存返回。
2.执行器拿到引擎行数据,直接加1操作得到新的一行,再调用引擎接口写入这行数据
3.引擎讲数据更新到内存中,同时记录redo log,此时redo log处于prepare状态,告知执行器完成随时可以提交事务。
4.执行器生成这个操作的binlog,并写入磁盘
5.执行器调用引擎提交事务,引擎redo log改成提交状态

总结

  • 这边采用了一个分段提交,增加了binlog日志的准确性,是维持数据逻辑一致性的常用方案
  • 数据恢复/数据库扩容 是先同步当天备份后同步binlog日志
  • redo log 用于保证crash-safe能力
  • innodb_flush_log_at_trx_commit sync_binlog 建议设为1保证数据不被丢失

01 | 基础架构:一条SQL查询语句是如何执行的?

#写在前面

最近在看丁奇在专栏中讲解mysql的一套课程,作为观摩老师傅的技巧不由的掏出了我的小本本把每集我认为比较核心的知识点记录在了自己的博客上。同时也分享出极客时间的这套课程
MYSQL丁奇45讲,侵必删。

知识点

  • 连接器
  • 查询缓存
  • 分析器
  • 优化器
  • 执行器

mysql基础架构

mysql的基础架构图

连接器

  • 建立连接
  • 获取权限
  • 维持管理链接

mysql -h$ip -P$port -u$user -p

连接器负责的权限是再每次连接时查询出来的,即使后续管理员修改了权限没有断开权限也不会更改。
show processlist可以看见当前的数据库连接状态,如果长时间未连接会自动断开wait_timeout控制它,默认8小时

长连接:连接成功后客户端持续请求,一直使用同一个连接
短连接:每次执行完几次查询后就断开连接,下一次查询重新建立一个
利:建立连接比较麻烦有时间和内存开销
弊:内存开销,MySQL在执行过程中临时使用的内存管理在连接对象中,5.7之前需要程序之间写逻辑杀死进程并重启,5.7过后mysql_reset_connection初始化连接资源

查询缓存

查询缓存适合于配置表,因为不常修改。查询缓存只要表中的一行数据更新整张表的查询缓存都会清空,存在的形式是key-value既 语句->结果。MYSQL提供了SQL_CACHE显式来指定。需要注意的是MYSQL8.0后的版本删除了查询缓存

select SQL_CACHE * from users where id = 28866

分析器

这个环节会解析语法,查看语法是否合法,语句的动作以及操作的表

优化器

在经过分析器后,MYSQL知道了用户的意图,然后选择最优的索引或者执行方案进入下个阶段,这个在讲索引的时候会讲到

执行器

开始执行时要先判断下你是否对相应表有权限,如果没有返回错误提示,如果有权限就会根据引擎定义去使用引擎接口调取数据

web-push 国内实现浏览器的消息推送

一次业务需要我们用户部提出一个web push的需求,说来惭愧虽然在国外web push已经算主流的用户召唤手段了但是国内因为某种大家都知道的原因它被大多厂家放弃。下面我会把本站的实现web push的一些方法在下面写出来,欢迎指正。

web push 是什么

浏览器授权后可以实时消息通知对方,类似于APP中的消息通知。但是整体支持并没全部覆盖,支持web push的浏览器,内核有限,加上国内用户有功夫网的保护,无法授权并且通知到用户,所以这门在国外如火中天的用户召回技术在国内很少有人提及

web-push能干什么

  • 召回用户,增加用户粘性
  • 消息通知
  • 减少活动中的短信运营成本

web-push 通知如下图

web-push通知框

本次 web push 实现用到的知识

订阅

  • Notifications API (浏览器通知接口)
  • Service Workers(长驻浏览器中的脚本)

推送

  • JWT鉴权
  • shadowsocks
  • web-push

web-push实现原理

注册服务(订阅)

Notifications API

Notifications API 允许网页控制向最终用户显示系统通知 —这些都在顶级浏览上下文视口之外,因此即使用户已经切换标签页或移动到不同的应用程序,也可以显示。该API被设计成与不同平台上的现有通知系统兼容。

下面给出的是权限注册代码,可以在浏览器的Console面板贴上它,浏览器会弹出询问授权信息选择是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//这段代码讲向用户请求通知的权限,返回3种状态
//granted(被授予) denied(被拒绝) default(默认)

Notification.requestPermission().then(function(result) {
if (result === 'denied') {
console.log('拒绝');
return;
}
if (result === 'default') {
console.log('默认');
return;
}
if (result === 'granted') {
console.log('允许');
return;
}
});

如下图所示

Notification注册询问

下面我们调用Notification接口占时一个浏览器的推送通知继续Console面板贴上它

1
2
3
4
5
var options = {
body: '你好呀,这是一个测试',
icon: ''
}
var n = new Notification('张俊杰的博客测试dome',options);

允许结果如下图

web-push通知效果

总结下上面的两个小dome其实是让用户允许询问通知获得浏览器授权的一个过程,然后通知一下用户的例子。但是实际使用中

Service Worker

Service Worker是浏览器为web提供的一个功能让web端有常驻浏览器线程的能力,需要我们自己注册脚本到Service Worker中在下图中就可以看见我们注册的一个sw.js脚本。

浏览器Service Worker展示

下面这个脚本会检测浏览器是否支持服务工作线程和推送消息,并且注册服务工作线程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if ('serviceWorker' in navigator && 'PushManager' in window) {
console.log('Service Worker and Push is supported');

navigator.serviceWorker.register('https://www.phpzjj.com/js/app/sw.js')
.then(function(swReg) {
console.log('Service Worker is registered', swReg);

swRegistration = swReg;
})
.catch(function(error) {
console.error('Service Worker Error', error);
});
} else {
console.warn('Push messaging is not supported');
pushButton.textContent = 'Push Not Supported';
}

如果注册成功会如下图显示

serviceWorker的注册

下面的代码既是我们注册的常驻文件icon可以引用自定义的网络图片,这边为了省事就用的本地静态图了

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
'use strict';
var url = ''
self.addEventListener('push', function(event) {


const data = event.data.json()
const title = data['title'];
url = data['url']
const options = {
body: data['body'],
icon: 'images/icon.png',
badge: 'images/badge.png'
};

event.waitUntil(self.registration.showNotification(title, options));
});

self.addEventListener('notificationclick', function(event) {

event.notification.close();

event.waitUntil(
clients.openWindow(url)
);
});

整个注册脚本的封装(JS功底的确有限代码有点丑陋)

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
/**
* 2019年02月16日18:33:22
* 基于Notification的web推送
*/
var config = new function (){
return {
debug:true, //打开错误提示
publicKey:'BLMtwQjfLMjmcGjcoX9AhSnEd6yl5JAAcyG9UkyNB0RL_AWuN8bLGf0RE2JWV6LBEsApgXtCdWiHn74jrE4dv_s'
}
}

let swRegistration = null;

/**
* 申请注册Notification权限
*
* no:浏览器不支持
* agree:用户同意过
* success:用户第一次同意
* fail:用户拒绝
*
*/

function register(callback) {
var state = ''
// 浏览器是否支持
if (!("Notification" in window)) {

if(config['debug']){
console.log('浏览器不支持');
}

callback('no')
}

// 检查用户是否同意接受通知
else if (Notification.permission === "granted") {
callback('agree')
}
// 否则我们需要向用户获取权限
else if (Notification.permission !== 'denied') {

Notification.requestPermission(function (permission) {
// 申请权限

if (permission === "granted") {
callback('success')
}else{
callback('fail')
}

});
}

}


function subscribeUser(callback) {


const applicationServerKey = urlB64ToUint8Array(config["publicKey"]);

return swRegistration.pushManager.subscribe({
userVisibleOnly: true,
applicationServerKey: applicationServerKey
})
.then(function(subscription) {
callback(Base64.encode(JSON.stringify(subscription)))
})
.catch(function(err) {
console.log('Failed to subscribe the user: ', err);
});
}



/**
* 接口加密
* @param {*} base64String
*/
function urlB64ToUint8Array(base64String) {

const padding = '='.repeat((4 - base64String.length % 4) % 4);
const base64 = (base64String + padding)
.replace(/\-/g, '+')
.replace(/_/g, '/');

const rawData = window.atob(base64);
const outputArray = new Uint8Array(rawData.length);

for (let i = 0; i < rawData.length; ++i) {
outputArray[i] = rawData.charCodeAt(i);
}
return outputArray;
}




//注册
if ('serviceWorker' in navigator && 'PushManager' in window) {
console.log('Service Worker and Push is supported');

navigator.serviceWorker.register('/js/app/sw.js')
.then(function(swReg) {
swRegistration = swReg;
})
.catch(function(error) {
console.error('Service Worker Error', error);
});
} else {
console.warn('Push messaging is not supported');
}


var Base64 = {

// private property
_keyStr: "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=",

// public method for encoding
encode: function(input) {
var output = "";
var chr1, chr2, chr3, enc1, enc2, enc3, enc4;
var i = 0;

input = Base64._utf8_encode(input);

while (i < input.length) {

chr1 = input.charCodeAt(i++);
chr2 = input.charCodeAt(i++);
chr3 = input.charCodeAt(i++);

enc1 = chr1 >> 2;
enc2 = ((chr1 & 3) << 4) | (chr2 >> 4);
enc3 = ((chr2 & 15) << 2) | (chr3 >> 6);
enc4 = chr3 & 63;

if (isNaN(chr2)) {
enc3 = enc4 = 64;
} else if (isNaN(chr3)) {
enc4 = 64;
}

output = output + this._keyStr.charAt(enc1) + this._keyStr.charAt(enc2) + this._keyStr.charAt(enc3) + this._keyStr.charAt(enc4);

}

return output;
},

// public method for decoding
decode: function(input) {
var output = "";
var chr1, chr2, chr3;
var enc1, enc2, enc3, enc4;
var i = 0;

input = input.replace(/[^A-Za-z0-9\+\/\=]/g, "");

while (i < input.length) {

enc1 = this._keyStr.indexOf(input.charAt(i++));
enc2 = this._keyStr.indexOf(input.charAt(i++));
enc3 = this._keyStr.indexOf(input.charAt(i++));
enc4 = this._keyStr.indexOf(input.charAt(i++));

chr1 = (enc1 << 2) | (enc2 >> 4);
chr2 = ((enc2 & 15) << 4) | (enc3 >> 2);
chr3 = ((enc3 & 3) << 6) | enc4;

output = output + String.fromCharCode(chr1);

if (enc3 != 64) {
output = output + String.fromCharCode(chr2);
}
if (enc4 != 64) {
output = output + String.fromCharCode(chr3);
}

}

output = Base64._utf8_decode(output);

return output;

},

// private method for UTF-8 encoding
_utf8_encode: function(string) {
string = string.replace(/\r\n/g, "\n");
var utftext = "";

for (var n = 0; n < string.length; n++) {

var c = string.charCodeAt(n);

if (c < 128) {
utftext += String.fromCharCode(c);
} else if ((c > 127) && (c < 2048)) {
utftext += String.fromCharCode((c >> 6) | 192);
utftext += String.fromCharCode((c & 63) | 128);
} else {
utftext += String.fromCharCode((c >> 12) | 224);
utftext += String.fromCharCode(((c >> 6) & 63) | 128);
utftext += String.fromCharCode((c & 63) | 128);
}

}

return utftext;
},

// private method for UTF-8 decoding
_utf8_decode: function(utftext) {
var string = "";
var i = 0;
var c = c1 = c2 = 0;

while (i < utftext.length) {

c = utftext.charCodeAt(i);

if (c < 128) {
string += String.fromCharCode(c);
i++;
} else if ((c > 191) && (c < 224)) {
c2 = utftext.charCodeAt(i + 1);
string += String.fromCharCode(((c & 31) << 6) | (c2 & 63));
i += 2;
} else {
c2 = utftext.charCodeAt(i + 1);
c3 = utftext.charCodeAt(i + 2);
string += String.fromCharCode(((c & 15) << 12) | ((c2 & 63) << 6) | (c3 & 63));
i += 3;
}

}

return string;
}

}

//为了满足日后的一些统计要求这边加上了回调,本来想封装成插件用配置操作,但是我懒。。。而且功能也实现了,上面代码无需多关心有兴趣可以看看如果是实际使用替换 publicKey 即可

var register = register(function(e){
if(config['debug']){
console.log(e);
}

if(e ==="success"){

subscribeUser(function(e){
$.post("/api/push", {token: e});
})

}

})

把整个代码跑起来实际流程是这样的

授权:询问用户索取权限->生成公钥后验签的用户唯一标识信息->base64转码->ajax给后台数据库保存

1
2
eyJlbmRwb2ludCI6Imh0dHBzOi8vdXBkYXRlcy5wdXNoLnNlcnZpY2VzLm1vemlsbGEuY29tL3dwdXNoL3YyL2dBQUFBQUJjZXJ4dWdvanhOTHdhalN6cXdlc3JwdVQyTTJYUjFJdjV2aXZVc081V0hrLUQ3dkxhZ3dZd2ZERkN6UmhkbmItMHBHR19jNGZLSzNGS0FRR1dwdUp2OXVQdTJHbC0zZElmRzRGNXZfUUtqWFpsMkRSczNiNkRBVTRyY3hlQlVXTURKRDBWMzRNVGtzcXhtSGV6WWY4X2pRcjhfeTBCckY3enRaeTJYcGVmNXpEYzdBMCIsImtleXMiOnsiYXV0aCI6InFwLXg5U01qQ1JhSzlhLWVMR1JSV3ciLCJwMjU2ZGgiOiJCRjdqYnVTZlYzWlNlV0VsRXZSMkhrRFlnSHg5cWxHLUVFdHVuOWVGTkpqRURpVVJ0VlN1MVppMTVyb3VydWNrUDNkb0w4UURmS2h0UjBxV3dwZjFuR1kifX0=

1
{"endpoint":"https://updates.push.services.mozilla.com/wpush/v2/gAAAAABcerxugojxNLwajSzqwesrpuT2M2XR1Iv5vivUsO5WHk-D7vLagwYwfDFCzRhdnb-0pGG_c4fKK3FKAQGWpuJv9uPu2Gl-3dIfG4F5v_QKjXZl2DRs3b6DAU4rcxeBUWMDJD0V34MTksqxmHezYf8_jQr8_y0BrF7ztZy2Xpef5zDc7A0","keys":{"auth":"qp-x9SMjCRaK9a-eLGRRWw","p256dh":"BF7jbuSfV3ZSeWElEvR2HkDYgHx9qlG-EEtun9eFNJjEDiURtVSu1Zi15rouruckP3doL8QDfKhtR0qWwpf1nGY"}}

ps:如果你没科学上网,请拿火狐浏览器测试。

publicKey 的公私钥一定要配对否则后续的通知用户是接收不到的,浏览厂商为了保证用户不被普天满地的广告覆盖也加强了推送时对身份的验证。这里就需要引入applicationServerKey的概念,它又被称作VAPID

两种生成公私钥的方法
1:传送门
2:一些轮子里支持生成

推送消息

Linux下Shadowsocks的http协议服务

这里记录一些在国内无法推送谷歌浏览器的一些方法,更多关于推送的消息方法见谷歌他们的轮子上面讲的比较全了,有文档案例我就又懒一下。这边我用的是php源码,在翻了他们的源码后发现底层用的GuzzleHttp(有良好的异步支持)并不需要用我一开始想的swoole或者另外一些多进程的方法,并且在new WebPush()时候暴露出了配置参数,也就是说支持代理访问。大体如下就好

1
2
new WebPush($auth,[],10,['proxy' => 'udp://192.168.1.5:1087'] );

升级Python

我用的CentOs版本比较老,Python还是2.7的所以先升到3.6

算了尝试了下我放弃了yum还要安装一堆依赖,以后还是用Centos 7 年轻不懂事选了一个6.5哎。

安装 Shadowsocks 服务端

一.尝试在梯子上安装

1
2
sudo yum install python-setuptools && easy_install pip

二.编辑配置文件

1
2
3
4
5
6
7
8
9
10
11
sudo vi /etc/shadowsocks.json

{
"server":"my_server_ip",
"local_address": "127.0.0.1",
"local_port":1080,
"server_port":my_server_port,
"password":"my_password",
"timeout":300,
"method":"aes-256-cfb"
}

三.启动

1
2
3
4
//正常后台启动
sslocal -c /etc/shadowsocks.json -d start
//因为服务端和用户端在一台,会有点冲突
nohup sslocal -c /etc/shadowsocks.json &

四.测试

1
curl --socks5 127.0.0.1:5343 https://www.phpzjj.com/

如果有正常返回证明socks5的Linux代理完成,在实例化的时候带上代理~

new WebPush($auth,[],10,['proxy' => 'socks5://192.168.1.5:1087'] );

请我喝杯咖啡吧~