Tree : Top View - HackerRank解题记录

题目：
You are given a pointer to the root of a binary tree. Print the top view of the binary tree.
Top view means when you look the tree from the top the nodes, what you will see will be called the top view of the tree. See the example below.
You only have to complete the function.
For example :

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
Top View : 1 -> 2 -> 5 -> 6

Input Format

You are given a function,

void topView(node * root) {

}
Constraints

1 Nodes in the tree  500

Output Format

Print the values on a single line separated by space.

Sample Input

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
Sample Output

1 2 5 6

Explanation

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
From the top only nodes 1,2,5,6 will be visible.
思路：
先看一张图（图片来自搜）

TopView的意思是从上往下看，能看到的节点，并且是从左到右的顺序来输出。
我们可以给每个节点标上一个列的标识，设定root的列标识为0，右节点加1，左节点减1，然后再从层次遍历，把遇到的节点存到一个有序的map里面，列标识作为key，只要曾经有过这个key，那么就忽略，最终输出这个map里的内容即可
代码：

public static void topView(Node root) { Map<Integer,Integer> map = new TreeMap<Integer,Integer>(); Queue<Node> queue = new LinkedList<>(); Queue<Integer> queue2 = new LinkedList<Integer>(); queue.add(root); queue2.add(0); while (queue.peek() != null) { Node tmp = queue.poll(); Integer level = queue2.poll(); if (!map.containsKey(level)) { map.put(level, tmp.data); } if (tmp.left != null) { queue.offer(tmp.left); queue2.offer(level - 1); } if (tmp.right != null) { queue.offer(tmp.right); queue2.offer(level + 1); } } for (Map.Entry<Integer,Integer> entry : map.entrySet()) { System.out.print(entry.getValue()); System.out.print(" "); } }

原题链接：https://www.hackerrank.com/challenges/tree-top-view/problem

Read More →

设计模式-建造者模式

        建造者模式，又叫构建者模式，构建器模式等等，定义这里我就不赘述了，网上书上都很多，可以很方便找来看。我为什么不说一遍呢，第一，觉得大部分的定义都描述的不是很易懂，第二，我自己目前还没达到能够下定义的水平。

        先来看看代码，然后再给出我的理解。

public class Article {
    private String title;

    private String content;

    private String sign;

    private Date time;
//省略了getter,setter,toString

}

public interface ArticleBuilder {
    void setTitle(String title);
    void buildContent(String title);
    void setTime(Date date);
    Article getResultArticle();

}

public class ConcreteArticleBuilder implements ArticleBuilder {
    private Article article = new Article();

    @Override

    public void setTitle(String title) {
        article.setTitle(title);

    }

    @Override

    public void buildContent(String content) {
        article.setContent(content);

    }

    @Override

    public void setTime(Date date) {
        article.setTime(date);

    }

    @Override

    public Article getResultArticle() {
        return article;

    }
}

public class ArticleWriter {

    private ArticleBuilder builder;
    public ArticleWriter(ArticleBuilder builder) {
        this.builder = builder;

    }

    public Article construct() {
        builder.setTitle("");

        builder.buildContent("");

        builder.setTime(new Date());

        return builder.getResultArticle();

    }
}

public class BuilderPatternDemo {
    public static void main(String[] args) {
        ArticleBuilder carBuilder = new ConcreteArticleBuilder();

        ArticleWriter cd = new ArticleWriter(carBuilder);

        Article car = cd.construct();

        System.out.println(car);

    }
}

建造者模式的核心类是Builder接口和具体的Builder实现类，比如StringBuilder，我们在使用的过程中，几乎忽略了Director角色和抽象Builder（Appendable）的存在，而Director角色也通常是业务逻辑中的角色，对于抽象程度不高的业务代码中，没有什么影响。对于一个架构良好的设计中，各角色的存在还是很有必要的。

建造者模式和工厂模式的区别在于，工厂模式使用类似于流水线的方式目的在于生产一批对象，而建造者模式核心的关注点是如何创建一个对象，以及创建过程中的每个细节。工厂模式的适用于批量创建多个对象的场景，建造者模式适用创建单个复杂的不同对象，用建造者创建的多个对象之间的差异较大。

再用另外一个比喻，一个是工厂，生产出来的是千篇一律的产品，另外一个是指挥家，创造的音乐是有个性的，几乎是唯一的音乐。

再比如，创作一幅画，这个也可以用建造者模式

建造者模式在JDK中身影：StringBuilder

