Canal Client 代码入门

发表于 2021-11-17

首先分享之前的所有文章 , 欢迎点赞收藏转发三连下次一定 >>>> 😜😜😜

文章合集 : 🎁 juejin.cn/post/694164…

Github : 👉 github.com/black-ant

CASE 备份 : 👉 gitee.com/antblack/ca…

一 . 前言

这一篇来开始学习 canal 的源码 , 文章目的 :

了解 canal 项目结构
如何启动 canal 源码
canal Client 主流程

canal 主要用于基于MySQL 的增量日志解析 , 它将自己模拟为一个备份库 , 主库会推送 binlog 带 Canal , Canal 解析 binlog , 并且推送到其他的环境

二 . canal 使用流程

Canal 启动包含个部分 :

从 Canal Git 拉取最新的依赖包 ( canal.deployer)
修改 Canal 配置文件 , 并且启动 Canal Server
自行编写 Canal Client , 完成 binlog 的截取

前期准备

1 2	java复制代码create user 'canal'@'%' identified by 'Canal@123456'; grant SELECT, REPLICATION SLAVE, REPLICATION CLIENT on . to 'canal'@'%' identified by 'Canal@123456';

Canal 配置文件 (\conf\example\instance.properties)

java复制代码// 数据库访问地址
canal.instance.master.address=192.168.158.30:3306
// binlog日志名称 , 可以处理指定的日志
canal.instance.master.journal.name=
// 起始偏移量 , 从指定的位置开始同步
canal.instance.master.position=
// 
canal.instance.master.timestamp=
canal.instance.master.gtid=

canal.instance.dbUsername=canal
canal.instance.dbPassword=Canal@19950824
canal.instance.connectionCharset = UTF-8

canal.instance.filter.regex=.*\\..*
canal.instance.filter.black.regex=mysql\\.slave_.*

canal.mq.topic=example
canal.mq.partition=0

Canal 启动环节

Canal 启动只需要调用 \bin\startup.bat 即可 , 其中可能会涉及到如下问题 :

java复制代码//  log 日志
topic 分片日志 : \logs\example
canal 主日志 : 


// >>> 问题

// 1. Received error packet: errno = 1236, sqlstate = HY000 errmsg = Misconfigured master - master server_id is 0
> 修改my.cnf , 添加 server_id=1

// 2. can't found begin/commit position before with fixed position mysql-bin.000018:1360
canal.instance.master.journal.name 和 position 配置问题

Canal Client 拦截

Canal 项目中提供了一个案例项目 : github.com/alibaba/can… , 个人加了一些注释 :

java复制代码<!-- Step 1 :　添加依赖关系 -->
<dependency>
    <groupId>com.alibaba.otter</groupId>
    <artifactId>canal.client</artifactId>
    <version>1.1.0</version>
</dependency>

java复制代码public static void main(String args[]) {

    // 创建链接
    // 此处包含三种创建方式 : newSingleConnector / newClusterConnector / newClusterConnector
    CanalConnector connector = CanalConnectors.newSingleConnector(
        new InetSocketAddress(AddressUtils.getHostIp(),11111), "example", "", "");
    
    int batchSize = 1000;
    int emptyCount = 0;
    try {
    
        // 打开连接
        connector.connect();
        // 配置扫描范围
        connector.subscribe(".*\..*");
        // 回滚到未进行ack的地方，下次fetch的时候，可以从最后一个没有ack的地方开始拿
        connector.rollback();
        
        int totalEmptyCount = 120;
        
        
        while (emptyCount < totalEmptyCount) {
            Message message = connector.getWithoutAck(batchSize); // 获取指定数量的数据
            long batchId = message.getId();
            int size = message.getEntries().size();
            if (batchId == -1 || size == 0) {
                emptyCount++;
                System.out.println("empty count : " + emptyCount);
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                }
            } else {
                emptyCount = 0;
                // 打印SQL语句
                // System.out.printf("message[batchId=%s,size=%s] \n", batchId, size);
                printEntry(message.getEntries());
            }

            connector.ack(batchId); // 提交确认
            // connector.rollback(batchId); // 处理失败, 回滚数据
        }

        System.out.println("empty too many times, exit");
    } finally {
        connector.disconnect();
    }
}

private static void printEntry(List<Entry> entrys) {
    for (CanalEntry.Entry entry : entrys) {
        if (entry.getEntryType() == CanalEntry.EntryType.TRANSACTIONBEGIN || entry.getEntryType() == CanalEntry.EntryType.TRANSACTIONEND) {
            //开启/关闭事务的实体类型，跳过
            continue;
        }
        //RowChange对象，包含了一行数据变化的所有特征
        //比如isDdl 是否是ddl变更操作 sql 具体的ddl sql beforeColumns afterColumns 变更前后的数据字段等等
        RowChange rowChage;
        try {
            rowChage = RowChange.parseFrom(entry.getStoreValue());
        } catch (Exception e) {
            throw new RuntimeException("ERROR ## parser of eromanga-event has an error , data:" + entry.toString(), e);
        }
        //获取操作类型：insert/update/delete 等类型
        CanalEntry.EventType eventType = rowChage.getEventType();

        //打印Header信息
        System.out.println(String.format("================》; binlog[%s:%s] , name[%s,%s] , eventType : %s",
                entry.getHeader().getLogfileName(), entry.getHeader().getLogfileOffset(),
                entry.getHeader().getSchemaName(), entry.getHeader().getTableName(),
                eventType));

        //判断是否是DDL语句
        if (rowChage.getIsDdl()) {
          
            System.out.println("================》;isDdl: true,sql:" + rowChage.getSql());
        }

        //获取RowChange对象里的每一行数据，打印出来
        for (RowData rowData : rowChage.getRowDatasList()) {
            //如果是删除语句
            if (eventType == EventType.DELETE) {
                printColumn(rowData.getBeforeColumnsList());
                //如果是新增语句
            } else if (eventType == CanalEntry.EventType.INSERT) {
                printColumn(rowData.getAfterColumnsList());
                //如果是更新的语句
            } else {
                //变更前的数据
                System.out.println("------->; before");
                printColumn(rowData.getBeforeColumnsList());
                //变更后的数据
                System.out.println("------->; after");
                printColumn(rowData.getAfterColumnsList());
            }
        }
    }

}

private static void printColumn(List<Column> columns) {
    for (Column column : columns) {
        System.out.println(column.getName() + " : " + column.getValue() + "    update=" + column.getUpdated());
    }
}

三 . canal 项目结构

Canal Client 源码很清晰 , 代码量也不大 , 这里仅大概过一下

3.1 CanalConnector 接口

CanalConnector提供了很多核心的工具方法 (可以看看源码 , 里面写的很详细) , 它有 SimpleCanalConnector 和 ClusterCanalConnector 2个主要的实现类 , 分别用于处理基础功能和集群功能

Canal 支持三种创建连接的方式 :

java复制代码// 创建单链接的客户端链接
CanalConnector connector = CanalConnectors.newSingleConnector(new InetSocketAddress("127.0.0.1", 11111), "example", "", "");

// 创建带cluster模式的客户端链接，自动完成failover切换，服务器列表自动扫描
CanalConnector connector1 = CanalConnectors.newClusterConnector("127.0.0.1:2181", "example", "", "");

