并发容器

发表于 2022-03-20 分类于编程

文章字数：1260,阅读全文大约需要5分钟

JUC包下的14个并发容器，专门应付并发状态下线程安全的问题

介绍

ConcurrentHashMap并发版的HashMap
CopyOnWriteArrayList并发版的ArrayList
CopyOnWriteArraySet并发版的Set
ConcurrentLinkedQueue基于链表的并发队列（不阻塞）
ConcurrentLinkedDeque基于双向列表的并发队列
ConcurrentSkipListMap基于跳表的并发Map
跳表：链表之上加了一层索引，就是一个新的链表，指向源数据的双数索引的位置。这一层的索引之上还可以增加索引，指向本层的双数位置。链表版的二分法。
ConcurrentSkipListSet基于跳表的并发Set
ArrayBlockingQueue阻塞队列基于数组
LinkedBlockingQueue阻塞队列基于链表
LinkedBlockingDeque阻塞队列基于双链表
PriorityBlockingQueue线程安全的优先队列
SynchronousQueue读写成对的队列
LinkedTransferQueue基于链表的数据交换队列
DelayQueue延时队列

一、ConcurrentHashMap

最常见的并发容器之一，常作用于并发场景下的缓存。底层还是哈希表，但是java8中有了优化。

java7采用分段锁，即数据被分成16个部分。每个部分一把锁，各部分之间不冲突。
java8放弃了分段锁，采用CAS乐观锁。
java8中增加了同哈希值组成的链表长度超过8之后会转换成红黑树

二、CopyOnWriteArrayList

并发版的ArrayList, 底层结构还是数组。原理是增删改的操作会加锁，其中删改会创建新的数组并替换原来的。
适用于读多写少的情况，并且读没有加锁，所以可能读到脏数据。
读的效率高。

三、CopyOnWriteArraySet

并发版的Set, 内部使用CopyOnWriteArrayList实现的。每次add都会遍历内部数据，检查是否重复。不存在执行插入（加锁）
和CopyOnWriteArrayList注意点类似，多了一条数据量不能太大，否则遍历成本过高。

四、ConcurrentLinkedQueue

基于链表实现的并发队列，不阻塞。使用乐观锁CAS保证现存的安全。内部是链表，理论上没有大小限制。

五、ConcurrentLinkedDeque

基于双向链表的并发队列，可以分别对于首尾进行操作。可以先进先出也可以先进后出。

六、ConcurrentSkipListMap

基于跳表SkipList的并发Map, 跳表是用空间换时间的数据结构。
每一层都是上一层的一半数据，类似于二分查找的实现方式来增加搜索效率。

七、ConcurrentSkipListSet

基于跳表的并发Set, 使用ConcurrentSkipListMap实现的

八、ArrayBlockingQueue

基于数组的阻塞队列，构造时需要指定大小。
添加元素时如果数组满了会阻塞，知道有位置可以放。（也可以设置返回或者超时等待）
通过锁ReentrantLock保证线程安全

九、LinkedBlockingQueue

基于链表的阻塞队列，相比不阻塞ConcurrentLinkedQueue多了容量的现在。不设置默认int的最大值

十、LinkedBlockingDeque

和LinkedBlockingQueue类似，底层是双链表

十一、PriorityBlockingQueue

线程安全的优先队列，构造的时候需要传入一个比较器。内部会根据元素的优先级排序。读取的时候会根据优先级从高到低读取。
优先级低的可能会因为一直有更高级的元素而无法被读取。

十二、SynchronousQueue

数据同步交换队列，内部只能存一个元素。每次插入操作必须要取才能再次插入。
任何一个对SynchronousQueue写需要等到一个对SynchronousQueue的读操作，反之亦然

十三、LinkedTransferQueue

基于链表的交换队列，比SynchronousQueue更强大。
实现了TransferQueue接口，通过transfer方法放入元素时如果有线程在阻塞去元素，就会把元素直接给等待队列。如果没有人等待，则放到队列尾部，并阻塞直到有人读取。

十四、DelayQueue

可以使放入的元素在指定延时之后才被消费者取出，元素需要实现Delayed接口

并发工具类

发表于 2022-03-20 分类于编程

文章字数：755,阅读全文大约需要3分钟

一、Fork/Join

1.1分治思想

