kafka为什么快

批处理(发送消息时多条缓存起来再发),分片,顺序写,producer2broker(mmap共享空间) broker2consumer(sendFile)。 broker和client之间是有心跳机制的。

kafka过期:用的是时间轮

kafka 消费者组:kafka消费者组默认的分区分配策略,消费者线程数不能大于分区数(当消费者总数大于分区数的话,多余的消费者进程会一直挂着什么都不干,但是当某个消费者线程down掉的话,之前那些多余的消费者线程会顶替上来),多个消费者组订阅同一个topic组成广播。

kafka 零拷贝 directIO mmap sendfile , kafka是leader负责所有的读写,followers只是备份。

producer2broker request.required.acks (0:只管发,1:发了要leader确定,-1:发了要同步给所有followers,N/2+1:过半确认返回)

broker2consumer auto.commit.enable (true 消费端自动ack, false 消费端手动ack,手动提交offset),kafka采用的是拉模式消费,消费速度由consumer控制,防止broker推送速度大于consumer消费速度而崩溃。

存储:kafka以 - 为存储文件夹名,里面的文件按日志追加形式WAL进行分段 (有很多个小文件,方便旧的整块删除)。topic过多顺序IO会降为随机IO

事务:确保在一个事务中发送的多条消息,要么都成功,要么都失败。注意,这里面的多条消息不一定要在同一个主题和分区中,可以是发往多个主题和分区的消息(像跟mysql一样对不同的表update)。当然,你可以在 Kafka 的事务执行过程中,加入本地事务,来实现和 RocketMQ 中事务类似的效果,但是Kafka是没有事务反查机制的。

kafka之导致Rebalance: partition发生变化;订阅的Topic个数发生变化(不停的动态订阅topic);消费者组成员个数发生变化(最常见)。新增成员或已有成员离开。每个消费者都会跟 Coordinator 保持心跳(新版本有独立的心跳),rebalance时消费者会停止消费,加入到重平衡事件当中。

session.timeout.ms 用来控制最大多长时间向coordinator发送自己的心跳不会被认为超时,默认值10秒。

heartbeat.interval.ms 用来控制发送心跳请求频率,值越小,发送心跳频率会越高。

max.poll.interval.ms 限定了消费端应用程序两次调用poll方法(拉数据)的最大时间间隔,默认值是 5分钟,业务处理时长大于这个间隔会导致rebalance(消费速度过慢)。

kafka之topic:topic过多顺序IO会降为随机IO(很多文件一起写变成随机io),不停的动态订阅topic会不停的触发rebalance。




pprof使用流程:

pprof可分析(堆、cpu、协程数、系统线程数、阻塞同步、互斥锁数) go tool pprof连接进行pprof采集,默认采集30秒。go tool graphviz生成svg文件或火焰图观察链路和耗时或生成信息放在本地进入pprof终端查看。pprof可分析golang程序cpu占用过高问题或系统线程数过多cpu负载高。

golang优缺点:编译型二进制(比php),有GC(比C艹),协程并发,资源利用率高,快速。缺点:过多的err处理对转语言新人不友好。(框架 包已有)

golang调度: 1、先从本地队列拿,2、没有从全局队列里拿一半回本地队列,3、从网络轮询器里获取并Inject到全局队列里,4、从别的P里偷一半放到本地,注:每61次会从全局队列里获取一个,防止在全局队列里的G饿死。

Sysmon监控线程:1.14版后基于信号抢占

处于_Psyscall状态的p,当系统调用超过20us时,并队列里还有其他G要处理,Sysmon会去抢占P,把M和G独立出去运行。

处于_Prunning状态的p,当运行时间超过10ms时,如死循环,Sysmon会去抢占G,把当前G调度让出运行权

2分钟没触发GC,会触发。生成大量堆内存,GC频率越来越高,Sysmon会把GC的阈值动态的调高,所以要定期2分钟清理。

周期性扫描网络轮询器,把监听到数据的goroutine 注入到全局队列