代码地址：https://github.com/angelala00/learn/tree/master/src/main/java/cn/jc/designpattern/builderpattern

下面再附上实现《设计模式》中的Builder模式的代码：

https://github.com/angelala00/learn/tree/master/src/main/java/cn/jc/designpattern/builderpattern1

Read More →

设计模式-抽象工厂

        工厂方法模式中，工厂类用于生成一系列对象实例并且以这些对象的父级类型作为返回结果。当有多个这样的工厂，这些工厂之间会生产出一系列不同的对象，这种情况下，我们可以定义一个抽象工厂来描述工厂的行为，即创建一系列对象的方法，再让具体的工厂类继承这个抽象工厂。也可以说是把一个系列的工作抽象出来一个抽象的类型，这个抽象的类型就是抽象工厂。

先来看一下结构图：

下面来看一下具体代码：

定义抽象类型

public interface Animal {
    void say();}

public interface Cat extends Animal {
}

public interface Dog extends Animal {
}

public interface Duck extends Animal {
}

定义抽象工厂接口

public interface AnimalFactory {
    /**     * 抽象工厂方法     * 特点与工厂方法一致：     * 创建了一个对象     * 返回类型为一个接口或者抽象类     * 有多个类实现了上述抽象类型     *     * @param animalType     * @return     */    Animal getAnimal(String animalType);}

抽象类型的具体类与具体工厂类（US）

public class CatUs implements Cat {
    @Override    public void say() {
        System.out.println("america cat");    }
}

public class DogUs implements Dog {
    @Override    public void say() {
        System.out.println("america dog");    }
}

public class DuckUs implements Duck {
    @Override    public void say() {
        System.out.println("america duck");    }
}

public class AnimalFactoryUs implements AnimalFactory {
    @Override    public Animal getAnimal(String animalType) {
        if ("dog".equals(animalType)) {
            return new DogUs();        } else if ("cat".equals(animalType)) {
            return new CatUs();        } else if ("duck".equals(animalType)) {
            return new DuckUs();        } else {
            return null;        }
    }
}

抽象类型的具体类与具体工厂类（CHINA）

public class CatChina implements Cat {
    @Override    public void say() {
        System.out.println("china duck");    }
}

public class DogChina implements Dog {
    @Override
    public void say() {
        System.out.println("china dog");    }
}

public class DogChina implements Dog {
    @Override
    public void say() {
        System.out.println("chinese dog");    }
}

public class DuckChina implements Duck {
    @Override    public void say() {
        System.out.println("china cat");    }
}

public class AnimalFactoryChina implements AnimalFactory {
    @Override    public Animal getAnimal(String animalType) {
        if ("dog".equals(animalType)) {
            return new DogChina();        } else if ("cat".equals(animalType)) {
            return new CatChina();        } else if ("duck".equals(animalType)) {
            return new DuckChina();        } else {
            return null;        }
    }
}

测试主类

public class AnimalfactoryDemo {
    public static void main(String[] args) {
        AnimalFactoryChina animalFactoryChina = new AnimalFactoryChina();        animalFactoryChina.getAnimal("dog").say();
        AnimalFactoryUs animalFactoryUs = new AnimalFactoryUs();        animalFactoryUs.getAnimal("dog").say();    }
}

代码地址
https://github.com/angelala00/learn/tree/master/src/main/java/cn/jc/designpattern/abstractfactory

再多说一点
在研究抽象工厂的时候，也参考了多个网上搜索到的文章，记得有一篇是https://www.runoob.com/design-pattern/abstract-factory-pattern.html，看过之后总觉得不是很理想，文章中的代码看起来也是抽象工厂的逻辑和结构，然而某一个具体的工厂却有闲置的方法，比如ShapeFactory的getColor方法，这样在使用者看来，总会产生一些困惑，所以又找了纸质书资料，最终参考了《设计模式Java手册》中关于抽象工厂模式的讲解，并且把其中的代码实现了（地址：https://github.com/angelala00/learn/tree/master/src/main/java/cn/jc/designpattern/abstractfactory1）之后，觉得这里说的案例，更能准确的描述抽象工厂。于是有了本文的Demo。

JDK中抽象工厂的身影：
java.sql.Driver的connect方法。
Connection为connect方法返回的抽象类型。在java.sql.Driver中，没有给出具体的工厂类，而是由DriverManager来管理，动态注册到一个工厂集合中。

Read More →

