精华内容
下载资源
问答
  • 垂直拆分和水平拆分

    万次阅读 2017-07-15 22:22:09
    垂直拆分就是要把表按模块划分到不同数据库表中(当然原则还是不破坏第三范式),这种拆分在大型网站的演变过程中是很常见的。当一个网站还在很小的时候,只有小量的人来开发和维护,各模块和表都在一起,当网站不断...

    概念介绍

    垂直拆分

      垂直拆分就是要把表按模块划分到不同数据库表中(当然原则还是不破坏第三范式),这种拆分在大型网站的演变过程中是很常见的。当一个网站还在很小的时候,只有小量的人来开发和维护,各模块和表都在一起,当网站不断丰富和壮大的时候,也会变成多个子系统来支撑,这时就有按模块和功能把表划分出来的需求。其实,相对于垂直切分更进一步的是服务化改造,说得简单就是要把原来强耦合的系统拆分成多个弱耦合的服务,通过服务间的调用来满足业务需求看,因此表拆出来后要通过服务的形式暴露出去,而不是直接调用不同模块的表,淘宝在架构不断演变过程,最重要的一环就是服务化改造,把用户、交易、店铺、宝贝这些核心的概念抽取成独立的服务,也非常有利于进行局部的优化和治理,保障核心模块的稳定性。如下图
    缺点 垂直拆分单表在大数据量的表中依然存在性能瓶颈


    id列1列2列3列4列5列6

    以上的表格进行垂直拆分,会变成一下两个表格(就是个例子,具体还要根据实际情况分析)

    id列1列2列3
    id列4列5列6

    通常会按照一下原则拆分
    1. 把不常⽤的字段单独放在⼀张表;
    2. 把text,blob等⼤字段拆分出来放在附表中;
    3. 经常组合查询的列放在⼀张表中;

    垂直拆分更多时候就应该在数据表设计之初就执⾏的步骤,然后查询的时候⽤jion关键起来即可;
    如果系统过于庞大,拆分的表可以放在不同的数据库中,甚至不同的Server中,怎样划分Server就要根据功能模块和项目实际划分。而有些频繁使用的数据也一定要做读写分离;

    比如微博和阿里。读和写都比较频繁,肯定会做读写分离。
    如果日志信息也放在了数据库中的一张表中,每天近千万条的日志,那么一天表中的数据量就会很大,在做查询或者其他更新数据时,就会很缓慢,那这时就要考虑水平拆分了。

    水平拆分

      上面谈到垂直切分只是把表按模块划分到不同数据库,甚至数据库也分为了不同Server,但没有解决单表大数据量的问题,而水平切分就是要把一个表按照某种规则把数据划分到不同表或数据库里。例如像计费系统和日志系统。通过按时间来划分表就比较合适,因为系统都是处理某一时间段的数据。而像SaaS应用,通过按用户维度来划分数据比较合适,因为用户与用户之间的隔离的,一般不存在处理多个用户数据的情况,简单的按user_id范围来水平切分

    通俗理解:水平拆分行,行数据拆分到不同表中; 垂直拆分列,表数据拆分到不同表中

    id列1列2列3

    一段时间或者满足最初定义的规则后,进行水平拆分,也就进行数据的行拆分,表的结构不发生变化

    id列1列2列3

    拆分原则
    通常情况下,我们使⽤取模的⽅式来进⾏表的拆分;⽐如⼀张有400W的⽤户表users,为提高其查询效率我们把其分成4张表users1,users2,users3,users4 ,通过用id取模的方法把数据分散到四张表内Id%4+1 = [1,2,3,4]然后查询,更新,删除。
    例如:id = 17,17%4 + 1 = 2, $tableName = ‘users’.’2’
    Select * from users2 where id = 17;
    在insert时还需要⼀张临时表uid_temp来提供自增的id,该表的唯⼀⽤处就是提供⾃增的ID;

    insert into uid_temp values(null);

    得到⾃增的ID后,又通过取模法进行分表插⼊;
    注意:进行水平拆分后的表,字段的列和类型和原表保持一致,但是要记得去掉auto_increment自增长。

    另外部分业务逻辑也可以通过地区,年份等字段来进行归档拆分

    进⾏拆分后的表,只能满足部分查询的高效查询需求,这时我们就要在产品策划上,从界⾯上约束用户查询⾏为
    比如我们是按年来进行归档拆分的,这个时候在页⾯设计上就约束⽤户必须要先选择年,然后才能进行查询;
    在做分析或者统计时,由于是自己公司内部工作的需求,多点等待其实是没关系的,并且并发很低,这个时候可以⽤union把所有表都组合成⼀张视图来进⾏查询,然后再进⾏查询;

    使用场景

    垂直与水平联合切分

      由上面可知垂直切分能更清晰化模块划分,区分治理,水平切分能解决大数据量性能瓶颈问题,因此常常就会把两者结合使用,这在大型网站里是种常见的策略

    案例:
    以mysql为例,简单购物系统暂设涉及如下表:
    1. 产品表(数据量10w,稳定)  
    2. 订单表(数据量200w,且有增长趋势)  
    3. 用户表 (数据量100w,且有增长趋势) 
    垂直拆分:
      解决问题: 表与表之间的io竞争
      不解决问题: 单表中数据量增长出现的压力
      方案:

    1. 把产品表和用户表放到一个server上
    2. 订单表单独放到一个server上

    水平拆分:
      解决问题: 单表中数据量增长出现的压力
      不解决问题: 表与表之间的io争夺
      方案:

    1. 用户表通过性别拆分为男用户表和女用户表;   
    2. 订单表通过已完成和完成中拆分为已完成订单和未完成订单;  
    3. 产品表未完成订单放一个server上;   
    4. 已完成订单表盒男用户表放一个server上;   
    5. 根据新用户和老用户,因为新用户相应的活跃度高;
    展开全文
  • 数据库的垂直划分和水平划分

    千次阅读 2014-05-06 09:19:23
    数据库的垂直划分和水平划分 博客分类:  Database 数据结构应用服务器OracleQQ算法 数据库的水平划分和垂直划分很早以前就接触了,只是没有实践,没有什么体会,只有最近两年才有接触,今天也...

    http://liriguang.iteye.com/blog/625309

    数据库的垂直划分和水平划分


    数据库的水平划分和垂直划分很早以前就接触了,只是没有实践,没有什么体会,只有最近两年才有接触,今天也和大家聊聊。


    垂直划分 


    按照功能划分,把数据分别放到不同的数据库和服务器。


    当一个网站开始刚刚创建时,可能只是考虑一天只有几十或者几百个人访问,数据库可能就个db,所有表都放一起,一台普通的服务器可能就够了,而且开发人员也非常高兴,而且信心十足,因为所有的表都在一个库中,这样查询语句就可以随便关联了,多美的一件事情。但是随着访问压力的增加,读写操作不断增加,数据库的压力绝对越来越大,可能接近极限,这时可能人们想到增加从服务器,做什么集群之类的,可是问题又来了,数据量也快速增长。


    这时可以考虑对读写操作进行分离,按照业务把不同的数据放到不同的库中。其实在一个大型而且臃肿的数据库中表和表之间的数据很多是没有关系的,或者更加不需要(join)操作,理论上就应该把他们分别放到不同的服务器。例如用户的收藏夹的数据和博客的数据库就可以放到两个独立的服务器。这个就叫垂直划分(其实叫什么不重要)。


    当博客或者收藏夹的数据不断增加后,应该怎么办,这样就引出了另外一个做法,叫水平划分。

     

    水平划分

     

    则把一个表的数据划分到不同的数据库,两个数据库的表结构一样。怎么划分,应该根据一定的规则,可以根据数据的产生者来做引导,上面的数据是由人产生的,可以根据人的id来划分数据库。然后再根据一定的规则,先获知数据在哪个数据库。

    其实很多大型网站都经历了数据库垂直划分和水平的划分的阶段。其实这个可以根据经验来确定,不一定由某些硬性的规则。

    以刚才的博客为例,数据可以根据userid的奇偶来确定数据的划分。把id为基数的放到A库,为偶数的放B库。




     


    这样通过userId就可以知道用户的博客的数据在哪个数据库。其实可以根据userId%10来处理。还可以根据著名的HASH算法来处理。

     

    当初看手机之家的架构是发现他们是:

    水平切分:对数据进行水平分割。

    a.最好分到同一个数据库。

    b.一种已经证明是切实可行的方案:主表+辅表。

    c.有3种类型:主表不打散、主表打散无辅表、主表打散有辅表。

    d.但对程序员来说,TA看到的只是一张表,不妨称之为虚表(逻辑表)? ,这张虚表实际上可能是由N张实表(物理表)组成的。

     

    哈哈,我还是喜欢把数据分到不同的数据库,这个可以按照业务来和环境来定吧。

     

    在说句题外话,如果是大型数据库,还可以做读写分离等。
     

    展开全文
  • 1. 前言相信你经常被 读写分离、垂直拆分、水平拆分、分库分表 这几个名词搞得很懵逼。我有时候也很懵逼,那么今天就来把这几个数据库常用术语搞清楚,同时也记录一下。2. 读写分离这个相...

    1. 前言

    相信你经常被 读写分离、垂直拆分、水平拆分、分库分表 这几个名词搞得很懵逼。我有时候也很懵逼,那么今天就来把这几个数据库常用术语搞清楚,同时也记录一下。

      

    2. 读写分离

    这个相对比较好理解一些,就是将数据库分为主从库,一个主库(Master)用于写数据,多个从库(Slaver)进行轮询读取数据的过程,主从库之间通过某种通讯机制进行数据的同步,是一种常见的数据库架构。下面这张图就展示了 “一主二从” 的结构:

    2.1 为什么要读写分离

    大多数互联网数据操作往往都是读多写少,随着数据的增长,数据库的“读”会首先成为瓶颈。如果我们希望能线性地提升数据库的读性能和写性能,就需要让读写尽可能的不相互影响,各自为政。

    在使用读写分离之前我们应该考虑使用缓存能不能解决问题。然后再考虑对数据库按照 “读” 和 “写” 进行分组。读写分离意味着将一体的结构的进行分散,在数据量大、高并发的情景中要考虑以下这些问题

    1. 如何保证 Master 的高可用,故障转移,熔断限流等。

    2. 读写操作的区分规则,代码层面如何处理好读命令和写命令,尽量无感知无业务入侵。

    3. 数据一致性的容忍度。虽然是数据同步,但是由于网络的不确定性这仍然是一个不可忽视的问题。


    3. 分库

    数据库垂直拆分、数据库水平拆分 统称 分库。是指按照特定的条条件和维度,将同一个数据库中的数据拆分到多个数据库(主机)上面以达到分散单库(主机)负载的效果。这样我们变相地降低了数据集的大小,以空间换时间来提升性能。

    3.1 数据库垂直拆分

    数据库垂直拆分 指的是按照业务对数据库中的表进行分组,同组的放到一个新的数据库(逻辑上,并非实例)中。需要从实际业务出发将大业务分割成小业务。比如商城的整个业务中的 用户相关表,订单相关表,物流相关表 各自独立分类形成 用户系统数据库,订单系统数据库,物流系统数据库 如下图:

    这样带来了一些好处:(a)业务清晰,职责单一 (b)易维护,易扩展 (c)数据服务化 。

    同时也有一些负面的作用:(a)提高了整个应用的复杂度,而且会形成跨库事务 (b)引发 “木桶效应”,任何一个短板有可能影响整个系统 (c)部分表关系不能 join 只能通过服务相互调用来维系。甚至由于网络问题引发数据不一致。

    在需要进行分库的情况下,通常可优先考虑垂直拆分。

    3.2 数据库水平拆分

    在数据库垂直拆分后遇到单机数据库性能瓶颈之后,就可以考虑数据库水平拆分了。之所以先垂直拆分才水平拆分,是因为垂直拆分后数据业务清晰而且单一,更加方便指定水平的标准。

    比如我们对商城业务垂直拆分后的 用户系统 进行水平拆分就比对整个商城业务进行水平拆分好找维度,我们可以根据用户注册时间的区间、用户的区域或者用户 ID 的范围、 hash 等条件,然后关联相关表的记录将数据进行拆分,如果放在整个商城业务上你是以用户为准还是以订单为准都不太好考虑。

    我们按照每 100 万为区间对用户系统水平拆分如下:

    这种拆分的好处在于:(a)单个库的容量可控 (b)单挑记录保证了数据完整性 (c)数据关系可以通过 join 维持 (d) 避免了跨库事务 ;

    缺点同样存在:(a)拆分规则对编码有一定的影响 (b)不同业务的分区交互需要统筹设计


    4. 分表

    分表也分为 数据表垂直拆分数据表水平拆分

    4.1 数据表垂直拆分

    数据表垂直拆分就是纵向地把表中的列分成多个表,把表从“宽”变“窄”。一般遵循以下几个点进行拆分:

    • 冷热分离,把常用的列放在一个表,不常用的放在一个表。

    • 大字段列独立存放

    • 关联关系的列紧密的放在一起

    我们把用户表中常用的和不常用的而且大字段分离成两张表:

    4.2 数据表的水平拆分

    表的水平拆分感觉跟库的水平拆分思想上都是一样的,只不过粒度不同。表结构维持不变。也就是说拆分后数据集的并集等于拆分前的数据集。理解了 3.2 章节 之后这个就没有什么可说的了。


    5. 总结

    这里简单阐述了几个数据库优化概念,在实际操作中往往会组合使用。我们在实际操作之前要做好数据量的预估,这样能够根据预测未来数据的增量来进行选型。

    业务数据增长较小,常用于表的拆分。增长特别大达到上万级别则可以选择分库,比如一些资金积分流水,历史记录之类的。有些时候并不是拆分完就万事大吉了。

    比如我们按照地区拆分后,A 地区业务增长很快业绩很好,而 B 地区推广不力竞争激烈业绩萧条,造成了数据倾斜。也会影响分库分表的期望效果。

    这需要建立长效的监控预测机制来应对,甚至根据实际情况及时调整策略。数据拆分还面临分布式的很多问题,分布式事务,高可用,数据一致性,全局唯一性都是应该考虑的问题。

    有道无术,术可成;有术无道,止于术

    欢迎大家关注Java之道公众号

    好文章,我在看❤️

    展开全文
  • 设计模式是代码可用性的延伸 设计模式分类:创建型模式,结构型模式,行为型模式 静态代理、JDK动态代理以及CGLIB动态代理 代理模式是java中最常用的设计模式之一,尤其是在spring框架中广泛应用。对于java的代理...

    Java面试总结(2021优化版)已发布在个人微信公众号【技术人成长之路】,优化版首先修正了读者反馈的部分答案存在的错误,同时根据最新面试总结,删除了低频问题,添加了一些常见面试题,对文章进行了精简优化,欢迎大家关注!😊😊

    【技术人成长之路】,助力技术人成长!更多精彩文章第一时间在公众号发布哦!

    Java面试总结汇总,整理了包括Java基础知识,集合容器,并发编程,JVM,常用开源框架Spring,MyBatis,数据库,中间件等,包含了作为一个Java工程师在面试中需要用到或者可能用到的绝大部分知识。欢迎大家阅读,本人见识有限,写的博客难免有错误或者疏忽的地方,还望各位大佬指点,在此表示感激不尽。文章持续更新中…

    序号内容链接地址
    1Java基础知识面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390612
    2Java集合容器面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588551
    3Java异常面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390689
    4并发编程面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104863992
    5JVM面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390752
    6Spring面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397516
    7Spring MVC面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397427
    8Spring Boot面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397299
    9Spring Cloud面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397367
    10MyBatis面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/101292950
    11Redis面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/103522351
    12MySQL数据库面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104778621
    13消息中间件MQ与RabbitMQ面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588612
    14Dubbo面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104390006
    15Linux面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104588679
    16Tomcat面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397665
    17ZooKeeper面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104397719
    18Netty面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/104391081
    19架构设计&分布式&数据结构与算法面试题(2020最新版)https://thinkwon.blog.csdn.net/article/details/105870730

    架构设计

    请列举出在JDK中几个常用的设计模式?

    单例模式(Singleton pattern)用于Runtime,Calendar和其他的一些类中。工厂模式(Factory pattern)被用于各种不可变的类如 Boolean,像Boolean.valueOf,观察者模式(Observer pattern)被用于 Swing 和很多的事件监听中。装饰器设计模式(Decorator design pattern)被用于多个 Java IO 类中。

    什么是设计模式?你是否在你的代码里面使用过任何设计模式?

    设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。设计模式是代码可用性的延伸

    设计模式分类:创建型模式,结构型模式,行为型模式

    静态代理、JDK动态代理以及CGLIB动态代理

    代理模式是java中最常用的设计模式之一,尤其是在spring框架中广泛应用。对于java的代理模式,一般可分为:静态代理、动态代理、以及CGLIB实现动态代理。

    对于上述三种代理模式,分别进行说明。

    静态代理

    静态代理其实就是在程序运行之前,提前写好被代理方法的代理类,编译后运行。在程序运行之前,class已经存在。
    下面我们实现一个静态代理demo:

    img

    定义一个接口Target

    package com.test.proxy;
    
    public interface Target {
    
        public String execute();
    }
    

    TargetImpl 实现接口Target

    package com.test.proxy;
    
    public class TargetImpl implements Target {
    
        @Override
        public String execute() {
            System.out.println("TargetImpl execute!");
            return "execute";
        }
    }
    

    代理类

    package com.test.proxy;
    
    public class Proxy implements Target{
    
        private Target target;
    
        public Proxy(Target target) {
            this.target = target;
        }
    
        @Override
        public String execute() {
            System.out.println("perProcess");
            String result = this.target.execute();
            System.out.println("postProcess");
            return result;
        }
    }
    

    测试类:

    package com.test.proxy;
    
    public class ProxyTest {
    
        public static void main(String[] args) {
    
            Target target = new TargetImpl();
            Proxy p = new Proxy(target);
            String result =  p.execute();
            System.out.println(result);
        }
    
    }
    

    运行结果:

    perProcess
    TargetImpl execute!
    postProcess
    execute
    

    静态代理需要针对被代理的方法提前写好代理类,如果被代理的方法非常多则需要编写很多代码,因此,对于上述缺点,通过动态代理的方式进行了弥补。

    动态代理

    动态代理主要是通过反射机制,在运行时动态生成所需代理的class.

    img

    接口

    package com.test.dynamic;
    
    public interface Target {
    
        public String execute();
    }
    

    实现类

    package com.test.dynamic;
    
    public class TargetImpl implements Target {
    
        @Override
        public String execute() {
            System.out.println("TargetImpl execute!");
            return "execute";
        }
    }
    

    代理类

    package com.test.dynamic;
    
    
    import java.lang.reflect.InvocationHandler;
    import java.lang.reflect.Method;
    
    public class DynamicProxyHandler implements InvocationHandler{
    
        private Target target;
    
        public DynamicProxyHandler(Target target) {
            this.target = target;
        }
    
        @Override
        public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
            System.out.println("========before==========");
            Object result = method.invoke(target,args);
            System.out.println("========after===========");
            return result;
        }
    }
    

    测试类

    package com.test.dynamic;
    
    import java.lang.reflect.Proxy;
    
    public class DynamicProxyTest {
    
        public static void main(String[] args) {
            Target target = new TargetImpl();
            DynamicProxyHandler handler = new DynamicProxyHandler(target);
            Target proxySubject = (Target) Proxy.newProxyInstance(TargetImpl.class.getClassLoader(),TargetImpl.class.getInterfaces(),handler);
            String result = proxySubject.execute();
            System.out.println(result);
        }
    
    }
    

    运行结果:

    ========before==========
    TargetImpl execute!
    ========after===========
    execute
    

    无论是动态代理还是静态带领,都需要定义接口,然后才能实现代理功能。这同样存在局限性,因此,为了解决这个问题,出现了第三种代理方式:cglib代理。

    cglib代理

    CGLib采用了非常底层的字节码技术,其原理是通过字节码技术为一个类创建子类,并在子类中采用方法拦截的技术拦截所有父类方法的调用,顺势织入横切逻辑。JDK动态代理与CGLib动态代理均是实现Spring AOP的基础。

    img

    目标类

    package com.test.cglib;
    
    public class Target {
    
        public String execute() {
            String message = "-----------test------------";
            System.out.println(message);
            return message;
        }
    }
    

    通用代理类

    package com.test.cglib;
    
    import net.sf.cglib.proxy.MethodInterceptor;
    import net.sf.cglib.proxy.MethodProxy;
    
    import java.lang.reflect.Method;
    
    public class MyMethodInterceptor implements MethodInterceptor{
    
        @Override
        public Object intercept(Object obj, Method method, Object[] args, MethodProxy proxy) throws Throwable {
            System.out.println(">>>>MethodInterceptor start...");
            Object result = proxy.invokeSuper(obj,args);
            System.out.println(">>>>MethodInterceptor ending...");
            return "result";
        }
    }
    

    测试类

    package com.test.cglib;
    
    import net.sf.cglib.proxy.Enhancer;
    
    public class CglibTest {
    
        public static void main(String[] args) {
            System.out.println("***************");
            Target target = new Target();
            CglibTest test = new CglibTest();
            Target proxyTarget = (Target) test.createProxy(Target.class);
            String res = proxyTarget.execute();
            System.out.println(res);
        }
    
        public Object createProxy(Class targetClass) {
            Enhancer enhancer = new Enhancer();
            enhancer.setSuperclass(targetClass);
            enhancer.setCallback(new MyMethodInterceptor());
            return enhancer.create();
        }
    
    }
    

    执行结果:

    ***************
    >>>>MethodInterceptor start...
    -----------test------------
    >>>>MethodInterceptor ending...
    result
    

    代理对象的生成过程由Enhancer类实现,大概步骤如下:

    1. 生成代理类Class的二进制字节码;

    2. 通过Class.forName加载二进制字节码,生成Class对象;

    3. 通过反射机制获取实例构造,并初始化代理类对象。

    单例模式

    单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。

    意图:保证一个类仅有一个实例,并提供一个访问它的全局访问点。

    主要解决:一个全局使用的类频繁地创建与销毁。

    懒汉式,线程安全

    代码实例

    public class Singleton2 {
    
        private static Singleton2 instance;
    
        private Singleton2() {}
    
        public static synchronized Singleton2 getInstance() {
            if (instance == null) {
                instance = new Singleton2();
            }
    
            return instance;
        }
    
    }
    

    饿汉式,线程安全

    代码实例

    public class Singleton3 {
    
        private static Singleton3 instance = new Singleton3();
    
        private Singleton3() {}
    
        public static Singleton3 getInstance() {
            return instance;
        }
    
    } 
    

    双检锁/双重校验锁 + volatile关键字

    代码实例

    public class Singleton7 {
    
        private static volatile Singleton7 instance = null;
    
        private Singleton7() {}
    
        public static Singleton7 getInstance() {
            if (instance == null) {
                synchronized (Singleton7.class) {
                    if (instance == null) {
                        instance = new Singleton7();
                    }
                }
            }
    
            return instance;
        }
    
    }
    

    工厂模式

    工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。

    意图:定义一个创建对象的接口,让其子类自己决定实例化哪一个工厂类,工厂模式使其创建过程延迟到子类进行。

    主要解决:主要解决接口选择的问题。

    我们将创建一个 Shape 接口和实现 Shape 接口的实体类。下一步是定义工厂类 ShapeFactory

    FactoryPatternDemo,我们的演示类使用 ShapeFactory 来获取 Shape 对象。它将向 ShapeFactory 传递信息(CIRCLE / RECTANGLE / SQUARE),以便获取它所需对象的类型。

    工厂模式

    步骤 1

    创建一个接口。

    Shape.java

    public interface Shape {
        void draw();
    }
    

    步骤 2

    创建实现接口的实体类。

    Rectangle.java

    public class Rectangle implements Shape {
        @Override
        public void draw() {
            System.out.println("Inside Rectangle::draw() method.");
        }
    }
    

    Square.java

    public class Square implements Shape {
        @Override
        public void draw() {
            System.out.println("Inside Square::draw() method.");
        }
    }
    

    Circle.java

    public class Circle implements Shape {
        @Override
        public void draw() {
            System.out.println("Inside Circle::draw() method.");
        }
    }
    

    步骤 3

    创建一个工厂,生成基于给定信息的实体类的对象。

    ShapeFactory.java

    public class ShapeFactory {
    
        //使用 getShape 方法获取形状类型的对象
        public Shape getShape(String shapeType) {
            if (shapeType == null) {
                return null;
            }
            shapeType = shapeType.toLowerCase();
    
            switch (shapeType) {
                case "circle":
                    return new Circle();
                case "rectangle":
                    return new Rectangle();
                case "square":
                    return new Square();
                default:
                    return null;
            }
    
        }
    
    }
    

    步骤 4

    使用该工厂,通过传递类型信息来获取实体类的对象。

    FactoryPatternDemo.java

    public class FactoryPatternDemo {
    
        public static void main(String[] args) {
            ShapeFactory shapeFactory = new ShapeFactory();
    
            //获取 Circle 的对象,并调用它的 draw 方法
            Shape shape1 = shapeFactory.getShape("CIRCLE");
            //调用 Circle 的 draw 方法
            shape1.draw();
    
            //获取 Rectangle 的对象,并调用它的 draw 方法
            Shape shape2 = shapeFactory.getShape("RECTANGLE");
            //调用 Rectangle 的 draw 方法
            shape2.draw();
    
            //获取 Square 的对象,并调用它的 draw 方法
            Shape shape3 = shapeFactory.getShape("SQUARE");
            //调用 Square 的 draw 方法
            shape3.draw();
        }
    
    }
    

    步骤 5

    验证输出。

    Inside Circle::draw() method.
    Inside Rectangle::draw() method.
    Inside Square::draw() method.
    

    观察者模式

    当对象间存在一对多关系时,则使用观察者模式(Observer Pattern)。比如,当一个对象被修改时,则会自动通知它的依赖对象。观察者模式属于行为型模式。

    意图:定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。

    主要解决:一个对象状态改变给其他对象通知的问题,而且要考虑到易用和低耦合,保证高度的协作。

    实现

    观察者模式使用三个类 Subject、Observer 和 Client。Subject 对象带有绑定观察者到 Client 对象和从 Client 对象解绑观察者的方法。我们创建 Subject 类、Observer 抽象类和扩展了抽象类 Observer 的实体类。

    ObserverPatternDemo,我们的演示类使用 Subject 和实体类对象来演示观察者模式。

    观察者模式

    步骤 1

    创建 Subject 类。

    Subject.java

    public class Subject {
    
        private List<Observer> observers = new ArrayList<>();
    
        private int state;
    
        public int getState() {
            return state;
        }
    
        public void setState(int state) {
            this.state = state;
            notifyAllObservers();
        }
    
        public void attach(Observer observer) {
            observers.add(observer);
        }
    
        public void notifyAllObservers() {
            for (Observer observer : observers) {
                observer.update();
            }
        }
    
    }
    

    步骤 2

    创建 Observer 类。

    Observer.java

    public abstract class Observer {
    
        protected Subject subject;
    
        public abstract void update();
    
    }
    

    步骤 3

    创建实体观察者类。

    BinaryObserver.java

    public class BinaryObserver extends Observer {
    
        public BinaryObserver(Subject subject) {
            this.subject = subject;
            this.subject.attach(this);
        }
    
        @Override
        public void update() {
            System.out.println("Binary String: "
                    + Integer.toBinaryString(subject.getState()));
        }
    
    }
    

    OctalObserver.java

    public class OctalObserver extends Observer {
    
        public OctalObserver(Subject subject){
            this.subject = subject;
            this.subject.attach(this);
        }
    
        @Override
        public void update() {
            System.out.println( "Octal String: "
                    + Integer.toOctalString( subject.getState() ) );
        }
    
    }
    

    HexaObserver.java

    public class HexaObserver extends Observer {
    
        public HexaObserver(Subject subject){
            this.subject = subject;
            this.subject.attach(this);
        }
    
        @Override
        public void update() {
            System.out.println( "Hex String: "
                    + Integer.toHexString( subject.getState() ).toUpperCase() );
        }
    
    }
    

    步骤 4

    使用 Subject 和实体观察者对象。

    ObserverPatternDemo.java

    public class ObserverPatternDemo {
    
        public static void main(String[] args) {
            Subject subject = new Subject();
    
            new BinaryObserver(subject);
            new HexaObserver(subject);
            new OctalObserver(subject);
    
            System.out.println("First state change: 15");
            subject.setState(15);
            System.out.println();
    
            System.out.println("Second state change: 10");
            subject.setState(10);
        }
    
    }
    

    步骤 5

    验证输出。

    First state change: 15
    Binary String: 1111
    Hex String: F
    Octal String: 17
    
    Second state change: 10
    Binary String: 1010
    Hex String: A
    Octal String: 12
    

    装饰器模式

    装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其结构。这种类型的设计模式属于结构型模式,它是作为现有的类的一个包装。

    意图:动态地给一个对象添加一些额外的职责。就增加功能来说,装饰器模式相比生成子类更为灵活。

    主要解决:一般的,我们为了扩展一个类经常使用继承方式实现,由于继承为类引入静态特征,并且随着扩展功能的增多,子类会很膨胀。

    实现

    我们将创建一个 Shape 接口和实现了 Shape 接口的实体类。然后我们创建一个实现了 Shape 接口的抽象装饰类 ShapeDecorator,并把 Shape 对象作为它的实例变量。

    RedShapeDecorator 是实现了 ShapeDecorator 的实体类。

    DecoratorPatternDemo,我们的演示类使用 RedShapeDecorator 来装饰 Shape 对象。

    装饰器模式

    步骤 1

    创建一个接口。

    Shape.java

    public interface Shape {
    
        void draw();
    
    }
    

    步骤 2

    创建实现接口的实体类。

    Rectangle.java

    public class Rectangle implements Shape {
    
        @Override
        public void draw() {
            System.out.println("Shape: Rectangle");
        }
    
    }
    

    Circle.java

    public class Circle implements Shape {
    
        @Override
        public void draw() {
            System.out.println("Shape: Circle");
        }
    
    }
    

    步骤 3

    创建实现了 Shape 接口的抽象装饰类。

    ShapeDecorator.java

    public abstract class ShapeDecorator implements Shape {
    
        protected Shape decoratorShape;
    
        public ShapeDecorator(Shape decoratorShape) {
            this.decoratorShape = decoratorShape;
        }
    
        @Override
        public void draw() {
            decoratorShape.draw();
        }
    }
    

    步骤 4

    创建扩展了 ShapeDecorator 类的实体装饰类。

    RedShapeDecorator.java

    public class RedShapeDecorator extends ShapeDecorator {
    
        public RedShapeDecorator(Shape decoratorShape) {
            super(decoratorShape);
        }
    
        @Override
        public void draw() {
            decoratorShape.draw();
            setRedBorder(decoratorShape);
        }
    
        private void setRedBorder(Shape decoratorShape) {
            System.out.println("Border Color: Red");
        }
    
    }
    

    步骤 5

    使用 RedShapeDecorator 来装饰 Shape 对象。

    DecoratorPatternDemo.java

    public class DecoratorPatternDemo {
    
        public static void main(String[] args) {
            Shape circle = new Circle();
            Shape redCircle = new RedShapeDecorator(new Circle());
            Shape redRectangle = new RedShapeDecorator(new Rectangle());
    
            System.out.println("Circle with normal border");
            circle.draw();
    
            System.out.println("\nCircle of red border");
            redCircle.draw();
    
            System.out.println("\nRectangle of red border");
            redRectangle.draw();
    
        }
    
    }
    

    步骤 6

    验证输出。

    Circle with normal border
    Shape: Circle
    
    Circle of red border
    Shape: Circle
    Border Color: Red
    
    Rectangle of red border
    Shape: Rectangle
    Border Color: Red
    

    秒杀系统设计

    什么是秒杀

    通俗一点讲就是网络商家为促销等目的组织的网上限时抢购活动

    业务特点

    • 高并发:秒杀的特点就是这样时间极短瞬间用户量大

    • 库存量少:一般秒杀活动商品量很少,这就导致了只有极少量用户能成功购买到。

    • 业务简单:流程比较简单,一般都是下订单、扣库存、支付订单

    • 恶意请求,数据库压力大

    解决方案

    前端:页面资源静态化,按钮控制,使用答题校验码可以防止秒杀器的干扰,让更多用户有机会抢到

    nginx:校验恶意请求,转发请求,负载均衡;动静分离,不走tomcat获取静态资源;gzip压缩,减少静态文件传输的体积,节省带宽,提高渲染速度

    业务层:集群,多台机器处理,提高并发能力

    redis:集群保证高可用,持久化数据;分布式锁(悲观锁);缓存热点数据(库存)

    mq:削峰限流,MQ堆积订单,保护订单处理层的负载,Consumer根据自己的消费能力来取Task,实际上下游的压力就可控了。重点做好路由层和MQ的安全

    数据库:读写分离,拆分事务提高并发度

    秒杀系统设计小结

    • 秒杀系统就是一个“三高”系统,即高并发、高性能高可用的分布式系统
    • 秒杀设计原则:前台请求尽量少,后台数据尽量少,调用链路尽量短,尽量不要有单点
    • 秒杀高并发方法:访问拦截、分流、动静分离
    • 秒杀数据方法:减库存策略、热点、异步、限流降级
    • 访问拦截主要思路:通过CDN和缓存技术,尽量把访问拦截在离用户更近的层,尽可能地过滤掉无效请求。
    • 分流主要思路:通过分布式集群技术,多台机器处理,提高并发能力。

    分布式

    分布式概述

    分布式

    分布式(distributed)是为了解决单个物理服务器容量和性能瓶颈问题而采用的优化手段,将一个业务拆分成不同的子业务,分布在不同的机器上执行。服务之间通过远程调用协同工作,对外提供服务。

    该领域需要解决的问题极多,在不同的技术层面上,又包括:分布式缓存、分布式数据库、分布式计算、分布式文件系统等,一些技术如MQ、Redis、zookeeper等都跟分布式有关。

    从理念上讲,分布式的实现有两种形式:

    水平扩展:当一台机器扛不住流量时,就通过添加机器的方式,将流量平分到所有服务器上,所有机器都可以提供 相同的服务;

    垂直拆分:前端有多种查询需求时,一台机器扛不住,可以将不同的业务需求分发到不同的机器上,比如A机器处理余票查询的请求,B机器处理支付的请求。

    集群

    集群(cluster)是指在多台不同的服务器中部署相同应用或服务模块,构成一个集群,通过负载均衡设备对外提供服务。

    两个特点

    可扩展性:集群中的服务节点,可以动态的添加机器,从而增加集群的处理能力。

    高可用性:如果集群某个节点发生故障,这台节点上面运行的服务,可以被其他服务节点接管,从而增强集群的高可用性。

    两大能力

    负载均衡:负载均衡能把任务比较均衡地分布到集群环境下的计算和网络资源。

    集群容错:当我们的系统中用到集群环境,因为各种原因在集群调用失败时,集群容错起到关键性的作用。

    微服务

    微服务就是很小的服务,小到一个服务只对应一个单一的功能,只做一件事。这个服务可以单独部署运行,服务之间通过远程调用协同工作,每个微服务都是由独立的小团队开发,测试,部署,上线,负责它的整个生命周期。

    多线程

    多线程(multi-thread):多线程是指程序中包含多个执行流,即在一个程序中可以同时运行多个不同的线程来执行不同的任务。多线程是为了提高CPU的利用率。

    高并发

    高并发(High Concurrency)是一种系统运行过程中发生了一种“短时间内遇到大量请求”的情况,高并发对应的是访问请求,多线程是解决高并发的方法之一,高并发还可以通过分布式,集群,算法优化,数据库优化等方法解决。

    分布式系统设计理念

    分布式系统的目标与要素

    分布式系统的目标是提升系统的整体性能和吞吐量另外还要尽量保证分布式系统的容错性(假如增加10台服务器才达到单机运行效果2倍左右的性能,那么这个分布式系统就根本没有存在的意义)。

    即使采用了分布式系统,我们也要尽力运用并发编程、高性能网络框架等等手段提升单机上的程序性能。

    分布式系统设计两大思路:中心化和去中心化

    分布式系统设计两大思路:中心化和去中心化

    中心化设计

    • 两个角色: 中心化的设计思想很简单,分布式集群中的节点机器按照角色分工,大体上分为两种角色: “领导”“干活的”
    • 角色职责: “领导”通常负责分发任务并监督“干活的”,发现谁太闲了,就想发设法地给其安排新任务,确保没有一个“干活的”能够偷懒,如果“领导”发现某个“干活的”因为劳累过度而病倒了,则是不会考虑先尝试“医治”他的,而是一脚踢出去,然后把他的任务分给其他人。其中微服务架构 Kubernetes 就恰好采用了这一设计思路。
    • 中心化设计的问题
      1. 中心化的设计存在的最大问题是“领导”的安危问题,如果“领导”出了问题,则群龙无首,整个集群就奔溃了。但我们难以同时安排两个“领导”以避免单点问题。
      2. 中心化设计还存在另外一个潜在的问题,既“领导”的能力问题:可以领导10个人高效工作并不意味着可以领导100个人高效工作,所以如果系统设计和实现得不好,问题就会卡在“领导”身上。
    • 领导安危问题的解决办法: 大多数中心化系统都采用了主备两个“领导”的设计方案,可以是热备或者冷备,也可以是自动切换或者手动切换,而且越来越多的新系统都开始具备自动选举切换“领导”的能力,以提升系统的可用性。

    去中心化设计

    • 众生地位平等: 在去中心化的设计里,通常没有“领导”和“干活的”这两种角色的区分,大家的角色都是一样的,地位是平等的,全球互联网就是一个典型的去中心化的分布式系统,联网的任意节点设备宕机,都只会影响很小范围的功能。
    • “去中心化”不是不要中心,而是由节点来自由选择中心。 (集群的成员会自发的举行“会议”选举新的“领导”主持工作。最典型的案例就是ZooKeeper及Go语言实现的Etcd)
    • 去中心化设计的问题: 去中心化设计里最难解决的一个问题是 “脑裂”问题 ,这种情况的发生概率很低,但影响很大。脑裂指一个集群由于网络的故障,被分为至少两个彼此无法通信的单独集群,此时如果两个集群都各自工作,则可能会产生严重的数据冲突和错误。一般的设计思路是,当集群判断发生了脑裂问题时,规模较小的集群就“自杀”或者拒绝服务。

    分布式与集群的区别是什么?

    • 分布式: 一个业务分拆多个子业务,部署在不同的服务器上
    • 集群: 同一个业务,部署在多个服务器上。比如之前做电商网站搭的redis集群以及solr集群都是属于将redis服务器提供的缓存服务以及solr服务器提供的搜索服务部署在多个服务器上以提高系统性能、并发量解决海量存储问题。

    CAP定理

    CAP定理

    在理论计算机科学中,CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer’s theorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:

    选项描述
    Consistency(一致性)指数据在多个副本之间能够保持一致的特性(严格的一致性)
    Availability(可用性)指系统提供的服务必须一直处于可用的状态,每次请求都能获取到非错的响应(不保证获取的数据为最新数据)
    Partition tolerance(分区容错性)分布式系统在遇到任何网络分区故障的时候,仍然能够对外提供满足一致性和可用性的服务,除非整个网络环境都发生了故障

    Spring Cloud在CAP法则上主要满足的是A和P法则,Dubbo和Zookeeper在CAP法则主要满足的是C和P法则

    CAP仅适用于原子读写的NOSQL场景中,并不适合数据库系统。现在的分布式系统具有更多特性比如扩展性、可用性等等,在进行系统设计和开发时,我们不应该仅仅局限在CAP问题上。

    注意:不是所谓的3选2(不要被网上大多数文章误导了)

    现实生活中,大部分人解释这一定律时,常常简单的表述为:“一致性、可用性、分区容忍性三者你只能同时达到其中两个,不可能同时达到”。实际上这是一个非常具有误导性质的说法,而且在CAP理论诞生12年之后,CAP之父也在2012年重写了之前的论文。

    当发生网络分区的时候,如果我们要继续服务,那么强一致性和可用性只能2选1。也就是说当网络分区之后P是前提,决定了P之后才有C和A的选择。也就是说分区容错性(Partition tolerance)我们是必须要实现的。

    CAP定理的证明

    关于CAP这三个特性我们就介绍完了,接下来我们试着证明一下为什么CAP不能同时满足

    img

    为了简化证明的过程,我们假设整个集群里只有两个N1和N2两个节点,如下图:

    N1和N2当中各自有一个应用程序AB和数据库,当系统满足一致性的时候,我们认为N1和N2数据库中的数据保持一致。在满足可用性的时候,我们认为无论用户访问N1还是N2,都可以获得正确的结果,在满足分区容错性的时候,我们认为无论N1还是N2宕机或者是两者的通信中断,都不影响系统的运行。

    我们假设一种极端情况,假设某个时刻N1和N2之间的网络通信突然中断了。如果系统满足分区容错性,那么显然可以支持这种异常。问题是在此前提下,一致性和可用性是否可以做到不受影响呢?

    我们做个假象实验,如下图,突然某一时刻N1和N2之间的关联断开:

    img

    有用户向N1发送了请求更改了数据,将数据库从V0更新成了V1。由于网络断开,所以N2数据库依然是V0,如果这个时候有一个请求发给了N2,但是N2并没有办法可以直接给出最新的结果V1,这个时候该怎么办呢?

    这个时候无法两种方法,一种是将错就错,将错误的V0数据返回给用户。第二种是阻塞等待,等待网络通信恢复,N2中的数据更新之后再返回给用户。显然前者牺牲了一致性,后者牺牲了可用性。

    这个例子虽然简单,但是说明的内容却很重要。在分布式系统当中,CAP三个特性我们是无法同时满足的,必然要舍弃一个。三者舍弃一个,显然排列组合一共有三种可能。

    BASE理论

    BASE理论由eBay架构师Dan Pritchett提出,在2008年上被分表为论文,并且eBay给出了他们在实践中总结的基于BASE理论的一套新的分布式事务解决方案。

    BASEBasically Available(基本可用)Soft-state(软状态)Eventually Consistent(最终一致性) 三个短语的缩写。BASE理论是对CAP中一致性和可用性权衡的结果,其来源于对大规模互联网系统分布式实践的总结,是基于CAP定理逐步演化而来的,它大大降低了我们对系统的要求。

    BASE理论的核心思想

    即使无法做到强一致性,但每个应用都可以根据自身业务特点,采用适当的方式来使系统达到最终一致性。也就是牺牲数据的一致性来满足系统的高可用性,系统中一部分数据不可用或者不一致时,仍需要保持系统整体“主要可用”。

    针对数据库领域,BASE思想的主要实现是对业务数据进行拆分,让不同的数据分布在不同的机器上,以提升系统的可用性,当前主要有以下两种做法:

    • 按功能划分数据库
    • 分片(如开源的Mycat、Amoeba等)。

    由于拆分后会涉及分布式事务问题,所以eBay在该BASE论文中提到了如何用最终一致性的思路来实现高性能的分布式事务。

    BASE理论三要素

    BASE理论三要素

    1. 基本可用

    基本可用是指分布式系统在出现不可预知故障的时候,允许损失部分可用性。但是,这绝不等价于系统不可用。

    比如:

    • 响应时间上的损失:正常情况下,一个在线搜索引擎需要在0.5秒之内返回给用户相应的查询结果,但由于出现故障,查询结果的响应时间增加了1~2秒
    • 系统功能上的损失:正常情况下,在一个电子商务网站上进行购物的时候,消费者几乎能够顺利完成每一笔订单,但是在一些节日大促购物高峰的时候,由于消费者的购物行为激增,为了保护购物系统的稳定性,部分消费者可能会被引导到一个降级页面
    2. 软状态

    软状态指允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时

    3. 最终一致性

    最终一致性强调的是系统中所有的数据副本,在经过一段时间的同步后,最终能够达到一个一致的状态。因此,最终一致性的本质是需要系统保证最终数据能够达到一致,而不需要实时保证系统数据的强一致性。

    数据结构与算法

    冒泡排序

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,依次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    算法描述

    • 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    • 针对所有的元素重复以上的步骤,除了最后一个;
    • 重复步骤1~3,直到排序完成。

    动图演示

    冒泡排序

    代码实现

    下面的排序算法统一使用的测试代码如下,源码GitHub链接

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    	// 只需要修改成对应的方法名就可以了
        bubbleSort(array);
    
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * Description:冒泡排序
     *
     * @param array 需要排序的数组
     * @author JourWon
     * @date 2019/7/11 9:54
     */
    public static void bubbleSort(int[] array) {
    	if (array == null || array.length <= 1) {
    		return;
    	}
    
    	int length = array.length;
    
    	// 外层循环控制比较轮数i
    	for (int i = 0; i < length; i++) {
    		// 内层循环控制每一轮比较次数,每进行一轮排序都会找出一个较大值
    		// (array.length - 1)防止索引越界,(array.length - 1 - i)减少比较次数
    		for (int j = 0; j < length - 1 - i; j++) {
    			// 前面的数大于后面的数就进行交换
    			if (array[j] > array[j + 1]) {
    				int temp = array[j + 1];
    				array[j + 1] = array[j];
    				array[j] = temp;
    			}
    		}
    	}
    
    }
    

    算法分析

    最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

    选择排序

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

    选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    算法描述

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

    • 初始状态:无序区为R[1…n],有序区为空;
    • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1…i-1]和R(i…n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
    • n-1趟结束,数组有序化了。

    动图演示

    选择排序

    代码实现

    下面的排序算法统一使用的测试代码如下,源码GitHub链接

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    	// 只需要修改成对应的方法名就可以了
        selectionSort(array);
    
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * Description: 选择排序
     *
     * @param array
     * @return void
     * @author JourWon
     * @date 2019/7/11 23:31
     */
    public static void selectionSort(int[] array) {
    	if (array == null || array.length <= 1) {
    		return;
    	}
    
    	int length = array.length;
    
    	for (int i = 0; i < length - 1; i++) {
    		// 保存最小数的索引
    		int minIndex = i;
    
    		for (int j = i + 1; j < length; j++) {
    			// 找到最小的数
    			if (array[j] < array[minIndex]) {
    				minIndex = j;
    			}
    		}
    
    		// 交换元素位置
    		if (i != minIndex) {
    			swap(array, minIndex, i);
    		}
    	}
    
    }
    
    /**
     * Description: 交换元素位置
     *
     * @param array
     * @param a
     * @param b
     * @return void
     * @author JourWon
     * @date 2019/7/11 17:57
     */
    private static void swap(int[] array, int a, int b) {
    	int temp = array[a];
    	array[a] = array[b];
    	array[b] = temp;
    }
    

    算法分析

    最佳情况:T(n) = O(n2) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

    快速排序

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    算法描述

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    • 从数列中挑出一个元素,称为 “基准”(pivot);
    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    动图演示

    快速排序

    代码实现

    下面的排序算法统一使用的测试代码如下,源码GitHub链接

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    	// 只需要修改成对应的方法名就可以了
        quickSort(array);
    
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * Description: 快速排序
     *
     * @param array
     * @return void
     * @author JourWon
     * @date 2019/7/11 23:39
     */
    public static void quickSort(int[] array) {
    	quickSort(array, 0, array.length - 1);
    }
    
    
    private static void quickSort(int[] array, int left, int right) {
    	if (array == null || left >= right || array.length <= 1) {
    		return;
    	}
    	int mid = partition(array, left, right);
    	quickSort(array, left, mid);
    	quickSort(array, mid + 1, right);
    }
    
    
    private static int partition(int[] array, int left, int right) {
    	int temp = array[left];
    	while (right > left) {
    		// 先判断基准数和后面的数依次比较
    		while (temp <= array[right] && left < right) {
    			--right;
    		}
    		// 当基准数大于了 arr[left],则填坑
    		if (left < right) {
    			array[left] = array[right];
    			++left;
    		}
    		// 现在是 arr[right] 需要填坑了
    		while (temp >= array[left] && left < right) {
    			++left;
    		}
    		if (left < right) {
    			array[right] = array[left];
    			--right;
    		}
    	}
    	array[left] = temp;
    	return left;
    }
    

    算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn)

    递归

    什么叫递归

    递归函数就是直接或间接调用自身的函数,也就是自身调用自己。

    一般什么时候使用递归?

    递归是常用的编程技术,其基本思想就是“自己调用自己”,一个使用递归技术的方法即是直接或间接的调用自身的方法。递归方法实际上体现了“以此类推”、“用同样的步骤重复”这样的思想。

    还有些数据结构如二叉树,结构本身固有递归特性;此外,有一类问题,其本身没有明显的递归结构,但用递归程序求解比其他方法更容易编写程序。

    需满足的两个条件

    1. 有反复执行的过程(调用自身)
    2. 有跳出反复执行过程的条件(递归出口)

    经典问题:阶乘

    递归阶乘n! = n * (n-1) * (n-2) * ...* 1(n>0)
    
    public static Integer recursionMulity(Integer n) {
        if (n == 1) {
            return 1;
        }
        return n * recursionMulity(n - 1);
    }
    

    经典问题:不死神兔(斐波那契数列)

    3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

    分析:首先我们要明白题目的意思指的是每个月的兔子总对数;假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子,

    那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1、0、0,第二个月分别为0、1、0,

    第三个月分别为1、0、1,第四个月分别为,1、1、1,第五个月分别为2、1、2,第六个月分别为3、2、3,第七个月分别为5、3、5……

    兔子总数分别为:1、1、2、3、5、8、13……

    于是得出了一个规律,从第三个月起,后面的兔子总数都等于前面两个月的兔子总数之和,即为斐波那契数列。

    public static int fib(int mon) {
        if (mon < 2) {
            return 1;
        } else {
            return fib(mon - 1) + fib(mon - 2);
        }
    }
    

    二分查找

    在数组[130,150,170,190,210,230,250,270,290,310]中查找数字190,红色为二分线(折半线),灰色为查找区域,黑色为排除区域。

    img二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法,前提是数据结构必须先排好序,时间复杂度可以表示O(h)=O(log2n),以2为底,n的对数。其缺点是要求待查表为有序表,且插入删除困难。

    左加右不加,找右缩左,找左缩右

    public class BinarySearch {
        public static void main(String[] args) {
            int[] arr = {5, 12, 23, 43, 66, 98, 100};
            System.out.println(binarySort(arr, 23));
        }
    
        /**
         * 循环实现二分查找
         *
         * @param arr
         * @param key
         * @return
         */
        public static int binarySearch(int[] arr, int key) {
            //第一个下标
            int low = 0;
            //最后一个下标
            int high = arr.length - 1;
            int mid = 0;
            //防越界
            if (key < arr[low] || key > arr[high] || low > high) {
                return -1;
            }
            while (low <= high) {
                mid = (low + high) >>> 1;
                if (key < arr[mid]) {
                    high = mid - 1;
                } else if (key > arr[mid]) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    }
    

    二分查找中中间值的计算

    这是一个经典的话题,如何计算二分查找中的中值?大家一般给出了两种计算方法:

    • 算法一: mid = (low + high) / 2
    • 算法二: mid = low + (high – low)/2

    乍看起来,算法一简洁,算法二提取之后,跟算法一没有什么区别。但是实际上,区别是存在的。算法一的做法,在极端情况下,(low + high)存在着溢出的风险,进而得到错误的mid结果,导致程序错误。而算法二能够保证计算出来的mid,一定大于low,小于high,不存在溢出的问题。

    一致性Hash算法

    概述

    一致性Hash是一种特殊的Hash算法,由于其均衡性、持久性的映射特点,被广泛的应用于负载均衡领域和分布式存储,如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。

    普通的Hash函数最大的作用是散列,或者说是将一系列在形式上具有相似性质的数据,打散成随机的、均匀分布的数据。不难发现,这样的Hash只要集群的数量N发生变化,之前的所有Hash映射就会全部失效。如果集群中的每个机器提供的服务没有差别,倒不会产生什么影响,但对于分布式缓存这样的系统而言,映射全部失效就意味着之前的缓存全部失效,后果将会是灾难性的。一致性Hash通过构建环状的Hash空间代替线性Hash空间的方法解决了这个问题。

    良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面:

    • 平衡性(Balance)

    平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

    • 单调性(Monotonicity)

    单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

    • 分散性(Spread)

    在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    • 负载(Load)

    负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    • 平滑性(Smoothness)

    平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

    一致性Hash算法原理

    简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-232-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:整个空间按顺时针方向组织。0和232-1在零点中方向重合。

    下一步将各个服务器使用Hash进行一次哈希,具体可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下:

    接下来使用如下算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。

    例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:

    根据一致性哈希算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

    下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

    下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:

    此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X 。一般的,在一致性哈希算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

    综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

    Java代码实现

    public class ConsistentHash<T> {
    
        /**
         * 节点的复制因子,实际节点个数 * numberOfReplicas = 虚拟节点个数
         */
        private final int numberOfReplicas;
        /**
         * 存储虚拟节点的hash值到真实节点的映射
         */
        private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
    
        public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
            this.numberOfReplicas = numberOfReplicas;
            for (T node : nodes) {
                add(node);
            }
        }
    
        public void add(T node) {
            for (int i = 0; i < numberOfReplicas; i++) {
                // 对于一个实际机器节点 node, 对应 numberOfReplicas 个虚拟节点
                /*
                 * 不同的虚拟节点(i不同)有不同的hash值,但都对应同一个实际机器node
                 * 虚拟node一般是均衡分布在环上的,数据存储在顺时针方向的虚拟node上
                 */
                String nodestr = node.toString() + i;
                int hashcode = nodestr.hashCode();
                System.out.println("hashcode:" + hashcode);
                circle.put(hashcode, node);
    
            }
        }
    
        public void remove(T node) {
            for (int i = 0; i < numberOfReplicas; i++) {
                circle.remove((node.toString() + i).hashCode());
            }
        }
    
    
        /**
         * 获得一个最近的顺时针节点,根据给定的key 取Hash
         * 然后再取得顺时针方向上最近的一个虚拟节点对应的实际节点
         * 再从实际节点中取得 数据
         *
         * @param key
         * @return
         */
        public T get(Object key) {
            if (circle.isEmpty()) {
                return null;
            }
            // node 用String来表示,获得node在哈希环中的hashCode
            int hash = key.hashCode();
            System.out.println("hashcode----->:" + hash);
            //数据映射在两台虚拟机器所在环之间,就需要按顺时针方向寻找机器
            if (!circle.containsKey(hash)) {
                SortedMap<Integer, T> tailMap = circle.tailMap(hash);
                hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
            }
            return circle.get(hash);
        }
    
        public long getSize() {
            return circle.size();
        }
    
        /**
         * 查看表示整个哈希环中各个虚拟节点位置
         */
        public void testBalance() {
            //获得TreeMap中所有的Key
            Set<Integer> sets = circle.keySet();
            //将获得的Key集合排序
            SortedSet<Integer> sortedSets = new TreeSet<Integer>(sets);
            for (Integer hashCode : sortedSets) {
                System.out.println(hashCode);
            }
    
            System.out.println("----each location 's distance are follows: ----");
            /*
             * 查看相邻两个hashCode的差值
             */
            Iterator<Integer> it = sortedSets.iterator();
            Iterator<Integer> it2 = sortedSets.iterator();
            if (it2.hasNext()) {
                it2.next();
            }
            long keyPre, keyAfter;
            while (it.hasNext() && it2.hasNext()) {
                keyPre = it.next();
                keyAfter = it2.next();
                System.out.println(keyAfter - keyPre);
            }
        }
    
        public static void main(String[] args) {
            Set<String> nodes = new HashSet<String>();
            nodes.add("A");
            nodes.add("B");
            nodes.add("C");
    
            ConsistentHash<String> consistentHash = new ConsistentHash<String>(2, nodes);
            consistentHash.add("D");
    
            System.out.println("hash circle size: " + consistentHash.getSize());
            System.out.println("location of each node are follows: ");
            consistentHash.testBalance();
    
            String node = consistentHash.get("apple");
            System.out.println("node----------->:" + node);
        }
    
    }
    
    展开全文
  • 数据库水平扩展和垂直扩展

    千次阅读 2018-03-12 16:03:24
    详细什么是数据库的水平扩展和垂直扩展呢?我们以以下的样例来说明。    比方我们如今有两个表:用户信息表 产品订单表  水平的拆分的方案,即不改动数据库表结构。通过对表中数据的拆分而达到分片的目的: 1)...
  • 数据库水平扩展与垂直扩展

    千次阅读 2018-05-25 17:40:10
    一般我们把sharding机制分成水平扩展(横向扩展,或者向外扩展)和垂直扩展两种方式。 详细什么是数据库的水平扩展和垂直扩展呢?我们以以下的样例来说明。 比方我们如今有两个表:用户信息表 产品订单表 水平的拆分...
  • 数据库的水平扩展与垂直扩展

    万次阅读 2014-10-31 17:41:53
    数据库水平扩展与垂直扩展  在互联网应用中,数据库经常是我们存储和访问数据的常用介质。随着负载的增大,对数据库读写性能的要求往往成为很大的挑战。在这种情况下我们可以考虑数据库相关的replication机制提高...
  • 结构张量(structure tensor)

    千次阅读 2018-11-07 19:32:24
    在数学中,结构张量(也称为第二矩矩阵)是从函数的梯度导出的矩阵。它总结了一个点的指定邻域中梯度的主要...Ix,Iy分别表示图像的水平梯度与垂直梯度。而后分别用K与H表示矩阵ST的行列式与迹。 根据所求的K与H...
  • 相信你经常被读写分离、垂直拆分、水平拆分、分库分表这几个名词搞得很懵逼。我有时候也很懵逼,那么今天就来把这几个数据库常用术语搞清楚,同时也记录一下。 2. 读写分离 这个相对比较好理解一些,就是将数据库...
  • 高并发(水平扩展,垂直扩展)

    千次阅读 2018-10-31 10:56:50
    互联网分布式架构设计,提高系统并发能力的方式,方法论上主要有两种:垂直扩展(Scale Up)与水平扩展(Scale Out)。 垂直扩展 :提升单机处理能力。垂直扩展的方式又有两种: (1)增强单机硬件性能,例如...
  • 图像形态学操作时候,可以通过自定义的结构元素实现结构元素 对输入图像一些对象敏感、另外一些对象不敏感,这样就会让敏 感的对象改变而不敏感的对象保留输出。通过使用两个最基本的 形态学操作 – 膨胀与...
  • 垂直布局的HTML表单

    千次阅读 2018-02-23 22:01:51
    垂直布局的表单对于比较复杂的表单,要填写的内容相对较多,采用水平布局显然不合适。因此,垂直布局的表单更加常用。垂直对齐的表单中,标签和输入框可以使用三种对齐方式,包括顶对齐、左对齐和右对齐。CSS 顶对齐...
  • 商品表结构分析

    千次阅读 2019-05-26 10:07:52
    文章目录引言表结构分析 引言 先引入两个概念: SPU:Standard Product Unit (标准产品单位) ,一组具有共同属性的商品集 SKU:Stock Keeping Unit(库存量单位),SPU商品集因具体特性不同而细分的每个商品 ...
  •  2)与图像的水平垂直梯度有关,定义如下: 在MATLAB中,可以用如下语句求解:[Ix,Iy]=gradient(Image); 3)求出结构张量矩阵的行列式,和迹(矩阵对角线之和)  行列式:K=det(E);  迹:
  • 商品规格数据结构与商品表结构分析:1. 商品规格数据结构1.1 规格属性内容1.2 横表与数表1.3 表结构1.3.1 SpecGroup规格组1.3.2 SpecParam规格参数1.4 从面向对象的角度分析2. 商品表结构分析2.1 SPU和SKU2.2 表结构...
  • 结构化 VS 非结构

    千次阅读 2016-01-25 17:25:33
    如果说结构化信息更多的忠实、详实地记录了企业的生产交易活动,是显性的表示,那么 非结构化信息则隐性包含了掌握着企业命脉的关键,隐含着许多提高企业效益的机会。 非结构化数据 ...
  • 标准BT.656并行数据结构

    千次阅读 2012-09-26 17:15:12
    BT.656并行接口除了...其中,23~311行是偶数场视频数据,336~624行是奇数场视频数据,其余为垂直控制信号。 BT.656每行的数据结构如图4所示。 图4中,每行数据包含水平控制信号和YC
  • 与机器学习算法有关的数据结构

    千次阅读 2018-03-26 17:07:13
    摘要:在机器学习中需要运用到许多数据结构,掌握它们是非常重要的。希望本文能有所帮助拥有机器学习技能是不够的。你还需要良好的数据结构的工作知识。学习更多,并解决一些问题。因此,你已经决定不再使用固定的...
  • 标准BT.656并行数据结构

    千次阅读 2009-04-23 10:43:00
    标准BT.656并行数据结构 BT.656并行接口除了传输4:2:2的YCbCr视频数据流外,还有行、列同步...其中,23~311行是偶数场视频数据,336~624行是奇数场视频数据,其余为垂直控制信号。BT.656每行的数据结构如图4所示。
  • 基于格雷码+相移方案的结构光重建解析

    千次阅读 热门讨论 2019-12-29 17:52:32
    由于前段时间一直处在算法的应用开发阶段,长时间将心思花在硬件选型、原型机设计、原型机搭建和联调等上面,没有抽足够的时间来记录相关算法的开发经历,年底...整个文章将以双目结构光为基础,内容包括以下几个部...
  • 数据库表结构设计

    千次阅读 2015-10-15 11:01:30
     理解基本表的性质后,在设计数据库时,就能将基本表与中间表、临时表区分开来。  4. 范式标准   基本表及其字段之间的关系, 应尽量满足第三范式。但是,满足第三范式的数据库设计,往往不是最好的设计...
  • 图像 结构张量(structure tensor)

    万次阅读 2018-05-15 21:34:30
    此处的张量就是一个关于图像的结构矩阵,矩阵结构构成如下:Rx,Ry分别为图像的水平垂直梯度,而后进行求矩阵T的行列式K与迹(trace)H。根据K与H的关系来求得区分图像的平坦、边缘与角点区域:平坦区域:H=0;边缘...
  • 插件体系结构软件开发方法研究

    千次阅读 2011-01-01 00:31:00
    本文首先分析了插件式体系结构软件的结构和工作原理,详细地对插件系统的设计思想,开发中的原则、建议、技术方法以及可行性进行了总体的细致深入的分析。SharpDevelop是采用微软.NET技术基于插件树体系结构开发的...
  • 深度相机(二)--结构光深度测距

    万次阅读 多人点赞 2016-09-09 13:47:35
    原文: http://blog.sina.com.cn/s/blog_80ce3a550100wg5j.html http://blog.csdn.net/u013360881/article/details/51395427 ... 结构光编码: 在3D 的深度获取上,最为常见的方法是类似于双目匹配获取深度...
  • IRP和IO_STACK_LOCATION结构

    千次阅读 2011-12-27 18:03:11
    图5-1显示了IRP的数据结构,阴影部分代表不透明域。下面是该结构中重要域的简要描述。 MdlAddress(PMDL)域指向一个内存描述符表(MDL),该表描述了一个 与该请求关联的用户模式缓冲区。如果顶级设备对象的Flags域...
  • 此文章详细完整的介绍了位图的存储结构,详细读完此文你一定收获颇丰的.
  • MySQL性能优化四之数据库结构优化

    千次阅读 2016-08-29 12:12:41
    5.表的水平拆分(为了解决数据表中数据过大的问题,水平拆分每一个表的结构都是完全一致的) 5.1. 如何将数据平分到 N 张表中的常用方法: 1) 对 ID 进行 hash 运算,如果要拆分成 5 个表, mod(id,5) 取出 0...
  • 为什么选择分布式垂直架构

    千次阅读 2017-11-03 10:58:32
     在我们开始开发otto.de网上商店时,我们选择了分布式垂直架构。之前的工作经验告诉我们,一体化架构(monolithic architecture)不能够满足不断增长的需求。爆发式增长的数据,持续提高的负载和对系统的扩展,所有的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,615
精华内容 10,646
关键字:

区分垂直结构水平结构