golang cpu利用率高:死循环或进程有大量计算、GC在执行垃圾回收时,操作系统会不断对这些有或者没有被引用的变量进行扫描,这涉及操作系统的算法,执行这种算法时会占用CPU的资源(sys利用率)。新开辟的变量和内存过多,导致系统不停的检查是否有不需要引用的变量了,造成占用CPU资源过多。负载高:还是系统调用导致线程数多,任务数过多。

golang mutex同步原语:其实是把协程gopark放到sudog链表里挂着,解锁时是goready放进队列里。可搜sync_runtime_SemacquireMutex代码,并不是PV操作(线程级)陷入内核的。读写锁是写优先于读的,防读锁过多导致写一直阻塞,读多写少RWMutex。写多读少mutex就行。

golang内存分配: ,

TCmalloc(ThreadCache(单位object),CentralCache(单位object),PageHeap(单位span))多级内存分配threadCache每个线程都有可以减少锁开销,CentralCache空闲块链表数量和threadCache数量相同。

Golang内存管理(mcache(P本地),mcentral(管理全局的mspan),mheap(单位mspan)) 每个P都有独立的mcache减少锁开销,mcentral空闲块链表数量和P数量相同。

申请的内存大于32KB直接申请mheap。

golang defer原理:defer语句在当前G结构体里的的g._defer链表把defer结构体串起来的,新来的defer是推入链表头部的。 关键搜索词:newdefer

函数return执行流程:1.先给返回值赋值(匿名和有名返回值),2.g._defer链表的头开始执行defer结构里指向的函数,3.包裹函数return返回。

GC STW:混合写屏障机制,先扫描栈空间对象全部标黑。混合写屏障 栈空间不启动,堆空间启动。

强三色不变性:黑色对象引用的必须是灰色,弱三色不变性:所有被黑色对象引用的白色对象都有被灰色引用或间接引用.

GC流程:

启动GC时会stop the world启动混合写屏障,扫到所有栈上堆上的root的对象加入队列,然后start the word。然后并发扫描各个goroutine的栈,使其变黑并一直保持,这个过程不需要STW. 完成GC后会stop the world关闭混合写屏障

1.虽然 golang 是先实现的插入写屏障,后实现的混合写屏障,但是从理解上,应该是先理解删除写屏障,后理解混合写屏障会更容易理解;

2.插入写屏障没有完全保证完整的强三色不变式(栈对象的影响),所以赋值器是灰色赋值器,最后必须 STW 重新扫描栈;

3.混合写屏障消除了GC期间的所有的 STW,实现的是黑色赋值器,不用 STW 扫描栈;

混合写屏障的精度和删除写屏障的一致,比以前插入写屏障要低;

4.混合写屏障扫描栈式逐个暂停,逐个扫描的,对于单个 goroutine 来说,栈要么全灰,要么全黑;

5.暂停机制通过复用 goroutine 抢占调度机制来实现;

6.生成大量堆内存,GC频率越来越高,Sysmon会把GC的阈值动态的调高,以减少GC次数,所以会有固定2分钟清理一次。也别写内存泄漏代码。

内存逃逸(逃逸分析):外部引用(指针逃逸)、动态变量大小逃逸(for循环 length是变量)、动态类型逃逸(不确定大小)、栈空间不足逃逸(对象太大)、闭包引用对象逃逸

make与new的区别,new返回结构体指针,make用到特殊类型channel、map、slice。返回对应结构体

P的最大上限 256:




高并发系统:核心思想,缓存、多级缓存、分片、集群、主从、异步削峰、限流过载保护、压测、服务化+熔断

webscoket常用:推事件 拉数据

websocket协议规范: 特别注意头信息 textMessage BinaryMessage PingMessage PongMessage

前端平滑新按钮更新添加 推事件广播,前端再拉数据,推拉结合

websocket推更新事件,前端监听到后请最新的js css代码动态覆盖更新