设计模式-工厂模式

    工厂模式，也叫工厂方法模式，定义一个用于创建对象的接口，可以控制对哪个类进行实例化

public interface Animal {

    void say();
}

public class Cat implements Animal {
    @Override
    public void say() {
        System.out.println("miao miao miao");
    }
}

public class Dog implements Animal {
    @Override
    public void say() {
        System.out.println("wang wang wang");
    }
}

public class Duck implements Animal {

    @Override
    public void say() {
        System.out.println("ga ga ga");
    }
}

public class AnimalFactory {
    /**
     * 此方法为工厂方法模式，
     * 特点为：
     * 创建了一个对象
     * 返回类型为一个接口或者抽象类
     * 有多个类实现了上述抽象类型
     * @param color
     * @return
     */
    public Animal getAnimal(String color) {
        if ("dog".equals(color)) {
            return new Dog();
        } else if ("cat".equals(color)) {
            return new Cat();
        } else if ("duck".equals(color)) {
            return new Duck();
        } else {
            return null;
        }
    }
}

Demo入口

public class AnimalFactoryDemo {

    public static void main(String[] args) {
        AnimalFactory af = new AnimalFactory();
        Animal cat = af.getAnimal("cat");
        cat.say();
        Animal dog = af.getAnimal("dog");
        dog.say();
        Animal duck = af.getAnimal("duck");
        duck.say();
    }

}

工厂模式的使用场景
需要大量创建对象的工作，不同条件下要创建不同的对象，这些对象都是一个抽象类型的实现类对象

JDK中工厂模式的身影：
《设计模式Java手册》一书中提到，Iterable的子类型的iterator方法是典型的工厂方法模式的应用。我的理解，这里更应该是一个抽象工厂，当然，针对某一个具体的类，比如ArrayList，来说，它的iterator()方法，就是一个工厂方法。

    /**
     * JDK中工厂方法模式，iterator方法
     * 来自《设计模式Java手册》
     * @param args
     */
    public static void main2(String[] args) {
        List list = Arrays.asList(new String[]{"funasdf", "rocsdfd", "sparkkkasf"});
        Iterator i = list.iterator();
        while (i.hasNext()) {
            System.out.println(i.next());
        }

    }

觉得这里的理解还是有些欠缺，等有新的收获再来回顾。

Read More →

关于“复用”的一点想法

       关于复用，如何合理的复用这个事，想说清楚，真不是那么容易的事情，下面我说一个表是否复用的大致场景，以及我的感想。

有一个现有的表，然后有一个新业务，这个新业务和原来的表对应的业务很像（可想象空间很大），

那应该不应该复用，这里可能很难下定论，因为不知道这两个业务在长远看来是否是有共性，是否是可合并的，是否是互斥的，等等因素

如果仅仅是为了少建表这一个原因的复用，那么我认为是不可取的，这种情况下，可能表的字段满足当前的需求，但字段意义是有着千差万别的

很多情况下，为了区分这两个业务，可能会用type这类字段来区分一下，然后很大概率可能发生的情况是某一个业务需要调整，增加了一个字段，这时候另一个业务是完全不需要的，长此以往，可想而知这个表将来是什么样子，至少我看到这个表，以及对应的多个业务，是想吐的。

当然也有可能在刚开始复用的时候，是判断不出后面是这样的场景，那么在扩展表的时候，就需要有一定的决断力，表该拆的时候，一定要拆，不要为了省事，凑合着用。

往往实际开发的时候，不是这样，拆分可能会带来额外的工作量以及风险，工作量会因人而异，如果代码质量好，拆分的工作量可能会低些，然后另一个大家都不愿意触碰的是风险，如果因这些改动而造成了一些问题，那这个问题谁来担，公司中因为这个因素，使得大家几乎没有任何动力去优化当前现有的难看的代码，除非是公司文化使然，或者是领导明确了优化范围以及提供相应的测试资源，明确了此次需求的责任人，把这个事当成一个项目去做，可是，这样不对么？对么？

就我的意愿来说，我是希望在每次开发迭代中，把重构放第一位，从整体到局部，这样来说，是否复用的问题就变成如何设计当前的项目问题了。

可是反过来我又问自己，多出来的时间怎么办？风险谁来把控？

我自己尝试着回答，如果从长期来看，在一直保持着持续重构的基础之上，每次多出来的时间与风险，是完全可以抵消下一次迭代的开发周期节约的时间成本以及后期查问题的维护成本，

这个收益是延迟的，而且在一个本来就很乱的基础之上，首次做重构的工作，是很难的，如果后期不能持续这个传统，那么这一次艰难的重构工作会变得费力不讨好的事情。

还有一个点是，在重构的过程，最好是相关的业务人一起讨论，产品或者功能的性质，以后的演变的可能性，技术实现方案能支持到什么程度，等等，一方面有助于相关的业务人理解业务，另一方面也让PM能够重新审视自己的产品是否有问题。 

写这个，也是因为公司代码中看到太多因为不合理的复用而导致的代码烂到不行，一边吐槽，一边梳理一下自己的想法。

Read More →

设计模式-单例模式

        设计模式，通常指GOF的《设计模式 可复用面向对象软件的基础》书中提到的面向对象编程23种设计模式，话不多说，先来看一个单例模式。

单例模式，可以保证在系统中单例类只能有一个实例。

接下来我把在网上流行的大部分实现方案以及个人在思考单例模式的实现过程整理如下
方案一：

/**
 * 饿汉式
 * 使用时直接使用静态变量，理念不好，不利于扩展
 */
public class Singleton {
    /**
     * 初始化动作写到静态代码块中是一样的效果
     */
    public static Singleton instance = new Singleton();

    private Singleton() {
    }
}

方案二：

/**
 * 饿汉式
 * 使用时调用 getInstance 方法，后期如有需求可直接改动方法实现即可
 */
public class Singleton {
    public static Singleton instance = new Singleton();

    private Singleton() {
    }

    public static Singleton getInstance() {
        return instance;
    }
}

方案三：

/**
 * 懒汉式，使用时才初始化
 * 线程不安全，单线程环境下可用
 */
public class Singleton {
    public static Singleton instance = null;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
} 

方案四：

/**
 * 懒汉式，使用时才初始化
 * 线程安全，方法加锁，效率低
 */
public class Singleton {
    public static Singleton instance = null;

    private Singleton() {
    }

    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

方案五：

/**
 * 懒汉式，使用时才初始化
 * 线程安全，代码块加锁，效率高，
 */
public class Singleton {
    /**
     * 这里如果不加volatile声明，可能会因为JVM对指令重排导致异常
     */
    public static volatile Singleton instance = null;

    private Singleton() {
    }

    /**
     * 这里如果只判断里层，那和方法加锁一样了，如果只判断外层，那线程安全的问题没有解决
     * 这种方案可能在实例初始化时，如果遇到多线程问题，会有资源竞争，
     * @return
     */
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized (Singleton.class) {
                if (instance == null) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

方案六：

/**
 * 静态内部类实现，针对内部类SingletonHolder来看，属于饿汉式，针对外部类Singleton来看，属于懒汉式的效果
 * 只有在调用getInstance方法的时候才会初始化内部类SingletonHolder的属性也就是单例实例
 * 由JVM帮我们保证了线程安全，JVM在初始化类的时候是不允许多线程进入的
 */
public class Singleton {
    public static String someStaticProperty = null;

    private Singleton() {
    }

    public static Singleton getInstance() {
        return SingletonHolder.INSTANCE;
    }

    private static class SingletonHolder {
        private static final Singleton INSTANCE = new Singleton();
    }
}

方案七：

/**
 * 用枚举来实现单例，有很多优点，无需考虑线程安全问题，还可以防止反序列化重新创建对象。
 * 枚举来作为单例的实现方案最初看到是在EffactiveJava中提出的，但没有被普遍使用该方案
 * 个人认为原因，枚举出来的比较晚，大家不是很熟悉，枚举是属于懒汉式
 * 对枚举的解读参考文章：https://www.cnblogs.com/kailejun/p/6624471.html
 */
public enum Singleton {
    INSTANCE;

    public void someMethod() {

    }
}

代码地址：
https://github.com/angelala00/learn/tree/master/src/main/java/cn/jc/designpattern/singleton

方案五和方案六是多线程环境下用的最普遍的两种方案，大部分人更认可的是方案六。

JDK中单例模式的身影：
java.long.Runtime

前提知识，面向对象编程

Read More →

排序算法演示动画

        写前面两篇排序的时候，百度找图片，看到还比较不错的动图，能够展示数据在内存中的变化。然而性格使然，我会仔细的观察动图，仔细观察的话发现要么是无法较好的展示比较过程，要么是交换的过程与实际代码执行的有一些出入，心想自己做一个效果出来。这一想不要紧，4月30号-5月4号，花了几个晚上时间，终于搞定了俩算法的排序效果动图，这效率低的也是没谁了。

中间的尝试过程，以及遇到的问题，
1，开始用JavaScriptr的canvas，画出了初始化的状态，做到动效觉得会很麻烦，卡住了。
2，咨询前端同事，建议用css，于是改用div，做到动效的时候，仍然卡住，原因是延迟函数执行的效果和预期不一致，大致能猜到js的闭包特性导致。
3，于是想到用Java的canvas直接画出来，于是乎动手，写到动效，又卡住，动效过程中及时渲染没搞定，无奈对API不熟悉，暂时放弃。
4，重新思考div方案中遇到的问题的解决办法，按说，仔细处理一下延迟方法，应该可行，于是再次动手，这次把冒泡的效果做出来了，想着没问题了，接着套入插入排序，然而执行效果又与预期不一致，究其原因发现插入排序中多了break导致，break无法让事先定时的timer取消往下执行，这下又卡住了，带着问题入睡。
5，早上再继续，想到把排序过程和效果分开来写（最开始就是分开写的，过程中觉得直接一边排序一边展示效果更合理，然而后来证明，分开也有分开的好处），这下可以了。

中间遇到问题原因之一是对前端展示部分的代码熟悉程度不够，二是没有整体从开始思考可行的方案，也是因对前端代码的评估过于简单了，只在脑海中想了一下，就觉得没问题。JS的canvas，CSS的动画，Java的Canvas，应该都能实现该效果，这里暂且不深究了，本来的目的也只是想在做排序的时候，可以做出辅助理解的动画效果。


冒泡排序

https://github.com/angelala00/learn/blob/master/src/main/html/sort/bubblesort.html

插入排序

https://github.com/angelala00/learn/blob/master/src/main/html/sort/insertionsort.html

Read More →

面试基础-插入排序

第二个排序算法，插入排序的思想是遍历数组中的每一个元素，插入到已经有序的数组中，插入的过程仍需保持数组的有序性。实际写代码时，插入的过程类似于冒泡的过程，从后往前遍历，找到合适的位置插入。插入排序是一次只关心一个元素，直接找到最终位置，冒泡排序是一次比较若干元素，找到一个最大元素放到最终位置。

测试输入：new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};

    /**
     * 从后往前遍历插入，这个插入过程有点像冒泡，只冒到合适的位置即可
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                compareTimes++;
                if (arr[j] < arr[j - 1]) {
                    Util.swap(arr, j, j - 1);
                    swapTimes++;
                } else {
                    break;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:61 交换次数:46

图片仍来自百度，图片能大致反应排序的思想，但仍不能完全的反应内存真实的动作，所以想自己写一个动画，来反应排序过程中数据在内存中的动画效果，包括比较过程，包括交换过程。努力ing

Read More →

面试基础-冒泡排序

        多年的开发经验仍不能透彻理解一些基础的算法，按说懂个大概也行啊，言语稍微变通一下就可以啦，可更重要的是言语表达也是不在行，遇到一些姿态较高的，又爱跟你较真和抬扛的人的时候，就无奈了。想想算了吧，随他吧。可是你自己呢，别人看到的你仍是小白啊，那我就把自己当作小白，重新来过吧。
        没有系统的按照教科书的顺序，只按自己想到哪，学到哪，记录到哪。

下面进入正题，先来个冒泡排序。一个最简版本，一个稍微优化版本。

测试输入：new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};

    /**
     * 最差的冒泡排序
     * n*(n-1)次比较，0-n*(n-1)次交换
     *
     * @param arr
     */
    public void sort0(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    Util.swap(arr, j, j + 1);
                    swapTimes++;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:240 交换次数:46

    /**
     * 稍优化一点的冒泡排序
     * n*(n-1)/2次比较，（0-n*(n-1)/2）次交换
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    swapTimes++;
                    Util.swap(arr, j, j + 1);
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:120 交换次数:46

时间复杂度均为O(n^2)

code地址：https://github.com/angelala00/learn/blob/master/src/main/java/cn/jc/datastructure/sort/BubbleSort.java

Read More →

死锁产生条件和如何处理死锁

死锁是在计算机系统中，两个或者两个以上的进程（或者线程），在执行过程中由于某些存在竞争的资源没有合理的管理和释放而导致线程阻塞，无法继续执行下去的状态。

图片来自百度

死锁产生的条件

1，资源互斥，资源同时只能被有限的线程占有

2，阻塞不释放，线程申请资源阻塞后，不释放已经持有的资源

3，不可剥夺，线程持有的资源，是不能被其它线程剥夺的，只能由自己使用完了释放

4，循环等待，存在一个资源等待环，

死锁会导致资源无法释放，系统hang住，这毕竟是我们不想看到的现象

在死锁产生之前，我们需预防和避免，主要思想就是破坏产生的条件，下面针对四个条件分别进行破坏~

1，资源互斥，如果资源是可以被无限共享和使用的，那也就不存在死锁的问题了

2，线程申请资源阻塞后，释放已经持有的资源，线程返回失败

3，线程按优先级排序，优先级高的线程可以剥夺优先级低的线程持有的资源

4，申请资源的时候检测，如果此次申请如果能产生环路，则取消此次申请

其它方案

5，一次性请求所有资源

6，资源编号，按顺序申请使用

7，超时释放重试

实际方案中，应该是没有针对剥夺与资源互斥上面下手的

在死锁产生之后，我们需要处理后续的问题

1，检测死锁，终止死锁等待环中的节点

2，重启进程

《Java并发编程实战》中谈到，数据库系统在设计的时候考虑到了死锁的监测以及从死锁中恢复，当检测到死锁时，将选择一个事务作为牺牲者，让其它事务继续执行，应用程序可以重新发起被强行中止的事务

对于java程序，无法从死锁中恢复，所以都会在开发阶段避免死锁，在实际应用中，对于已经发生死锁的情况，通常都需要根据进程信息等，先定位到死锁的位置，然后重启来解决当时的问题，再优化死锁产生的位置，达到根治的目的 

Read More →

分布式事务梳理

分布式事务目前流行的方案也有很多种，网上能找到大把的技术文章，但看人家的文章总是有各种问题，要么某些地方不好理解，要么某些地方认为不正确，还是按自己的视角来梳理一下。

目前看到的方案，2PC，3PC，TCC，事务消息，本地消息表，等等。

一，2PC

多个数据库在同一个公司，同一个网段可访问到，以及数据库支持2PC，先对多个要提交的事务先发起预提交，多个库确认可以commit了之后，再发起确认commit，当然这个方案存在一些问题，前面说的前提是一些场景上的限制，场景适用后，在发起commit阶段仍然会有可能有不一致的可能性存在，后面会有3PC，同样也是解决了部分问题，无法最终解决一致性问题。

二，3PC

3PC是在2PC的基础之上，在commit又分成了2步，进一步减少数据不一致的可能性。

三，TCC

其实TCC和2PC原理基本一样，只是TCC是不同的资源可能在不同公司，采用不同的服务的方式，多个服务需要支持一个完整的事务，这时候2PC就不适用了，TCC相当于把每个需要事务控制的服务提供确认和取消的操作，这样，在发起事务前先预先锁住资源，待所有资源都确认可以获得，再发起确认操作，中间如有某一个资源预先获取失败，则会取消其它的资源的持有。

在一篇文章又看到解释TCC又分几种类型，通用型，补偿型，异步确保型。通用型也就是刚刚说到的这种，补偿型稍微有点不一样，只提供提交和撤回操作，异步确保型则引入MQ。

对于TCC方案，后面的确认环节同样存在一定的问题，会有不一致的可能性存在，这时候就需要一些超时机制，check机制来尽可能的自动确保事务的一致性，这些机制几乎能解决因网络抖动，服务暂时不可用或者down机后快速恢复等情况引发的问题，对于一些更严重的故障，甚至比如程序出了bug，无法恢复的情况，最终也只能引入人工来修复。

四，事务消息

刚才有提到引入MQ，对于发MQ和本地的操作如何能够保证一致性呢，这个就引出了事务消息的概念，普通的MQ无法保证消息发成功和本地的业务的完全一致性，为了这个目标，在MQ系统中引用2PC的方案，先提交一次消息，然后执行业务，完成之后再次提交一次确认消息，对于没有收到确认的消息，定时轮询回查业务方，或者定期删除。

五，事务消息-本地消息表

有文章提到ebay的一个实现方案，本地消息表来保证本地事务，然后再需要一个timer来轮询本地消息表，检查没有投递成功的消息重复调用发送。如果没有RocketMQ这种支持事务的MQ，可以选用此方案，对业务的入侵较大，不易复用。

基于消息的最终一致方案，目的是保证本地操作和消息发送成功作为一个事务保证一致性。如果消费者端的业务执行成功与否会影响到消息生产者端，则还需要一个回调来报告消费端的成功与失败。

六，Paxos

Zookeeper使用的一致性算法，据说真正的解决了一致性问题，稍后再看。

七，

没有名字，但各大厂都提供的支付接口，与调用方本地的事务需要保证的一致性，我认为这也是解决分布式事务的一个很好的方案。

调用方先创建本地订单，然后调用支付接口，拿到结果后更新本地订单。

针对本地订单已经创建，但是没有拿到支付结果的订单，重复调用支付，支付接口根据调用方的orderid唯一来做幂等。

支付服务方还会定时调用回调接口报告支付成功与失败，来保证事务的一致性和完整性，定时调用本地接口。

如果本地重试和支付宝重试均失败，那就需要人工介入。

对于遇到的一些场景进行分类的话，可以有几个维度的划分

需要回滚，比如订中转的机票，适合用TCC的方案

不需要回滚，比如单纯的支付场景，比如随主业务一起发通知的场景，只需要保证最终能够成功或者到达即可，更适合采用事务消息的方案

这里认为退票和退款这两种情况不属于回滚，属于另起的一个单独的事务

实时一致性，必须强一致，实时看到效果，在线等的场景

最终一致性，允许延迟，只要求最终一致即可，上面的方案七

允许少量不一致的业务，偶尔也会来凑热闹，这个就不属于分布式事务了

基于跨数据库的分布式事务，同一服务内的跨库场景，适用2PC或者3PC

基于跨服务的分布式事务，上面说的场景大多数属于这一类，仍需具体看场景来使用TCC或者事务消息等

分布式消息，本地事务与消息的一致，通常针对不需要回滚的，允许非实时一致的，可选用此方案

再回顾一下对这几个方案的理解，本质的原理几乎是一样的，都需要双方确认，以及提供do和undo操作，以及最终的人工处理。

每次我在遇到不好理解，或者不好解决的问题的时候，都会把这个场景拿到现实生活中找类似的场景，打个比方说吧，就说刚才的订中转机票的场景，现在放到现实中找例子，比如有一个客户需要从订票代理A手里购买航空公司B和航空公司C的票，代理A打电话给B，问票还有么，有的话给自己留一会，如果没有，此次订票失败，代理A再打电话给C问票还有么，有的话给自己留一会，没有的话再回过来告诉A刚才那个票不要了，如果两方都有，就打电话告诉B，票我确定要了，然后再打电话告诉C，票我要了，正常事务就完事了，可是A再最后给C打电话的时候，电话打不通了，联系不上C，那会怎么办，A会一直重试再打几次电话，直到打通为止，正常情况下，不会一直打不通，真遇到了极端情况，C公司系统坏了，票买不了了，航班取消了等等，那也只能有一方赔付事务中断导致的损失，这些永远也无法用一个事务完成的了的，对于前面的正常情况，都是可以用事务来处理。

相关概念

事务，分布式事务 

Read More →

XXE漏洞解决记录

        内网漏洞平台报了一个XXE漏洞，是我们一个服务域名的根路径，刚一看还以为是弄错了，查了一下代码，果然存在这样的跟路径Controller。看了下逻辑，该服务是用于接收微信的事件通知的，微信是以xml格式提交过来的请求，代码中对XML的解析没有做特殊处理，于是乎。。。
        接到工单后，搜了一下xxe漏洞，简单作个了解，原因XML协议中允许引入外部实体声明。这个外部实体的引用就给了不法分子很大的想象空间。外部的实体引用是个url，写成内部文件路径，可以扫描系统任意路径的文件，写成黑各自己服务的路径，可以收集服务器的信息，写成内网服务地址，可以攻击内网服务，再随意更换ip和端口，可以扫描端口等等。小小一个漏洞，可以利用的地方居然这么多，赶紧修复。

先在本地用postman构造注入的xml内容，模拟注入请求，服务B按预期收到了服务A的请求。

SAXReader reader = new SAXReader();
reader.setFeature("http://xml.org/sax/features/external-general-entities", false); 
reader.setFeature("http://xml.org/sax/features/external-parameter-entities", false); 
Document document = reader.read(xml);

加上以上红色的代码后，再次发送注入请求，服务B不再收到服务A的请求。
自测没问题后，开始上线流程，上完线后，自己用微信关注，取关公众号，服务均能正常接收微信上报过来的事件报文，回归完毕。


参考：
https://blog.csdn.net/zhengpeitao/article/details/82142869
https://www.cnblogs.com/r00tuser/p/7255939.html
https://www.jianshu.com/p/77f2181587a4

Read More →

关于redis分布式锁的几个疑问点

我们在分布式场景下，需要用到分布式锁，分布式锁的实现方案可以有redis实现，zk实现等，这里只讨论redis的方案

先稍微铺垫一下两个redis的不成熟方案，

一，

Get，判断是否存在，如存在直接返回失败，不存在继续

Set，设置锁，key对应的value为1，并设置过期时间

Del，业务执行完毕释放锁

code如下：
    private static long expireTime = 20000;

    public static boolean getLock(String key) {
        String lock = RedisUtil.get(key);
        if (!"1".equals(lock)) {
            RedisUtil.set(key, "1");
            RedisUtil.expire(key, expireTime);
            return true;
        } else {
            return false;
        }
    }

    public static void releaseLock(String key) {
        String check = RedisUtil.get(key);
        if (check != null) {
            RedisUtil.del(key);
        }
    }

此方案明显存在的问题就是，多个线程同时请求get，不存在，同时set，所以会有多个线程进入的可能

二，

Setnx，key对应的value为1，判断返回结果，0为设置失败，已经存在key，直接返回失败，1设置成功，继续

Expire，设置过期时间

Del，业务执行完毕释放锁

code如下：
    private static long expireTime = 20000;

    public static boolean getLock(String key) {
        long lock = RedisUtil.setNX(key, "1");
        if (lock == 1) {
            RedisUtil.expire(key, expireTime);
            return true;
        } else {
            return false;
        }
    }

    public static void releaseLock(String key) {
        String check = RedisUtil.get(key);
        if (check != null) {
            RedisUtil.del(key);
        }
    }

此方法，如果在setnx后expire前宕机，那key就不会被删除也没有过期，别的线程永远也进不来了

然后说下目前同事用到的，以及网上找到的比较被认可的解决方案

Setnx，key对应的value为过期时间戳，判断设置结果，1设置成功，返回成功，0设置失败，key存在内容，继续

Get，取出key的值，判断过期，如没过期，返回失败，如已过期，或者key已经不存在了，继续

Getset，设置锁，同时拿到返回值为设置之前的值，判断是否与刚才取出的值相等，如相等，证明是自己设置的，返回成功，如不相等，证明不是自己设置的，返回失败

Del，业务执行完毕释放锁

code如下：
    private static long expireTime = 20000;

    public static boolean getLock(String key) {
        long lock = RedisUtil.setNX(key, "" + System.currentTimeMillis() + expireTime);
        if (lock == 1) {
            return true;
        } else {
            String check = RedisUtil.get(key);
            if (check != null && System.currentTimeMillis() < Long.valueOf(check)) {
                //key还没有过期
                return false;
            } else {
                //key过期或者已经不存在了
                String old = RedisUtil.getSET(key, "" + System.currentTimeMillis() + expireTime);
                if (old == null) {
                    //说明此时已经key已经不存在，获取锁成功
                    return true;
                } else {
                    // TODO 疑问点1，这里同事用的是否过期的判断，会不会存在风险？
                    if (check.equals(old)) {
                        //获取锁成功
                        return true;
                    } else {
                        //在getSET之  前已经被别的线程获取了锁，获取锁失败
                        return false;
                    }
                }
            }
        }
    }

    public static void releaseLock(String key) {
        String check = RedisUtil.get(key);
        if (check != null) {
            if (System.currentTimeMillis() < Long.valueOf(check)) {
                // TODO 疑问点2，有没有可能删除别的线程设置的key
                RedisUtil.del(key);
            } else {
                // TODO 疑问点3，过期了是否需要删除
            }
        } else {
        }
    }

    // TODO 疑问点4，expire正常来说是需要设置成一个业务一定在此时间内能执行完成的时间，那么，业务如果万一没有执行完成的时候，redis锁还安全么？
    // TODO 疑问点5，redis锁真的安全吗，多个线程错综复杂的执行顺序，如何能比较好的理解呢？
    // TODO 疑问点6，这里还有个疑问，是不是理论上每两行代码之间都可能会中断，比如宕机，比如卡死过了很长时间之后继续执行？这个疑问明显的体现出了基础的薄弱

由于没有找到合适的人讨论，所以这里暂时把自己的疑问记录下来，待以后有机会再理解透彻 

Read More →