体现了分而治之的算法思想
将大任务分成若干规模小的子任务
规模为N的问题，N<阈值直接解决。N>阈值分解成若干小规模问题。子问题见互相对立，且与原问题形式相同。子问题的解合并就是原问题的解。
动态规划和分治的不同在于动态规划的子问题间没有联系。

1.2 fork/join

Fork将大问题分成小问题
Join小问题的解合并成大问题的解
工作窃取，线程执行完自己任务队列的任务后会从其他任务队列最后面取任务执行。节约资源

ForkJoinPool pool = new ForkJoinPool();
// 自己定义的任务
MyTask myTask = new ForkJoinTask(src, 0, src.length - 1);
Pool.invoke(myTask);// 主线程阻塞
// pool.execute(myTask);// 异步执行主线程不阻塞
Result = myTask.join();//阻塞等待结果

自定义任务需要继承于RecuriveTask/RecursiveAction/ForkJoinTask，ForkJoinTask是父级类，一般用另外两个

// <>里为返回值
class SumTask extends RecursiveTask<Integer> {
    private final static int THRESHOLD = 10; // 子任务的最大数量
    private int[] src; // 表示要处理的数组
    private fromIndex; //开始的下标
    private toIndex; // 结束的下标

    public SumTask(int[] src, int fromIndex, int toIndex) {
        this.src = src;
        this.fromIndex = fromIndex;
        this.toIndex = toIndex;
    }

    @Override
    protected Integer compute() {
        if(toIndex - fromIndex < THRESHOLD) {
            // 小于子任务最大数量，直接计算返回
            int count = 0;
            for(int i = fromIndex; i <= toIndex; i++) {
                count = count + src[i];
            }
            return count;
        } else {
            int mid = (formIndex + toIndex) / 2;
            // 拆分成两个任务，并执行，返回两个任务执行结果的和
            SumTask left = new SumTask(src, fromIndex, mid);
            SumTask right = new SumTask(src, mid + 1, toIndex);
            invokeAll(left, right);
            return left.join + right.join();
        }
    }
}

二、CountDownlatch

一个线程等待其他线程工作完成之后执行，加强版的join
CountDownlatch(n)初始化n个标记
await()等待标记数量为0
countdown()标记数量-1

三、CyclicBarrier

一组线程达到某个屏障，阻塞。直到一组最后一个到达屏障，开放。
CyclicBarrier(n)总共几个线程
await()等待所有的线程都到达await()位置
等于CountDownlatch每个线程自动countdown()

四、Semaphore

控制同时访问某个特定资源的数量，常用于流量控制
new Semaphore(n)初始化n个令牌，release()可累加超过初始的数
acquire()令牌-1
release()令牌+1

五、Exchange

两个线程之间的数据交换
exchange(Object)两个线程都调用此方法，线程会阻塞在此位置。直到两个线程都到这个位置，会进行一次数据交换。
只能适用于两个线程

六、Callable和Future

Callable可以返回值和抛出异常，线程的业务内容
FutureTask将Callable包装成Runnable

6.1future接口

isDone是否结束
isCanncelled任务完成前被取消，返回true
cancel(true)中断并运行任务，成功返回true。cancel(false)不会中断。已结束返回false
get()阻塞等待结果

并查集

发表于 2022-03-20 分类于编程

文章字数：844,阅读全文大约需要3分钟

介绍

并查集是一种管理元素分组的数据结构，可以管理一系列不相交的集合。
并查集支持两种元素操作

合并Union, 将两个集合并为一个集合
查询Find, 查询两个元素是否在同一个集合中

并查集的原理就是选取一个元素作为整个集合的父节点（代表节点），所以如果两个元素一直向上查找父节点，最后的根节点一样，则这两个元素在同一个集合中。合并的原理也一样，将其中一个元素集合的父节点设置为另一个元素集合的父节点，这样两个元素所在的集合就有共同的父节点。

移除最多同行或同列的石头

leetcode第947题

题目：
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的同行或者同列上有其他石头存在，那么就可以移除这块石头。
给你一个长度为n的数组stones，其中stones[i] = [xi, yi]表示第i块石头的位置，返回可以移除的石子的最大数量。