Nginx惊群:有用进程锁去处理

HTTPS: 为什么要rsa和aes结合,对称加密(aes)具有加解密速度快,性能高的特点 ,而rsa保密性好,性能不佳。所以是先rsa加密aes互相得到对称密文,然后aes进行加密通信。当keepalive到时,重新发起https里aes密文会变

HTTPS流程:1:个人信息和公钥hash成摘要、2:然后用私钥加密成数据签名,数据签名和公钥个人信息hash算法一起发出去、3:然后用公钥解数据签名得到摘要,和发过来的信息生成的摘要进行对比、4:最后得到互相通信的加密算法

HTTP2.0:二进制分帧(独立的stream帧) 首部压缩(两端维护了header索引表,以后传输用下标) 多路复用(虚拟信道,独立的帧时分复用发送) 请求优先级 服务器推送(双向流)

web安全:

xss :过滤带html标签的字符串

csrf :攻击者盗用了你的身份,以你的名义发送恶意请求。

防范:同源检测(origin referer)、带token提交验证、双重Cookie验证(url上带字段与cookie里的字段校验) ,设置cookie里的Samesite属性用来标明这个Cookie是个“同站 Cookie”

sql注入 预编译语句和参数化查询



etcd异地多活 镜像模式mirror-maker、raft协议 (数据同步,选主)。是CP系统,当发生网络分区时,有个区会重新选主,但少的区无法复制到大多数,成为不可用,另一个区是大多数可正常进行同步保证一致,对外部而言是保证一致的。

微服务框架、GRPC与HTTP2.0

网关限流,服务限流。

而熔断降级作为保护服务自身的手段,通常是在客户端进行规则配置和熔断识别:



CPU:

孤儿进程:一个父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养,并由init进程对它们完成状态收集工作。

僵尸进程:一般工作中叫Z进程,即一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程,如何处理Z进程 ,杀死父进程,都转成孤儿进程让init进程处理。cpu负载过高说明任务过多,或是僵尸进程过多

CPU的利用率:CPU处于用户态执行的时间(users),系统内核执行的时间(sys),和空闲系统进程执行的时间(idle)。平时说的CPU利用率是指:1-CPU空闲运行时间/总运行时间. CPU利用率显示的是程序在运行期间实时占用的CPU百分比

CPU负载计算:取决于CPU任务队列长度而不是CPU利用率,使用CPU队列长度则可以很直接反应CPU的负载量。load average 是对 CPU 负载的评估,其值越高,说明其任务队列越长,处于等待执行的任务越多。就是一段时间内一共有多少任务在使用或等待使用CPU。CPU负载显示的是一段时间内正在使用和等待使用CPU的平均任务数。CPU利用率高,并不意味着负载就一定大。

CPU负载分担到每个CPU上的负载是多少呢?那就要看我这台服务器有一共有多少个内核了。比如:4个内核15分钟的负载最理想的状态是4*0.7

CPU时间 = user(用户态)+sys(内核态)+nice()+idle(IO等待以外其它等待时间)+iowait(硬盘IO等待时间)+irq(硬中断时间)+softirq(软中断时间)




操作系统:

mmap与brk:brk申请的内存是连续的,mmap则不需要

内核态:cpu可以访问内存的所有数据,包括外围设备,例如硬盘,网卡,cpu也可以将自己从一个程序切换到另一个程序。系统调用用户态会陷入内核态。

用户态:只能受限的访问内存,且不允许访问外围设备,占用cpu的能力被剥夺,cpu资源可以被其他程序获取。当系统调用时用户态的cpu上下文是保存在内核栈的pt_regs里。

用户态和内核态:在CPU的所有指令中,有些指令是非常危险的,如果错用,将导致系统崩溃,比如清内存、设置时钟等。防止他们获取别的程序的内存数据、获取外围设备的数据, 并发送到网络。如果所有的进程都能使用这些指令,那么系统死机的概率将大大增加。所以要设置级别权限。(系统调用 ,缺页异常,外设中断会用户态陷入内核态)

