用户您好!请先登录!

分类目录算法

数据结构中的那些树

前言

没有必要过度关注本文中二叉树的增删改导致的结构改变,规则操作什么的了解一下就好,看不下去就跳过,本文过多的XX树操作图片纯粹是为了作为规则记录,该文章主要目的是增强下个人对各种常用XX树的设计及缘由的了解,也从中了解到常用的实现案例使用XX树实现的原因。

数据在计算机中的存储结构主要为顺序存储结构链式存储结构索引存储结构散列存储结构,其中链式存储结构最常见的示例是链表与树,链式存储结构主要有以下特点:

  • 优点:逻辑相邻的节点物理上不必相邻,插入、删除灵活,只需改变节点中的指针指向
  • 缺点:存储空间利用率低,需通过指针维护节点间的逻辑关系;查找效率比顺序存储慢

度:当前节点下的子节点个数

阅读更多

KMP算法那点事

简介

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

提取加速匹配的信息

上面说道 KMP 算法主要是通过消除主串指针的回溯来提高匹配的效率的,那么,它是则呢样来消除回溯的呢?就是因为它提取并运用了加速匹配的信息!

阅读更多

几种常见的延时队列实现方案

一、延时队列的应用

什么是延时队列?顾名思义:首先它要具有队列的特性,再给它附加一个延迟消费队列消息的功能,也就是说可以指定队列中的消息在哪个时间点被消费。

延时队列在项目中的应用还是比较多的,尤其像电商类平台:

  1. 订单成功后,在30分钟内没有支付,自动取消订单
  2. 外卖平台发送订餐通知,下单成功后60s给用户推送短信。
  3. 如果订单一直处于某一个未完结状态时,及时处理关单,并退还库存
  4. 淘宝新建商户一个月内还没上传商品信息,将冻结商铺等

上边的这些场景都可以应用延时队列解决。

阅读更多

高并发高性能的时间轮超时器

在许多业务场景中,我们都会碰到延迟任务,定时任务这种需求。特别的,在网络连接的场景中,常常会出现一些超时控制。由于服务端的连接数量很大,这些超时任务的数量往往也是很庞大的。实现对大量任务的超时管理并不是一个容易的事情。

本章我们将介绍几种用于实现超时任务的数据结构,并且最后分析 Netty 在超时任务上采取的结构和代码。

JDK 原生提供的超时任务支持 – java.util.Timer

JDK 在 1.3 的时候引入了Timer数据结构用于实现定时任务。Timer的实现思路比较简单,其内部有两个主要属性:

  • TaskQueue:定时任务抽象类TimeTask的列表。
  • TimerThread:用于执行定时任务的线程。

Timer结构还定义了一个抽象类TimerTask并且继承了Runnable接口。业务系统实现了这个抽象类的run方法用于提供具体的延时任务逻辑。

阅读更多

Reactor和Proactor模型

Reactor模型

Reactor模式是处理并发I/O比较常见的一种模式,用于同步I/O,中心思想是将所有要处理的I/O事件注册到一个中心I/O多路复用器上,同时主线程/进程阻塞在多路复用器上;一旦有I/O事件到来或是准备就绪(文件描述符或socket可读、写),多路复用器返回并将事先注册的相应I/O事件分发到对应的处理器中。

Reactor是一种事件驱动机制,和普通函数调用的不同之处在于:应用程序不是主动的调用某个API完成处理,而是恰恰相反,Reactor逆置了事件处理流程,应用程序需要提供相应的接口并注册到Reactor上,如果相应的事件发生,Reactor将主动调用应用程序注册的接口,这些接口又称为“回调函数”。用“好莱坞原则”来形容Reactor再合适不过了:不要打电话给我们,我们会打电话通知你。

阅读更多

布隆过滤器简介

在程序的世界中,布隆过滤器是程序员的一把利器,利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难

阅读更多

用小内存来处理大规模数据

当你写了一个处理数据的软件,它可能在小样本文件上运行地很好,但一旦加载大量真实数据后,这个软件就会崩溃。

问题在于你没有足够的内存——如果你有 16GB 的 RAM ,你就无法一次载入 100GB 大小的文件。载入这么大的文件时,操作系统在某个时刻就会耗尽内存,不能分配存储单元,你的程序也就会崩溃。

所以,你该怎样防止这类情况发生?你可以启动一个大数据集群——你所需要做的是:

  • 搞到一个计算机集群。
  • 花一周时间搭建这个集群。
  • 大部分情况下,你需要学习一套全新的 API,重写你所有的代码。

这个代价可能很昂贵,会令人沮丧;幸运的是,大部分情况下,我们不必这样做。

