8皇后问题

一、问题

一个 8×8 的棋盘,希望往里放 8 个棋子,每个棋所在的行、列、对角线上都不能有其他棋子。找出所有满足要求的布局。

二、分析与解

首先画出下面这样一个棋盘:

行、列的下标都是从 0 开始。

逐行摆放棋子,比如当前要摆放第 R 行的棋子时,认为 0 至 R-1 行的棋子是符合要求的,那么对于第 R 行,尝试把棋子摆放到第 C 列,检测是否满足要求,如果满足则继续下一行摆放下一行,不满足则则尝试放至 C+1 列。如果摆放到了第 8 行,则认为得到了一个解。

检测算法:从上图可以看出,只需要检查三种场景,对于位置(row, col):

  1. 左下对角线;该对角线上的点符合 col >= 0 && (row--, col--)
  2. 垂直列;(row–, col), 行 渐减,列不变。
  3. 右下对角线。该对角线上的点符合 col < 8 && (row--, col++)

继续阅读

SpringBoot druid 踩坑笔记

这是一个同事碰到的案例。

现象

SpringBoot 应用卡死、无反应。

处理过程

1、 导出线程栈,发现 Tomcat 处理线程都阻塞在获取连接上,从栈上看连接池使用的是 druid。

2、 对照 druid 源码,发现线程一直被阻塞是因为没有设置获取连接的超时时间。而从配置来看是有设置的。被阻塞的线程栈如下:

"http-nio-8006-exec-200" #7057 daemon prio=5 os_prio=0 tid=0x00007fc82c0a3800 nid=0x1b99 waiting on condition [0x00007fc7c9a57000]
   java.lang.Thread.State: WAITING (parking)
    at sun.misc.Unsafe.park(Native Method)
    - parking to wait for  <0x00000000c2923bd8> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
    at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
    at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2039)
    at com.alibaba.druid.pool.DruidDataSource.takeLast(DruidDataSource.java:1444)
    at com.alibaba.druid.pool.DruidDataSource.getConnectionInternal(DruidDataSource.java:1088)
    at com.alibaba.druid.pool.DruidDataSource.getConnectionDirect(DruidDataSource.java:953)
    at com.alibaba.druid.filter.FilterChainImpl.dataSource_connect(FilterChainImpl.java:4544)
    at com.alibaba.druid.filter.stat.StatFilter.dataSource_getConnection(StatFilter.java:661)
    at com.alibaba.druid.filter.FilterChainImpl.dataSource_connect(FilterChainImpl.java:4540)
    at com.alibaba.druid.pool.DruidDataSource.getConnection(DruidDataSource.java:931)
    at com.alibaba.druid.pool.DruidDataSource.getConnection(DruidDataSource.java:923)
    at com.alibaba.druid.pool.DruidDataSource.getConnection(DruidDataSource.java:100)

3、 通过内存 dump 发现,druid 连接池除 连接串、用户名、密码等几个属性之外的属性都是默认值。
此时连接池里总共有8个连接,都是空闲的,却没有线程能获取到连接,都在阻塞、没有被唤醒。网上查了下,应该是 druid 的bug。

继续阅读

《MySQL 实战45讲》–笔记–锁

根据加锁的范围,MySQL 里面的锁大致可以分成全局锁、表级锁和行锁三类。

全局锁

全局锁是对整个数据库实例加锁。MySQL 提供的一个加全局锁的命令: Flush tables with read lock (FTWRL),让整个库处于只读状态。

全局锁的典型使用场景是做全库逻辑备份。

逻辑备份工具 mysqldump 使用参数 -single-transaction 的时候在导数据之前就会启动一个事务,来确保拿到一致性视图。

一致性读的前提是引擎要支持这个隔离级别的事务。

set global readonly=true 也可以让全库进入只读状态。但存在两个风险: readonly 的值可能被用来做其他逻辑,比如判等一个库是主库还是备库;设置 readonly 之后,如果客户端发生异常,则数据库会一直保持 readonly 状态。

