虫虫的技术博客 技术 生活

Tuesday, April 30, 2019

面试基础-插入排序

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

测试输入: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

Monday, April 29, 2019

面试基础-冒泡排序

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

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

测试输入: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

Friday, April 19, 2019

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

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

图片来自百度

死锁产生的条件
1,资源互斥,资源同时只能被有限的线程占有
2,阻塞不释放,线程申请资源阻塞后,不释放已经持有的资源
3,不可剥夺,线程持有的资源,是不能被其它线程剥夺的,只能由自己使用完了释放
4,循环等待,存在一个资源等待环,

死锁会导致资源无法释放,系统hang住,这毕竟是我们不想看到的现象
在死锁产生之前,我们需预防和避免,主要思想就是破坏产生的条件,下面针对四个条件分别进行破坏~
1,资源互斥,如果资源是可以被无限共享和使用的,那也就不存在死锁的问题了
2,线程申请资源阻塞后,释放已经持有的资源,线程返回失败
3,线程按优先级排序,优先级高的线程可以剥夺优先级低的线程持有的资源
4,申请资源的时候检测,如果此次申请如果能产生环路,则取消此次申请
其它方案
5,一次性请求所有资源
6,资源编号,按顺序申请使用
7,超时释放重试
实际方案中,应该是没有针对剥夺与资源互斥上面下手的

在死锁产生之后,我们需要处理后续的问题
1,检测死锁,终止死锁等待环中的节点
2,重启进程

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

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

Wednesday, April 10, 2019

分布式事务梳理

分布式事务目前流行的方案也有很多种,网上能找到大把的技术文章,但看人家的文章总是有各种问题,要么某些地方不好理解,要么某些地方认为不正确,还是按自己的视角来梳理一下。
目前看到的方案,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公司系统坏了,票买不了了,航班取消了等等,那也只能有一方赔付事务中断导致的损失,这些永远也无法用一个事务完成的了的,对于前面的正常情况,都是可以用事务来处理。

相关概念

事务,分布式事务 

Popular Posts

Copyright © 虫虫的成长历程 | Powered by Blogger Design by PWT | Blogger Theme by NewBloggerThemes.com