文件操作:

1、在写文件的时候同时删除文件,文件依旧可以读写,多进程打开文件时inode里的i_count会增加,在删除文件时i_count为0时才真正删除(类似引用计数,标记有多少个进程打开) i_nlink是硬连接计算 https://www.cnblogs.com/yangyuliufeng/p/9339088.html

2、同一个文件是可以open多次的。每次open都会建立一个新的file句柄/指针与file结构体,指向同一个文件的inode节点。生成子进程时会共享file结构体。

线程同步和进程同步的本质区别在于锁放在哪,放在私有的进程空间还是放在多进程共享的空间,并且看锁是否具备进程共享的属性

多线程同步:互斥锁、自旋锁、读写锁、条件变量。在linux里线程和进程是同一结构体task_struct,多线程的本质仍是进程。

多进程同步:设置信号量+对信号量做PV原语操作(信号与信号量区别),消息队列、管程、文件大锁。多线程的本质仍是进程

死锁 :两进程/线程,两资源上锁,产生了锁交叉,

进程通信:套接字、消息队列、共享内存空间、管道、远程过程调用、信号(父子进程wait/waitpid)。linux里线程和进程是同一结构体task_struct

进程/线程调度:FIFO、短进程优先、最高响应比优先、时间片轮转法、最短剩余时间优先、多级反馈队列算法。调度时Cpu上下文件会存到进/线程的thread_struct里,thread_info用于系统快速找到task_struct

虚拟内存:变量操作->访问快表->访问虚拟内存地址->访问页目录(是否有对应物理内存)->产生缺页异常中断->判断有没有足够的物理内存(没有就脏页刷盘)->访问磁盘swap空间->加载到内存->设置页表。伙伴系统。内存对齐:代码里小类型数据聚一起可以内存对齐,好处内存碎片大大减少,节省空间。

虚拟内存寻址空间:

寻址空间,用户态所占空间和内核态所占空间大小几乎各一半(32位)

零拷贝:directIO mmap(connfd->filefd 4 次上下文切换,1 次 CPU 拷贝和 2 次 DMA 拷贝) sendfile(filefd->connfd 2次上下文切换,1 次 CPU 拷贝)

mmap的优缺点:

优点:

1、省了传统读写的用户态和内核态的cpu上下文切换,提高了大文件读写效率。

缺点:

1、mmap是按页做映射的所发如果文件小于4KB也是占用4KB内存,如果连续mmap小文件会浪费很多内存空间

2、mmap映射文件的大小是不能超过文件大小,所以要提前得之文件大小,不能动态扩展文件。

3、如果系统频繁的使用mmap操作,而且每次mmap的size都不同,那么就会使得内存可能缺少足够的连续的内存空间。

进程切换:

1.切换页目录以使用新的地址空间并要刷掉快表。

2.切换内核栈和硬件上下文。

线程切换:

1.只切换内核栈和硬件上下文,切换时要陷入内核。

协程切换:协程(2kb内存)切换没有内核的开销协程上下文切换只涉及到cpu三个寄存器(PC程序计数器 / SP堆栈指针 / DX寄存器)的值修改(协程切换只涉及基本的CPU上下文切换,而且是由P执行处理无内核帮忙,切换只发生在用户态);而对比线程的上下文切换则需要涉及模式切换(线程切换,cpu要用户态陷入内核态,要操作系统去完成线程调度,还有线程私有栈(内核栈)的切换 要切换的上下文比协程多,再返回用户态)

协程切换的时机:1、select阻塞时,2、io(文件,网络)读写阻塞时,3、channel阻塞时,4、等待锁,5、sleep时,6、runtime.Gosched()这些阻塞时会调用gopark把协程切换出去到对应的结构体里挂起,当就绪goready时会把他们扔回全局队列等待调度。系统调用时间过长时会切出去独立 线程处理。




网络:

http状态码:504(nginx网关执行/等待超时)、502(Nginx发现与自己通信的连接断掉/找不到了,常驻进程里常见程序panic退出或是进程未启动)

TCP通信:当服务器返回数据修改TCP包服务器源IP时,对端是否可以收到 。可以,操作系统并不检测对端源ip地址信息。但是会对checkSum做校验处理,在校验和生成之前修改源IP,再发送给对端,对端是可以接收包的,并不检验源ip地址。

TCP为啥可靠:ACK和超时重发机制、滑动窗口流控、拥塞控制(慢启动,快重传,快恢复)

TCP校验和:做校验处理,TCP校验和也包括了96位的伪头部,其中有源地址、目的地址、协议以及TCP的长度。这可以避免报文被错误地路由。

路由转发:由A发给路由器B,B经过重封装后,源IP和目标IP是不变的,源MAC地址变成B2的MAC地址目标MAC地址变成C1的MAC地址

timewait作用

1:保证服务端ack没收到重发

2:旧连接持续时间内所产生的所有报文都从网络中消失,如果没有timeWait 新的连接可能会同ip同端口,传播延迟的数据包会被新连接 接收 。有timewait了2msl的时间足够消化延迟数据包或让其消散。

通用连接池:

timewait过多导致的问题,closewait过多导致的问题

服务端重启,tcp连接异常关闭问题:在发ping时对端会发RST重,会报connection reset by peer

URG(紧急包) SYN(握手) FIN(挥手) PSH(推数据) RST(重置过期连接) ACK(确认) TCP六标志位

TCP中的半链接与全链接



epoll: 是没有用mmap的,默认是水平触发。

epoll_ctl把connfd放到epollfd并拷贝到内核态,有数据来时对应connfd复制到rdlist

epollwait系统调用 会判断rdlist是否为空,不为空则把fd信息从内核态复制到用户态数组里。

水平触发:没有把数据一次性全部读写完,那么下次调用 epoll_wait()时,它还会通知你在上没读写完的文件描述符上继续读写,当然如果你一直不去读写,它会一直通知你

边缘触发:没有把数据全部读写完,那么下次调用epoll_wait()时,它不会通知你,也就是它只会通知你一次,直到该文件描述符上出现第二次可读写事件才会通知你!!!



mysql:索引表 回表 覆盖索引 sql语句 全同步 半同步(等待至少一个从库接收到并写到relay log中才返回给客户端)复制

三范式:1NF:字段不可分,每个字段是原子级别的、2NF:有主键,非主键字段依赖主键,ID字段就是主键,它能表示这一条数据是唯一的、3NF:非主键字段不能相互依赖

mysql主从复制:主库写入binlog、salve开启一个I/O Thread,该线程在master打开一个连接,主要工作是拉取binlog的最新数据写入relay log里,写入relayLog里成功就可以返回响应给主库了、SqlThread会读取中继日志的最新内容,并顺序执行该日志中的SQL事件(连接上主库,主库会把binlog发送给从库)

mysql分库分表:一致性Hash(解决数据二次全量迁移散列的问题,一致性hash只影响迁移的相邻节点,注意热点节点要进行虚拟节点多节点扩散)

mysql删除记录:是打个delete标记,并没有真正删,是由后台线程purse在定时处理,删记录表空间不缩小(防页移动产生的随机io),清碎片得手动重建表并迁移。

mysql在线数据迁移:

mysql锁:行锁、表锁、间隙锁、next-key lock、自增锁、意向共享锁(读)、意向排他锁(写),当加行锁时也会给表上一个意向锁(意向锁间不阻塞),意向锁的作用是当加表锁时无需去遍历整张表判断哪个记录有没有上锁,直接被意向表锁阻塞。

没有索引的列,当前读操作时,会加全表gap锁,生产环境要注意。

非唯一索引列,如果where条件部分命中(>、<、like等)或者全未命中,则会加附近Gap间隙锁。例如,某表数据如下,非唯一索引2,6,9,9,11,15。如下语句要操作非唯一索引列9的数据,gap锁将会锁定的列是(6,11],左开右闭,该区间内无法插入数据。