// 建带cluster模式的客户端链接，自动完成failover切换
CanalConnector connector2 = CanalConnectors.newClusterConnector(Arrays.asList(new InetSocketAddress(AddressUtils.getHostIp(), 11111)), "example", "", "");

ClusterCanalConnector 重试的原理 (failover切换的方式)

java复制代码// Step 1 : 构建集合列表
// failover 通过 SimpleNodeAccessStrategy 策略实现切换
private List<SocketAddress> nodes = new ArrayList<SocketAddress>();
private int                 index = 0;
public SocketAddress nextNode() {
    try {
        return nodes.get(index);
    } finally {
        // 此处会重新构建索引值
        index = (index + 1) % nodes.size();
    }
}

// Step 2 :  ClusterCanalConnector 的创建环节
// 可以看到 , 创建的还是 SimpleCanalConnector , 只不过重写了策略方法
currentConnector = new SimpleCanalConnector(null, username, password, destination) {

    @Override
    public SocketAddress getNextAddress() {
        // 在 ClusterCanalConnector 中如果抛出异常了 , 会将 address 置空
        return accessStrategy.nextNode();
    }

};

// Step 3 : ClusterCanalConnector 访问异常切换
} catch (Exception e) {
    logger.warn("failed to connect to:{} after retry {} times", accessStrategy.currentNode(), times);
    currentConnector.disconnect();
    // 首先会将连接置空 , 下次获取连接时使用下一个节点
    currentConnector = null;
    times = times + 1;
    
    // 外层有2个循环 ,当超过重试次数后会抛出异常 , 不再参与循环
    if (times >= retryTimes) {
        throw new CanalClientException(e);
    } else {
        // fixed issue #55，增加sleep控制，避免重试connect时cpu使用过高
        try {
            Thread.sleep(retryInterval);
        } catch (InterruptedException e1) {
            throw new CanalClientException(e1);
        }
    }
}


// 总结 : 
整个结构非常的精妙 , 2个 while 循环 , 一个用于重新创建连接 , 一个用于反复重试

ClusterCanalConnector 的 zk 方式

java复制代码核心的处理方式就是通过 ZkClientx 发起远程的调用

// 监听 zk 中节点的变化
String clusterPath = ZookeeperPathUtils.getDestinationClusterRoot(destination);
this.zkClient.subscribeChildChanges(clusterPath, childListener);

dataListener = new IZkDataListener() {

    //  watch 判断变化后 , 调用初始化操作
    public void handleDataChange(String dataPath, Object data) throws Exception {
        // runningAddress = new InetSocketAddress(strs[0], Integer.valueOf(strs[1]));
        initRunning(data);
    }

};

四 . canal 主处理流程

4.1 数据的拉取

从上文已经看过了 , 不管是哪种方式 , 其最终都是建立了 InetSocketAddress , 且端口为 11111

我们来看一下各环节的数据情况 :

Message 属性格式

Message message = connector.getWithoutAck(BATCH_SIZE);

其中主要包含 binlog 文件信息 , 偏移量 , 操作类型等数据

4.2 SQL 的读取

java复制代码
// RowChange对象，包含了一行数据变化的所有特征 , 其中主要包含 如下配置 :
- eventType: CREATE
- isDdl: true
- sql: "CREATE TABLE `test`.`table6`  (\r\n  `id` int(0) NOT NULL,\r\n  `username` varchar(255)  NULL,\r\n  `time` datetime(0) NULL,\r\n  `version` int(255) NULL,\r\n  PRIMARY KEY (`id`)\r\n)"
- ddlSchemaName: "test"
RowChange rowChage = RowChange.parseFrom(entry.getStoreValue());


// 读取 EventType
// EventType 是一个枚举 , 里面包含 INSERT , UPDATE , DELETE 等多种状态 , 用于标识 SQL 类型
EventType eventType = rowChage.getEventType()


// 获取字段集合 , 适用于数据操作
// CanalEntry 中包含一个集合用于存放字段值 :private java.util.List<RowData> rowDatas_;
rowData.getBeforeColumnsList()

4.3 不同操作的 SQL 样式

CREATE TABLE

创建语句会直接携带 SQL 过来

INSERT

插入数据时 , 值只要在 AfterColumn 中

UPDATE

Update 时会记录修改前数据和修改后数据 , 所以也可以在这里做数据审计 , 避免反复查询

DELETE

delete 和 insert 正好相反

五. 扩展

5.1 扩展思路

对于 DDL 语句 , 是不需要进行相关同步的 , 主要同步的就是数据变更的相关操作.

在业务中 , 可以同步到 MySQL , Redis ,ES 等多种介质中 ,

同时Canal 最新版本已经默认支持 MQ 的直接推送 , github.com/alibaba/can… , TODO : 后续看 Canal Server

5.2 同步案例

TODO : 后续有时间会完善一个同步案例

总结

这篇文章主要是入门篇 , 是Canal 学习过程中的一些笔记和梳理 , 第二阶段会进入 Canal Server 学习 , 对 Server 中如何拉取 Binlog , 如何模拟数据库进行深入的学习

同时会对其扩展点进行思考

参考文档

www.cnblogs.com/janes/p/931…

blog.csdn.net/yehongzhi19…

www.cnblogs.com/wangzhisdu/…

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

剖析一下Arrays的用法

发表于 2021-11-17

这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战

写在前面

Arrays是Java中的一个类，其中含有一些对数组操作的静态方法，今天我们就来学习一下其中的一些常用的静态方法。

Arrays类中的一些方法

toString方法

将数组转换为字符串的方法，相信也在其他的类中也会见到，效果一样的，都是将属性转换成字符串的功效。

排序方法

sort排序方法，绝对是我们平时最常用的方法，给数组元素排序的需求可是不少，该方法可以给double类型的数组进行排序，同时也支持int类型的数组排序。可以直接通过Arrays.sort()进行调用。

1 2	ini复制代码int [] arr = {1,3,2,5}; Arrays.sort(arr);

上述可以会得到一个排序好的结果，那就是{1,2,3,5}

查询方法

Arrays中的查询方法，平时使用的倒是不多，可以通过以下代码进行调用：

1 2	java复制代码int[] arr = {1,2,3,4,5,11}; Arrays.binarySearch(arr, 11);

通过这个方法可以返回对应的索引下标，如果没有相应的元素，则会返回一个负数。

复制方法

Arrays中的copyOf方法，就是提供的复制功能，通过Arrays.copyOf方法，可以获得一个新的数组对象，进而达到复制的效果。

1 2	java复制代码int[] arr = {1,2,3,4,5,11}; Arrays.copyOf(arr);

比较方法

Arrays中的比较方法，当然也是以equals来命名的了，其功能就是来比较两个数组是否相同的。

ini复制代码int [] arr1={2,3,4};
int [] arr2={1,2,3};
int [] arr3={2,3,4};
boolean a = Arrays.equals(arr1,arr2);
boolean b = Arrays.equals(arr1,arr3);
System.out.println(a+" , "+b);

输出结果为：

false,true

批量设置方法

Arrays中的fill方法，是可以进行批量设置数组元素的方法，如果你需要一个全部元素都是一个值的数组，那么就可以这么使用了。