你需要一个简单而容易的解决方案:在单机上处理你的数据,最小化环境搭建开销,尽可能利用你正在使用的代码库。实际上,大部分情况你都可以做到这样,只要使用一些方法即可,有时候这些方法被称为“核外计算”(out-of-core computation)。

本文将介绍如下内容:

  • 你究竟为什么需要 RAM。
  • 处理无法放入内存的数据最简单的方法:花些钱。
  • 处理大量数据的三种基本软件方法:压缩、分块、索引。

阅读更多

百度分布式ID生成器:UidGenerator

UidGenerator是百度开源的Java语言实现,基于Snowflake算法的唯一ID生成器。而且,它非常适合虚拟环境,比如:Docker。另外,它通过消费未来时间克服了雪花算法的并发限制。UidGenerator提前生成ID并缓存在RingBuffer中。 压测结果显示,单个实例的QPS能超过6000,000。(另外,也可参考美团的雪花算法开源实现Leaf)

依赖环境:

  • JDK8+
  • MySQL(用于分配WorkerId)

1. snowflake

由下图可知,雪花算法的几个核心组成部分:

  • 1位sign标识位;
  • 41位时间戳;
  • 10位workId(数据中心+工作机器,可以其他组成方式);
  • 12位自增序列;
时钟回拨问题?百度开源的分布式唯一ID生成器UidGenerator出手了

阅读更多

几种常用的算法简析

1. 分治算法

1.1 基本概念

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

阅读更多

知识图谱在美团智能场景下的应用与实践

导读:目前为止 IT 产业经历了六次浪潮,分别为:大型机时代,小型机时代,个人电脑时代,桌面互联网时代,移动互联网时代和 AIOT 时代。在这些时代背后可以发现是人机交互方式的变化:从鼠键交互,到触控交互,再到语音智能交互,可以看到人机交互的方式在向更自然更直接化的方式演进。今天会和大家分享基于知识图谱的问答在美团智能交互场景中的应用和演进。

今天的介绍会围绕下面三点展开:

  • 智能交互背景介绍
  • 受限场景问答应用和演进
  • 复杂场景问答应用和演进

智能交互背景介绍

1. 智能交互的划分

知识图谱在美团智能场景下的应用于实践

智能交互的划分基本上是根据人类需求拆分:

  • 检索式交互—信息获取,比较经典的方法 FAQ:QA 匹配,QQ 匹配;
  • 任务式交互—执行任务,比如订机票 ( 酒店 ) 的特定任务;
  • 闲聊式交互—娱乐与休闲,基于深度学习的端到端的学习系统。

阅读更多

推荐系统基础知识

本文主要包括推荐系统的相关概念、推荐系统的架构和流程、常见的推荐算法、挖掘、召回、排序、评估和总结这几部分。

概念部分会简述推荐系统相关的理论知识,架构和流程主要是介绍推荐系统的通用架构和常规的推荐流程。

算法部分主要是一些常见的推荐算法介绍,挖掘》召回》排序主要是基于推荐流程的详细展开。

评估部分指的是如何评估一个推荐系统的好坏,总结部分主要是整体内容的回顾,以及一个真实推荐系统的案例。

1. 相关概念

1.1. 什么是推荐系统

先来看下Wiki的定义:

一种信息过滤系统,用来预测用户对物品的行为和偏好。

按照字面意思理解下来,就是帮助过滤信息,预测用户对物品的行为和偏好。

在今日头条曹欢欢博士的一次分享中提到了这样一个定义:

资讯推荐系统本质上要解决用户,资讯和环境的匹配,y=F(Xi,Xu,Xc)

感觉把这个定义延伸到其他推荐系统上也是成立的,那就是推荐系统本质上要解决用户,物品和环境的匹配问题,帮助建立用户和物品之间的连接。

回到定义本身,理论上说能实现这个功能的系统都可以称之为推荐系统。

阅读更多

看得懂的分布式协调算法Paxos图解

Google Chubby的作者Mike Burrows对Paxos的评价极高:“这个世界上只有一种一致性算法,那就是 Paxos”。

其实也不为过,像非常有名的 Raft 算法、Zab 算法等都是基于 Paxos 的简化和改进。

Paxos 解决什么问题

Paxos 是解决分布式环境下多节点的数据一致性问题,先看下一致性问题。

例如一个cache集群有3个节点,每个节点都可以写入。

深度原理学习之–让人看得懂的分布式协调算法Paxos图解

集群内各个节点需要做数据同步,如果没有一致性算法做保证,3个节点内数据就可能混乱,例如:

  • 节点1收到请求后,同步给节点2、3,节点2立即收到了,但因为网络原因,节点3没有立即同步。
  • 在节点3同步之前,节点2也发起了同步请求,因为2、3间的网络状况好,节点3立即同步了。
  • 所以,节点1、2的同步顺序是x=1,x=2,而节点3的同步顺序是x=2,x=1,造成了节点间数据不一致。

Paxos 就是用来解决这个问题,保证各节点数据的绝对一致,不会混乱。

阅读更多

搜索引擎基本原理

搜索引擎是什么?

这里有个概念需要提一下。信息检索 (Information Retrieval 简称 IR) 和 搜索 (Search) 是有区别的,信息检索是一门学科,研究信息的获取、表示、存储、组织和访问,而搜索只是信息检索的一个分支,其他的如问答系统、信息抽取、信息过滤也可以是信息检索。

本文要讲的搜索引擎,是通常意义上的全文搜索引擎、垂直搜索引擎的普遍原理,比如 Google、Baidu,天猫搜索商品、口碑搜索美食、飞猪搜索酒店等。

Lucene 是非常出名且高效的全文检索工具包,ES 和 Solr 底层都是使用的 Lucene,本文的大部分原理和算法都会以 Lucene 来举例介绍。

为什么需要搜索引擎?

看一个实际的例子:如何从一个亿级数据的商品表里,寻找名字含“秋裤”的 商品。

阅读更多

倒排索引那点事

倒排索引是搜索引擎中最为核心的一项技术之一,可以说是搜索引擎的基石。可以说正是有了倒排索引技术,搜索引擎才能有效率的进行数据库查找、删除等操作。

1. 倒排索引的思想

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。

在搜索引擎中,查询词可以切分成若干个单词,所以对于搜索引擎中的倒排索引对应的属性就是单词,而对应的记录就是网页(也可以广泛地称为是文档)。所以,搜索引擎中的倒排索引是实现“单词-文档矩阵”的一种具体存储形式,通过倒排索引,可以根据单词(属性)快速获取包含这个单词的文档列表(记录)。倒排索引主要由两个部分组成:“单词词典”和“倒排文件”。

阅读更多

微服务分布式事务中的Saga模式

该文是基于《微服务模式》作者Chris Richardson的QCONSF 2017会议上的PPT文章(这里)和其 Eventuate Tram Saga框架之上,对Saga模式进行的原理性解说,其中包含banq个人经验总结和见解,请从批判性视角看待。Chris Richardson的另外一本书籍《POJO in Action》曾经是帮助Spring成功挑战了EJB2。

在微服务环境下为什么不能使用ACID事务?因为每个微服务都拥有自己的私有数据库,比如订单服务有自己的订单数据库,而客户服务有自己的客户数据库,如果有一个业务操作需要跨订单和客户一起操作,那么一般使用JTA+XA方式跨订单数据库和客户数据库操作:

@ Transactional //事务元注解
public void crossAction(XX){
    //事务开始

    //这里ORDERS是属于订单服务的私有数据库
    SELECT ORDER_TOTAL FROM ORDERS WHERE CUSTOMER_ID = ?

    //这里CUSTOMERS是属于客户服务的私有数据库
    SELECT CREDIT_LIMIT FROM CUSTOMERS WHERE CUSTOMER_ID=?

    INERT INTO ORDERS .....

    //提交事务

}
<p>

以上JTA操作如果结合XA数据源配置,将会实现2PC两段事务提交。

阅读更多

智能运维那点事(1)

矛盾是事物发展的源泉和动力。运维中的矛盾无处不在,既有来自业务与技术的矛盾,也有来自开发和运维的矛盾,还有来自数据中心内部的矛盾,解决这些矛盾只能靠发展。

一、安全生产

数据中心的主要职责是安全生产,围绕着安全生产有三个目标:

  1. 高可用架构:高可用的IT基础设施可以确保应用系统的可用性与连续性,包括:应用集群、系统热迁、数据库集群、存储复制、物理备份等。
  2. 高效运维:围绕着高可用架构,进行一些列高效运维工作,包括:资源供给、应用部署、日常变更、故障处理、数据治理等。
  3. 节约成本:在满足高可用和高效的前提下,尽量节约成本,包括资源优化、性能优化、以及减少成本不敏感的资源浪费。

阅读更多

Raft算法原理详解

简介

关于Raft算法,有两篇经典的论文,一篇是《In search of an Understandable Consensus Algorithm》,这是作者最开始讲述Raft算法原理的论文,但是这篇论文太简单了,很多算法的细节没有涉及到。更详细的论文是《CONSENSUS: BRIDGING THEORY AND PRACTICE》,英文好的话去读原作是最好的,很多Raft的实现都是论文的复刻版。

Raft算法概述

Raft算法由leader节点来处理一致性问题。leader节点接收来自客户端的请求日志数据,然后同步到集群中其它节点进行复制,当日志已经同步到超过半数以上节点的时候,leader节点再通知集群中其它节点哪些日志已经被复制成功,可以提交到raft状态机中执行。

阅读更多

分布式系统中的唯一id生成策略及实现

系统唯一ID是我们在设计一个系统的时候常常会遇见的问题,也常常为这个问题而纠结。生成ID的方法有很多,适应不同的场景、需求以及性能要求。所以有些比较复杂的系统会有多个ID生成的策略。

简单分析一下需求

所谓全局唯一的 id 其实往往对应是生成唯一记录标识的业务需求

这个 id 常常是数据库的主键,数据库上会建立聚集索引(cluster index),即在物理存储上以这个字段排序。这个记录标识上的查询,往往又有分页或者排序的业务需求。所以往往要有一个time字段,并且在time字段上建立普通索引(non-cluster index)。普通索引存储的是实际记录的指针,其访问效率会比聚集索引慢,如果记录标识在生成时能够基本按照时间有序,则可以省去这个time字段的索引查询。

这就引出了记录标识生成的两大核心需求:

  • 全局唯一
  • 趋势有序

阅读更多

排序算法的总结与演示

使用JAVA实现的十个经典排序算法,可直接运行。

0、排序算法说明

0.1 排序的定义

对一序列对象根据某个关键字进行排序。

0.2 术语说明

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
  • 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
  • 内排序:所有排序操作都在内存中完成;
  • 外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
  • 时间复杂度:一个算法执行所耗费的时间。
  • 空间复杂度:运行完一个程序所需内存的大小。

参考:稳定排序与不稳定排序

0.3 算法总结

十大经典排序算法最强总结(含JAVA代码实现)

图片名词解释:

  • n: 数据规模
  • k: “桶”的个数
  • In-place: 占用常数内存,不占用额外内存
  • Out-place: 占用额外内存

阅读更多

关于限流那点事,尤其是分布式的

一、限流的作用

由于API接口无法控制调用方的行为,因此当遇到瞬时请求量激增时,会导致接口占用过多服务器资源,使得其他请求响应速度降低或是超时,更有甚者可能导致服务器宕机。

限流(Rate limiting)指对应用服务的请求进行限制,例如某一接口的请求限制为100个每秒,对超过限制的请求则进行快速失败或丢弃。

限流可以应对:

  • 热点业务带来的突发请求;
  • 调用方bug导致的突发请求;
  • 恶意攻击请求。

因此,对于公开的接口最好采取限流措施。

阅读更多

最通俗也是最深刻的CAP理论

“写在前面:每一个体系,每个一框架,每个入经战场的系统,都有背后严格的理论作为依据,知其所以然,才能真得知其然。— Fish”

本文的原作者是 Martin Kleppmann, 著有《Designing Data-Intensive Applications》一书,无论是这本书还是这篇文章,都能站在一个独特的视角去阐释那些可能被大多数人误解的理念,让读者醍醐灌顶。

这可能是我看过最通俗也是最深刻的CAP理论

在此之前我就隐约对文中提到的一些 CAP 误解嗤之以鼻,这篇文章让我更加确信了之前零碎的认知,不夸张地讲,这应该是我看过的最通俗也是最深刻的 CAP 科普文。

阅读更多

分布式全局唯一ID生成策略

“唯一ID”在应用程序中是一个很常见的需求,它用于唯一标识一个业务对象、一个资源、或者一个消息等等。在数据库中,唯一ID一般是用来做为一个数据的主键。看过前面介绍MySQL索引原理的文章的朋友应该知道,主键对于数据库的重要性不言而喻。

在单机场景下,要得到一个全局唯一的ID是非常容易的,你可以使用数据库的自增功能。

但是如果在分布式的场景下,想要构建构建一个全局唯一的ID就有些不一样。因为分布式系统一般是高并发场景,那自然不适合使用单机数据库的自增功能了。如果你的技术选型恰好是MySQL这样的“非分布式数据库”,那就得参考一下业界常见的分布式全局唯一ID生成策略了。

阅读更多

Raft 协议学习笔记

好久没有更新博客了,最近研究了Raft 协议,谈谈自己对 Raft 协议的理解。希望这篇文章能够帮助大家理解 Raft 论文。

Raft 是什么?

Raft 是一种分布式系统的一致性算法。

在分布式系统中,我们需要让一组机器作为一个整体向外界提供服务。由于在实际的条件下,我们认为每台机器都是不100%可靠的,随时都可能发生宕机。每台机器之间的通信也不是可靠的,可能发生通信的阻塞、丢失、重试。所以需要某些算法来保证在大多数机器都正常的情况下向外提供可靠的服务。

在 Raft提出之前,Paxos 已经被提出,但是 Paxos 相当复杂。Raft 的目标就是提出一种易于理解的分布式一致性算法。

阅读更多