当一条sql的where上的条件没有索引的话会直接使用表锁,而不是行锁

自增锁: 表级锁,在insert完后就释放锁了,并不会伴随整个事务


mysql事务执行流程:开启事务、索引表记录加行锁、读数据到cache上、修改前的数据写undolog(持久化)、修改数据cache的的值、修改后的数据写redolog buffer、写binlog cache(满了写到binlog临时文件)、commit触发2pc(redologbuffer持久化到redologFile prepare状态 持久化binlogCache到binlogFile(释放临时资源binlog Cache redologFile commit状态)) 。

binlog 格式:Statement 格式存的是执行语句容易主从不一致,较少用、row格式会存两条数据,更新前和更新后的值 占空间,较常用,能保证主从一致。

redolog记的是对物理数据页的修改、顺序写。


当前读:读取的是最新版本,并且对读取的记录加锁,阻塞其他事务同时改动相同记录 select in share mode, select for update, update, delete, insert

快照读:单纯的select操作开启事务后第一个select语句才是快照读的地方,undolog和多版本并发控制MVCC实现

幻读:幻读是针对当前读的,在RR下真正解决幻读是Next-Key 锁,当前读下会用Next-key锁 锁住记录和条件的左右间隙,当有insert操作时会间隙锁阻塞。不能insert新数据,再在当前读时就不会出现幻读。

MVCC:MVCC是针对快照读的,RR级别开事务时只生成一次视图,RC每次select时都重新生成视图,活跃事务数组配合undolog读取比自己事务ID小或等于自己事务ID的快照记录。

快照图与当前读



mysql高可用:

MHA(MHA能做到在0~30秒之内自动完成数据库的故障切换操作,并且在进行故障切换的过程中,MHA能在最大程度上保证数据的一致性,以达到真正意义上的高可用,1、主要是基于半同步复制有一个slave里有最新的数据。2、当binlog来不及传送时会尝试登陆主库传送binlog,当binlog传送的时间过长 全中断半同步复制转为异步复制,这时磁盘上会遗留很多未复制的binlog,会导致从库拉起成主库后数据丢了。这个是用在服务没挂的情况)

MHA:MySQL 服务挂了,但是可以从服务器拷贝二进制。但如果硬件宕机或者 SSH 不能连接,不能获取到最新的 binlog 日志,如果复制出现延迟,会丢失数据。使用 MySQL5.5 的半同步复制,可以大大降低数据丢失的风险。MHA 可以和半同步复制结合起来。如果只有一个 Slave 已经收到了最新的二进制日志,MHA 可以将最新的二进制日志应用于其他所有 Slave 服务器上,保持数据一致性。最新版 0.56 版本,增加了支持 GTID 的功能,建议在 MySQL5.6 及之后版本使用。MySQL5.5建议使用管理节点版本 0.55,数据节点 0.54。

(所谓主从复制拖后半同步转为异步原理)另外,在半同步复制时,如果主库的一个事务提交成功了,在推送到从库的过程当中,从库宕机了或网络故障,导致从库并没有接收到这个事务的Binlog,此时主库会等待一段时间(这个时间由rpl_semi_sync_master_timeout的毫秒数决定),如果这个时间过后还无法推送到从库,(主从同步延时过长)那MySQL会自动从半同步复制切换为异步复制,当从库恢复正常连接到主库后,主库又会自动切换回半同步复制。

MMM (由于MMM无法完全的保证数据一致性,{因为备主挂了后,活主把数据同步给从库后,启动备主,不巧活主挂了,此时备主数据落后于从库},所以MMM适用于对数据的一致性要求不是很高,但是又想最大程度的保证业务可用性的场景)

b+树扩缩容方式:

每个中间节点都至少包含ceil(m/2)个孩子,最多有m个孩子。无论插入多少元素要始终保持最大元素在根节点当中。