思路：
只要同行或同列里存在其他石子，则当前的石子就可以被移除
可以把同行或同列有相交的石子连起来，组成一个集合
则棋盘上会有若干集合，每个集合都可以按顺序移除石子，直到只剩一个
所以，有多少个这种集合，最少就能剩下几个石子
用石子总数减去集合数，就是最多移除的石子数
查找集合就可以使用并查集，将相交的石子所在的集合合并，最后查找有几个并查集就可以了

解

public int removeStones(int[][] stones) {
    // 父节点集合，代表每个元素的父节点
    int[] fathers = new int[stones.length];
    // 初始化集合，设置每个元素为一个单独的集合，即父节点是自己
    for (int i = 0; i < fathers.length; i++) {
        // 父节点是自己
        fathers[i] = i;
    }
    // 循环所有石子，如果在一行或者一列，则并集
    for (int i = 0; i < stones.length; i++) {
        for (int j = i + 1; j < stones.length; j++) {
            if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                join(fathers, i, j);
            }
        }
    }
    // 查找一下fathers里每个元素的父级，最后统计一下有几个集合。
    // 总数-集合数就是结果
    return stones.length - (int)Arrays.stream(fathers).map(val -> findFather(fathers, val)).distinct().count();
}

/**
 * 合并操作
 * 
 * @param fathers 父节点集合
 * @param i
 * @param j
 */
private void join(int[] fathers, int i, int j) {
    // 如果i和j所在的集合的父节点不一样，则代表是两个集合，需要合并
    if (findFather(fathers, i) != findFather(fathers, j)) {
        // 其中一个集合的父节点设置父节点为另一个集合的父节点
        fathers[findFather(fathers, j)] = findFather(fathers, i);
    }
}

/**
 * 查找父节点
 * 
 * @param fathers
 * @param x
 * @return
 */
private int findFather(int[] fathers, int x) {
    // 如果父节点不是集合的根节点（集合的父节点）
    while (fathers[x] != x) {
        // 设置当前节点的父节点为父节点的父节点，减少下次查询的次数。也可以在查找到根节点后将路径上所有的节点父节点都设置成集合根节点
        fathers[x] = fathers[fathers[x]];
        // 向上查找
        x = fathers[x];
    }
    return x;
}

验证, 写了一个将leetcode测试用例数组转换成java数组的小工具

public static void main(String[] args) {
    String data = "[[0,1],[1,0],[1,1]]";
    data = delChar(data);
    final String[] dataSplit = data.split(",\\[");
    int[][] stones = new int[dataSplit.length][2];
    for (int i = 0; i < stones.length; i++) {
        int[] one = new int[2];
        String oneData = dataSplit[i].replace("[", "");
        oneData = oneData.replace("]", "");
        one[0] = Integer.parseInt(StringUtils.split(oneData, ",")[0]);
        one[1] = Integer.parseInt(StringUtils.split(oneData, ",")[1]);
        stones[i] = one;
    }
    Solution solution = new Solution();
    System.out.println(solution.removeStones(stones));
}

public static String delChar(String data) {
    return StringUtils.substring(data, 1, data.length() - 1);
}

开启druid管理界面

发表于 2022-03-20 分类于编程

文章字数：28,阅读全文大约需要1分钟

# druid 状态监控
spring.datasource.druid.filter.stat.enabled=true
spring.datasource.druid.filter.stat.db-type=postgresql
# druid 监控过滤器
spring.datasource.druid.web-stat-filter.enabled=true
spring.datasource.druid.web-stat-filter.exclusions="*.js,*.gif,*.jpg,*.png,*.css,*.ico,/druid/*"
# druid 监控页面
spring.datasource.druid.stat-view-servlet.enabled=true
spring.datasource.druid.stat-view-servlet.url-pattern=/druid/*

强引用、软引用、弱引用、虚引用

发表于 2022-03-20 分类于编程

文章字数：540,阅读全文大约需要2分钟

强引用

平常使用的Object a = new Object()就是强引用
JVM内存不足时宁愿抛出OOM也不会随意回收存活的对象

软引用

通过SoftReference实现
只有内存不足时才会试图回收软引用指向的对象
如果软引用指向的对象被回收了，SoftReference对象就会被加入到ReferenceQueue队列中。使用poll()方法可以检查对象是否被回收，此方法返回队列前面的一个SoftReference对象
可以做缓存
弱引用
通过WeakReference实现
GC检查到只有弱引用指向的对象就会清除此对象（即不能维护调用链的存活判断）
同样可以和一个引用队列ReferenceQueue关联
应用：ThreadLocal的key就是弱引用，不会因为key有依赖导致对象不被GC
虚引用
也叫幻想引用
使用PhantomReference实现
无法通过虚引用操作对象
仅能通过关联的ReferenceQueue知道对象是否被回收

微服务业务监控elk和efk

发表于 2022-03-20 分类于编程

文章字数：1443,阅读全文大约需要5分钟

在业务中收集需要的数据，并且进行处理和展示的架构。业务中收集数据的工作被称为埋点，一般使用日志的方式进行。

大致流程

微服务日志埋点：使用日志输出框架，例如Logback
日志收集：收集Logback输出的日志，使用FileBeat

2.1 消息队列传输：这里可以使用消息队列减轻日志解析压力

数据解析，落盘：将Logback传来的数据格式化成可用的格式如json，然后生成ElasticSearch分片格式并发送（落盘）
数据使用：ElasticSearch收到后就可以提供查询服务，供使用者获取信息
数据展示：使用Kibana展示数据

详解

数据生成

数据埋点：数据埋点就是将需要的数据在业务中抽离出来，一般使用日志框架就可以了Logback。也可以自己输出成文件。
格式：输出的格式需要统一，例如

1 2	# {时间}\|{来源}\|{对象id}\|{类型}\|{对象属性(以&分割)} 2019-11-07 10:32:01\|api-gateway\|1\|request-statistics\|ip=171.221.203.106&browser=CHROME&operatingSystem=WINDOWS_10

埋点输出位置：需要和日志文件分开，使用单独的目录。Logback的配置就可以实现

数据收集

日志收集中间件有很多，FileBeat、Flume、Fluentd、rsyslog等
每台服务器需要部署一个收集中间件，即使一个服务器部署了多个微服务也可以只部署一个收集中间件。
收集到的信息可以通过消息队列的方式发送给下一个处理环节，使用消息队列可以增加并发性能，削峰填谷，减轻压力。也可以同时发送给多个系统，使数据有多个用途。

数据解析

使用Logstash的grok表达式可以解析日志数据，并且格式化。

1	2019-11-07 10:32:01\|api-gateway\|1\|request-statistics\|ip=171.221.203.106&browser=CHROME&operatingSystem=WINDOWS_10

格式化后

{
	timestamp: '2019-11-07 10:32:01',
	appName: 'api-gateway',
	resouceid: '1',
	type: 'request-statistics',
	ip: '171.221.203.106',
	browser: 'CHROME',
	operatingSystem: 'WINDOWS_10'
}

Logstash还能完成数据落盘功能，自动创建Elasticsearch索引，并根据天为单位分片
可以通过索引模板来指定每个字段的类型和分词器等属性

数据使用

除了自己写查询并使用外还可以使用kibana可视化Elasticsearch中的日志

ELK

指的是Elasticsearch + Logstash + kibana组成的日志处理系统

EFK

将ELK中的Logstash替换成轻量级的filebeat,牺牲了一定的数据格式化能力，但是性能提升很大

安装EFK

安装Elasticsearch

# 创建并进入文件夹
mkdir -p /opt/software && cd /opt/software
# 拉取软件包
wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.3.2-linux-x86_64.tar.gz
# 解压 z:使用gzip x:解压，c是压测 v:显示正在处理的文件名 f:指定文件（必须在最后面，因为后面需要跟文件名）
tar -zxvf elasticsearch-7.3.2-linux-x86_64.tar.gz
# 移动到指定文件夹
mv elasticsearch-7.3.2 /opt/elasticsearch
# 添加一个用户[elasticsearch]并绑定用户根目录[-d /opt/elasticsearch] 设置用户为不能用来登录的[-s /sbin/nologin], 如果需要登录，可以不加[-s ...]并且设置[-p pwd]设置登录密码
useradd elasticsearch -d /opt/elasticsearch -s /sbin/nologin
# 添加两个文件夹的权限
chown elasticsearch.elasticsearch /opt/elasticsearch -R
chown elasticsearch.elasticsearch /opt/logs/elasticsearch -R
# 设置单个进程可拥有的虚拟内存数量，防止elasticsearch内存不够
echo "vm.max_map_count = 655350" >> /etc/sysctl.conf
# 刷新系统配置
sysctl -p

配置

# 集群名字
#cluster.name: my-application

# 节点名字
#node.name: 192.168.1.31

# 日志位置
path.logs: /opt/logs/elasticsearch

# 本节点访问IP
network.host: 192.168.1.31

# 本节点访问
http.port: 9200

# 节点运输端口
transport.port: 9300

# 集群中其他主机的列表
#discovery.seed_hosts: ["192.168.1.31", "192.168.1.32", "192.168.1.33"]

# 首次启动全新的Elasticsearch集群时，在第一次选举中便对其票数进行计数的master节点的集合
#cluster.initial_master_nodes: ["192.168.1.31", "192.168.1.32", "192.168.1.33"]

# 启用跨域资源共享
http.cors.enabled: true
http.cors.allow-origin: "*"

# 只要有2台数据或主节点已加入集群，就可以恢复
#gateway.recover_after_nodes: 2

安装filebeat

mkdir -p /opt/software && cd /opt/software
wget https://artifacts.elastic.co/downloads/beats/filebeat/filebeat-7.3.2-linux-x86_64.tar.gz
mkdir -p /opt/logs/filebeat/
tar -zxvf filebeat-7.3.2-linux-x86_64.tar.gz
mv filebeat-7.3.2-linux-x86_64 /opt/filebeat
# 不另外创建用户，因为filebeat需要监听elasticsearch的日志文件

配置

# 文件输入
filebeat.inputs:
  # 文件输入类型
  - type: log
    # 开启加载
    enabled: true
    # 文件位置
    paths:
      - /var/log/nginx/access.log
    # 自定义参数
    fields:
      type: nginx_access  # 类型是nginx_access,和上面fields.type是一致的

# 输出至elasticsearch
output.elasticsearch:
  # elasticsearch集群
  hosts: ["http://192.168.1.31:9200",
          "http://192.168.1.32:9200",
          "http://192.168.1.33:9200"]

  # 索引配置
  indices:
    # 索引名
    - index: "nginx_access_%{+yyy.MM}"
      # 当类型是nginx_access时使用此索引
      when.equals:
        fields.type: "nginx_access"

# 关闭自带模板
setup.template.enabled: false

# 开启日志记录
logging.to_files: true
# 日志等级
logging.level: info
# 日志文件
logging.files:
  # 日志位置
  path: /opt/logs/filebeat/
  # 日志名字
  name: filebeat
  # 日志轮转期限，必须要2~1024
  keepfiles: 7
  # 日志轮转权限
  permissions: 0600

安装kibana

mkdir -p /opt/software && cd /opt/software
wget https://artifacts.elastic.co/downloads/kibana/kibana-7.3.2-linux-x86_64.tar.gz
tar -zxvf kibana-7.3.2-linux-x86_64.tar.gz
mv kibana-7.3.2-linux-x86_64 /opt/kibana
useradd kibana -d /opt/kibana -s /sbin/nologin
chown kibana.kibana /opt/kibana -R

配置

# 本节点访问端口
server.port: 5601

# 本节点IP
server.host: "192.168.1.21"

# 本节点名字
server.name: "192.168.1.21"

# elasticsearch集群IP
elasticsearch.hosts: ["http://192.168.1.31:9200",
                      "http://192.168.1.32:9200",
                      "http://192.168.1.33:9200"]

启动所有服务

# elasticsearch启动（3台es均启动）
sudo -u elasticsearch /opt/elasticsearch/bin/elasticsearch

# filebeat启动
/opt/filebeat/filebeat -e -c /opt/filebeat/filebeat.yml -d "publish"

# kibana启动
sudo -u kibana /opt/kibana/bin/kibana -c /opt/kibana/config/kibana.yml

快速排序

发表于 2022-03-20 分类于编程

文章字数：916,阅读全文大约需要3分钟

快速排序的思想就是把第一个数作为基数，比基数小的放到前面，比基数大或等于的放到基数后面。然后再对基数以前和基数以后的部分分别进行前面的操作，直到基数前面和基数后面都只有一个数时（左侧游标和右侧游标相遇）

时间复杂度O(N*logN)

具体方案

调用：

写一个用于整理区域的方法
递归调用，整理所有的部分（整理当前，的到基数位置，递归整理基数之前的区域，递归整理基数之后的区域）

整理方法：

选第一位为基数
右游标从前找比基数小的数，放到左游标处(左右游标的位置上都没有值，因为一旦选中某个元素，就意味着这个元素不符合要求，需要放到另一边)
左游标向后找比基数大的数，放到右游标的位置。
循环2，3操作，知道左右游标相遇，这个位置就是基数应该放在的地方
返回基数的位置，方便上面的递归调用时判断基数前后区域

代码

/**
 * @author colin.cheng
 * @version V1.0
 */