1 2	ini复制代码int[] nums = new int[5]; Arrays.fill(nums, 1);

如此，打印出来的值就会是[1,1,1,1,1]。

总结

Arrays类中还有一些别的方法，大多都是针对数组、集合进行功能操作的方法，如果你需要操作数组的话，可以来这个类中找一找，一定会有意想不到的效果。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

力扣刷题笔记【位运算】 → 318 最大单词长度乘积

发表于 2021-11-17

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战

题目

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例

1
2
3

arduino复制代码输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

1
2
3

arduino复制代码输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

1
2
3

less复制代码输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

提示

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母

解题思路

位运算

暴力的解法是两层遍历，再分别判断每一个字符串是否与其它字符串有公共字母，这样的时间复杂度太高了，会导致结果超时。

在暴力法中，我们每一次都需要计算每个字符串里面的元素，那么我们可以找一个变量，将该次计算结果进行保存，后续需要用到的时候，直接拿来使用就好来，这样就不要进行重复的计算操作。

同时，由于words数组仅包含小写字母，仅有26位，那么我们可以利用二进制的特性，通过与运算来快速得出两个字符串是否有公共字母。

java复制代码class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        // 定义数组，保存每一个字符串的字母
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i){
            int tmp = 0;
            // 遍历字符串
            for(char w : words[i].toCharArray()){
                // 将对应元素标记为 1
                tmp |= (1 << (w - 'a'));
            }
            // 赋值
            arr[i] = tmp;
        }

        // 最大值
        int max = 0;
        
        // 将字符串与数组中其它字符串进行对比
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                // 如果没有公共字母，则更新最大值
                if((arr[i] & arr[j]) == 0){
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        
        // 返回结果
        return max;
    }
}

复杂度分析

时间复杂度：O(N2)O(N^2)O(N2)
空间复杂度：O(N)O(N)O(N)

最后

文章有写的不好的地方，请大佬们不吝赐教，错误是最能让人成长的，愿我与大佬间的距离逐渐缩短！

如果觉得文章对你有帮助，请 点赞、收藏、关注、评论 一键四连支持，你的支持就是我创作最大的动力！！！

题目出处: leetcode-cn.com/problems/ma…

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

SQL 子查询怎么优化？写的很深的这种！子查询简介原始执

发表于 2021-11-17

这是我参与11月更文挑战的第13天，活动详情查看：2021最后一次更文挑战

子查询 （Subquery）的优化一直以来都是 SQL 查询优化中的难点之一。关联子查询的基本执行方式类似于 Nested-Loop，但是这种执行方式的效率常常低到难以忍受。当数据量稍大时，必须在优化器中对其进行去关联化 （Decoorelation 或 Unnesting），将其改写为类似于 Semi-Join 这样的更高效的算子。

前人已经总结出一套完整的方法论，理论上能对任意一个查询进行去关联化。本文结合 SQL Server 以及 HyPer 的几篇经典论文，由浅入深地讲解一下这套去关联化的理论体系。它们二者所用的方法大同小异，基本思想是想通的。

子查询简介

子查询是定义在 SQL 标准中一种语法，它可以出现在 SQL 的几乎任何地方，包括 SELECT, FROM, WHERE 等子句中。

总的来说，子查询可以分为关联子查询（Correlated Subquery） 和非关联子查询（Non-correlated Subquery） 。后者非关联子查询是个很简单的问题，最简单地，只要先执行它、得到结果集并物化，再执行外层查询即可。下面是一个例子：

sql复制代码SELECT c_count, count(*) AS custdist
FROM (
         SELECT c_custkey, count(o_orderkey) AS c_count
         FROM CUSTOMER
                  LEFT OUTER JOIN ORDERS ON c_custkey = o_custkey
             AND o_comment NOT LIKE '%pending%deposits%'
         GROUP BY c_custkey
     ) c_orders
GROUP BY c_count
ORDER BY custdist DESC, c_count DESC;

非关联子查询不在本文讨论范围之列 ，除非特别声明，以下我们说的子查询都是指关联子查询。

关联子查询的特别之处在于，其本身是不完整的：它的闭包中包含一些外层查询提供的参数。显然，只有知道这些参数才能运行该查询，所以我们不能像对待非关联子查询那样。

根据产生的数据来分类，子查询可以分成以下几种：

标量（Scalar-valued） 子查询：输出一个只有一行一列的结果表，这个标量值就是它的结果。如果结果为空（0 行），则输出一个 NULL。但是注意，超过 1 行结果是不被允许的，会产生一个运行时异常。

标量子查询可以出现在任意包含标量的地方，例如 SELECT、WHERE 等子句里。下面是一个例子：

sql复制代码SELECT c_custkey
FROM CUSTOMER
WHERE 1000000 < (
    SELECT SUM(o_totalprice)
    FROM ORDERS
    WHERE o_custkey = c_custkey
)

Query 1: 一个出现在 WHERE 子句中的标量子查询，关联参数用红色字体标明了

vbnet复制代码SELECT o_orderkey, (
    SELECT c_name
    FROM CUSTOMER
    WHERE c_custkey = o_custkey
) AS c_name FROM ORDERS

Query 2: 一个出现在 SELECT 子句中的标量子查询

存在性检测（Existential Test） 子查询：特指 EXISTS 的子查询，返回一个布尔值。如果出现在 WHERE 中，这就是我们熟悉的 Semi-Join。当然，它可能出现在任何可以放布尔值的地方。

sql复制代码SELECT c_custkey
FROM CUSTOMER
WHERE c_nationkey = 86 AND EXISTS(
        SELECT * FROM ORDERS
        WHERE o_custkey = c_custkey
    )

Query 3: 一个 Semi-Join 的例子

集合比较（Quantified Comparision） 子查询：特指 IN、SOME、ANY 的查询，返回一个布尔值，常用的形式有：x = SOME(Q) （等价于 x IN Q）或 X <> ALL(Q)（等价于 x NOT IN Q）。同上，它可能出现在任何可以放布尔值的地方。

1
2
3

sql复制代码SELECT c_name
FROM CUSTOMER
WHERE c_nationkey <> ALL (SELECT s_nationkey FROM SUPPLIER)

Query 4: 一个集合比较的非关联子查询

原始执行计划

我们以 Query 1 为例，直观地感受一下，为什么说关联子查询的去关联化是十分必要的。

下面是 Query 1 的未经去关联化的原始查询计划（Relation Tree）。与其他查询计划不一样的是，我们特地画出了表达式树（Expression Tree），可以清晰地看到：子查询是实际上是挂在 Filter 的条件表达式下面的。

)

实际执行时，查询计划执行器（Executor）在执行到 Filter 时，调用表达式执行器（Evaluator）；由于这个条件表达式中包含一个标量子查询，所以 Evaluator 又会调用 Executor 计算标量子查询的结果。

这种 Executor - Evaluator - Executor 的交替调用十分低效 ！考虑到 Filter 上可能会有上百万行数据经过，如果为每行数据都执行一次子查询，那查询执行的总时长显然是不可接受的。

Apply 算子