1)若为空树,创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。

2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入记录。插入后,若当前结点key的个数小于等于m-1,则插入结束。否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第3步。

3)针对索引类型结点:若当前结点key的个数小于等于m-1,则插入结束。否则,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第3步。


B+树:

m阶B+树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树),阶数m同时限制了叶子结点最多存储m-1个记录。

所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data) 。为所有叶子结点增加了一个链指针

B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data在一起,则无法区间查找。

假设主键为bigint类型,InnoDB 的bigint占用8个字节,指针占用6个字节,8+6=14,所以我们可以得出,一个page能存放的指针个数为16k/(8+6)约等于1170

B树 :

所有键值分布在整颗树中(索引值和具体data都在每个节点里);

任何一个关键字出现且只出现在一个结点中;

搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);

在关键字全集内做一次查找,性能逼近二分查找;


B树和
B+树的最大区别 在于范围查询时的过程与性能B+树适用于范围查找:B树要中序遍历不断的进行“回溯”过程,会带来较多的随机
IO,B+树链表一直Next就行了能顺序IO。

B+树用链表往下找就行了



redis-mysql 一致性 (延迟双删)

分布式锁 跳表 脑裂


Redis事务操作:(mutli exec最好就同一key)、lua原子操作

string:有点像golang的slice 动态字符串(字符数组[]buf,len长度,free 数组buf剩余空间)

list:双向链表

set:长度小于512用inset(可以理解为数组),长度大于512用 hashtable

zset组成:(字典(dict)+多级链表(zskiplist),dict用于member找score(zscore指令), 多级链表用于score范围查找)

ziplist编码:是一个经过特殊编码的双向链表,它的设计目标就是为了提高存储效率。当zset保存的元素数量小于128个,所有元素的长度小于64字节 用ziplist

redis惊群 redsi缓存消失 高并发下所有请求打到数据库,用分布式锁防等redis缓存有数据

redis主从同步操作:redis主从同步是异步同步的,当主库挂了,哨兵会找一个最优的从库当主库( 1:从库优先级、2:从库复制进度、3:从库 ID 号,一般优先都一样、所以是先找复制进度最快的从库拉起当主库,减少数据不一致的损失)

redis接入新从库时,先rdb全量同步,写操作放缓冲区增量同步(replBacklogBuffer环形数组,Slave在同步掉线时不用再全局同步,可以在原来的位置继续同步),

redis持久化:RDB(阻塞只发生在fork子进程阶段) 、AOF(时时fsync、只写页缓存(write)、时时write但每秒fsync)、4.0后新增混合持久化(aof rewrite 的时候就fork子进程做rdb持久化把 rdb的内容写到 aof 文件开头,以前的aofrewrite要aof重写缓冲区做增量追加)

开启混合存储模式后 aof 文件加载的流程如下:

aof 文件开头是 rdb 的格式, 先加载 rdb 内容再加载剩余的 aof

aof 文件开头不是 rdb 的格式,直接以 aof 格式加载整个文件


redis哨兵模式: 高可用流程,单哨兵监测到并转为主观下线,通知其他哨兵,N/2+1哨兵主观下线转客观下线 ,主库下线,哨兵们发起投票raft由谁成为leader进行选主(1:从库优先级、2:从库复制进度、3:从库 ID 号,一般优先级一样,找复制进度最快的减少数据不一致)

redis-cluster模式 : 高可用流程,某个节点主观下线 通知其他节点,过半主观下线则客观下线。然后各个主节点去故障的从节点进行选举投票找出最合适的从节点替换成主节点(和哨兵一样,也是选复制进度快的)。

redis分布式限流:全局性和本地性 像golang的groutine的全局队列和P的本地队列。

redis分布式限流之发票服务器:这种方案的思想是建立在Redis令牌桶方案的基础之上的。如何解决每次取令牌都伴随一次网络开销,该方案的解决方法是建立一层控制端,利用该控制端与Redis令牌桶进行交互,只有当客户端的剩余令牌数不足时,客户端才向该控制层取令牌并且每次取一批。