public class midTest {
    public int arrayTheList(int[] arr,int l,int r){
        //选中第一位作为基数
        int x = arr[l];
        //左和右的游标遇到时结束
        while (l<r){
            //右游标移动到小于基数的值上
            while(l<r&&arr[r]>=x){
                r--;
            }
            //放到左边游标的位置上（相当于从右边找不符合要求的数，全部放到左边）
            if(l<r){
                arr[l]=arr[r];
            }

            //左边找不符合要求的数，放到右边
            while(l<r&&arr[l]<=x){
                l++;
            }
            if(l<r){
                arr[r]=arr[l];
            }
        }
        //当左边游标和右边游标相同时这个位置填充基数
        arr[l]=x;
        //返回基数位置
        return l;
    }

    void quick_sort(int[]arr,int l,int r){
        //递归的结束条件
        if(l<r){
            //1.整理当前区域，返回基数位置
            int i = arrayTheList(arr,l,r);
            //2.整理基数左边的区域
            quick_sort(arr,l,i-1);
            //3.整理基数右边的区域
            quick_sort(arr,i+1,r);
        }
    }

        public static void main(String[] args) {
        int[] arr={21,35,2,6,4,8,2,4,98,4,95,1,60,5,7,2,2,0,2,14,0,123,3,654,484,34,5235,68,455,834,568,3458,56,31,69,55,349,582,1,97,35,95,84,8492,2,546,475,354};
        midTest t = new midTest();
        //调用排序
        t.quick_sort(arr,0,arr.length-1);
        System.out.println("--------------");
        //输出结果
        int index=0;
        for(int i:arr){
            System.out.print(i);
            index++;
            if(index!=arr.length){
                System.out.print(",");
            }
        }
    }
}

#输出结果

1	0,0,1,1,2,2,2,2,2,2,3,4,4,4,5,6,7,8,14,21,31,34,35,35,55,56,60,68,69,84,95,95,97,98,123,349,354,455,475,484,546,568,582,654,834,3458,5235,8492

基于栈的快速排序

上面的使用的是递归，递归如果深度过深可能会造成jvm栈空间不足。所以修改了一下调用的方法，改为使用先进后出的数据结构stack,和递归效果一样，但是每次的函数执行完就退出，不会像递归那样不关闭

import java.util.Stack;

/**
 * @author colin.cheng
 * @date
 */
public class demo {

    public static Stack<Node> stack = new Stack();

    public static void main(String[] args) {

        int[] values = {1, 23, 51, 24, 124, 15, 124, 15123, 114, 4, 564, 42, 5, 434, 3434, 344, 444, 2, 5, 90, 7, 7, 8,
            54, 3, 4, 65, 43, 34, 5, 743, 24, 514, 5, 2};
        sortArray(values, 0, values.length - 1);
        for (int v : values) {
            System.out.print(v + ",");
        }
    }

    /**
     * 调用区域排序，并把基准点左右区域的排序任务入栈
     * 
     * @param args
     * @param l
     * @param r
     */
    static void dealArrayAndAddToStack(int[] args, int l, int r) {
        int baseIndex = sort(args, l, r);

        if (l < baseIndex - 1) {
            Node leftNode = new Node(l, baseIndex - 1);
            stack.push(leftNode);
        }

        if (baseIndex + 1 < r) {
            Node rightNode = new Node(baseIndex + 1, r);
            stack.push(rightNode);
        }
    }

    /**
     * 排序调度
     * 
     * @param args
     * @param l
     * @param r
     */
    public static void sortArray(int[] args, int l, int r) {
        dealArrayAndAddToStack(args, l, r);
        // 任务出栈
        while (!stack.empty()) {
            Node currentNode = stack.pop();
            dealArrayAndAddToStack(args, currentNode.left, currentNode.right);
        }
    }

    /**
     * 区域排序
     * 
     * @param args
     * @param l
     * @param r
     * @return
     */
    public static int sort(int[] args, int l, int r) {
        int base = args[l];

        while (l < r) {

            while (l < r && args[r] >= base) {
                r--;
            }

            if (l < r) {
                args[l] = args[r];
            }

            while (l < r && args[l] <= base) {
                l++;
            }

            if (l < r) {
                args[r] = args[l];
            }

        }
        args[l] = base;
        return l;
    }

    static class Node {
        public int left;
        public int right;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
}

简易版

public void sort(int[] nums, int lIndex, int rIndex) {
    if (lIndex < rIndex) {
        int l = lIndex, r = rIndex, x = nums[lIndex];
        while (l < r) {
            while (l < r && nums[r] > x) {
                r--;
            }
            if (l < r) {
                nums[l] = nums[r];
                l++;
            }
            while (l < r && nums[l] < x) {
                l++;
            }
            if (l < r) {
                nums[r] = nums[l];
                r--;
            }
        }
        nums[l] = x;
        sort(nums, lIndex, l - 1);
        sort(nums, l + 1, rIndex);
    }
}

慢查询

发表于 2022-03-20 分类于编程

文章字数：1166,阅读全文大约需要4分钟

定义及作用

配置

位置

windows下配置文件为my.ini
linux下配置文件位置为my.cnf

开启配置

1
2
3

slow_query_log = 1 # 0关闭 1开启
slow_query_log_file = slow.log # 慢文件存放位置(安装目录date文件夹下)
long_query_time = 5 # 查询多久以上的算是慢

排查

1 2	Query_time: xxx # 执行时间 Lock_time: xxx # 锁定时间

分析工具

mysqldumpslow
MySQL自带的慢查询文件解析工具，自带分析。位于bin下。

1
2
3

mysqldumpslow -s at -t 5 /usr/local/data/slow.log
-s at # 算出平均时间
-t 5 # top5

常见优化

系统层面入手(排查sql导致cpu占用过高)
1
top -H # 查出性能占用最大的pid

mysql参数优化

# 独立表空间
Using filesort

# 设置缓存空间(连表之类的操作使用的缓存空间)
set sort_buffer_size = 256*1024*1024

sql优化

子查询变成关联查询

反范式设计优化

针对范式化设计而言
为了性能和读取效率考虑，适当对数据库设计范式进行违反
允许适当冗余，以空间换时间(减少连表)

索引优化

explain查看索引使用情况
根据使用情况重写建立索引(创建时范围索引放最后)

执行计划

1	explain sql

key 是否使用了索引，使用了什么索引
key_len 是否充分使用了索引

varchar(50)的索引计算

字符类型 varchar +2 char+0
字符集 utf8(3) 一个字符的长度
本身长度 50
是否null null(+ 1) not null(+ 0)

1 2	50 * 3 varchar(50) * 一个字符3个字节 + 0(not null) + 2(varchar类型)

可以通过索引长度计算出使用了几个索引

Explain字段详解

mysql> explain select * from servers;
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
| id | select_type | table   | type | possible_keys | key  | key_len | ref  | rows | Extra |
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
|  1 | SIMPLE      | servers | ALL  | NULL          | NULL | NULL    | NULL |    1 | NULL  |
+----+-------------+---------+------+---------------+------+---------+------+------+-------+
row in set (0.03 sec)

1. id

执行顺序的标识，id大的优先执行

2. select_type

SIMPLE简单的查询，不使用UNION或子查询等
PRIMARY查询中包含任何复杂字部分，最外层查询会被标记为PRIMARY
UNION中的后一个语句标记为UNION
DEPENDENT UNION，UNION中的后一个语句，取决于外面的查询
UNION RESULT是UNION语句的结果
SUBQUERY子查询中的第一个SELECT
DEPENDENT SUBQUERY，子查询中的第一个SELECT，取决于外面的查询
DERIVED派生表的SELECT，FROM子句的子查询
UNCACHEABLE SUBQUERY一个子查询的结果不能被缓存，必须重新评估外链接的第一行

3. table

这一行的数据是关于那张表的，可能是tableNamex，x代表执行的步骤

4. type

表示查找到这一行的方式，性能从低到高

ALL遍历全表找到匹配的行
index遍历全部索引树找到匹配的行
range只检索给定范围的行，使用一个索引来选择行
ref表的连接匹配条件，即那些列或常量被用于查找索引上的值
eq_ref类似ref区别在于是使用的所有是唯一索引，即多表中使用primary key或者unique key作为关联条件
const、system，当MySQL对查询某部分进行优化，并转换成一个常量时，使用这些类型访问。例如主键置于where中，MySQL就能把改查询转换成一个常量，system是const的特例，当查询的表只有一行情况下是system。
NULL执行时不用访问表或索引，例如从索引列选取最小值，可以直接通过索引查找完成。

5. possible_keys

指出MySQL能使用那个索引在表中找到记录，查询涉及到的字段若存在索引，则索引会被列出，但不一定会被利用到。

6.key

MySQL决定使用的键

7. key_len

表示索引中使用的字节数，可通过改列计算查询中使用的索引的长度。

8. ref

列与索引的比较，表示上述表的连接匹配条件，即那些列或常量被用于查找索引列的值

9. rows

估算出结果集行数，表示MySQL根据表统计信息及索引选用情况估算找到所需记录所需要读的行数

10. Extra

包含MySQL解决查询的详细信息

Using where，不用读取表中的所有信息，通过索引就能获取所需数据

执行计划

发表于 2022-03-20 分类于编程

文章字数：817,阅读全文大约需要3分钟

key_len

表示索引使用的字节数，可通过计算查询中使用的索引长度。不损失精度准确性情况下，越短越好
显示的是值为索引字段的最大可能长度，而不是实际长度，即根据表定义计算得出的

key_len字符型

类型|大小|用法
CHAR|0-255|定长字符串
WARCHAR|0-65535|变长字符串

CHAR UTF-8一个字符大小为3
CHAR UTF-8如果允许为null长度+1
VARCHAR UTF-8在CHAR的基础上+2表示变长的大小

key_len数值型

类型|大小|有符号范围
TINYINT|1|-128,127
SMALLINT|2|-3276,32767
MEDIUMINT|3|-8388608,8388707
INT/INTEGER|4|-2147483648,2147483647
BIGINT|8|
FLOAT|4|
DOUBLE|8|

key_len日期

datetime在5.6中长度是5个字节
datetime在5.5中长度是8个字节

key_len总结

变长需要额外2个字节记录长度
null需要1个字节的额外空间，索引最好不要null
复合索引最左前缀的特性，key_len可以看复合索引是否全部使用

ref

显示索引的那一列被使用了，如果有可能，是一个常数。那些列或者常量被用于查找索引列上的值。
const表示使用了常量
db.table.id那个数据库的那个表的那个字段使用了索引

rows

根据表信息统计和索引选用，估算找到信息大致所需读取的行

Extra

包含护士和在其他列中显示但十分重要的信息
Using filesort使用文件排序，即没有用到索引，需要使用外部索引，进利用表内索引无法按顺序读取。此时需要在语句中加上索引的where、group by…
Using temporary使用了临时表用于加快查询，在group by最左边加入where in的字段，可以消除临时表。子查询优化成连表…
Using index覆盖索引，查询的所有字段都是索引，就可以直接从索引读取。
Using where使用了where查询

type

效率顺序，最好是ref以上

system
const
eq_ref
ref 使用了条件索引
range
index 扫描了整个索引文件（全表扫描的一种）
ALL

接口幂等

发表于 2022-03-20 分类于编程

文章字数：595,阅读全文大约需要2分钟

幂等指的是任意次数的操作和一次操作的执行影响相同。

不同场景的幂等

查询：查询并不会对于数据造成影响，所以天然幂等
删除：指定删除数据行，此时指定的数据行只有一条，所以无论删除多少次影响都是一样的。也是天然幂等
唯一索引：使用唯一索引，使一个对象的新增操作只能执行一次，并发新增就会报错。（dao层接口幂等）
token机制：用于防止页面重复提交。
用户访问页面时后台随机生成Token并保存，用户表单提交时会带上Token，后台进行校验。每个Token只能使用一次，所以第二次提交就会失效。
Token如果在Redis里，并且是
数据库锁
操作的时候先加锁，防止其他请求并发操作。
查询状态
将操作的唯一值存入数据库，请求到了之后查询一下是否是已经处理的请求。
业务代码实现
操作之前先查询关键数据，查看操作是否已经完成。并发不高的可以这么用