CreateArtTechnology / Blog
  • 布隆过滤器简介
     7     2019-12-26 21:02:33

    背景遇见一道算法题:
    从一个未排序的整数数组,找出其中没有出现过的最小的正整数。
    要求:时间复杂度为O(n),使用常数级别的额外空间。
    根据题目要求,
    时间复杂度为O(n),说明不允许排序,不允许多重循环,只允许常数次单层循环;常数级别的额外空间,说明不允许使用HashSet、HashMap这样的容器进行统计;没说数组长度有多少,猜测是非常长。
    犯难了,想不出怎么解,关键是常数额外空间。于是想使用指定长度的布隆过滤器,也算常数额外空间对吧?(当然这个解法并不好使)
    ......

    共4张

  • 分布式CAP定理和BASE定理
     7     2019-05-24 16:26:22

    CAP定理目前的大型网站系统几乎都是分布式的,而分布式系统难以实现整个系统的强一致性。1998年,加州大学的计算机科学家 Eric Brewer 提出,分布式系统有三个指标:
    Consistency 一致性Availability 可用性Partition Tolerance 分区容错
    Eric Brewer表示这三个指标不可能同时做到。这个结论就叫做 CAP 定理。原文见参考资料,有图解。
    C 一致性一致性指标要求用户的读写操作始终正确,即写入的数据在读出来时与写入时一致。可以理解为主库写入从库读出时需要保证从库已同步主库数据。
    A 可用性可用性指标要求每个正常请求必须有正常的响应,不可忽略。可以理解为像主库从库请求,都得返回正常响应。
    P 分区容错由于分布式系统的特性,服务器间的通信可能出现异常,分区容错指标需要兼容这种异常情况。可以理解为主从库网络断连,要兼容主库写入而从从库读的情况。
    ......


  • 数据库事务的ACID特性Atomic 原子性组成事务的操作不可分割,只有全部执行成功才提交,任何一部分操作失败都必须将整个事务回滚。即事务里的每个操作,要么都发生,要么都不发生。
    Consistency 一致性数据库宗师从一个一致性的状态转换到另一个一致性的状态。即不应该出现异常数据。
    Isolation 隔离性多个事务执行时,一个事务在最终提交之前对其他事务“通常来说”是不可见的。一般而言,完全保证隔离性会影响性能,因而有些数据库在处理隔离性时有所妥协,对事务的隔离性分级,不同的隔离级别会引起脏读、不可重复读、幻读等问题,后续介绍。
    Durability 持久性执行结果持久化保存,可故障恢复,但不再回滚。
    事务隔离级别不同产生的影响脏读一个事务读取到另一事务未提交的更新新据。当一个事务正在访问数据,并且对数据进行了修改,而这种修改还没有提交到数据库中,这时,另外一个事务也访问这个数据,然后使用了这个数据。因为这个数据是还没有提交的数据,那么另外一个事务读到的这个数据是脏数据,依据脏数据所做的操作也可能是不正确的。关键:读到未提交的错误数据。
    读到错误数据
    ......

    共3张


  • 背景当数据计算或数据查询代价较大,或数据可以反复重用时,缓存当前数据通常是一个很好的选择。缓存系统的设计目标通常为以下几点:
    通过复用数据降低计算或查询的响应时间,提高吞吐量降低后方存储的负载压力在写入操作与实际存储之间增加缓存,使得系统解耦,削峰填谷存在冷热数据区别时,缓存热数据降低整个系统的响应时间
    考虑到大多数情况下缓存是用在读远多于写的场景下,那么还需要考虑以下问题:
    一般使用内存作为缓存(也有使用SSD的,如360的 PIKA),相较于硬盘读写速度更快,容量更小,成本更高,无法保存所有数据(其实也没必要)缓存内容需要初始化,一般来说数据从后方存储中读取并设置到缓存中很多数据是会变化的,也就是说缓存会失效,需要定期更新
    穿透、雪崩、击穿由于以上特点,流量大的缓存系统在设计时需要注意缓存失效或更新产生的问题。
    缓存穿透出现恶意攻击(其实也有可能是bug),访问缓存和后方存储中不存在的数据,每次请求都会达到后方存储,导致存储负载增高或挂掉。
    ......

    共4张

  • 分支预测简介
     9     2019-05-05 17:07:49

    什么是分支预测现象描述java - Why is it faster to process a sorted array than an unsorted array? - Stack OverflowStackOverflow上的一个问题描述:下边这段代码是用来对一大批数据求和的。由于只是逐项求和,本来不需要排序,但是原提问者发现排序前后程序运行时间差距非常大。
    import java.util.Arrays;
    import java.util.Random;
    public class Main
    {
    public static void main(String[] args)
    ......


  • 粘包问题简介
     8     2019-04-26 14:56:59

    TCP粘包是什么是指使用TCP协议时一次性接收到的“消息数据包”过多,无法有效分隔每个包的数据。比如,两个文件未经特殊处理,按顺序在同一个TCP连接中传输,接收端从接收缓冲区中读取的数据就很难区分两个文件数据的分界点在哪。当然,TCP协议本身并不是基于数据包的协议,这是在理论基础上对实际生产环境妥协造成的结果。
    粘包产生的原因众所周知,TCP协议是需要在客户端和服务端经过三次握手建立一个端到端的连接的。也就是说,每次通过TCP协议发送的消息,需要经过如下过程:
    建立连接,三次握手发送数据断开连接
    生产中使用TCP连接有两种方式:
    TCP短连接必要时才建立连接,数据发送结束后就断开连接,释放资源每次发送的数据量很小,那么在建立连接与断开连接的操作上的消耗占比就会过大,导致系统资源、系统响应时间等均收到影响但是,如果能够确保一包数据发送完成后就断开连接,那么不会出现粘包问题TCP长连接建立连接后不断开只有一次建立连接的消耗,后续可以复用这个连接反复进行数据传输,吞吐量会更高
    TCP被设计为可靠的流传输协议,会自适应地重发丢失的数据,理论上TCP发送完完整的消息就应当断开。但是,为了更高的效率及避免网络拥塞,实际生产环境往往会使用一个长连接收发多段数据。一旦发送方将多个数据通过一个连接发送(比如Nagle优化算法,将多个小数据块合并发送),那么接收方就得使用相应的方法区分多个数据,否则就出现了粘包问题。
    ......

  • Service Mesh简介
     7     2019-04-15 19:59:42

    Service Mesh是什么中文翻译是服务网格,是微服务架构中重要的基础设施。简单来说,这是一个实现服务间请求可靠传递的,负责服务发现、服务间通信,且对应用程序透明的轻量级网络代理。通俗来说,其实就是服务端到端的数据传输代理,类似TCP/IP,将微服务必要且重复的功能抽离,包括服务发现、异常处理、熔断等功能。
    网络架构的抽象应用程序中网络传输控制的演变
    1.网络逻辑与应用逻辑耦合
    2.依靠TCP/IP,网络逻辑从应用逻辑中抽离
    微服务网络服务的演变
    1.服务自行维护服务注册与发现、负载均衡、熔断、重试等
    ......

    共10张

  • 伪共享简介
     8     2019-03-14 17:57:20

    伪共享是什么CPU Cache众所周知CPU处理速度与硬盘、内存的访问速度相差过大,需要通过CPU缓存进行磨合,否则会导致CPU整体吞吐量受到极大的影响。而单一层缓存无论是价格、命中率、查找速度方面都是不能够满足要求的,因此现在很多CPU出现了三级缓存结构,访问速度如下:
    CPU缓存延迟,单位是CPU时钟周期,可以理解为CPU执行一个指令的时间
    其中L1是L2的子集,L2是L3的子集,L1到L3缓存容量依次增大,查找耗时依次增大,CPU查找顺序依次是L1、L2、L3、主存。L1与CPU core对应,是单核独占的,不会出现其他核修改的问题。一般L2也是单核独占。而L3一般是多核共享,可能操作同一份数据,那么就有可能出问题。
    Cache Line现代CPU读取数据通常以一块连续的块为单位,即缓存行(Cache Line)。所以通常情况下访问连续存储的数据会比随机访问要快,访问数组结构通常比链结构快,因为通常数组在内存中是连续分配的。
    PS. JVM标准并未规定“数组必须分配在连续空间”,一些JVM实现中大数组不是分配在连续空间的。
    缓存行的大小通常是64字节,这意味着即使只操作1字节的数据,CPU最少也会读取这个数据所在的连续64字节数据。
    ......