上文说到的 Relation - Expression - Relation 这种交替引用不仅执行性能堪忧，而且，对于优化器也是个麻烦的存在——我们的优化规则都是在匹配并且对 Relation 进行变换，而这里的子查询却藏在 Expression 里，令人无从下手。

为此，在开始去关联化之前，我们引入 Apply 算子：

Apply 算子 （也称作 Correlated Join）接收两个关系树的输入，与一般 Join 不同的是，Apply 的 Inner 输入（图中是右子树）是一个带有参数的关系树。

Apply 的含义用下图右半部分的集合表达式定义：对于 Outer Relation RR 中的每一条数据 rr，计算 Inner Relation E(r)E(r)，输出它们连接（Join）起来的结果 r⊗E(r)r⊗E(r)。Apply 的结果是所有这些结果的并集（本文中说的并集指的是 Bag 语义下的并集，也就是 UNION ALL）。

)

Apply 是 SQL Server 的命名，它在 HyPer 的文章中叫做 Correlated Join。它们是完全等价的。考虑到 SQL Server 的文章发表更早、影响更广，本文中都沿用它的命名。

根据连接方式（⊗⊗）的不同，Apply 又有 4 种形式：

Cross Apply A×A×：这是最基本的形式，行为刚刚我们已经描述过了；
Left Outer Apply ALOJALOJ：即使 E(r)E(r) 为空，也生成一个 r∘{NULLs}r∘{NULLs}。
Semi Apply A∃A∃：如果 E(r)E(r) 不为空则返回 rr，否则丢弃；
Anti-Semi Apply A∄A∄：如果 E(r)E(r) 为空则返回 rr，否则丢弃；

我们用刚刚定义的 Apply 算子来改写之前的例子：把子查询从 Expression 内部提取出来。结果如下：

)

上面的例子中，我们可以肯定 Scalar Agg 子查询有且只有 一行结果，所以可以直接转成 Apply。但某些情况下，可能无法肯定子查询一定能返回 0 或 1 行结果（例如，想象一下 Query 2 如果 c_custkey 不是唯一的），为了确保 SQL 语义，还要在 Apply 右边加一个 Max1RowMax1Row 算子：

Max1Row(E)=⎧⎩⎨⎪⎪Null,E,error,if |E|=0if |E|=1otherwiseMax1Row(E)={Null,if |E|=0E,if |E|=1error,otherwise

理论上，我们可以将所有的子查询转换成 Apply 算子 ，一个通用的方法如下：

如果某个算子的表达式中出现了子查询，我们就把这个子查询提取到该算子下面（留下一个子查询的结果变量），构成一个 ALOJALOJ 算子。如果不止一个子查询，则会产生多个 ALOJALOJ。必要的时候加上 Max1RowMax1Row 算子。
然后应用其他一些规则，将 ALOJALOJ 转换成 A×A×、A∃A∃、A∄A∄。例如上面例子中的子查询结果 XX 被用作 Filter 的过滤条件，NULL 值会被过滤掉，因此可以安全地转换成 A×A×。

下面这个例子中，Filter 条件表达式中包含 Q1Q1、Q2Q2 两个子查询。转换之后分别生成了对应的 Apply 算子。其中 Q2Q2 无法确定只会生成恰好一条记录，所以还加上了 Max1RowMax1Row 算子。

)

基本消除规则

第一组规则是最基本的规则，等式中的 ⊗⊗ 说明它不限制连接类型，可以是 {×,LOJ,∃,∄}{×,LOJ,∃,∄} 中的任意一个。

)

这两条规则是非常显而易见的，翻译成大白话就是：如果 Apply 的右边不包含来自左边的参数，那它就和直接 Join 是等价的。

下面是对 Query 3 应用规则 (2) 的例子：

)

Project 和 Filter 的去关联化

第二组规则描述了如何处理子查询中的 Project 和 Filter，其思想可以用一句话来描述：尽可能把 Apply 往下推、把 Apply 下面的算子向上提 。

)“))

注意这些规则仅处理 Cross Apply 这一种情况。其他 3 种 Apply 的变体，理论上都可以转换成 Cross Apply，暂时我们只要知道这个事实就可以了。

你可能会问：通常我们都是尽可能把 Filter、Project 往下推，为什么这里会反其道而行呢？关键在于：Filter、Project 里面原本包含了带有关联变量的表达式，但是把它提到 Apply 上方之后，关联变量就变成普通变量了！ 这正是我们想要的。

我们稍后就会看到这样做的巨大收益：当 Apply 被推最下面时，就可以应用第一组规则，直接把 Apply 变成 Join ，也就完成了子查询去关联化的优化过程。

下面是对 Query 2 应用规则 (3) 的例子。之后再应用规则 (1)，就完成了去关联化过程。

)

Aggregate 的去关联化

第三组规则描述如何处理子查询中的 Aggregate（即 Group By）。和上一组一样，我们的指导思想仍然是：尽可能把 Apply 往下推、把 Apply 下面的算子向上提 。

下面等式中，GA,FGA,F 表示带有 Group By 分组的聚合（Group Agg），其中 AA 表示分组的列，FF 表示聚合函数的列；G1FGF1 表示不带有分组的聚合（Scalar Agg）。

)

这一组规则不像之前那么简单直白，我们先看一个例子找找感觉。下面是对 Query 1 运用规则 (9) 的结果：

)

规则 (9) 在下推 Apply 的同时，还将 ScalarAgg 变成了 GroupAgg，其中，分组列就是 R 的 key，在这里也就是 CUSTOMER 的主键 c_custkey。

如果 R 没有主键或唯一键，理论上，我们可以在 Scan 时生成一个。

为什么变换前后是等价的呢？变换前，我们是给每个 R 的行做了一次 ScalarAgg 聚合计算，然后再把聚合的结果合并起来；变换后，我们先是将所有要聚合的数据准备好（这被称为 augment），然后使用 GroupAgg 一次性地做完所有聚合。

这也解释了为什么我们要用 ALOJALOJ 而不是原本的 A×A× ：原来的 ScalarAgg 上，即使输入是空集，也会输出一个 NULL。如果我们这里用 ALOJALOJ，恰好也会得到一样的行为（＊）；反之，如果用 A×A× 就有问题了——没有对应 ORDERS 的客户在结果中消失了！

规则 (8) 处理的是 GroupAgg，道理也是一样的，只不过原来的分组列也要留着。

ScalarAgg 转换中的细节＊

细心的读者可能注意到，规则 (9) 右边产生的聚合函数是 F′F′，多了一个单引号，这暗示它和原来的聚合函数 FF 可能是有些不同的。那什么情况下会不同呢？这个话题比较深入了，不感兴趣的同学可以跳过。

首先我们思考下，GroupAgg 以及 ALOJALOJ 的行为真的和变换前一模一样吗？其实不然。举个反例：

sql复制代码SELECT c_custkey, (
    SELECT COUNT(*)
    FROM ORDERS
    WHERE o_custkey = c_custkey
) AS count_orders
FROM CUSTOMER

设想一下：客户 Eric 没有任何订单，那么这个查询应当返回一个 ['Eric', 0] 的行。但是，当我们应用了规则 (9) 做变换之后，却得到了一个 ['Eric', 1] 的值，结果出错了！

为何会这样呢？变换之后，我们是先用 LeftOuterJoin 准备好中间数据（augment），然后用 GroupAgg 做聚合。LeftOuterJoin 为客户 Eric 生成了一个 ['Eric', NULL, NULL, ...] 的行；之后的 GroupAgg 中，聚合函数 COUNT(*) 认为 Eric 这个分组有 1 行数据，所以输出了 ['Eric', 1]。

下面是个更复杂的例子，也有类似的问题：

sql复制代码SELECT c_custkey
FROM CUSTOMER
WHERE 200000 < (
    SELECT MAX(IF_NULL(o_totalprice, 42)) -- o_totalprice may be NULL
    FROM ORDERS
    WHERE o_custkey = c_custkey
)

作为总结，问题的根源在于：F(∅)≠F({NULL})F(∅)≠F({NULL})，这样的聚合函数 FF 都有这个问题。

变换后的 GroupAgg 无法区分它看到的 NULL 数据到底是 OuterJoin 产生的，还是原本就存在的 ，有时候，这两种情形在变换前的 ScalarAgg 中会产生不同的结果。

幸运的是，SQL 标准中定义的聚合函数 F(col)F(col) 都是 OK 的——它们都满足 F(∅)=F({NULL})F(∅)=F({NULL})，我们只要对 FF 稍加变换就能解决这个问题。

对于例子一，将 COUNT(*) 替换成一个对非空列（例如主键）的 Count 即可，例如：COUNT(o_orderkey)；
对于例子二，需要把 MIN(IF_NULL(o_totalprice, 42)) 分成两步来做：定义中间变量X，先用 Project 计算 X = IF_NULL(o_totalprice, 42)，再对聚合函数 MIN(X) 进行去关联化即可。

集合运算的去关联化

最后一组优化规则用来处理带有 Union（对应 UNION ALL）、Subtract（对应 EXCEPT ALL）和 Inner Join 算子的子查询。再强调一遍，我们的指导思想是：尽可能把 Apply 往下推、把 Apply 下面的算子向上提 。

下面的等式中，×× 表示 Cross Join，⋈R.key⋈R.key 表示按照 RR 的 Key 做自然连接：r∘e1∘e2r∘e1∘e2 。和之前一样，我们假设 RR 存在主键或唯一键，如果没有也可以在 Scan 的时候加上一个。

)“))

注意到，这些规则与之前我们见过的规则有个显著的不同：等式右边 RR 出现了两次。这样一来，要么我们把这颗子树拷贝一份，要么做成一个 DAG 的执行计划，总之会麻烦许多。

事实上，这一组规则很少能派上用场。在 [2] 中提到，在 TPC-H 的 Schema 下甚至很难写出一个带有 Union All 的、有意义的子查询。

其他

有几个我认为比较重要的点，用 FAQ 的形式列在下面。

► 是否任意的关联子查询都可以被去关联化？

可以说是这样的，在加上少量限定之后，理论上可以证明：任意的关联子查询都可以被去关联化。

证明方法在 [1]、[3] 中都有提及。以 [1] 中为例，思路大致是：

对于任意的查询关系树，首先将关联子查询从表达式中提取出来，用 Apply 算子表示；
一步步去掉其中非基本关系算子，首先，通过等价变换去掉 Union 和 Subtract；
进一步缩小算子集合，去掉 OuterJoin、ALOJALOJ、A∃A∃、A∄A∄；
最后，去掉所有的 A×A×，剩下的关系树仅包含基本的一些关系算子，即完成了去关联化。

另一方面，现实世界中用户使用的子查询大多是比较简单的，本文中描述的这些规则可能已经覆盖到 99% 的场景。虽然理论上任意子查询都可以处理，但是实际上，没有任何一个已知的 DBMS 实现了所有这些变换规则。

► HyPer 和 SQL Server 的做法有什么异同？

HyPer 的理论覆盖了更多的去关联化场景。例如各种 Join 等算子，[3] 中都给出了相应的等价变换规则（作为例子，下图是对 Outer Join 的变换）。而在 [1] 中仅仅是证明了这些情况都可以被规约到可处理的情形（实际上嘛，可想而知，一定是没有处理的）。

)

另一个细节是，HyPer 中还存在这样一条规则：

)

其中，D=ΠF(T2)∩A(T1)(T1)D=ΠF(T2)∩A(T1)(T1)，表示对 T1T1 的 Distinct Project 结果（所谓的 Magic Set）。直接看等式比较晦涩，看下面的例子就容易理解了：

)

图中，在做 Apply 之前，先拿到需要 Apply 的列的 Distinct 值集合，拿这些值做 Apply，之后再用普通的 Join 把 Apply 的结果连接上去。

这样做的好处是：如果被 Apply 的数据存在大量重复，则 Distinct Project 之后需要 Apply 的行数大大减少。这样一来，即使之后 Apply 没有被优化掉，迭代执行的代价也会减小不少。

► 本文说的这些变换规则，应该用在 RBO 还是 CBO 中呢？换句话说，去关联化后之后的执行计划一定比去关联化之前更好吗？

答案是，不一定。

直观的看，如果 Apply 的左边数据量比较少（例如，仅有 1 条数据），那直接带入 Apply 的右边计算反而是更好的方式。另一种情况是，右边有合适的索引，这种情况下，多次 Apply 的代价也并非不可接受。

所以把这些规则放进一个 CBO 的优化器是更合适的，优化器根据代价估计选出最优的计划来。甚至，在某些情况下，我们还会自右向左地运用这些等式，做“加关联化”。

这和用 HashJoin 还是 NestedLoopJoin 是同样的道理。事实上，NestedLoopJoin 就是 Apply 的一个特例。如果存在合适的索引，NestedLoopJoin 效率高于 HashJoin 是很常见的事情。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

你可能不怎么知道的 Kafka 拦截器

发表于 2021-11-17

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战

在后端开发中经常会涉及到类似「拦截器」或者「过滤器」的组件，以 Spring Interceptor 为例，它的工作原理就是在每一次请求之前及之后处理一部分逻辑，这样可以让应用程序在不影响业务逻辑的前提下，实现一个可插拔的事件处理链。

Kafka 拦截器介绍

在 Kafka 中，也有相似的特性，也就是 Kafka 的拦截器。

Kafka 中的拦截器有两种，分别是生产者拦截器和消费者拦截器。生产者拦截器可以在消息发送之前以及消息成功提交之后插入逻辑；而消费者拦截器可以在消息消费之前以及提交位移后插入逻辑。

使用方法

在 Kafka 的生产者端和消费者端，都有一个配置项 interceptor.classes 用来配置拦截器，从配置名称可以看出，拦截器是通过一个类来实现的，并且可以配置多个拦截器。注意，这里要配置拦截器类的全限定名。

之前写到生产者分区策略的时候写过，可以通过实现一个 Kafka 提供的接口及其方法来自定义分区策略，拦截器的实现也一样，通过实现 org.apache.kafka.clients.producer.ProducerInterceptor 或者 org.apache.kafka.clients.consumer.ConsumerInterceptor 接口及其方法，创建拦截器类，并配置到 interceptor.classes 即可。

在 ProducerInterceptor 接口中有两个方法：

onSend 会在消息发送之前调用，再次可以加入修改消息内容的逻辑。
onAcknowledgement 会在消息提交成功或者发送失败的时候调用，如果发送消息使用了带有 callback 参数的方法，那么此调用在 callback 之前。

需要注意的是，以上的两个方法并不一定是在同一线程中调用，且要注意如果这里的逻辑过复杂，会影响到生产者端的消息处理效率。

在 ConsumerInterceptor 接口中同样有两个方法：

onConsume 在消费者端正式处理消息之前被调用。
onCommit 在提交位移之后调用。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Bash中的变量类型，还有这两种！

发表于 2021-11-17

「这是我参与11月更文挑战的第5天，活动详情查看：2021最后一次更文挑战」

你必须非常努力，才能看起来毫不费力！

微信搜索公众号[ 漫漫Coding路 ]，一起From Zero To Hero !

前言

上一篇文章Bash 中的变量类型，你知道几种？，我们一起学习了 Bash 中自定义变量和环境变量的使用，本篇文章来学习后面两种：位置参数变量和预定义变量。

变量分类

我们先来复习下 Bash 中的四种变量类型：

自定义变量：类似Java、Go语言中的自定义变量，灵活性最高；
环境变量：主要保存和系统环境相关的变量，系统已经定义好了很多环境变量，同时允许用户新增自定义环境变量，灵活性较高；
位置参数变量：这种变量主要是用来向脚本中传递参数或者数据用的，参数名不能自定义，变量的作用也是固定的，只能更改值；
预定义变量：Bash中已经定义好的变量，变量名不能自定义，变量作用也是固定的。

位置参数变量

这种变量主要是用于执行脚本时，向脚本传递参数：

位置参数变量	作用
$n	n为数字，$0代表命令本身，$1到$9代表第1到9个参数，10以上的参数需要用大括号包含，例如${10}
$*	这个变量代表命令中的所有参数，$* 把所有的参数看作一个整体，即一个字符串
$@	这个变量代表命令中的所有参数，每个参数都看作独立的，可以想象为一个list
$#	代表命令行参数个数

我们来写个脚本实际体验下，就容易理解了：

shell复制代码[root@VM-0-5-centos ~]# vim test.sh

#!/bin/bash
echo "param count:  $#"

# 将输入的两个参数相加后输出
num1=$1
num2=$2
sum=$((num1+num2))
echo "num1: $num1"
echo "num2: $num2"
echo "sum: $sum"

# 体验 $* 和 $@ 的区别
echo 'all params of $*' $*
echo 'all params of $@' $@
for i in "$*"
        do
                echo '$* param:' "$i"
        done

for i in "$@"
        do
                echo '$@ param:' "$i"
        done



[root@VM-0-5-centos ~]# chmod 755 test.sh
[root@VM-0-5-centos ~]# ./test.sh 1 2
param count:  2
num1: 1
num2: 2
sum: 3
all params of $* 1 2
all params of $@ 1 2
$* param: 1 2
$@ param: 1
$@ param: 2

在实际使用中，我们很少使用位置参数变量进行逻辑处理，因为用户使用脚本时并不知道脚本需要几个参数，只有编写者才知道。最佳实践，更多的是引导用户输入参数，然后进行处理。

接收键盘输入

shell复制代码# read [选项] [变量名]

选项：

-p "提示信息"：在等待输入时，输出提示信息
-t 秒数：指定等待时间
-n 字符数：read只接收固定长度的字符数，到达长度就执行
-s：隐藏输入的数据，适用于密码输入

测试接收键盘输入：

shell复制代码[root@VM-0-5-centos ~]# vim read.sh

#!/bin/bash

read -t 30 -p "please input your username: " username
echo "username is $username"

read -s -t 30 -p "please input your password: " password
echo "password is $password"
echo -e "\n"

read -n 1 -t 30 -p "Please select your gender [M/F]: " gender
echo "Gender is: $gender"


[root@VM-0-5-centos ~]# chmod 755 read.sh
[root@VM-0-5-centos ~]# ./read.sh
please input your username: lifelmy
username is lifelmy
please input your password: password is 123456


Please select your gender [M/F]: MGender is: M

预定义变量

预定义变量	作用
$?	最后一次命令执行命令的返回状态。变量值为0，表示上个变量正确执行；非0表示上个命令执行失败（具体什么非0值由命令自己决定）
$$	当前的进程号
$!	后台运行的最后一个进程的进程号

还记得我们之前学习过的多命令执行吗，那里的 && 和 || 命令，就是使用 $? 来判断上一条命令是否正确执行的。

shell复制代码[root@VM-0-5-centos ~]# echo "hello"
hello
# 上一条命令正确执行，输出0
[root@VM-0-5-centos ~]# echo $?   
0
[root@VM-0-5-centos ~]# sfadf
-bash: sfadf: 未找到命令
# 上一条命令错误执行，输出非0值
[root@VM-0-5-centos ~]# echo $?
127

测试 $$ 和 $! :

shell复制代码[root@VM-0-5-centos ~]# vim process.sh

#!/bin/bash

echo "current process id is $$"

# 最后加一个&，表示 把查找命令放到后台执行
find /root -name "hello.sh" &

echo "last process id is $!"

# 测试 $$ 和 $!
[root@VM-0-5-centos ~]# ./process.sh
current process id is 24230
last process id is 24231

[root@VM-0-5-centos ~]# /root/hello.sh

总结

本篇文章首先回顾了 Bash 中的变量分类：自定义变量、环境变量、位置参数变量和预定义变量，并详细介绍了后两种：

位置参数变量的使用，以及引导用户键盘输入；
预定义变量的使用。

个人博客: lifelmy.github.io/

微信公众号：漫漫Coding路

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

golang 微服务中的断路器 hystrix

发表于 2021-11-17

「这是我参与11月更文挑战的第 16 天，活动详情查看：2021最后一次更文挑战」

之前说到过微服务容错处理，可以使用断路器

使用断路器的原因是：

当下游的服务因为过载或故障，无法提供服务，我们需要及时的让上游服务知悉，且暂时熔断调用方和提供方的调用链，这是为了避免服务雪崩现象的发生

go 里面可以使用什么方式来做断路器呢？

hystrix-go

go 中有一个项目实现了这个断路器的功能：

https://github.com/afex/hystrix-go

Hystrix 能够在服务提供者出现故障时，隔离调用者和提供者，防止服务级联失败

并且 Hystrix 还提供失败回滚的逻辑，是系统快速从异常中恢复

为啥要用 Hystrix 来作为断路器？

Hystrix 自身完美的是实现了断路器模式
自身可以提供信号量和线程隔离的方式以保护服务调用者的线程资源
对延迟和失败提供了强大的容错能力，为系统提供保护和控制

图解 Hystrix 运行流程

如下是 golang 微服务容错处理是如何做的？提到的断路器的三种状态：

结合起来看看 Hystrix 具体流程

上述流程我们可以这样来理解

使用 hystrix 的时候，hystrix 会给每一个远程调用逻辑封装成一个指令，这个指令包含这个远程调用的逻辑和失败回滚逻辑，这个命令是 hystrix 唯一识别的
hystrix 根据对应的指令获取到对应的断路器，判断断路器是否打开
- 若打开
  - 执行执行失败回滚逻辑，不直接执行远程调用逻辑，因此此时服务已经熔断了
- 若关闭或者是半开状态
  - 将执行池请求通行证
hystrix 中我们可以配置多个参数，最大并发数量，超时时间，最小请求阈值，超时窗口时间和错误比例阈值等等

图中我们可以看到 Metrics 控制器，

当我们的服务执行异常或者下游服务超时的时候， hystrix 命令就会向 Metrics 控制器上报执行结果，并且 hystrix 命令对应的逻辑会进入到失败回滚逻辑

Metrics 控制器的作用

Metrics 控制器使用滑动窗口的方式统计一段时间内的调用次数，失败次数，超时次数和被拒绝的次数，下一篇的案例代码中，有体现如何配置

这个被拒绝的次怎么理解呢？指的是在向执行池子请求通行证的时候，池子已满，故被拒绝

如果这段时间内，执行错误的频率出超过了断路器错误率的阈值，那么断路器就会打开

在重试超时定时器到达之前的请求都会直接进入失败回滚逻辑，拒绝执行真正的远程调用

因此这就可以达到微服务容错的目的

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是小魔童哪吒，欢迎点赞关注收藏，下次见~

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

分代垃圾回收机制——新生代收集前言

发表于 2021-11-17

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

前言

垃圾回收算法主要有三种:

1、标记清除算法

2、标记整理算法

3、标记复制算法

一般不会采用其中一种进行垃圾回收，而是采用分代回收机制，下面就来了解分代回收机制。

概念

现在大多商业jvm的垃圾收集器都遵循了分代收集的理论进行设计。

它把堆内存中的区域划分成两大块，一个叫新生代（Young Generation），一个叫老年代（Young Generation）两个区域，在新生代中每次垃圾收集时都发现有大量对象死去，然后每次回收后存活的少量对象逐步晋升到老年代中存放。

用完就能丢弃的对象就放在新生代中，长时间使用的对象就放在老年代中。这样就可以根据生命周期的不同特点使用不同的垃圾回收策略，老年代的垃圾回收很久才一次，新生代就会经常进行垃圾回收。

每个区域又分为三个部分：Eden（伊甸园）、幸存区 From、幸存区 To。

minor GC 工作原理

第一次垃圾回收

当我们创建一个对象的时候它最开始会创建在 Eden 中。

之后会有越来越多的对象被创建在Eden 里，直至Eden内存被占用满这个时候就会出现一次垃圾回收，新生代的垃圾回收叫做 minor GC

minor GC流程就是先标记垃圾然后把垃圾清除，然后把存活的对象复制到幸存区To中并且会把幸存的对象寿命加1，并且会交换幸存区 From 和幸存区To,这就是第一次垃圾回收。

第二次垃圾回收

第一次垃圾回收完之后Eden区域又有剩余的内存可以使用了，这个时候我们又创建了很多新对象，并再一次把该区域占满。

触发垃圾回收，前部分都是一样，先标记清除，再复制到幸存区 To中，由于进行过交换这个时候的幸存区To就不是第一次垃圾回收的幸存区To了，而是第一次垃圾回收前的幸存区From。

再标记幸存区To中对象是否为垃圾，是垃圾就清除掉，不为垃圾就放入幸存区From中，并把对象寿命加1，再次交换幸存区 From 和幸存区To。

幸存区结论：谁空谁就是幸存区To

第n次垃圾回收

假设一个对象的寿命超过了一个域值了，就证明这个对象是比较有价值的，那么就会晋升到老年代中，新生代继续进行minor GC策略。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

多线程之线程的等待和唤醒！详细解析线程中的wait()和no

发表于 2021-11-17

这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战

线程的等待与唤醒方法

在Object.java中,定义了wait(), notify() 和notifyAll() 等接口:
- wait()的作用:
  - 让当前线程进入等待状态
  - wait() 也会让当前线程释放所持有的锁
- notify()和notifyAll()的作用:
  - 唤醒当前对象上等待的所有线程
  - notify() 是唤醒单个线程
  - notifyAll() 是唤醒所有线程
notify(): 唤醒此对象监视器上等待的单个线程
notifyAll(): 唤醒此对象监视器上等待的所有线程
wait(): 让当前线程处于等待或者堵塞状态,直到其余线程调用此对象的notify() 方法或者notifyAll() 方法,当前线程被唤醒进入就绪状态
wait(long timeout): 让当前线程处于等待或者阻塞状态,直到其余线程调用此对象的notify() 方法或者notifyAll() 方法,或者等待时间超过指定的时间,当前线程被唤醒进入就绪状态
wait(long timeout, int nanos): 让当前线程处于等待或者阻塞状态,直到其余线程调用此对象的notify() 方法或者notifyAll() 方法,或者其余某个线程中断当前线程,或者等待时间超过指定的时间,当前线程被唤醒进入就绪状态

wait()与notify()

java复制代码class MyThread extends Thread {
	public MyThread(String name) {
		super(name);
	}

	public viod run() {
		synchronized(this) {
			System.out.println(Thread.currentThread().getName() + "调用notify()方法");
			// 唤醒当前的wait线程
			notify();
		}
	}
}

public class WaitTest {
	public static void main(String[] args) {
		Thread thread1 = new Thread("thread1");

		synchronized(thread1) {
			try {
				System.out.println(Thread.currentThread().getName() + "启动线程thread1");
				thread1.start();

				System.out.println(Thread.currentThread().getName() + "调用wait()方法");
				thread1.wait();

				System.out.println(Thread.currentThread().getName() + "继续执行");
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
	}
}

console复制代码main启动线程thread1
main调用wait()方法
main调用notify()方法
main继续执行

在这里插入图片描述

主线程代表主线程main. 线程t1代表WaitTest中启动的线程Thread1. 锁代表thread1对象的同步锁
主线程main通过new Thread(“thread1”) 新建线程thread1. 然后通过synchronized(thread1) 获取对象的同步锁.接着调用thread1.start() 方法启动线程thread1
主线程main执行thread1.wait() 释放 “thread1对象的锁” 并且进入 “等待或者阻塞状态”, 等待thread1对象上的线程通过notify() 或者notifyAll() 唤醒
线程thread1运行之后,通过synchronized(this) 获取当前对象的锁,然后调用notify() 方法唤醒当前对象上的等待线程,即唤醒主线程main
线程thread1运行结束后,释放当前对象的锁.然后主线程main获取thread对象的锁,接着运行
问题: thread1.wait() 应该是让线程thread1等待,但是为什么让主线程main等待了?
- wait() 作用是让 [当前线程] 等待 ,[当前线程] 是指正在CPU上运行的线程
- 意味着尽管thread1.wait() 是通过线程thread1调用的wait() 方法,但是调用thread.wait() 的位置

wait(long timeout)与notify()

wait(long timeout) 会让当前线程处于等待阻塞状态,直到其余线程调用此对象的notify() 方法或notifyAll() 方法或者超过指定的时间量,当前线程被唤醒进入就绪状态
主线程main执行t1.start()启动线程t1
主线程main执行t1.wait(3000), 主线程main进入阻塞状态. 需要使用t1对象锁的线程通过notify() 或者notifyAll() 唤醒或者超时3000ms之后自动唤醒,主线程进入就绪状态,然后才可以运行
线程t1运行之后,进入循环会不断地运行
超时3000ms之后,主线程main会进入就绪状态,然后接着进入运行状态

wait()与notifyAll()

notifyAll(): 唤醒此对象监视器上等待的所有线程
主线程新建并启动了3个线程t1, t2, t3
主线程通过sleep(3000) 休眠3秒,在主线程休眠3秒的过程中,线程t1, t2, t3都运行了.运行的线程会执行obj.wait() 方法等待其余线程通过notify() 或者notifyAll() 来唤醒线程
主线程休眠3秒之后,接着运行,执行obj.notifyAll() 唤醒obj上的等待线程,即等待的线程t1, t2, t3. 紧接着,主线程的synchronized(obj) 运行完毕之后,主线程释放obj锁,这样线程t1, t2, t3就可以获取obj锁继续运行

问题

notify()是依据什么唤醒等待线程的,即wait()和notify()之间是通过什么相互关联的?
- 对象的同步锁
为什么notify().wait()等函数方法定义在Object类中,而不是定义在Thread类中?
- Object类中的wait() 和notify() 等函数方法是和synchronized一样,会对 [对象的同步锁] 进行操作
- wait() 会使 [当前线程] 等待,因为线程进入等待状态,所以线程应该释放持有的 [对象的同步锁], 否则其余线程获取不到该 [对象的同步锁] 而无法运行
- 线程调用wait() 之后,会释放持有的 [对象的同步锁], 等待线程被notify() 或者notifyAll() 唤醒
- 负责唤醒等待线程的唤醒线程,只有在获取该对象的 [对象的同步锁], 即等待线程的同步锁,并且调用notify() 或者notifyAll() 方法之后,才能唤醒等待线程.被唤醒的等待线程进入就绪状态,不能立即执行.因为唤醒线程还持有着该对象的 [对象的同步锁], 必须等到唤醒线程释放了该对象的 [对象的同步锁] 之后,等待线程才能获取到该对象的 [对象的同步锁] 继续运行
- 总的来说 ,notify(),wait() 等方法依赖于 [对象的同步锁],[对象的同步锁] 是对象持有的,并且每个对象有且仅有一个. 这就是notify(),wait() 等函数方法定义在Object类中而不是Thread类中的原因

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

力扣第九十八题-验证二叉搜索树前言一、思路二、实现三

发表于 2021-11-17

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

前言

力扣第九十八题 验证二叉搜索树 如下所示：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

1 2	ini复制代码输入： root = [2,1,3] 输出： true

示例 2：

1
2
3

csharp复制代码输入： root = [5,1,4,null,null,3,6]
输出： false
解释： 根节点的值是 5 ，但是右子节点的值是 4 。

一、思路

二叉搜索树必须满足如下的三个条件：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

这一题我刚开始看到就写了一个简单的递归，仅判断当前节点的值是否大于左孩子的值，以及当前节点的值是否小于右孩子的值。很显然，这样做会失败，因为会碰到如下的情况：

虽然 3 < 6 且 7 > 6，但是因为 [6, 3, 7] 作为根节点 5 的子树，他的每个节点的值都应该大于 5，故这个树不能构成二叉搜索树。

于是我就想该怎么解决这个问题呢？

刚开始我是保存了当前节点的 父节点 的值，确保以当前节点开始的子树中的值都会 大于或小于父节点的值，直到我又碰到了下面这种情况：

最下面的叶子节点 3 虽然大于它的父节点 2 以及父节点的 3。但因为它在的子树是作为根节点 3 的左孩子，所以子树中的每个节点值都应小于 3。所以这也构不成二叉搜索树。

于是我发现当前节点是否合规与他的路径有关，总结如下：

左节点 left 的值需要小于父节点，且大于第一次向右的值
右节点 right 的值需要大于父节点，且小于第一次向左的值

这是为什么呢？

其实很简单，因为 符号具有传递性，即 a > b, b > c 可以得出 a > c

举个例子：对于下图中的 i 来说。因为 g > f, f > c，只需要 i > g 就可以满足向右的节点值会一直增大。

又因为以 c 节点开始的子树是 b 节点的左孩子，c 节点开始的子树中的值都要小于 b 节点的值。那为什么不是小于 a 节点的值呢？因为即使 i < a 且 b < a，也无法判断 i 与 b 的大小。

所以，对于右节点来说，只需要大于父节点，且小于第一次向左的值

思路有了之后，实现起来就不难了。

二、实现

实现代码

实现代码与思路中保持一致

java复制代码    private class Path {
        Integer val;
        Boolean isLeft;

        public Path(Integer val, Boolean isLeft) {
            this.val = val;
            this.isLeft = isLeft;
        }
    }

    public boolean isValidBST(TreeNode root) {
        return dfs(root, new LinkedList<>());
    }

    public boolean dfs(TreeNode root, Deque<Path> rootValStack) {
        if (root == null)
            return true;
        // left的值需要小于父节点，且大于第一次向右的值
        if (root.left != null && (root.val <= root.left.val || rootValStack.stream().anyMatch(n -> !n.isLeft && n.val >= root.left.val))){
            return false;
        }
        // right的值需要大于父节点，且小于第一次向左
        if (root.right != null && (root.right.val <= root.val || rootValStack.stream().anyMatch(n -> n.isLeft && n.val <= root.right.val))) {
            return false;
        }
        boolean leftFlag, rightFlag;
        rootValStack.push(new Path(root.val, true));
        leftFlag = dfs(root.left, rootValStack);
        rootValStack.pop();
        rootValStack.push(new Path(root.val, false));
        rightFlag = dfs(root.right, rootValStack);
        rootValStack.pop();
        return leftFlag && rightFlag;
    }

测试代码

java复制代码    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(1, new TreeNode(0), new TreeNode(2)),
                new TreeNode(5, new TreeNode(4), new TreeNode(6)));
        TreeNode treeNode1 = new TreeNode(2, new TreeNode(2), new TreeNode(2));
        TreeNode treeNode2 = new TreeNode(120,
                new TreeNode(70,
                        new TreeNode(50, new TreeNode(25), new TreeNode(55)),
                        new TreeNode(100, new TreeNode(75), new TreeNode(110))),
                new TreeNode(140,
                        new TreeNode(130, new TreeNode(119), new TreeNode(55)),
                        new TreeNode(100, new TreeNode(75), new TreeNode(110)))

        );
        TreeNode treeNode3 = new TreeNode(3,
                new TreeNode(1, new TreeNode(0), new TreeNode(2, null, new TreeNode(3))),
                new TreeNode(5, new TreeNode(4), new TreeNode(6)));
        boolean flag = new Number98().isValidBST(treeNode3);
        System.out.println(flag);
    }

结果

三、总结

这一题击败率不是很理想，主要是因为对于每一个节点都要找到与父节点首个拐点的值是否满足条件。不知道你看了题解之后，有想到如何优化这个算法了吗？

提示一下：去除保存父节点的路径

感谢看到最后，非常荣幸能够帮助到你~♥

如果你觉得我写的还不错的话，不妨给我点个赞吧！如有疑问，也可评论区见~

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有