在 slave 上,如果用户有超级权限的话,全库只读 readonly=true 是失效的。

FTWRL 执行完后如果客户端异常断开,MySQL 会自动释放这个全局锁,整个库回到可以正常更新的状态。

继续阅读

《MySQL 实战45讲》–笔记–order by 实现

用 explain 命令查看执行计划的时候,Extra 列的值含有 “using filesort” 表示需要排序,可能是在内存里排序、也可能是磁盘文件排序。MySQL 给每个线程分配一块内存用于排序,称为 sort_buffer ,可以通过参数 sort_buffer_size 调整这个内存的大小。

如果要排序的数据都能放进 sort_buffer 则直接在内存里排序,否则需要借助磁盘临时文件进行辅助排序。

由于 InnoDB 是索引组织表,聚簇索引就是主键索引,下面的描述就用 rowid 替代主键值。

走索引全字段排序

  1. 初始化 sort_buffer,确定要放入 sort_buffer 的目标字段;
  2. 根据选择的索引查找满足条件的 rowid;
  3. 通过rowid到聚簇索引树获取整行数据,取目标字段放入sort_buffer;
  4. 从选择的索引取下一个记录的rowid;
  5. 重复步骤 3、4直到不满足条件;
  6. 对 sort_buffer 中的数据按照排序列进行排序。
  7. 遍历排序结果,把目标数据返回给客户端。

继续阅读

InnoDB Sorted Index Build

Sorted Index Build

InnoDB 在创建或重建索引时采用 批量加载而不是一次插入一个索引记录的方式。这种索引创建方法也称为 Sorted Index Build ,该方式不支持空间索引。

索引创建有三个阶段:

  1. 第一阶段,扫描聚簇索引,生成索引条目并添加到排序缓存(sort buffer)。当排序缓存满了后,条目被排序、写入临时的中间文件。这个过程也称为 run 。

  2. 第二阶段,一个或多个 run 写入临时中间文件,对文件里的所有条目执行合并排序。

  3. 在第三阶段,排序后的条目被插入到 B+tree 上。

Sorted Index build 采用自底向上方式来构建索引,采用这种方式,在 B+Tree 的每一层,持有对最右叶子页的引用。位于B+Tree需要的深度的最右叶子页被分配,条目按它们排序后的顺序插入。一旦叶子页满了,一个节点指针追加到父页上,同层叶子页被分配用于接下来的插入。这个过程持续至所有条目插入完成,这可能导致插入一直到顶层。

白话解读:最底层的最右叶子页插入索引记录,如果当前最右叶子页满了,生成一个新的最右叶子页作为接下来的插入位置,在新旧最右叶子页之间建立指针链接,然后把指向旧最右叶子页的指针追加到上一层的最右叶子页,触发上一层的最右叶子页插入,逻辑跟前面是一样的,这是个递归的过程,直至根页。这是一个自底向上、递归构建的过程

最终生成的索引结构如下图(图片来自MySQL内核解析:Innodb页面存储结构-1):
InnoDB索引结构

为后续插入保留空间

可以使用 innodb_fill_factor 配置选项来指定在 B+Tree 页空间保留的空闲百分比,用于后续在这些位置插入索引条目。

这个设置应用于索引树的叶子和非叶子页。不适用于外部页如用于 TEXT/CLOB 条目的。

这个配置是一个提示而非强制约束。

Consul 与 K8S 滚动部署

不停机发布讨论

近期公司的运维同事对一些系统尝试利用 K8S 的滚动发布机制不停机发布系统,应用和系统的状况是:POD 里的应用实例是注册在 Consul 上,Consul 的健康检查间隔是 10 秒;它们配置的 K8S 滚动发布机制直接把跑应用的 POD 终止了。

这样出现了:应用实例被终止后到 Consul 下次健康检查之前,Consul 认为应用实例是还存活的,把请求分发给了已经被停止的实例,这些请求当然是失败的。有的系统因为下游不支持重试,之前出现应用重试导致出现异常数据,就把 Ribbon、Feign、Hystrix 等的重试机制禁用了。而没有了重试机制请求就直接失败了,这样用户就会感知到系统发布。

大家开会讨论怎么才能让系统发布不会影响请求响应:

  1. 另一个部门的同事说他们就是所有接口都支持重试,所以允许对服务的某个实例请求失败可以重试到另一个实例,这样基本不会影响请求处理。让所有接口支持重试是需要上下游系统协调的,而且需要比较长的时间来实现。还有个问题是,不是所有接口都能重试的,举个行业特定的例子:信贷审批一般都会去查借款人的人行征信报告,多查一次可能导致借款人几个月都没法借款,设想一个报告查询的请求发出去了、在响应还没落地之前,应用实例就被终止了,这肯定是没法接受的。所以应用实例需要在被终止之前得到一个机会—-可以优雅停机的机会,它需要一个停机的通知。对于前面的问题,就是 K8S 要在停机前通知到 POD 里的实例,等通知返回后再终止 POD。

  2. 这就带来这个小插曲,我提出 K8S 在停止 POD 之前给 POD 里的应用发个通知的时候,运维同事说 Consul 和 K8S 是不同的系统,没法做到,他们说的非常肯定。。。

K8S POD 生命周期管理

对于一个问题,自己解决不了 跟 问题无解 是有区别。

在网上搜索一番后找到了 POD 生命周期钩子

继续阅读

MySQL InnoDB 二级索引的排序

排序问题

最近看了极客时间上 《MySQL实战45讲》,纠正了一直以来对 InnoDB 二级索引的一个理解不到位,正好把相关内容总结下。PS:本文的所有测试基于 MySQL 8.0.13 。

先把问题抛出来,下面的 SQL 所创建的表,有两个查询语句,哪个索引是非必须的?

CREATE TABLE `geek` (
  `a` int(11) NOT NULL,
  `b` int(11) NOT NULL,
  `c` int(11) NOT NULL,
  `d` int(11) NOT NULL,
  PRIMARY KEY (`a`,`b`),
  KEY `c` (`c`),
  KEY `ca` (`c`,`a`),
  KEY `cb` (`c`,`b`)
) ENGINE=InnoDB;

select * from geek where c=N order by a limit 1;
select * from geek where c=N order by b limit 1;

作者给的答案是索引 c 和 ca 的数据模型是一样的,因此 ca 是多余的。为啥??

我们知道,二级索引里存放的不是行的位置,而是主键的值,也知道索引是有序的。

如果 c 与 ca 的数据模型一样,那么就要求二级索引的叶子节点不仅是按索引列排序、而且还按关联的主键值进行排序

我以前的理解是 二级索引只按索引列进行排序,主键值是不排序的。

问了专栏作者,得到的答复是:索引 c 就是按照 cab 这样排序,(二级索引))有保证主键算进去、还是有序的。(PS:非原话,前后问了三次得到)。

本着 先问是不是,再问为什么 的思路,进行一番探究。

继续阅读

2018 年终总结

一、生活

最大的变化应该是变身房奴了,租房时房租每年涨10%,租金加上公积金再加小几千的现金支出够供房,所以也还好吧。

选择在南山买个老破小、而不去关外买个大点的,主要是考虑上下班方便,一般情况下坐公交半个钟能到公司,走路回来也只要50分钟。

国庆后老妈也出来深圳,回家吃晚饭的次数就多了,吃过晚饭去中山公园溜溜老婆也挺好。

二、工作

1. 拆服务

年初开始,大部门划分为多个小组,每个小组负责的模块都从原来的系统里拆分出来做服务,所有新项目基于 Spring Cloud 1.X 技术栈搭建。

我小组拆服务比较晚,正好可以看看其他组踩的坑,观察到的问题主要有:

  • Ribbon、Feign 的自动重试问题;对于没有做幂等处理的逻辑,就可能出现重复执行、数据重复等问题。

  • SpringBoot 默认的数据源属性前缀是 spring.datasource,Druid 连接池的 SpringBoot 的组件的数据源属性前缀默认是 spring.datasource.druid,这样可能导致配置不生效。还必须指定 Druid 获取连接的超时时间,否则可能都进入一直等待状态,应该是有活锁的bug。

"http-nio-8080-exec-100" #7057 daemon prio=5 os_prio=0 tid=0x00007fc83c0a3800 nid=0x1b99 waiting on condition [0x00007fd7c9a57001]
java.lang.Thread.State: WAITING (parking)
at sun.misc.Unsafe.park(Native Method)
- parking to wait for  &lt;0x00000000c2923bd8&gt; (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.await(AbstractQueuedSynchronizer.java:2039)
at com.alibaba.druid.pool.DruidDataSource.takeLast(DruidDataSource.java:1444)
at com.alibaba.druid.pool.DruidDataSource.getConnectionInternal(DruidDataSource.java:1088)
at com.alibaba.druid.pool.DruidDataSource.getConnectionDirect(DruidDataSource.java:953)
  • 用 Apollo 做配置管理,要考虑 线程池、连接池的实时刷新问题。Apollo 一般只支持刷新 Spring 容器管理的 @Value 注解的属性,这些池的属性一般都是没有这样的注解的。

  • Hystrix 用线程异步执行调用时,导致调用链跟踪中断。这个是小问题,不影响业务。

别人踩的坑也是可以学习的;技术还是要自己去验证、不能网上直接抄段代码就用。

2. 项目质量

小组负责的模块是纯后台服务,业务逻辑比较复杂,偏偏又是跟钱相关,不能出错。代码质量、逻辑的正确就非常重要。

趁着这次拆服务,把单元测试做起来,觉得效果还是不错的。让一个实习生给一个逻辑写单元测试时,发现了一个之前没注意到的数据问题;自己给一个模块补充测试用例时,也发现在某个场景下的逻辑问题。

19 年准备采取如下的步骤来做单元测试:

  1. 与具体的开发同事一起做需求分析;
  2. 让开发同事根据需求做单元测试用例设计:把场景、边界值等列出来;
  3. 复核测试用例及实现,所有对结果的校验必须用断言来实现。

欢迎关注我的微信公众号: coderbee笔记,可以更及时回复你的讨论。

《从0开始学架构》–笔记

第2篇 架构是什么

系统 泛指由一群有关联的个体组成,根据某种规则运作,能完成个别元件不能单独完成的工作的群体(能力)。

从逻辑的角度拆分系统后,得到的单元就是“模块”,从物理的角度拆分系统后,得到的单元就是“组件”。划分模块的主要目的是职责分离,划分组件的主要目的是单元复用。

框架是组件规范,提供基础功能的产品。软件架构指软件系统的“基础结构”,创造这些基础结构的准则,以及这些结构的描述。框架关注的是“规范”,架构关注的是“结构”。

软件架构指软件系统的顶层结构:
* 架构需要明确系统包含哪些“个体”,个体可以是 子系统、模块、组件等。
* 架构需要明确个体的运作和协作的规则。
* 顶层结构可以更好地区分系统和子系统。

自话:软件架构确定了系统中应该包含哪些个体,以及个体之间应该如何协作,以提供某种能力,从而实现系统的价值。

第2篇 架构设计的历史背景

“模块”“对象”“组件”本质上都是对达到一定规模的软件进行拆分,区别只是在于随着软件的复杂度不断增加,拆分的粒度越来越粗,拆分的层次越来越高。

第3篇 架构设计的目的

架构设计的主要目的是为了解决软件系统复杂度带来的问题。

架构设计首先要分析系统的复杂度所在,然后针对这些复杂度进行设计、制定方案。

第4篇 复杂度来源:高性能

软件系统中高性能带来的复杂度主要体现在两方面,一方面是单台计算机内部为了提高性能带来的复杂度;另一方面是多态计算机集群为了高性能带来的复杂度。

第5篇 复杂度来源:高可用

系统的高可用本质都是通过“冗余”来实现的,方法是增加机器。

高性能增加机器的目的在于“提升”处理性能,高可用增加机器的目的在于“冗余”处理单元。

存储高可用的难点不在于如何备份数据,而在于如何减少或者规避数据不一致对业务造成的影响。

高可用状态决策:无论是计算高可用还是存储高可用,其基础都是“状态决策”,即系统能够判断当前状态是正常还是异常,如果出现异常就要采取行动来保证高可用。

决策方式:
* 独裁式:所有冗余的个体向一个独立的决策主体上报状态信息,决策者进行决策。问题在于决策者本身是个单点。
* 协商式:两个独立的个体通过交流信息,然后根据规则进行决策,最常用的协商式决策就是主备决策。难点在于两者的信息交换出现问题时如何决策。
* 民主式:指多个独立的个体通过投票的方式来进行决策。缺陷是脑裂:原来统一的集群因为连接中断,造成两个独立分隔的子集群,每个子集群单独进行选举,选出两个决策者。解决方法是要求“投票节点数必须超过系统总结点数一半”。

第6篇 复杂度来源:可扩展性

可扩展性是指为了应对将来需求变化而提供的一种扩展能力。

设计具备良好可扩展性的系统,有两个基本条件:正确预测变化、完美封装变化。

预测变化的复杂性在于:不能每个设计点都考虑可扩展性、不能完全不考虑可扩展性、所有的预测都存在出错的可能性。

设计具备良好可扩展性的系统,有两个思考角度:从业务维度,对业务深入理解,对可预计的业务变化进行预测;从技术维度,利用扩展性好的技术,实现对变化的封装。

应对变化的常见方案一是将“变化”封装在一个“变化层”,将不变的部分封装在一个独立的“稳定层”。
方案二是提炼出一个“抽象层”和一个“实现层”,抽象是文档的,实现可根据具体业务需要定制开发,加入新的功能时,只需要增加新的实现,无需修改抽象层。

举例:设计一个支付网关对接不同的支付机构,为业务系统提供支付能力。每家支付机构的通信方式、请求/响应格式都是不一样的,但基本参数都是四要素信息(银行卡号、预留手机号、姓名、身份证号)、扣款金额等,扣款结果一般就是成功/失败/等通知,因此可以抽象出统一的接口,对接不同支付机构的具体实现类实现这个接口、完成具体的调用逻辑,当要对接新的支付机构时只需要添加一个实现类;业务系统只需访问这个统一的接口。

继续阅读

设计模式之工厂家族

《冒号课堂编程范式与OOP思想》 13.1 创建模式笔记

工厂家族

构造器的弊端:名字必须与类名一致,缺乏表现力;每次调用都会创建新对象;无法多态,new 必须使用具体类型,没法使用抽象的超类型。

抽象工厂模式:
1. 把静态工厂拆分成了一个接口和若干个实现类;
2. 把工厂方法模式中的主题类中的抽象工厂方法提炼为一个接口,用对象合成取代了类继承。

代码说明示例

1. 静态工厂模式:

public class StaticFactory {
    public enum Type {
        AWT, SWING
    };

    public static Container createFrame(Type type, String title) {
        switch (type) {
            case AWT:
                return new Frame(title);
            case SWING:
                return new JFrame(title);
            default:
                return null;
        }
    }

    public static Component createLabel(Type type, String text) {
        switch (type) {
            case AWT:
                return new Label(text);
            case SWING:
                return new JLabel(text);
            default:
                return null;
        }
    }
}

// 使用静态公共方法的类
class LoginForm {
    public Container createLoginWindow() {
        // 使用前要指定具体的类型
        StaticFactory.Type type = StaticFactory.Type.AWT;
        Container frame = StaticFactory.createFrame(type, "标题");
        Component label = StaticFactory.createLabel(type, "文本");
        // 组装组件
        return null;
    }
}

每个创建对象的方法都通过参数来指定要创建的具体对象类型,调用方必须指定具体的类型。

继续阅读