MySQL两段式提交

发表于 2022-06-21 分类于 MySQL

两段式提交是MySQL数据持久化的保证。

两种日志

binlog和redolog

binlog记录了数据库表结构和表数据变更，主要有两个作用：复制和恢复数据

redo log 是 Innodb 引擎独有的日志模块，它只记录有关 Innodb 引擎的事务日志，记录内容为对数据页的物理操作

	binlog	redolog
适用对象不同	mysql server 层	Innodb 存储引擎层
写入方式不同适用对象不同	追加写，一个文件满了写新文件mysql server 层	循环写固定文件Innodb 存储引擎层
写入方式不同	逻辑日志，一个事务具体操作内容	物理日志，页的修改情况
写入磁盘时间不同	提交事务前一次写入	在事务进行中有后台线程不断同步
用途不同	主从复制、数据备份	数据恢复

两段式提交

两种日志虽然都保证持久化，但是侧重点不同。

1、redo log（重做日志）让InnoDB存储引擎拥有了崩溃恢复能力。

2、binlog（归档日志）保证了MySQL集群架构的数据一致性，主从节点的同步都是通过binlog保证的。

如果单独提交
先写 redo log 后写 binlog，也就是事务可能还没有提交，系统崩溃了，虽然可以通过redo log恢复，但是binlog还没有这条数据，就会造成主从不一致先写 binlog 后写 redo log，这个过程说明事务已经提交了，系统崩溃了，虽然binlog里面有数据，但是redo log里面没有，也会发生主从不一致，并且redo log因为不全，即使重新恢复的时候也不是最新的数据

两段式提交

就是将redolog的提交拆为两各阶段，prepare阶段和commit阶段，在中间插入binlog提交。

发生异常

1、在prepare阶段写入redolog的时候发生异常，那不管redolog有没有写完，都会回滚，因为binlog没有写入，会导致日志不一样，主从数据不一致。

2、在commit阶段写入binlog的时候发生异常

    如果在写完之前，那也会回滚，毕竟没写完和没写一样，会导致日志不一样，主从数据不一样。

    如果在写完之后，那就不会回滚了，两种日志都写完了，能保证数据一致了。

3、在commit阶段提交redolog的时候发生异常，前面写完binlog就不会回滚了，那这里也不会回滚，能保证数据一致性。

MySQL的回表

发表于 2022-05-16 分类于 MySQL

简述

说起回表，肯定要说起MySQL的存储结构B+树。

每条数据是以主键和数据的形式存放在B+树的节点上，如果我们通过主键查询的话，直接通过和节点上的主键比较判断，相等的话直接取。

其他索引是将索引和主键值放在一起的，通过索引查到主键，在通过主键去查找数据。这也就是为什么主键索引会比其他索引快。

主键查询

主键和数据是通过B+数的形式存储的，查的时候肯定也是通过树的查询方式查询的。如下图查询主键Id为4的数据，先根据根节点查询，4小于10，再往子节点查找，然后跟子节点的值比较，在2、4之间，再寻找这区间的节点，第一个值是3，不匹配，在查找下一个，值是4匹配，放回数据记录data。

非主键索引查询

其实和主键查询差不多，只不过相当于两次主键索引查询，第一个查询到的不是数据，是主键值，再根据主键值，按照主键索引查询再来一次。如图，如果数据有一条数据是2019-04-01创建的，数据的主键id为4，我们想根据这个创建时间（不知道主键id）找到这条数据。那就是先根据创建时间找到主键4，后根据主键4找到记录数据data。

回表

分主键索引相当于两次查询，第一次查询主键，第二次查询数据，将第二次查询的数据结果放回给第一次查询结果，就叫回表。按照上面的图示，就是将data放回到创建时间的查询中。

覆盖查询

使用非主键查询的时候，也会存在不用回表的情况，这种叫做覆盖查询。

什么是覆盖查询呢，就是在我们使用索引的时候，索引本身包含的数据字段已经满足查询要求的字段了，就不用具体根据主键去找具体的记录数据了。

如果有一份人员信息数据，存有名称，性别，出生日期和其他一些字段。由于通过出生日期和性别的查询较多，我们用这两个字段构建了一个联合索引。现在我们要查询2019-04-01出生的女孩人数。

如图，联合索引按出生日期和性别联合构建的索引，先按出生日期排序，再按性别排序。通过索引，查询到只有一个主键为4满足，这时候我们需要计数，因为主键是唯一的，也不需要我们通过主键再次查询了，计算主键数量就够了，直接返回1。这就不用回表。

最左覆盖原则

上面我们说到根据联合索引查询，其实联合索引有两个值，我们只根据一个值去查询的，但也查询到了。这是为啥呢，这就是最左覆盖原则。根据我们的查询条件，会匹配索引，从左边第一个字段开始，所以我们查询的时候有条件过滤最好和索引顺序一直。如上图，我们查询的是整个表里面有女生多少人就没办法走联合索引了。

扩展

是不是觉得这个B+树还挺好用的，思路挺清晰的。但是如果我们的B+树层级很深，是不是查询比较的次数就多了，耗时也就多了，也就不好用了。所以大家知道B+树有多少层吗？

B+树一般是3~~4层，为啥说3~~4层呢，这也是个计算值，我们看一下具体怎么计算的。

MySQL的引擎是InnoDB，InnoDB默认页大小是16k，当然也可以设置，B+树的每个节点都是一页。从上面可以知道，节点分为数据节点和非数据节点，

在数据节点中，通常数据大小为1k，16k / 1k = 16，也就是每个数据页中大概会存放16条数据。

在非数据节点中，主要存放的是主键ID和指针，主键大概8字节，指针大概6字节，总共14字节，1k=1024字节，整页可以存放1170个（16 * 1024 / 14 = 1170）。

在3层的情况下，2层非数据节点，1层数据节点，可以存放大概21902400条数据。1170117016=21902400，已经到千万级别了，一个表里放千万条数据已经很大了，再大就要考虑分库分表了。

HashMap和ConcurrentHashMap的put方法详解

发表于 2022-05-08 分类于 JAVA

结构简述

HashMap和ConcurrentHashMap的结构都是一样的，jdk1.8之后都是数组+链表+红黑树，链表长度超过8之后转红黑树。

计算

节点为6个的时候，链表的平均查询时间：(1+2+3+4+5+6)/ 6 = 3.5，红黑树的平均查询时间 (1+22+33)/6=2.3

节点为7个的时候，链表的平均查询时间：(1+2+3+4+5+6+7)/ 7 = 4，红黑树的平均查询时间 (1+22+34)/7=2.4

节点为8个的时候，链表的平均查询时间：(1+2+3+4+5+6+7+8)/ 8 = 4.5，红黑树的平均查询时间 (1+22+34+1*4)/8=2.6

链表的时间复杂度为O(n)，而树的时间复杂度为O(ln n)，上面计算有明显的效率变化，至于为啥选8这个阈值，应该是基于大量数据收集之后比较而定的。

结构图

HashMap

流程图

代码详解

ConcurrentHashMap

流程图

代码详解

数组和链表的区别

发表于 2022-04-26 分类于 JAVA

虽然网上已经有很多了，但是我还是尝试总结一下，添加一点自己的心得。

总体来说，数组和链表是两种数据结构，所有的异同都是这两种数据结构的特点导致的。这两种数宝结构是计算机的基本数据结构，基态所有都是基于这两种数据结构实现的，只不过在细节上有区别。

简述

数组：多用于读多写少的情况，读取O(1)，写入O(n)，修改O(1)，删除O(n)；需要连续内存。

链表：多用于读少写多的情况，读取O(n)，写入O(1)，修改O(n)，删除O(1)；不需要连续内存。

数据结构差异

从下图很明显就能看出两者的差别。数组需要连续，即连在一起，而链表不需要，只需要有个指针指向下一个。但是这个指向下一个的指针，也需要占用内存，导致链表中的单个元素比数组中的一个元素的内存大。

增删改查的效率差异

上面的数据结构差异，不可避免的导致了读写性能的差异。

数组

就像把人都聚集在一起，排好大小个顺序放在一个房间(连续内存)里。

查：一般我们查，都是按下标去查数组里的元素，也就相当于知道按大小顺序排的第多少个，直接找到就行。O(1)

改：既然我们能查到某个元素，改的话就是换掉这个元素。就相当于找到某个位置的人，把这个人换掉，一个位置换个人而已。O(1)

增：这时候你需要增加一个人（元素）进来，找到位置，这时候这位置上原本是有人（元素）的，那现在插入的人（元素）来了，这位置和后面位置的人都要向后移一位。   O(n)

删：这刚好和上面的增操作是相反操作。找到合适位置后，踢出这个人（元素），后面位置上的人（元素）都要前进一位。O(n)

链表

就像我们把一个一个人分开，他们每个人只知道排在自己后面的人在什么位置(也可以知道前一个人)，类似于手拉手排队一样。

查：这时候没有具体位置给我们，因为我们也不知道每个人（元素）的具体位置。只是因为大家手拉手（指针）的原因，前一个人能找到排在他后面位置的人。那我们找一个人的时候，就需要每个人都问一边，问一下是不是我们要找的人，不是的话再找下一个，直至找到或者找完。O(n)

改：和上面相同，既然能找到，就能换掉，只不过这次换有点特殊。每个人都是手拉手（指针），我们换掉之后要保证他们还是手拉手（指针）。O(n)

增：这时候你需要增加一个人（元素）进来，找到位置，这时候这位置上原本是有人（元素）的，后面的位置也可能是有人（元素）的，此时我们不要移动后面的人，只需要前后位置人的手牵到的是新增人员（元素）的手行，这样就减少了移动的操作。O(1)

删：这刚好和上面的增操作是相反操作。找到合适位置后，踢出这个人（元素），这位置前后面位置上的人（元素）手拉手就行。O(1)

空间差异

数组

上面也说到了，数组就像把人都聚集在一起，排好大小个顺序放在一个房间(连续内存)里，那对房子的要求就比较高，需要有足够大的房子。如果新增一人，房间（连续内存）不够大了，那所有的人都要换一个大一点的房子进去按顺序排着。这样就不利于扩展，大家都知道大房子（连续内存）是稀缺资源。

链表

而链表就比较友好了，有块空地(内存)就行，因为不需要房子(连续内存)，这样对于空间(内存)利用率就比较高，能把所有没有房子(非连续内存)的地方都用上，这样就比较适合添加人。

扩展

其实计算机的所有底层内存逻辑基本都按这个连续和不连续的模式来的。比如二叉树这种数据结构，说白了也就是链表的一种变种，由链表的指向下一个变成指向下两个。

除此之外，在jvm底层的垃圾回收，基本也是按照这种套路，新老代的垃圾回收，各种回收算法。比如标记清理、标记整理。

标记清理: 只是把内存中无效的对象删掉，可以想象，一块内存中，其中有的对象被删了有的没删，这就导致这部分内存可用性就低，因为内存被没删的内存分隔成一小段一小段的，不是连续的。虽然空间利用率不高，但是这种办法简单，只要删掉无效的对象就行。

标记整理: 算法的前部分和标记-清理算法一样，将无效对象删掉，但是资格算法还有后续，将剩余的对象整理一起，放在内存的一端，这样空出的内存就又连续上了。这种算法对空间的利用率就比较好，但是比较麻烦，毕竟要整理嘛。

约瑟夫环问题

发表于 2022-04-10 分类于技术

约瑟夫斯问题

有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。在跳过指定数量的人之后，执行下一个人。对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

问题

有n个人编号，站成一圈：
1 2 3 4 … … n-1 n

现在从1开始进行报数，报到k的出列自杀，然后剩下的人继续从1报数（当到达编号为n的人时，下一个报数的从编号为1的人开始进行）：
1 2 3 4… k(出列自杀) 1 2 …

直到圈内只剩余m人，求胜利者的编号。
例如：当n=6, k=5, m=1时，5,4,6,2,3将会被依次处决，而1将会幸免。

示例代码如下：

import java.util.ArrayList;
import java.util.List;

public class JosephProblem {

    /**
     * 返回活着的人的位置
     *
     * @param total 总人数
     * @param magicNum 报数到该数字的人自杀
     * @param remain 笑着活下去的人
     * @return
     */
    private List getJosephNumbers(int total, int magicNum, int remain) {

        List<Integer> peopleList = new ArrayList<>();
        for (int i = 1; i <= total; i++) {
            peopleList.add(i);
        }
        List<Integer> diedList = new ArrayList<>();


        int index = -1;  //当前应该删除的位置
        while (true) {
            index = (index + magicNum) % peopleList.size();

            diedList.add(peopleList.get(index));
            peopleList.remove(index);

            //从上一个位置开始计数
            index--;

            //判断是否剩余m个，如果是的话结束
            if (peopleList.size() == remain) {
                System.out.println("共" + total + "人，依次报数，当报到" + magicNum + "的人自杀，" + remain + "个人笑着活下去.");
                System.out.println("死掉的序号顺序为：" + diedList);
                System.out.println("笑着活下去序号为：" + peopleList);
                System.out.println("----------------------------------");
                return peopleList;
            }
        }
    }

    public static void main(String[] args) {
        JosephProblem test = new JosephProblem();

        test.getJosephNumbers(10, 4, 1);
        test.getJosephNumbers(10, 2, 1);
        test.getJosephNumbers(10, 3, 1);
        test.getJosephNumbers(20, 10, 3);
        test.getJosephNumbers(20, 4, 6);
    }
}

输出结果：

共10人，依次报数，当报到4的人自杀，1个人笑着活下去.
死掉的序号顺序为：[4, 8, 2, 7, 3, 10, 9, 1, 6]
笑着活下去序号为：[5]
----------------------------------
共10人，依次报数，当报到2的人自杀，1个人笑着活下去.
死掉的序号顺序为：[2, 4, 6, 8, 10, 3, 7, 1, 9]
笑着活下去序号为：[5]
----------------------------------
共10人，依次报数，当报到3的人自杀，1个人笑着活下去.
死掉的序号顺序为：[3, 6, 9, 2, 7, 1, 8, 5, 10]
笑着活下去序号为：[4]
----------------------------------
共20人，依次报数，当报到10的人自杀，3个人笑着活下去.
死掉的序号顺序为：[10, 20, 11, 2, 14, 6, 19, 15, 9, 7, 5, 8, 13, 18, 12, 4, 17]
笑着活下去序号为：[1, 3, 16]
----------------------------------
共20人，依次报数，当报到4的人自杀，6个人笑着活下去.
死掉的序号顺序为：[4, 8, 12, 16, 20, 5, 10, 15, 1, 7, 14, 2, 11, 19]
笑着活下去序号为：[3, 6, 9, 13, 17, 18]
----------------------------------

简单时间管理

发表于 2022-03-30 分类于管理

时间管理

目标感

给每件事情设定deadline
给长期的事情设置周期循环事项

时间块

30分钟刻度划分
一般管理人员的时间快划分可以到30分钟或者1小时
半天刻度划分
研发人员会按照半天来划分时间，涉及到写代码、用例、测试计划、编译、部署等具体工作，需要时间来思考及实现，所以有效的时间块划分是半天或者一天。

固化日程

固化日程即养成好的习惯，使得时间利用率高，事情处理效率高。
有些固定模板可套用，如：

上班后/下班前处理今日事项和明日规划
早会及总结
上午做需求评审，下午写代码，晚上做分享

个人日程示例：

9.30-10.00：整理项目的进度和风险
10.00-11.00：思考编码方案
11.00-11.50： XX技术方案/监视团队代码
———————————————————
2.30-3.00：接口设计
3.15-6.00：编码
7.00-8.00：小组分享/学习
8.00-8.30：今日事项总结，明日事项规划

工具和方法论

工具：microsoft todo、滴答清单、calendar
方法论：GTD(Get things done)

GitHub个人网站搭建

发表于 2022-03-29 分类于环境搭建

简介

整个流程分3个步骤：新建个人仓库，本地hexo搭建，GitHub连接，本地博客搭建，GitHub设置。

新建个人仓库

1、登录GitHub，如果没有的话申请一下登录。

2、在GitHub上新建一个代码仓。

3、代码仓命名，一般代码仓名字都是用户名.github.io，比如我的用户是 xiaozhigang，则代码仓名 xiaozhigang.github.io

本地hexo搭建

代码上传下载需要Git，而hexo是通过node.js搭建的，所以在搭建hexo之前，需要先安装好Git和node.js。如果某个步骤已经安装好了，可以跳过。然后安装hexo以及安装hexo依赖。

1、Git安装

1、访问git官方地址，下载对应的安装包，进行安装（简单的点击下一步）。官方地址：https://git-scm.com/

2、安装好之后，鼠标右键可以看到：Git Bash Here，点击后打开了。

3、输入：git –version

2、node.js安装

1、访问nodejs官方地址，下载对应的安装包，进行安装（简单的点击下一步）。官方地址：https://nodejs.org/en/download/

2、安装好之后，配置环境变量，并在终端里面输入：node -v

3、安装Hexo

1、安装命令：npm install hexo -g

2、测试是否安装成功，命令：hexo -v

我这已经安装过了，就从网上抄了两个图

4、安装hexo依赖

命令：npm install --save hexo-deployer-git

GitHub连接

git配置SSH key

先看本地是否配置好SSH key（命令：cd ~/.ssh），我这已经是配置过的。

输入生成命令：ssh-keygen -t rsa -C “邮件地址”后。连续回车三次即可：

可以看到在用户文件夹下生成了一个ssh文件夹：

进入到ssh文件夹，复制id_rsa.pub文件里全部内容：

接着打开github主页，点击个人设置，点击左侧的SSH and GPG keys，点击New SSH key ：

将id_rsa.pub复制的内容粘贴到key中，title随便起一个就行。

点击 Add SSH key。

测试是否成功： ssh -T git@github.com

输入测试命令后，接着输入yes，出现下面这个提示说明成功：

配置账号和密码：

-

1	$ git config --global user.name "liyunchen" #你的github用户名$ git config --global user.email "xxx@163.com" #填写你的github注册邮箱

复制

备注：用户名和邮箱记得改为自己的

本地博客搭建

新建博客

开始之前先介绍一下heox的基本命令：

hexo new "postName" #新建文章hexo new page "pageName" #新建页面hexo generate #生成静态页面至public目录hexo server #开启预览访问端口（默认端口4000，'ctrl + c'关闭server）hexo deploy #部署到GitHubhexo help  # 查看帮助hexo version  #查看Hexo的版本

复制

对应的缩写，比如： hexo n == hexo new hexo g == hexo generate

新建一个保存博客的存放目录，比如：D:\公众号\0722。

进入到本地博客存放目录初始化个人博客命令：hexo init