redis的过期策略: 会将每个设置了过期时间的 key 放入到一个独立的字典中,以后会定时遍历这个字典来删除到期的 key。除了定时遍历之外,它还会使用惰性策略来删除过期的 key,所谓惰性策略就是在客户端访问这个 key 的时候,redis 对 key 的过期时间进行检查,如果过期了就立即删除。定时删除是集中处理,惰性删除是零散处理。

分布式锁:删除锁时的唯一值判断,防锁被其他线程删除

缓存雪崩:大面积缓存同时过期

缓存击穿:缓存突然消失 全打到数据库

缓存穿透:数据库没有这条记录,缓存里没有,数据库里也没有,所有访问直穿数据库,一直在刷。设置空值一段时间,或用布隆过滤器:bitmap。

redis渐进式rehash :新开一个2倍的哈希表,将rehashindex的值设置为0,在rehash期间,每次对字典执行增删改查,还会顺带将ht1哈希表在rehashindex(桶)上的所有键值对rehash到ht2,当rehash工作完成以后,rehashindex的值+1,随着字典操作的不断执行,ht0的所有键值对都会被rehash到ht2,将rehashindex的值设置为-1,表示rehash操作结束。 渐进式rehash采用的是一种分而治之的方式,将rehash的操作分摊在每一个的访问中,避免集中式rehash而带来的庞大计算量。




CAP理论

分布式Id:雪花算法 64位 第1位不用,41位毫秒级时间戳,10位工作机器ID(可自定义同步到etcd里),12位步长。趋势递增:99.999%情况是顺序写IO,0.001%的情况是随机写IO

mysql全同步复制 cp系统 ,mysql半同步复制 ap系统


cap理论的应用:强一致性强调的是强一致性读,写响应返回后其他请求立马去读能读到最新值



分布式事务可以ap(最终一致),也可以cp(强一致 加锁同步完成才参访问) ,ca(没有分布式,单点)

ap : 放弃强一致,追求分区容错性和可用性,mysql redis kafka 主从同步,异步同步 最终一致 。

cp : 数据库主从同步,全同步,从库加锁锁定,同步完成了从库才能访问,同步的过程从库不能对外提供服务。在网络分区的情况下强调强一致性读。所有设计是为了一致性,当发生网络分区时,为了保证一致性,是不可用的。如:etcd ,zk

etcd 分布式强一致算法,过半follower同步完成才返回,​ 放弃可用性,追求一致性和分区容错性,我们的zookeeper其实就是追求的强一致,又比如跨行转账,一次转账请求要等待双方银行系统都完成整个事务才算完成,如果后面的某个节点挂了,必然返回失败,只要转账成功,立马去读一定读到最新的值。

ca :无多机器网络隔离 单机







linux指令:

awk 是逐行处理文本(awk处理超大文件,大文件模糊查询正则匹配),不会占据大量内存,而且 awk 执行效率也挺高,可以用来处理超大型文件。

listof 显示进程已打开文件数

natstat 网络状态相关查询


高级数据结构:

基数树(radix 压缩前缀树):


动态负载均衡原理

后端服务动态更新计算得出后的权值

动态更新加权轮询的权值

然后按加权轮询去负载均衡

重试有好几种情况

1. fastfail

2. sleep重试 解决闪断

3. 批量扫描重试,解决最终一致性, 支付常见

4. mq排队+ack重试,解决丢失,以及同一个对象需要时序问题

5.面试问题:买家和卖家分表各自要查询,把公共部分独立出来垂直分表维护一份


TCP的滑动窗口与大文件散片上传的优缺点

监控系统 : 分治思想 各区域子数据中心收集服务器信息(服务器上报,每秒一次) 总中心:区域中心再把收集到的数据一同发给总中心(每5秒一次)


下表总结了若干Linux下的工具: