Veröffentlicht am

之前也有订阅draveness的博客跟着学习，这次抽时间把为什么设计系列文章再温习总结一遍，知识点常读常新吶！

为什么TCP需要三次握手

RFC793-Trannsmission Control Protocol文档中定义的TCP连接：用于保证可靠性和流控制机制的信息，包括socket、序列号及窗口大小。

The raliability and flow control mechanisms described above require that TCPs initialize and maintain certain status information for each data stream. The combination of this information, including sockets,sequence numbers, and windows sizes, is called a connection.

所以建立TCP连接就是要对上述的三种信息达成共识，连接中的socket是由互联网地址标志符和端口号组成，窗口大小主要用来做流量控制，最后的序列号是用来追踪通信发送的数据包序号，接收方可以通过序列号向发送方确认某个数据包成功接收。

因此问题转换成，为什么需要通过三次握手才可以初始化socket、sequenceNum、windowSize？

  • 通过三次握手才能阻止重复历史连接的初始化；
  • 通过三次握手才能对通信双方的初始序列号进行初始化；

历史连接

假设只有两次握手，发送方一旦发出建立连接的请求后就没法撤回请求，如果网络较差时，发送方多次连续发出建立连接请求。如果只通信两次那么接收方只能选择接受或拒绝，它并不清楚这一次请求是由于网络拥堵而早就过期的连接。

因此TCP选择三次握手来建立连接，并在连接中引入RST这一控制信息，接收方收到请求会将发送方发送的SEQ+1发送给对方，这时由发送方判断当前连接是否是历史连接：

  • 如果是历史连接，即SEQ过期超时，那么发送方会直接发送RST控制消息终止这一次连接；
  • 反之，发送方就会发送ACK控制消息，通信双方成功建立连接；

初始序列号

TCP需要在不稳定的网络构建一个可靠的传输层，在不稳定网络下可能存在：1）数据包被发送方多次重复发送；2）数据包在传输中被路由或者节点丢失；3）数据包到达接收方的顺序不正确。

为了解决这些问题，TCP协议在数据包中加入了序列号字段，支持：1）接收端去重；2）发送方在对应数据包未被ACK时重发；3）接收方根据序列号对数据包重排序。

TCP连接双方要获取初始序列号，需要向对方发送SYN控制消息并携带自己期望的初始化SEQ，对方收到后通过ACK控制消息一次SEQ+1来确认。

A-> SYN,SEQ=n->B ; B->ACK,SEQ=n+1->A; B->SYN,SEQ=m->A; A->ACK,SEQ=m+1->B。 其中中间两次可以将ACK+SYN合并发送，将四次减少为三次通信。

使用更多的通信次数交换相同的信息是可以实现的，三次是满足建立连接所需的最小次数。

为什么DNS使用UDP

实际上DNS不仅使用了UDP还使用了TCP，DNS查询类型不仅包含A记录、CNAME记录等常见查询，还有AXFR类型的特殊查询，这种特殊查询需要用于DNS区域传输，其作用是在多个命名服务器之间快速迁移记录，对数据准确性由有强烈的要求，由于查询返回的响应比较大，所以会使用TCP传递数据包。

UDP协议在过去的几十年都是DNS主要使用的协议，每次DNS查询都会直接向命名服务器发送UDP数据包。常见的DNS查询数据包都非常小，如果使用TCP的话建立连接需要三次通信，传输～130字节的数据，销毁连接需要4次通信，传输～160字节的数据。再考虑到实际场景中DNS解析可能会递归地与多个命名服务器通信，加倍放大了TCP协议在额外开销上的劣势。

现在网络设计中，我们不仅遇到了IPV4即将无法分配的情况，还需要引入DNSSEC等机制保证DNS查询和请求的完整性以及传输安全。导致DNS需要处理的数据包越来越大，理论上一个UDP数据包大小最多可达64KB，实际生产环境下数据包大于MTU（1500字节）时，数据包就会被分片传输、丢弃，部分网络甚至会拒绝处理包含EDNS选项的请求。导致UDP协议的DNS不稳定。

此时TCP可以非常好的解决这个问题，通过序列号和重传机制保证消息不重不漏，且建立连接和销毁连接的额外开销在大数据包面前可忽略不计。

为什么TCP协议有性能问题

TCP在设计之初没有考虑到现今复杂的网络环境，在地铁或火车上信号断断续续其实本质就是TCP协议造成的。

底层数据传输协议在设计时必须要对带宽利用率和通信延迟进行权衡和取舍，TCP选择了充分利用带宽，为流量而设计，期望在尽可能短的时间内传输更多的数据。

网络通信中，从发送方发出数据到收到来自接收方的确认，总时长称为往返时延。 RTT，Round-Trip Time。

弱网环境下影响TCP性能有以下几个因素：

  • TCP拥塞控制算法会在丢包时主动降低吞吐量；（首要原因）
  • TCP三次握手增加了数据传输的延迟和额外开销；
  • TCP的累计应答机制导致了数据段的传输；

每个TCP连接都会维护一个拥塞控制窗口CongestionWindow，决定了一次并发发送多少数据包。除了cwnd之外TCP连接双方都有一个rwnd接收窗口。在TCP连接开始时双方都不知道对方的rwnd大小，需要动态的估算机制改变传输的速度。

客户端能同时最大传输的数量时min（swnd，rwnd），初始大小时TCP_INIT_CWND。通过慢启动阈值slow start threshold（ssthresh）来决定：

  • < ssthresh, 使用慢启动，发送方每收到一个响应ACK，拥塞窗口大小就+1（即每个RTT时间内加倍）

  • ssthresh, 使用拥塞避免算法，每收到一个ACK，拥塞窗口大小就+1，当丢包时ssthresh设置为拥塞窗口的一半

重传机制： TCP传输可靠性时通过序列号和接收方的ACK来保证的，当TCP传输一个数据段时，它会将该数据段的副本放到重传队列并开启计时器。1）如果发送方收到ACK响应，从重传队列中删除；2）如果在计时器到期之间都没收到ACK则会重发该数据段。

TCP ACK的意思是指当前数据段之前的所有数据段都已经被接收和处理。一旦之前有一个数据包没有接收，之后的所有数据段即使接收到了也不会响应，超时时都会重传，在弱网环境下会导致大量的带宽浪费。

为了缓解上述问题，快重传技术当接收方收到乱序的数据段后，就会立刻连续发送三个ACK触发发送方的重传。

为什么UDP头只有8个字节

UDP协议头中只包含四个字段：源端口、目的端口、长度、校验码，其中每个字段16bit，所以总共8字节。其中长度是协议头和数据长度的总和，校验码使用IP首部、UDP首部和数据报中数据进行计算，接收方可以通过校验码进行验证数据的准确性。

UDP协议底层IP网际协议负责数据包在主机间的传输；UDP协议的首部端口号用于定位处理数据的具体进行并转发数据。UDP本质只起到定位具体进程的作用。

虽然UDP和TCP都有端口号概念，但两者不在一个命名空间，因为可以同时使用相同的端口号。

为什么TCP/IP协议会拆分数据

  • IP协议分片传输过大的数据包Packet，避免物理设备限制
  • TCP协议分段传输过大的数据段Segment，保证传输性能

在IP协议层不同的设备传输数据前会先确定一个IP数据包大小上限，即最大传输单元MTU Maximum transmission Unit。由整个链路上MTU最小的物理设备决定。（一般1500字节）

Path MTU Discovery算法：

  • 向目的主机发送IP头带DF控制位=1的数据包，Don’t Fragment不分片
  • 路径上的网络设备根据数据包大小和自己的MTU做不同的决定：
    • 数据包 > MTU，就会丢弃数据包，并返回一个包含该设备MTU的ICMP消息
    • 数据包 < MTU，就会继续向目的主机传递数据
  • 源主机收到ICMP消息后，不断使用新的MTU发送IP数据，直到数据包到达目的主机。

数据包分片时第一个数据包中包含UDP协议的相关信息，后续的都不包含，因此如果丢包整个UDP数据都无法组装。

TCP协议中引入了最大分段大小Max Segment Size，MSS，即TCP数据段能够携带的数据上限。正常情况下MSS=MTU-40，是操作系统内核层面的限制，通信双方会在三次握手时确定。

TCP协议之所以能够不重不漏按序传输，因为它会通过IP协议的MTU计算出MSS，并根据MSS分段避免IP协议对数据包进行分片。

为什么流媒体直播延迟高

流媒体直播从音视频的采集和编码到解码和播放设计了非常长的链路，需要途径主播端、流媒体服务器、观众端。在冗长的采集和分发流程中，不同过程都会通过一系列的技术保证直播的质量，为了保证可靠性、降低系统带宽而使用的手段共同造成了直播高延迟的问题。

  • 音视频使用的编码格式决定了客户端只能从特定帧开始解码；
  • 音视频传输使用的网络协议切片大小决定了客户端接收数据的间隔
  • 服务器和客户端为了保证用户体验和直播质量预留缓存

为什么HTTPS需要7次握手+9倍延迟

Netscape在1994年设计了HTTPS协议，使用安全套接字层SocketLayer，SSL，保证数据传输的安全。随着传输层安全协议TransportLayerSecurity TLS的发展，目前已经使用TLS取代了废弃的SSL协议。

HTTPS从发送方发出到接收响应需要经过4.5 RTT：

  • TCP协议三次握手建立TCP连接；（TCP快启策略使用存储在客户端的TFO cookie快速建立连接，可以减少通信次数）
  • TLS协议四次握手建立TLS连接；
  • HTTP协议，客户端发出请求，服务端发回响应。

其中TLS1.2建立过程如下：（1.3通过优化协议降低到1RTT）

  • 客户端向服务器发送client hello消息，携带客户端支持的协议版本、加密算法、压缩算法和一个客户端生成的随机数；
  • 服务端收到客户端的信息后；
    • 向客户端发送server hello消息，携带选择特定的协议版本，加密方法，会话ID，服务端生成的随机数；
    • 向客户端发送certificate消息，包含证书支持的域名、发送方和有效期信息；
    • 向客户端发送server key Exchange消息，传递公钥及签名信息；
    • 向客户端发送可选的certificateRequest，验证客户端证书；
    • 向客户端发送server hello done消息，通知服务器已经发送了全部消息；
  • 客户端收到消息后，验证证书
    • 向服务器端发送client key exchange消息，包含使用服务端公钥加密后的随机字符串
    • 向服务器发送change cipher spec消息，通知服务器后面的数据段要加密；
    • 向服务器发送finish消息，包含加密后的握手信息；
  • 服务器端收到消息后
    • 向客户端发送change cipher spec消息，通知客户端后面的数据段会加密传输
    • 向客户端发送finish消息，验证客户端的finish消息并完成TLS握手
      HTTP3使用基于UDP和QUIC协议进行握手，将TCP和TLS握手过程结合起来，把7次握手减少到了3次。

为什么TCP有粘包问题

粘包并不是TCP协议造成的，而是因为应用层协议设计者对TCP协议的错误理解，忽略TCP协议的定义并且缺乏设计应用层协议的经验。

  • TCP协议是面向字节流的协议，它可能会组合或者拆分应用层协议的数据
  • 应用层协议没有定义消息的边界，导致数据的接收方无法拼接

Nagle算法：通过减少数据包的方式提高TCP传输性能的算法，因为网络带宽有限，它不会降小的数据块直接发送到目的主机，而是会在本地缓冲区中等待更多待发送的数据，这种批量发送数据的策略虽然会影响实时性和网络延迟，但是能降低网络拥堵并减少额外开销。

当应用层使用TCP协议传输数据时，实际待发送的数据先写到了TCP协议的缓冲区，如果用户开启了Nagle算法，那么协议会等待缓冲区数据超过MSS最大数据段，或者上一个数据段被ACK时才会发送。

这样导致应用层多次写入的协议被合并或拆分发送，当接收方接收后应用层无法拆分和重组。 为了解决此问题，可以通过在应用层协议中基于长度或者终结符进行处理，或者基于特定的规则，如JSON数据。

UDP消息是有边界的，上限的65536，但一半都会被路径MTU限制。所以不会出现粘包问题。

为什么TCP协议有TIME_WAIT状态

TCP常见的关闭连接过程：

  • 当客户端没有待发送数据时，会想服务器端发送FIN消息，之后自己进入FIN_WAIT_1状态；
  • 服务器端收到客户端的FIN消息后，会进入到CLOSE_WAIT状态，并向客户端发送ACK消息。客户端收到ACK消息后会进入到FIN_WAIT_2状态；
  • 当服务器端没有待发送的消息后，服务器端会向客户端发送FIN消息；
  • 客户端接收到FIN消息后，进入TIME_WAIT状态并向服务器端发送ACK消息，服务器收到后进入CLOSED状态；
  • 客户端等待两个最大数据段生命周期的时间后也进入CLOSED状态。 MaxSegmentLifetime，MSL

TIME_WAIT仅在主动断开连接的一方出现，被动断开连接的一方会主动进入CLOSED状态。TCP需要TIME_WAIT状态和需要等待2MSL再CLOSED的原因一样：

  • 防止延迟的数据段被其他使用相同源地址、源端口号、目的地址、目的端口号的TCP连接收到；
  • 保证TCP连接的远程被正确关闭，即等待被动关闭的连接的一方收到FIN对应的ACK消息

阻止延迟数据段 ： 每个TCP数据都包含唯一的序列号，这个序列号保证TCP协议的可靠性和顺序性。为了保证新TCP连接的数据段不会和还在网络中传输的重复，TCP在分配新数据号之前需要至少静默1MSL。

TIME_WAIT等待2MSL是考虑到网络中可能存在来自发起方的数据段，这些数据段被服务器处理后又要返回响应给客户端。

保持连接关闭 ： 如果客户端等待时间不长，当服务器端还没有接收到ACK消息时，客户端就与服务器重新建立连接，客户端重新发送的SYN请求会收到服务器端RST消息，连接建立被终止。

如果客户端等待足够时间：1）服务器正常收到了ACK消息并关闭当前连接；2）服务器没收到ACK消息，重新发送FIN关闭连接并等待新的ACK。 所以只要客户端等2MSL时间，连接就会正常关闭，保证了数据传输的可靠性。

在某些场景下60s的等待时间难以接受，高并发场景下可能会产生大量的TIME_WAIT状态的TCP连接。可以通过使用net.ipv4.tcp_tw_reuse选项，通过TCP的时间戳选项允许内核重用处于TIME_WAIT状态的TCP连接。

为什么MAC地址不需要全球唯一

MAC：Media Access Control address，是分配给网络接口控制器的唯一标志符，它会在网络段中充当网络地址使用。 48位一般前半部分是组织标志符，后面是地址，需要在IEEE官方购买。

机构分发地址段并由设备商保证地址唯一的方式就是为了保证全世界所有硬件的网络地址唯一，但实际操作中是无法严格保证的，而且我们也不需要：

  • 不同操作系统上，我们都可以通过软件直接修改网卡的MAC地址；
  • 只需要保证一个局域网内的MAC地址不重复，网络就可以正常工作。 （因为交换机可以从数据帧的源地址学次到设备的MAC地址并插入本地缓存，跨局域网需要网络层的IP协议所以链路层地址重复影响不大）

为什么IPV6难以取代IPV4

  • NAT技术很大程度上缓解IPV4地址短缺问题；
  • IPV6协议并没有在设计时考虑和IPV4兼容问题；
  • 更细粒度的管控IPV4地址并回收闲置资源；

为什么集群需要Overlay网络

  • 云计算集群内、跨集群或者数据中心间的虚拟机和实例的迁移比较常见；
  • 单个集群中的虚拟机规模可能非常大，大量MAC地址和ARP请求会为网络设备带来巨大的压力；
  • 传统的网络隔离技术VLAN只能建立4096个虚拟网络，公有云以及大规模的虚拟化集群需要更多的虚拟网络才能满足网络隔离的需求。

目前K8S官方支持最大集群为5000节点，如果每个节点都只包含一个容器，这对于内部的网络设备其实没有太大的压力。但是在实际情况下集群中可能包含几万甚至几十万个容器，当某个容器向集群中发送ARP请求时，所有容器都会收到带来极高的网络负载。

使用VxLan搭建的Overlay网络中，网络会将虚拟机发送的数据重新封装成IP数据包，这样网络之需要知道不同VTEP的MAC地址，可以将MAC地址表项中的几十万条数据降低到几千条，ARP请求也只会在集群的VTEP之间扩散，远端的VTEP将数据拆包后也仅会在本地广播，不影响其他VTEP。大大降低了核心网络设备的压力。

网络隔离：同一个物理集群可能会被拆分成多个小块分配给不同的租户tenant，因为二层网络的数据帧会进行广播，出于安全考虑需要将这些不同的租户进行隔离。传统的网络隔离会使用虚拟局域网技术VLAN，其使用12位bit表示虚拟网络ID，上限是4096个。对于大规模集群来说远远不够，VxLAN会使用24bit的VNI表示虚拟网络个数，1677w+个虚拟网络能满足数据中心多租户网络隔离的需求。

为什么Redis选择单线程模型

Redis作为一个内存服务器，需要处理很多来自外部的网络请求，它使用IO多路复用机制同时监听多个文件描述符的可读和可写状态。Redis4.0之后的版本，在执行一些命令时会使用主处理线程之外的其他线程，如UNLINK、FLUSHALL、ASYNC、FLUSHDB ASYNC等非阻塞的删除操作。

单线程模型： Redis从一开始选择单线程模型主要考虑：1）使用单线程模型可维护性高，方便开发和测试；2）使用单线程模型也能并发处理客户端的请求；3）Redis中绝大多数操作的性能瓶颈都不是CPU。

Redis在删除超大键值对时并不能在几ms时间内处理完，可能需要在释放内存空间上消耗更多的时间。这样会阻塞待处理的任务影响redis可用性。释放内存空间的操作可以在后台线程异步执行，即UNLINK命令的实现原理，将键从元数据中删除，真正的删除操作会在后台异步执行。

为什么mysql使用B+树

首先MySQL和B+树没有直接关系，主要是因为mysql的默认存储引擎innodb。除了innodb之外mysql还支持多种存储引擎，如MyISAM等。

对于innodb来说，无论表中的数据主键索引还是辅助索引最终都会使用B+树来存储数据，其中前者在表中会以的方式存储，后者会以 的方式存储。所以后者查询时往往需要回表操作。

  • Innodb需要支持的场景和功能需要在特定查询上拥有较强的性能；
  • CPU将磁盘上的数据加载到内存需要花费大量的时间，B+树称为非常好的选择。

和hash对比：使用hash可以达到O（1）时间的查询，但是在处理范围查询或者排序时性能会非常差，只能进行全表扫描。使用B+树能够保证数据按照键的顺序进行存储，查询性能O（logN）也可接受。
和B树对比： 计算机以页为单位加载内存，页大小都是4KB。当我们需要在数据库中查询数据时，CPU会发现当前数据在磁盘而不在内存中，这时就会触发IO操作将数据加载到内存中进行访问，数据的加载都是以页为单位进行加载的，将数据从磁盘读取到内存中成本非常大，普通的非SSD磁盘需要经过队列、寻道、旋转以及传输等过程，大概需要花费10ms左右时间。B树会在非叶子结点中存储数据，B+树所有数据都是存储在叶子节点中。当一个表底层是B树时，我们总是要从根节点向下遍历子树查找满足条件的数据行，这引入了大量随机IO。而B+树所有数据都存储在叶子节点，且叶子节点通过指针链接，因此可以大量节省磁盘IO时间。

为什么Redis快照需要子进程

RDB和AOF是Redis为我们提供的持久化工具，其中RDB就是Redis的数据快照。RDB每隔一段时间都会对Redis服务中当下的数据集进行快照，除了Redis的配置文件设置间隔之外，还可以使用SAVE、BGSAVE命令。

  • SAVE在执行时会直接阻塞当前的线程，Redis是单线程的，所以SAVE命令会直接阻塞来自客户端的所有其他请求。
  • BGSAVE在后台生成快照，即首先fork子进程，子进程会执行将内存数据保存到RDB文件这一过程，不影响Redis主线程响应客户端请求。

通过fork生成的父子进程会共享包括内存空间在内的资源。fork函数并不会带来明显的性能开销，尤其是内存大量拷贝，是通过写时复制来完成，将真正的拷贝推迟到需要的时候。

fork函数返回0时，意味当前进程是子进程；反之表明是父进程，返回的是子进程的pid。fork后的父子进程会运行在不同的内存空间中，当fork发生时两者的内存空间有着完全相同的内容，对内存的写入和修改、文件映射都是独立的，两个进程不会相互影响。

为什么数据库会丢失数据

人为错误： 造成数据丢失的首要原因，如腾讯云数据丢失事件，虽然起因是硬件故障，但最终导致数据完成性受损的还是运维人员的不当操作。1）正常数据搬迁流程默认开启数据校验，开启后可以有效发现并规避源数据异常，但运维人员为了加速搬迁任务，违规关闭了数据校验；2）正常数据搬迁后源仓库要保留24h用于异常恢复，但运维人员为了尽快降低仓库使用率违规对源仓库进行了数据回收。因此尽量将操作标准化自动化流程处理，降低人为干预带来的风险，敬畏生产环境，谨慎的在生产环境执行一切操作。

硬件故障： 磁盘硬件使用时间足够长很有可能发生损坏，因此我们需要数据冗余的方式保证磁盘在发生不可修复读错误时能够恢复磁盘数据。Redundant Array of Independent Disk， RAID独立冗余磁盘阵列时一种能够将多个物理磁盘组合成一个逻辑磁盘的数据存储虚拟化技术，增加冗余并提高性能。

实现复杂： 除了持久化特性之外，数据库可能还需要提供ACID、BASE的保证，有些数据库还提供分片、副本、以及分布式事务等复杂功能，这些功能的引入也增加了数据库系统的复杂性。随着程序复杂性的增加，出现问题的可能性也随之增长。

为什么MySQL的自增主键不单调也不连续

MYSQL中默认的AUTO_INCREMENT属性在多数情况下可以保证主键的连续性，但是在实际使用中会遇到两个问题：1）记录的主键并不连续；2）可能会创建多个主键相同的记录。

  • 较早版本的MySQL将AUTO_INCREMENT存储在内存中，实例重启后会根据表中数据重置该值。（在8.0之后每次计数器的变化都会写入redo log，并在检查点存储在引擎私有的系统表中）
  • 获取AUTO_INCREMENT时不会使用事务锁，并发的插入事务可能会出现字段冲突导致插入失败。要想保证主键的连续性需要串行地执行插入语句。 （事务回滚会导致之前的id失效）

为什么Linux需要虚拟内存

利用中间层对资源进行更合理地调度充分提高资源的利用率并提供统一的抽象。

主存是比较稀缺的资源，虽然顺序读取只比磁盘快1个量级，但是随机读取确实磁盘的100，000倍，充分利用内存的随机访问速度是改善程序执行效率的有效方式。

操作系统以页为单位访问内存，当进程发现需要的数据不在内存中，MMU（内存管理单元）会将数据以页的形式加载到内存。

  • 虚拟内存可以利用内存起到缓存的作用，提高进程访问磁盘的速度；
  • 虚拟内存可以为进程提供独立的内存空间，并引入多层的页表结构将虚拟内存翻译成物理内存。简化程序链接、加载过程并通过动态库共享内存；
  • 虚拟内存可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统安全性；

因为主内存空间有限，当主内存不包含可使用的空间时，OS会从选择合适的物理内存页驱逐回磁盘，为新的内存页让出位置。缺页中断和页面替换技术都是页面调度算法，充分利用内存资源作为磁盘的缓存以提高程序的运行效率。

四层页表结构 ：实现虚拟地址到物理地址的转换。OS使用低12位（正好4K）作为页面的偏移量，剩下36位分为四组分别表示当前层级在上一层级的索引，所有虚拟地址都可以用上述的多层页表查找对应的物理地址。因为有多层的页表结构可以用来转换虚拟地址，所以多个进程可以通过虚拟内存共享物理内存。Redis的fork子进程时的写时复制就是利用了虚拟内存这一特性，fork时实际上只复制了父进程的页表。

为什么每层页表结构只能负责9位虚拟地址的寻址？ 64位虚拟地址占8B的大小，所以一个页表可以有4K/8B=2^9项。

64位虚拟内存在操作系统中需要多少层的页表结构才能寻址？ 12+9*5=57，因此需要5层。

为什么系统调用会消耗较多资源

为什么Linux默认页是4KB

4KB时一个历史遗留问题，在上世纪80年代确定的4KB一直保持到今天，是过去在特定场景下做出的权衡：

  • 过小的页面大小会带来较大的页表项增加寻址时TLB的查找时间和额外开销；
  • 过大的页面会浪费内存空间，造成内存碎片，降低内存的利用率。

除了内存利用率之外，较大的内存页也会增加内存拷贝时的额外开销，因为Linux写时复制，在多个进程共享同一块内存时，当其中一个进程修改了共享的虚拟内存会触发内存页的拷贝。这时操作系统内存页越小，写时拷贝带来的额外开销也会越小。

为什么CPU访问硬盘很慢

机械硬盘HDD和固态硬盘SSD是最常见的硬盘，SSD中随机访问4KB数据所需要的时间是访问主存的1500倍，机械硬盘的寻道时间是访问主存的100，000倍。

  • CPU需要通过I/O操作访问外部存储的数据，编程IO、中断驱动IO和DMA几种方式都会带来额外开销并占用较多的CPU时间；
    • 编程IO：CPU会负责全部的工作，向IO设备中写入数据后轮询设备状态等待完成后继续写入。占用全部CPU资源，造成计算资源的严重浪费。
    • 中断驱动IO：将一部分操作交给IO设备更高效，设备会在闲置时主动发起中断暂停当前进程并保存上下文，OS执行IO设备的中断处理程序。
    • DMA： CPU会一次将缓冲区的数据全部堵到DMA控制器中，DMA控制器负责将数据写入IO。解放CPU并减少中断次数，执行速度比CPU更慢。
  • 机械硬盘会通过机械结构访问其中存储的数据，每一次硬盘的随机IO都需要执行队列、寻道、旋转和转移数据几个过程，大约需要消耗10ms时间。

为什么NUMA会影响程序的延迟

  • NUMA引入本地内存和远程内存，CPU访问本地内存的延迟会小于访问远程内存；
  • NUMA的内存分配和内存回收策略结合时会可能导致Linux的频繁交换分区SWAP，影响系统的稳定性。

为什么HugePages可以提升数据库性能

2MB一般时HugePages的默认大小，在arm64和X86_64的架构上甚至支持1GB的大页面。

虽然HugePages的申请方式和默认的内存相差不多，但是它实际上是操作系统单独管理的特殊资源，K8S页会认为大页是不同于内存的独立资源。

  • HugePages可以降低内存页面的管理开销；
    • 减少内存中的页表层级，降低页表占用；
    • 更高的缓存命中率，CPU有更高的几率直接在TLB中获取对应的物理地址；
    • 减少获取大内存的次数
  • HugePages可以锁定内存，禁止操作系统的内存交换和释放（预先分配的资源，哪怕是内存不足时也不会被swap到磁盘）；

为什么Linux需要swapping

  • Swapping可以直接将进程中使用较少的页面换出内存，立刻给正在执行的进程分配内存；
  • Swapping可以将进程中的闲置页面换出内存，为其他进程未来使用内存做好准备；

系统内存不足时可以立即触发OOM杀掉进程，但是Swapping为系统管理者提供了另一种选择，利用磁盘交换空间避免程序直接退出。以降低服务质量的代价换取服务的部分可用性。

K8S中要求禁用Swapping，该OOM的时候就kill掉，迁移到其他机器上运行。

Veröffentlicht am

本文主要收录关于系统设计相关的问题学习笔记。

设计分布式ID生成器

现实中很多业务都有生成唯一ID的需求，如用户、微博、订单等，这些ID往往会作为数据库的主键要保证全局唯一。数据库会在该字段上做聚集索引，即此字段会影响各条数据在物理存储上的顺序。

ID要尽可能短来节省内存，同时使得索引效率更高。基本上64位能满足绝大多数场景。但通常并不需要这么多，可以根据业务需求预估ID最大值，然后选取合适的bit来表示ID。

查询时往往有排序分页需求，需要给每个数据添加一个时间字段，并在其上建立普通索引。但是普通索引访问较慢，所以尽量使得ID按时间粗略有序来节省这个字段。

  • 全局唯一
  • 按时间粗略有序
  • 尽可能短

一些生成ID的常用方法：

  • UUID: mongoDB自动给每条数据赋值ObjectId，保证不会重复，就是采用了UUID的算法。 ObjectID=4bytes timestamp + 3bytes 机器ID + 2bytes 进程ID + 3 bytes计数器。 优点是每个机器都可以独立产生ID，天然分布式，缺点是ID太长占用内存且查询效率低。
  • 多台mysql服务器： 组成一个高性能的分布式发号器，通过轮询均衡的将请求发送给N个mysql中的任意一个，然后返回一个ID。Mysql不需要把所有的ID都记录，只需要记录最大MAX_ID即可。更新使用REPLACE INTO删除旧值，增加新值。缺点是ID不是严格递增的
  • Snowflake: twitter的开源项目，专门生成ID。核心算法是0+ 41bit时间戳 + 13bit机器ID+10bit自增序列号。 41位时间戳可以表示～70年，10bit支持1023台机器，序列号支持1ms产生4095个id

设计短网址服务

当前互联网的网页总数大概是45亿，超过了2^32，但远远小于64位整数的上限值。微博的短网址服务用的是长度为7的字符串，可以看做是62位进制数，最大能表示62^7个网址，远大于45亿。

因此使用长度不超过7的字符串，由大小写字母+数字共62个字母组成。

一般来说一个长网址在不同地点不同用户等情况下生成的短网址应该不一样，这样在后端数据库可以更好的进行数据分析。入包含生成该网址的用户名、所在网站、http头的user agent信息等，因此长短网址最好是一对多映射。

通过hash计算短网址不可避免存在冲突，因此最好采用上节所使用的分布式ID生成器的方式如雪花算法来实现。

存储时以短网址作为key，长网址作为value存储在数据库中。可以使用传统的关系型数据库mysql postgresql，也可以使用任意一个分布式kv数据库，如redis，levelDB等。

重定向使用的是302临时重定向，因为如果使用301永久重定向的话搜索引擎会直接展示真实地址，导致我们无法根据短网址解析需要的用户信息等。

为了防止黑客网络攻击，短时间内向服务器发送大量请求导致耗光ID。

  • 可以采用限制单日IP的请求总数，超过阈值直接拒绝服务。
  • 同时可以用redis缓存，存储长网址->ID的映射，仅存储一天以内的数据并用LRU机制进行淘汰。

定时任务调度器

priorityBlockingQueue+Polling

  • 用java.util.concurrent.PriorityBlockingQueue来作为优先级队列，同时保证了线程安全。如果使用java.util.PriorityQueue需要实现ReentrantLock用锁把队列保护起来
  • 生产者通过while true循环生成随机任务进入队列
  • 消费者起一个线程通过while true每隔几秒检查队列，有任务则取出来执行

轮询的缺点就是间隔时间不好把握，间隔长任务无法及时处理，间隔短耗费CPU。

PriorityBlockingQueue+时间差

将方案一中的while true改成查看堆顶的元素但不取出，如果任务过期则取出，反之计算一个时间差，sleep该时间差。

虽然消除了轮询的缺点，但是该方案同时也有自身缺陷。如果计算时间差之后又有新的小于该时间差的任务加入队列，会导致处理不及时。

DelayQueue

改进后的priorityBlockingQueue，把计算时间差并让消费者等待该时间差的功能继承进了队列。消费者不需要关心时间差的事情，直接在while true循环中不断take即可。新的元素put时会唤醒所有等待的消费者线程。

为了避免多个消费者竞争，采用leader/follower模式，当一个线程时leader时它只需要一个时间差，其它follower无限等待。多个消费线程用take方法取任务，内部先加锁然后每个线程去peek头结点，如果leader不为空说明已经有线程在取，当前消费者无限等待。如果leader为空则设置leader为当前消费者并让其等待指定的时间。

需要注意的是take方法中会释放first=null，为了避免内存泄漏。如线程A获取first然后设置leader为A并让A等待一段时间；线程B同时进来获取first进入阻塞无限期等待，此时B持有first引用。A等待一定时间被唤醒后获得对象成功，出队后该对象应该被GC。但是此时B仍然持有此对象GC链路可达所以无法回收。极端情况下B无限休眠那么本该回收的对象就不能被GC销毁从而导致内存泄漏。

JDK中的ScheduledThreadPoolExecutor类似

时间轮 HashedWheelTimer

循环队列，每时间轮精度走一格。每个任务都需要一个字段记录圈数，每转一圈就-1，减到0就立刻取出。 Netty中已经有实现，性能高，插入和删除都是O（1），Linux内核定时器就是采用这种方案。

分布式定时任务调度器可以采用Redis的Zset和RabbitMQ等

设计一个线程安全的hashmap

hashmap有两种解决冲突的方案：开放地址法和链表法。

  • 开放地址法，所有元素都在一个一维数组中，遇到冲突后按照一定规则向后探测。
    • 线性探测法：冲突后向后依次遍历，优点是计算速度快对CPU缓存友好，缺点是探测过程中会产生clustering现象，扎堆导致效率低下；
    • 二次探测法：通过一个i的二次函数计算，性能介于线性和双哈希之间；
    • 双哈希法：偏移量di由另外一个哈希函数计算
  • 链表法，开放一个定长数组，每个格子指向一个桶，对每个元素计算出哈希并取模，找到对应的桶并插入该桶。发生冲突的元素会处于同一个桶中。

JDK7和JDK8中的java.util.HashMap采用了链表法，将其改为线程安全有几下几个方案：

  • 所有public方法都加上synchronized，相当于一把全局锁，所有操作都要先获得锁。HashTable就是这样做的，性能低；
  • 由于每个桶逻辑上都是独立的，将每个桶加一把锁，如果两个线程访问不同的桶就不需要争抢一把锁。这个方案并发性比前者好，不过锁的个数太多也会有很大开销；
  • 锁分离技术，假设有1w个桶第二种方法就不适合，新建1w个ReetrantLock实例开销很大。可以将所有的桶均匀的划分为16个部分，每一部分成为一个segment，每个段上有一把锁。JDK7中的concurrentHashMap就是这个思路。
  • JDK8中concurrentHashMap的实现又有很大变化，在锁分离的基础上，大量利用了CAS指令。并在底层存储有一个小优化，在链表长度太长>8时，链表就转换为红黑树。增删改查效率提升，该hashmap的实现代码从jdk7的1500行增长到6000+行

最近一个小时内访问频率最高的10个IP

  • 实时输出
  • 当前小时向前1小时
  • QPS可能会达到10w/s

类似TopK，但是不需要Lossy Count或者Count-Min Sketch之类的算法。

QPS 10w/s，一小时大概有2^28.4个请求，可以在内存中建立3600个HashMap,放在一个数组中，每秒对应一个hashMap。IP为key出现的次数为Value，这样一小时最多有2^29个KV对，每个KV对占8字节，总内存大概时2^32字节，即4GB，单机可以储存。

同时建立一个大小为10的小根堆，用于存放当前出现次数最大的IP，堆顶是10个IP里频率最小的。每次新来一个请求将该秒中hashMap里对应的IP计数器增加1，并查询IP是否在堆里存在：

  • 不存在则把该IP在3600个HashMap的计数器加起来，与堆顶出现次数进行比较。大于则替换
  • 如果已经存在，把堆内该IP的计数器+1，并相应调整

此外需要一个后台常驻线程，每过1s就把最旧的那个HashMap销毁，并为当前1s新建一个HashMap，以此来维持一个一小时窗口

每次查询top 10 IP就把堆内元素返回即可。

为什么不用IP+时间作为key，单个HashMap存储？ 答：这样无法淘汰1小时前的数据，只能全量扫描删除；另外key字符串内存占用远大于int，导致单机无法满足。

KV存储引擎

LevelDB整体结构

内存随机读写甚至比硬盘的顺序读要慢，因此要尽量避免随机读写。 LevelDB采用一种SSTable的数据结构来实现，SSTable是一组按照key排序好的KV对，key和value都是字节数组。SSTable既可以存储在内存，也可以在硬盘，底层使用LSM Tree来存放有序的KV对。

  • MemTable。内存中的SSTable，新数据先写入此处，然后批量写入磁盘。
  • Log文件，写Memtable之前先写Log文件，用WAL方式，可以用来恢复数据。
  • Immutable MemTable，内存中的MemTable达到一定大小后就不再接收新的数据，产生新的memtable来接收。Immutable memTable随后会写入硬盘变成SST文件。
  • SSTable文件，文件尾部追加一块索引，记录key->offset,提高随机读的效率。有多层组成，每层中单个文件的容量成倍增长。
  • Manifest文件，记录SST文件不同level的分布，以及元信息
  • Current文件，当前manifest的文件名。

SST文件末尾的索引都要放在内存中，减少读索引时的一次IO；

所有读都要先看memtable，没有再查看内存中的索引。所有写都只能写到memtable，sst文件不可修改。定期把immutable memtable写入硬盘成为sst文件。定期对sst文件进行合并。删除通过追加tombstone值表示删除key，在定期合并sst时丢弃。更新通过追加新的kv到文件末尾，读取文件时新数据最先被读到。

memtable里的数据时按照key有序的，因此插入新数据时需要把kv插入到合适的位置来保证key的有序性。其底层核心数据是一个跳表。

数据流采样

当有一个无限的整数数据流，如何随机的从中抽取k个整数来？

k=1时只需要随机抽取一个样本出来：1）第一个整数到来时保存这个数；2）第2个整数到达时以1/2的概率使用这个整数替换第一个数；3）第i个整数到来时以1/i的概率使用第i个整数替换被选中的数。

当K>1时，需要随机采样多个样本，方法跟上面类似，把1变成K即可。

基数估计（Cardinality Estimation）

独立访客UniqueVisitor等数据流中不同元素个数的统计是基数估计问题。

  • HashSet，存在大数据场景下单机内存不足问题。
  • 通过bitmap不存储元素本身，假设知道不同元素的个数上限为N，开一个长度为N的bit数组，此方法缺点是bitmap的长度和实际基数无关而是与基数的上限有关，假设存在1亿基数需要12.5M的bitmap。
  • LinearCounting,选择一个哈希函数h结果服从均匀分布，开一个长度为m的bitmap初始化为0，数据流每来一个元素计算其哈希值并对m取模然后将该位置置1.查询时如果还有u个bit为0，则总数近似为-mlog（u/m），其中m由基数大小和容许误差决定，假设基数大约为n，允许误差为e，m>(e^t-t-1)/(et)^2,其中t=n/m
  • LogLog Counting， 均匀随机化，选取一个哈希函数h应用于所有元素，然后对哈希值进行基数估计。对每个哈希值从高到低找到第一个1出现的位置，取这个位置的最大值设为p，基数约为2^p。（通过分桶平均的思想来降低误差，相当于多次求平均）缺点是基数不大的情况下该计算方法误差很大。
    • 哈希碰撞可以忽略不计，即尽量避免冲突 * h结果均匀分布
    • 哈希后的结果是固定长度
  • HyperLogLog Counting，在LLC基础上进行优化，通过使用调和平均数替代几何平均数降低离群值的干扰，并加入分段偏差纠正。

频率估计

如何计算数据流中任意元素的频率？Frequency Estimation问题。

  • hashMap，存在单机内存无法存在的问题；
  • 数据分片+hashmap，通过多台机器来满足内存需求；
  • Count-Min Sketch，和布隆过滤器类似，优点是节约内存，缺点是对于出现次数较少的元素准确性较差；
    • 选定d个hash函数，开一个d*m的二维数组作为哈希表；
    • 对于每个元素，分别使用d个hash计算hash值，然后对m取余，在对应位置上增1。二维数组上的每个整数称为sketch；
    • 要查询某个元素的频率，只需要取出d个sketch，返回最小的那个。
  • Count-Mean-Min Sketch，进行了如下改进显著改善在长尾数据上的精确度。
    • 来一个查询，首先按照count-min sketch正常流程取出d个sketch；
    • 对每个hash函数，估算出一个噪音，噪音等于该行所有整数的平均值（除了被查询的元素）
    • 用该行的sketch-该行的噪音作为真正的sketch
    • 返回d个sketch的中位数

TopK 频繁项

寻找数据流中最频繁出现的k个元素，如微博热搜榜，访问网站次数最多的前10个IP地址等。

  • hashMap+Heap，用hashMap存放所有元素出现的次数，用小根堆存放目前出现过的最频繁的k个元素。数据量大时存在内存不足的情况。
    • 每次从数据流进来一个元素，如果hashmap中存在则把对应计数器+1，不存在则插入；
    • 在堆中查找该元素，如果找到则把堆中计数器+1并调整堆。反之将元素的次数和堆顶元素比较，如果大于则替换堆顶元素并调整堆。
  • 多机hashMap+Heap，hash分配，每个节点独立计算后再合并。
  • Count-Min Sketch + Heap，使用Count-Min Sketch代替hashmap保证内存使用。
  • Lossy Counting，近似算法，思想是出现频率高的元素不太可能-1后变为0，低频元素不断被清理出去，这样内存占用会保持在一个很低的水平。
    • 建立一个hashmap，用于存放每个元素的出现次数；
    • 建立一个窗口；
    • 等待数据流不断流进这个窗口，直到窗口满后统计每个元素出现的频率，统计结束后每个元素的频率-1，然后将出现次数为0的元素从hashmap中删除
    • 返回建立窗口循环执行

成员查询

给定一个无限的数据流和一个有限的集合，如何判断数据流中的元素是否在这个集合？

布隆过滤器：

  • 解决redis缓存穿透
  • 爬虫时过滤已经获取的网址
  • 垃圾邮件过滤

经过k个哈希函数计算该数据，返回K个计算出的hash值；将k个hash值映射到对应的K个二进制的数组下标；把数据下表对应位置置1。

查询时同样利用k个哈希函数计算数据对应的k个hash值，找到对应下标。如果存在一处元素值为0，说明该数据不在。反之则认为数据存在。

优点：1）存储二进制数据占用空间小；2）插入和查询速度快；3）保密性好，不存在原始数据。
缺点：1）两个不同数据计算的hash值相同存在误判可能。2）删除困难。

Guava实现的布隆过滤器将数据放在了本地，分布式场景不适合。此时可以使用redis封装好的Redisson。

范围查询

给定一个无限的整数数据流，如何查询在某个范围内的元素出现的总次数？如select count(key) where key >=left and key <= right;

可以利用计算频率时的方法Count-Min Sketch计算每个元素的频率，将指定范围内所有元素的sketch加起来就是范围内的元素总数了。 但是因为每个sketch都是近似值，多个近似值相加误差被放大。

解决方法就是使用不同分辨率的Count-Min sketch，第一个sketch每个格子存放单个元素的频率，第二个sketch每个格子存放两个元素的频率（把元素的hash值最低位bit去掉，即>>1），依次类推。

查找范围时，从粗粒度到细粒度找多个区间，不重不漏的完整覆盖区间，把相应的值加起来即可。

设计模式在外卖业务的应用

设计模式在外面业务中的实践

  • 面向对象设计模式七大基本原则

    • 开闭原则：OpenCloseP，对扩展开放对修改关闭
    • 单一职责原则：SingleResponsibleP，实现类要单一职责
    • 里氏代换原则：Liskov SubsitutionP，不要破坏继承体系
    • 依赖倒转原则：Dependency InversionP，面向接口编程
    • 接口隔离原则：Interface SegregationP，设计接口时要精简单一
    • 合成聚合复用原则：Composite/Aggregation Reuse P
    • 最少知识原则，迪米特法则， Least KnowledgeP，Law of Demeter， 指导降低耦合

  • 美团邀请用户返奖业务场景
    首先根据用户状态判断是否满足返奖，如果满足继续判断用户是新用户还是老用户，从而给予不同的奖励方案：

    • 新用户
      • 普通奖励（固定额度）
      • 梯度奖励（根据用户邀请人数给予不同奖励金额）
    • 老用户：根据老用户属性来计算返奖金额，为了评估不同的邀新效果，老用户也会存在多种返奖机制

考虑开闭原则，对于返奖流程保持封闭，对可能扩展的返奖规则进行开放。将返奖规则抽象为返奖策略。在DDD中返奖策略是一个值对象，通过工厂方式生产针对不同用户的奖励策略值对象。

返奖规则和设计模式实践

工厂模式：工厂方法模式和抽象工厂模式。定义一个用于创建对象的接口，让子类决定实例化哪个对象。工厂方法是一个类的实例化延迟到子类。
// 抽象的产品
public abstract class Product {
public abstract void method();
}
//定义一个具体产品
class ProductA extends Product {
@Override
public void method(){}
}
//抽象的工厂
abstract class Factory {
abstract Product createProduct(Class c);
}
//具体的工厂可以生产相同的产品
class FactoryA extends Factory {
@Overrid
Product createProduct(Class c) {
Product pro = (Product) Class.forName(c.getName()).newInstance();
return pro;
}
}

策略模式：定义一系列算法，将每个算法都封装起来，且支持互换。是一种对象行为模式
//定义一个抽象接口
public interface Strategy {
void strategyImplementation();
}

public class StrategyA implements Strategy {
  @Override
  public void strategyImplementation(){}
}

//封装策略，屏蔽高层模块对策略、算法的直接访问，屏蔽可能存在的策略变化
public class Context {
  private Strategy strategy = null;
  public Context(Strategy strategy) {
    this.strategy = strategy;
  }
  public void doStrategy(){
    strategy.strategyImplementation();
  }
}

工程实践：我们可以使用工厂模式生成不同的策略，同时使用策略模式来进行不同策略的执行。

//抽象策略
public abstract class RewardStrategy {
  public abstract void reward(long userId);
  public void insertRewardAndSettlement(long userId, int reward) {}; //更新用户信息及结算
}

//新用户返奖具体策略A
public class newUserRewardStrategyA extends RewardStrategy {
  @Override
  public void reward(long userId) {...} //具体计算逻辑
}
//老用户返奖具体策略A
public class oldUserRewardStrategyA extends RewardStrategy {
  @Override
  public void reward(long userId) {...}
}
//抽象工厂
public abstract class StrategyFactory<T> {
  abstract RewardStrategy createStrategy(Class<T> c);
}
//具体工厂创建具体的策略
public class FactoryRewardStrategyFactory extends StrategyFactory {
  @Override
  RewardStrategy createStrategy(Class c) {
    RewardStrategy product = null;
    try {
      product = (RewardStrategy) Class.forName(c.getName()).newInstance();
    } catch (Exception e) {}
    return product;
  }
}

public class RewardContext {
  private RewardStrategy strategy;
  public RewardContext(RewardStrategy strategy) {
    this.strategy = strategy;
  }
  public void doStrategy(long userId) {
    int rewardMoney = strategy.reward(userId);
    insertRewardAndSettlement(long userId, int reward) {
      insertReward(userId, rewardMoney);
      settlement(userId);
    }
  }
}

public class InviteRewardImpl {
//返奖主流程
public void sendReward(long userId) {
    FactorRewardStrategyFactory strategyFactory = new FactorRewardStrategyFactory();  //创建工厂
    Invitee invitee = getInviteeByUserId(userId);  //根据用户id查询用户信息
    if (invitee.userType == UserTypeEnum.NEW_USER) {  //新用户返奖策略
        NewUserBasicReward newUserBasicReward = (NewUserBasicReward) strategyFactory.createStrategy(NewUserBasicReward.class);
        RewardContext rewardContext = new RewardContext(newUserBasicReward);
        rewardContext.doStrategy(userId); //执行返奖策略
    }if(invitee.userType == UserTypeEnum.OLD_USER){}  //老用户返奖策略，... 
  }
}

通过这两个模式的组合，当我们系统需要增加一种返奖策略时，只需要实现RewardStrategy接口即可，无需考虑其他的改动。

返奖流程和设计模式实践

当受邀人在下单后，返奖后台接收到下单记录，此时邀请人进入返奖流程。

  • 在接收到订单消息后，用户进入带校验状态，此时对订单进行返奖规则校验； （是否使用红包，红包是否在有效期，订单是否满足一定金额）
  • 若校验通过，用户进入预返奖状态，并放入延迟队列。若校验未通过，用户进入不返奖状态，结束流程；
  • T+N天后，处理延迟消息，若用户没有对订单进行退款，则进入待返奖状态。若用户退款，则进入不返奖状态，结束流程；
  • 执行返奖，若成功进入完成状态，结束流程。反之，进入待补偿状态；
  • 待补偿状态的用户会由任务定期触发补偿机制，直到返奖成功，进入完成状态，保障流程结束。

状态模式：当一个对象内在状态改变时，允许其改变行为，这个对象看起来像是改变了类。

//定义一个抽象的状态类
public abstract class State {
  Context context;
  public void setContext(Context context) {
    this.context = context;
  }
  public abstract void handle1();
  public abstract void handle2();
}
//定义状态A
public class ConcreteStateA extends State{
  @Override
  public void handle1() {} //本状态下必须要处理的事情
  @Override
  public void handle2() {
    super.context.setCurrentState(Context.ConcreteStateB); //切换到状态B
    super.context.handle2()；// 执行状态B的任务
  }
}
//定义状态B
public class ConcreteStateA extends State{
  @Override
  public void handle2() {} //本状态下必须要处理的事情
  @Override
  public void handle1() {
    super.context.setCurrentState(Context.ConcreteStateA); //切换到状态A
    super.context.handle1()；// 执行状态A的任务
  }
}
//定义一个上下文管理环境
public class Context {
  public final static ConcrestateA concreteStateA = new ConcreteStateA();
  public final static ConcreStateB concreteStateB = new ConcreateStateB();

  private state currentState;
  public state getCurrentState(){return currentState;}

  public void setCurrentState(State currentState){
    this.currentState = currentState;
    this.currentState.setContext(this);
  }
  public void handle1() { this.currentState.handle1();}
  public void handle2() { this.currentState.handle2();}
}
//定义client执行
public class Client {
  public static void main(String[] args) {
    Context context = new Context();
    context.setCurrentState(new ConcrestateA());
    context.handle1();
    context.handle2();
  }
}

工程实践：

//返奖状态执行的上下文
public class RewardStateContext {
  private RewardState rewardState;

  public void setRewardState(RewardState currentState) {this.rewardState = currentState;}
  public RewardState getRewardState() {return rewardState;}
  public void echo(RewardStateContext context, Request request) {
      rewardState.doReward(context, request);
  }
}
public abstract class RewardState {
  abstract void doReward(RewardStateContext context, Request request);
}
//待校验状态
public class OrderCheckState extends RewardState {
  @Override
  public void doReward(RewardStateContext context, Request request) {
    orderCheck(context, request);  //对进来的订单进行校验，判断是否用券，是否满足优惠条件等等
  }
}
//待补偿状态
public class CompensateRewardState extends RewardState {
  @Override
  public void doReward(RewardStateContext context, Request request) {
    compensateReward(context, request);  //返奖失败，需要对用户进行返奖补偿
  }
}
//预返奖状态，待返奖状态，成功状态，失败状态(此处逻辑省略)
//..
public class InviteRewardServiceImpl {
  public boolean sendRewardForInvtee(long userId, long orderId) {
    Request request = new Request(userId, orderId);
    RewardStateContext rewardContext = new RewardStateContext();
    rewardContext.setRewardState(new OrderCheckState());
    rewardContext.echo(rewardContext, request);  //开始返奖，订单校验
    //此处的if-else逻辑只是为了表达状态的转换过程，并非实际的业务逻辑
    if (rewardContext.isResultFlag()) {  //如果订单校验成功，进入预返奖状态
      rewardContext.setRewardState(new BeforeRewardCheckState());
      rewardContext.echo(rewardContext, request);
    } else {//如果订单校验失败，进入返奖失败流程，...
      rewardContext.setRewardState(new RewardFailedState());
      rewardContext.echo(rewardContext, request);
      return false;
    }
    if (rewardContext.isResultFlag()) {//预返奖检查成功，进入待返奖流程，...
      rewardContext.setRewardState(new SendRewardState());
      rewardContext.echo(rewardContext, request);
    } else {  //如果预返奖检查失败，进入返奖失败流程，...
      rewardContext.setRewardState(new RewardFailedState());
      rewardContext.echo(rewardContext, request);
      return false;
    }
    if (rewardContext.isResultFlag()) {  //返奖成功，进入返奖结束流程，...
      rewardContext.setRewardState(new RewardSuccessState());
      rewardContext.echo(rewardContext, request);
    } else {  //返奖失败，进入返奖补偿阶段，...
      rewardContext.setRewardState(new CompensateRewardState());
      rewardContext.echo(rewardContext, request);
    }
    if (rewardContext.isResultFlag()) {  //补偿成功，进入返奖完成阶段，...
      rewardContext.setRewardState(new RewardSuccessState());
      rewardContext.echo(rewardContext, request);
    } else {  //补偿失败，仍然停留在当前态，直至补偿成功（或多次补偿失败后人工介入处理）
      rewardContext.setRewardState(new CompensateRewardState());
      rewardContext.echo(rewardContext, request);
    }
    return true;
  }
}

投放系统中的设计模式

投放业务就是要在资源位中展示符合当前用户的资源。首先运营人员会配置需要展示的资源，以及对资源进行过滤的规则。

为了实现对过滤规则的解耦，对单个规则值对象修改封闭，对规则集合组成的过滤链开放。在资源位过滤时引入责任链模式。

责任链模式：多个对象都有机会处理请求，避免了请求的发送者和接受者之间的耦合。将这些对象连成一条链，并沿着传递该请求，直到有对象处理它为止。

//定义一个抽象的handler
public abstract class Handler {
  private Handler nextHandler;
  private int level;
  public Handler(int level) {
    this.level = level;
  }
  public setNextHandler(Handler handler) {
    this.nextHandler = handler;
  }
  public final void handleMessage(Request request) {
    if (level == request.getRequestLevel()) {
      this.echo(request);
    } else {
      if (this.nextHandler != null) {
        this.nextHandler.handleMessage(request);
      } else {
        System.out.Println("end");
      }
    }
  }
  public abstract void echo(Request request);
}
//定义一个具体handlerA
public class HandlerA extends Handler {
  public Handler(int level) {
    super(level);
  }
  @Override
  public void echo(Request request) {
    System.out.println("我是处理者1,我正在处理A规则");
  }
}
...
//客户端实现
class Client {
  public static void main(String[] args) {
    HandleRuleA handleRuleA = new HandleRuleA(1);
    HandleRuleB handleRuleB = new HandleRuleB(2);
    handleRuleA.setNextHandler(handleRuleB);  //这是重点，将handleA和handleB串起来
    handleRuleA.echo(new Request());
  }
}

工程实践：

//定义一个抽象的规则
public abstract class BasicRule<CORE_ITEM, T extends RuleContext<CORE_ITEM>>{
  //有两个方法，evaluate用于判断是否经过规则执行，execute用于执行具体的规则内容。
  public abstract boolean evaluate(T context);
  public abstract void execute(T context) {
}

//定义所有的规则具体实现
//规则1：判断服务可用性
public class ServiceAvailableRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {
  @Override
  public boolean evaluate(UserPortraitRuleContext context) {
    TakeawayUserPortraitBasicInfo basicInfo = context.getBasicInfo();
    if (basicInfo.isServiceFail()) {
      return false;
    }
    return true;
  }
  @Override
  public void execute(UserPortraitRuleContext context) {}
}
//规则2：判断当前用户属性是否符合当前资源位投放的用户属性要求
public class UserGroupRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {
  @Override
  public boolean evaluate(UserPortraitRuleContext context) {}

  @Override
  public void execute(UserPortraitRuleContext context) {
    UserPortrait userPortraitPO = context.getData();
    if(userPortraitPO.getUserGroup() == context.getBasicInfo().getUserGroup().code) {
      context.setValid(true);
    } else {
      context.setValid(false);
    }
  }
}
//规则3：判断当前用户是否在投放城市，具体逻辑省略
public class CityInfoRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {}
//规则4：根据用户的活跃度进行资源过滤，具体逻辑省略
public class UserPortraitRule extends BasicRule<UserPortrait, UserPortraitRuleContext> {} 

//我们通过spring将这些规则串起来组成一个一个请求链
<bean name="serviceAvailableRule" class="com.dianping.takeaway.ServiceAvailableRule"/>
<bean name="userGroupValidRule" class="com.dianping.takeaway.UserGroupRule"/>
<bean name="cityInfoValidRule" class="com.dianping.takeaway.CityInfoRule"/>
<bean name="userPortraitRule" class="com.dianping.takeaway.UserPortraitRule"/>

<util:list id="userPortraitRuleChain" value-type="com.dianping.takeaway.Rule">
    <ref bean="serviceAvailableRule"/>
    <ref bean="userGroupValidRule"/>
    <ref bean="cityInfoValidRule"/>
    <ref bean="userPortraitRule"/>
</util:list>

//规则执行
public class DefaultRuleEngine{
  @Autowired
  List<BasicRule> userPortraitRuleChain;
  public void invokeAll(RuleContext ruleContext) {
    for(Rule rule : userPortraitRuleChain) {
      rule.evaluate(ruleContext)
    }
  }
}

责任链模式最重要的优点就是解耦，将客户端与处理者分开，客户端不需要了解是哪个处理者对事件进行处理，处理者也不需要知道处理的整个流程。在我们的系统中，后台的过滤规则会经常变动，规则和规则之间可能也会存在传递关系，通过责任链模式，我们将规则与规则分开，将规则与规则之间的传递关系通过Spring注入到List中，形成一个链的关系。当增加一个规则时，只需要实现BasicRule接口，然后将新增的规则按照顺序加入Spring中即可。当删除时，只需删除相关规则即可，不需要考虑代码的其他逻辑。从而显著地提高了代码的灵活性，提高了代码的开发效率，同时也保证了系统的稳定性。

Veröffentlicht am

基础篇

消息队列本质：一发一存一消费。

最原始模型包含两个关键词：消息和队列。生产者将消息传递给队列的容器，然后再从容器中取出消息，转发给消费者。

常用的消息队列产品都在最原始模型上做了扩展，同时提出新名词：topic，partition，queue等

  • 队列模型：允许多个生产者往同一队列发送消息，但是如果有多个消费者，实际上是竞争关系，一条消息只能被一个消费者接收，读完即删除。

  • 发布-订阅模型：如果需要一份消息数据分发给多个消费者，每个消费者都要求收到全量消息。可行的方案是为每个消费者创建单独的队列，让生产者发送多份。同一数据复制多份浪费空间。为解决此问题就演化出发布订阅模型。存放消息的容器变为topic主题，订阅者在接收消息之前需要先订阅主题。每个订阅者都可以收到同一topic下的全量消息。和队列模型不同在于消息是否可以被多次消费。

MQ应用场景：系统解耦，异步通信，流量削峰。初次之外还可以延迟通知，最终一致性保证，顺序消息和流式处理等。

引入MQ之后之前一次RPC变成两次，生产者只和队列耦合，无需知道消费者的存在。多了中间节点队列进行消息转储，将同步变成异步。

如电商中订单业务中订单支付场景：支付成功后，需要更新订单状态，更新用户积分，通知商家新订单，更新推荐系统中用户画像等。 引入MQ之后只需要关注其最主要的流程：更新订单状态。其他全部交给MQ来通知。

  • 系统解耦：后续业务再扩展也不涉及核心流程的稳定性，降低维护成本；
  • 异步通信：其他步骤变成异步执行，减少订单支付的整体耗时，提升订单系统吞吐量；
  • 流量削峰：队列转储消息，对于超负载场景可以使用MQ作为漏斗进行限流；
  • 顺序投递，延时消费：利用队列本身的顺序性满足顺序消费场景，叠加定时任务完成消息的延时消费；

如何设计MQ：

  • 简单版：两次RPC+消息转储。利用成熟的RPC框架Dubbo或Thrift实现发消息和读消息接口；消息放在本地内存中，利用jdk自带的ArrayBlockingQueue
  • 适用生产环境：如何满足高性能、高可靠等非功能性需求。
    • RPC通信：直接利用成熟的RPC框架，不需要考虑服务注册与发现、负载均衡、通信协议、序列化方式等；也可以基于netty做底层通信，用zookeeper、Euraka等做注册中心，然后自定义通信协议，或者基于AMQP标准化的MQ协议来实现。后者定制化能力和优化空间更大。
    • 高可用：Broker高可用只需要保证可水平扩展集群部署，通过服务自动注册与发现、负载均衡、超时重试机制、发送和消费消息时的ack保证；存储高可用有两个思路1）kafka的分区+多副本模式，要考虑分布式下数据复制和一致性方案，类似zab、raft协议，并实现自动故障转移;2）用主流的DB、分布式文件系统、带持久化能力的kv系统；
    • 存储设计：追加写日志文件+索引文件的方式，索引设计可以考虑稠密或稀疏，查找消息可以利用跳表、二分查找等，还可以通过OS的页缓存，zero-copy技术提升磁盘读写；
    • 消费关系管理：基于Zookeeper，Apollo等配置中心管理
    • 高性能：Reactor网络IO模型，业务线程池，生产者批量发送，broker异步刷盘，消费端批量拉取等

Kafka神秘面纱

Kafka是linkedin内部孵化项目，设计用于处理1）运营活动场景：记录用户的浏览、搜索、点击、活跃度等行为；2）系统运维场景：监控CPU、内存、请求耗时等性能指标。两种数据都属于日志范畴，热点是数据实时生产，数据量大。Apache Kafka 是一个开源的分布式流处理平台。

演化过程：

  • 将一份消息分发给多个消费者，每个消费者获取全量的消息。即广播
  • 并非每个消费者都需要全部数据，MQ不理解消费语义无法分类投递。将难题抛给生产者，发送消息时进行逻辑分类，即利用topic
  • 多个消费者都对同一个topic感兴趣，如果采用传统的队列模式，取出消息后立即删除，另一个消费者就拿不到。很自然想到当topic增加消费者时复制数据队列。但是复制成本会导致性能问题。
  • 将所有消息进行持久化存储，由消费者自己各取所需，只需要传递一个消息的offset即可。将复杂的消费问题转嫁给消费者，使得kafka本身复杂度降低，为高性能和高扩展性打下基础。

kafka架构设计

海量消息存储问题就是kafka架构设计中最大的难点。容易想到方案：对数据进行分片存储。

常见分片存储场景：1）数据库中分库分表；2）缓存设计中分片集群架构；类似拆分思想在HDFS，ES中都能看到。

kafka也采用partition分区进行水平拆分。分区路由可以简单理解为hash函数。分区规则设定合理可以将消息均匀分配到不同分区中。

消费者和partition相结合做到并行处理需要满足两个基本诉求：1）广播消费能力：同一个topic可以被多个消费者订阅，一条消息可以被消费多次；2）集群消费能力：当消费者本身也是集群时，每条消息只能发送给集群中一个消费者进行处理。

kafka引入消费组的概念，组间进行广播消费，组内进行集群消费。并且限制每个 Partition 只能由消费组中的一个消费者进行消费。

存储可扩展、消息并行处理都解决后，对于高可用设计，kafka集群利用多副本机制实现自动故障转移能力。同一分区不同副本保存相同消息，副本之间一主多从，leader负责读写请求，follower只负责和leader同步，当leader故障时有机会被选举为新的leader并对外提供服务。

Veröffentlicht am

CPU寄存器

  • 通用寄存器： rax,rbx,rcx,rdx,rsi,rdi,rbp,rsp,r8-r15 64位，可以作为32/16/8位寄存器使用，需要换个名字，如eax，ax，al/ah
  • 程序计数器： rip，存放下一条即将执行的指令地址 64位
  • 段寄存器：fs和gs。一般用来实现线程本地存储TLS。 16位

内存

一个内存单元是1字节，任何大于一个字节的变量在内存中都存储在相邻连续的的几个内存单元之中。存储模式有两种（存储模式和CPU相关）：

  • 大端：数据的高字节保存在内存的低地址中，低字节保存在高地址中
  • 小端：数据的高字节保存在内存的高地址中，低字节保存在低地址中

函数调用栈

进程在内存中的布局： 从高到低 内核->栈->堆->全局数据->代码->系统保留区

  • 代码：能被CPU执行的机器代码（指令）和只读数据（如字符串常量），程序加载后该区域大小不变化
  • 全局数据：程序的全局变量，静态变量（C中有Go不包含），程序加载后大小不变
  • 堆： 程序运行时动态分配的内存，由内存分配器管理。大小随程序运行而变化。C++代码必须小心处理内存分配和释放，GO有垃圾回收器。

栈主要用来：保存函数局部变量；向被调用函数传参；返回函数的返回值；保存函数的返回地址（指从被调用函数返回后调用者应该继续执行的指令地址）

位于栈内存中的函数局部变量所使用的内存随函数调用而分配，随函数返回后自动释放。rsp寄存器始终指向栈顶，rbp寄存器指向函数栈帧的起始位置。

即便是同一个函数，每次调用都会产生一个不同的栈帧，因此对于递归要考虑是否存在栈溢出的风险。

汇编指令

AT&T格式的汇编指令格式：

  • 寄存器名前要加%作为前缀
  • 有2个操作数的，第一个为源操作数，第二个为目的操作数。
  • 立即操作数前面$前缀
  • 寄存器间接寻址的格式为offset(%register)，offset为0时省去。 括号也省去时表示直接寻址

常用指令：

  • add/sub
  • call/ret call首先会把rip寄存器的值入栈，然后设置rip值为目标地址。ret指令从被调用函数返回调用函数，实现原理是把call入栈的返回地址返回弹出给rip寄存器
  • jmp/je/jle/jge 跳转指令
  • push/pop指令，自动修改rsp寄存器
  • leave 指令没有操作数，一般放在函数尾部ret指令之前，用于调整rsp和rbp

GO汇编语言

引入了几个没有任何硬件寄存器对应的虚拟寄存器：

  • FP虚拟寄存器: 主要用来引用函数参数，指向调用者的栈帧
  • SB寄存器：保存程序地址空间的起始地址。即代码区的起始地址。主要用来定位全局符号

操作码： 寄存器操作码没有%前缀，且寄存器名称用大写
操作数宽度： 寄存器名称没有位数之分，操作码带后缀B(8) W(16) D(32) Q(64)

TEXT runtime·gogo(SB), NOSPLIT, $16-8

  • TEXT runtime·gogo(SB) 在代码区定义一个名称为gogo的全局函数，函数属于runtime包
  • NOSPLIT 编译器不要在此函数中插入栈是否溢出的代码
  • $16-8 函数栈帧大小为16字节，参数和返回值一共占用8字节。

从汇编层面看函数调用的实现原理

函数调用过程:

  • 参数传递：GCC编译器的C、C++代码一般通过寄存器传递参数，在AMD64 linux平台，gcc约定函数调用前面6个参数分别通过rdi rsi rdx r10 r8 r9传递。GO语言通过栈传递给别调用函数，最后一个参数最先入栈。参数在调用者的栈帧中，被调用函数通过rsp加一定的偏移量来获取参数；
  • call指令负责把执行call指令的rip寄存器入栈 （函数返回地址）
  • GCC通过rbp+偏移量的方式来访问局部和临时变量。GO编译器则通过rsp寄存器加偏移量的方式
  • ret指令负责将call指令入栈的返回地址出站给rip，从而实现从被调用函数返回后继续执行
  • GCC使用rax寄存器返回函数的返回值，GO语言使用栈返回函数调用的返回值。

main函数
push %rbp
mov %rsp，%rbp
sub $0x20,%rsp 栈给函数局部变量和临时变量预留32字节栈空间

普通函数开始
push %rbp
mov %rsp，%rbp

leaveq 相当于：
mov %rbp，%rsp
pop %rbp

系统调用

系统调用是指使用类似函数调用的方式调用操作系统提供的API。

用户代码调用操作系统API不是通过函数名调用，而是需要根据操作系统为每个API提供一个整型编号来调用。AMD64 Linux约定在系统调用时用rax寄存器存放该编号，同时约定使用rdi rsi rdx r10 r8 r9来传递前6个系统调用参数。

mov   0x10(%rsp),%rdi #第1个参数
mov   0x18(%rsp),%rsi #第2个参数
mov   0x20(%rsp),%rdx #第3个参数
mov   0x28(%rsp),%r10 #第4个参数
mov   0x30(%rsp),%r8  #第5个参数
mov   0x38(%rsp),%r9  #第6个参数
mov   0x8(%rsp),%rax  #系统调用编号 rax = 267，表示调用openat系统调用
syscall               #系统调用指令，进入Linux内核

操作系统线程及线程调度

C语言中一般使用pthread线程库，其创建的用户态线程其实就是Linux内核所支持的线程。和Go语言工作线程一样，都是由Linux内核负责管理和调度。

Go语言在操作系统线程之上又做了Goroutine，实现了一个二级线程模型。

  • 什么时候会发生调度？

    • 用户程序使用系统调用进入操作系统内核；
    • 硬件中断。硬件中断由操作系统提供，当硬件发生中断时，就会执行操作系统代码。其中比较重要的是时钟中断，这是操作系统发起抢占调度的基础。

  • 调度的时候会做哪些事情？
    操作系统把不同的线程调度到同一个CPU上运行，每个线程都会使用CPU的寄存器。所以操作系统把线程B调度运行时首先把之前的A线程所使用的寄存器值保存在内存。然后把保存在内存中的B线程的寄存器值放回CPU寄存器，接着线程B恢复之前状态运行。

线程调度时操作系统还需要保存指令指针寄存器rip以及与栈相关的rsp和rbp。所以恢复寄存器的值相当于改变的CPU下一条需要执行的指令，同时切换了函数调用栈。

因此可以对线程进行如下定义： 操作系统线程是由内核负责调度且拥有自己私有的一组寄存器值和栈的执行流。

线程本地存储及实现原理

TLS，其实就是存储线程私有的全局变量。 普通的全局变量在多线程中共享，而线程的私有全局变量是其私有财产，每个线程都有一个副本，线程对其修改只会修改到自己的副本。

int g = 0；
void* start(void* arg){
  printf("start, g[%p]: %d \n", &g, g)  // print start, g[0x601064] : 100
  g++;
  return NULL;
}
int main(int argc, char* argv[]) {
  pthread_t tid;
  g = 100;
  pthread_create(&tid, NULL, start, NULL); //start thread to run start()
  pthread_join(tid, NULL); // wait thread finish
  printf("main, g[%p]: %d \n", &g, g) // print main, g[0x601064] : 101
  return 0;
}

------------------------------------------
__thread int g = 0; 
void* start(void* arg){
  printf("start, g[%p]: %d \n", &g, g)  // print start, g[0x7f0181b046fc] : 0
  g++;
  return NULL;
}
int main(int argc, char* argv[]) {
  pthread_t tid;
  g = 100;  // => 0x0000000000400793 <+30>:movl   $0x64,%fs:0xfffffffffffffffc    fs段基址-4
  pthread_create(&tid, NULL, start, NULL); //start thread to run start()
  pthread_join(tid, NULL); // wait thread finish
  printf("main, g[%p]: %d \n", &g, g) // print main, g[0x7f01823076fc] : 100
  return 0;
}

子线程fs段基地址为0x7f36757c8700，g的地址为0x7f36757c86fc，它正好是基地址 - 4
主线程fs段基地址为0x7f3675fcb700，g的地址为0x7f3675fcb6fc，它也是基地址 - 4

gcc编译器（其实还有线程库以及内核的支持）使用了CPU的fs段寄存器来实现线程本地存储，不同的线程中fs段基地址是不一样的

goroutine简介

操作系统线程有两个问题：

  • 创建和切换开销过大： 都需要进入内核，存在性能消耗
  • 内存使用过大：内核在创建线程时都会默认为其分配一个较大的栈内存（虚拟地址空间），多数情况下用不了。栈内存空间创建后就不会变化，在某些场景下存在溢出风险。

用户态goroutine则相对轻量级：

  • 用户态，创建和切换无需进入内核，开销较小；
  • 启动时默认栈为2K，多数情况足够，不够还可以动态扩容和收缩。

goroutine建立在操作系统线程基础上，与操作系统线程实现了多对多的两级线程模型。对goroutine的调度就是程序代码按照一定的算法在适当的时候挑选合适的goroutine并放到CPU上运行的过程。

调度的实质同样也是，通过保存和修改CPU寄存器的值来达到切换线程 goroutine的目的。

为了实现需要引入一个数据结构来保存cpu寄存器的值以及goroutine的其他状态信息。在Go调度器源码中，这个数据结构是一个g的结构体，保存了goroutine的所有信息。一个实例对象对应了一个goroutine，调度器代码可以通过g对象来对goroutine进行调度。

仅仅有g结构体对象是不够的，至少还需要一个存放所有goroutine的容器。Go调度器引入schedt结构体，一方面保存调度器自身状态，另一方面还用来保存goroutine的运行队列。 因为每个Go程序中schedt结构体只有一个实例对象，共享的全局变量，每个工作线程都可以访问它，因此它拥有的运行队列为全局运行队列。

全局队列访问需要频繁加锁，因此调度器又为每个工作线程引入一个私有的局部goroutine运行队列。该局部队列被包含在p结构体的实例对象中。每个运行着go代码的工作线程都会与一个p结构体的实例对象关联在一起。

代表工作线程的是m结构体，每个工作线程都有唯一一个m结构体的实例对象与之对应。m结构体对象除了记录工作线程的诸如栈的起止位置、当前正在执行的goroutine以及是否空闲等状态信息，还通过指针维持着与p结构体的实例对象之间的绑定关系。

通过TLS，每个工作线程拥有各自私有的m结构体全局变量，因此能在不同的工作线程中使用相同的全局变量名来访问不同的m结构体对象。

for i = 0; i < N; i++ {
  create_os_thread(schedule)
}

ThreadLocal self *m //定义一个线程私有全局变量，一个指向m结构体对象的指针
schedule(){
  self = initm()
  if(self.p.runqueue is empty) {
    g = find_a_runnable_goroutine_from_global_runqueue()
  }else {
    g = find_a_runnable_goroutine_from_local_runqueue()
  }
  run_g(g)
  save_status_of_g(g)
}

程序入口 JMP _rt0_amd64(SB)， 这个符号中分别执行了下列步骤
TEXT _rt0_amd64(SB), NOSPLIT, $-8
MOVQ 0(SP), DI //argc
MOVQ 8(SP), SI //argv
JMP runtime.rt0_go(SB) //rt0_go函数完成了go程序启动时的所有初始化工作

初始化g0，g0主要作用是提供一个栈供runtime代码执行，这里主要对g0的几个与栈有关的成员进行初始化。 栈大约64K，SP-641024+104 ~ SP, 其中stackguard1，stackguard0，stack.hi均指向SP-641024+104， stack.hi指向SP

主线程和m0绑定，首先调用settls函数初始化主线程的TLS，把m0和主线程关联在一起。验证TLS功能是否正常，不正常直接abort退出程序。主线程通过get_tls可以获取g0，通过g0的m成员又可以找到m0

//把m0和g0关联起来m0->g0 =g0，g0->m =m0
// save m->g0 =g0
MOVQ CX, m_g0(AX) //m0.g0 = &g0
// save m0 to g0->m 
MOVQ AX, g_m(CX) //g0.m = &m0

初始化m0：接下来命令行参数处理完后调用osinit函数获取CPU核数量并保存在全局变量ncpu中。全局变量sched.maxmcount=10000，最多启动1w个工作线程。 mcommoninit将m0放入全局链表allm之中，确保GC不会自动回收。然后继续调用procresize创建和初始化p结构体对象。会创建指定个数（CPU核数和GOMAXPROCS决定）的p结构体对象，然后放到allp全局变量中。并把m0和allp[0]绑定在一起。

m0.p = allp[0]
allp[0].m = &m0

至此，m0，g0，和m需要的p完全关联在一起。

其中，procresize初始化allp流程如下

  • 使用make([]*p, nprocs)初始化全局变量allp
  • 循环创建并初始化nprocs个p结构体对象，并依次放入allp切片中
  • 把m0和allp[0]绑定在一起，即m0.p=allp[0],allp[0].m=m0
  • 把除了allp[0]之外的所有p放入全局变量sched.pidle空闲队列之中

创建main goroutine

schedinit完成调度系统初始化后，返回到rt0_go函数开始调用newproc()创建一个新的goroutine用于执行main函数。

newproc有两个参数，第二个参数fn是新建的goroutine将从这个fn函数开始执行，第一个参数是fn函数的参数以字节为单位的大小。

newproc是对newproc1的一个包装，主要获取fn函数第一个参数的地址，另一个使用systemstack函数切换到g0栈上（初始化场景本来就在g0，无需切换）

newproc1第一个参数fn，第二个参数是fn函数第一个参数的地址，第三个参数是fn参数以字节为单位的大小。其代码主要：从堆上分配一个g结构体对象newg，并为其分配一个2k的栈，并设置好栈成员。然后把newg需要执行的函数参数从newproc函数的栈拷贝到newg栈中。 然后对newg的sched成员初始化，该成员包含了调度器代码在调度goroutine到CPU运行时所必须的一些信息。其中sched的sp表示newg被调度运行时应该使用的栈的栈顶，pc成员表示当newg调度运行时从这个地址开始执行指令。

然而代码中newg.sched.pc被设置成了goexit函数地址＋１，即其第二条指令地址，而不是fn.fn

主要是因为gostartcallfn函数的处理，其首先从参数fc中提取出函数地址（初始化是runtime.main，然后调用gostartcall函数）。

gostartcall函数作用：1.调整newg的栈空间，把goexit函数的第二条指令地址入栈，伪造成goexit函数调用了fn，从而使fn执行完ret指令时返回到goexit函数执行最后的清理工作 2.重新设置newg.buf.pc为需要执行的函数的地址，即fn

newproc1函数最后设置了几个无关调度的成员变量，然后把newg状态改为_Grunnable，并放入运行队列。

调度main goroutine

mstart1首先调用save函数来保存g0的调度信息。（非常重要，是理解调度循环的关键点之一）

//getcallerpc()获取mstart1执行完的返回地址
//getcallersp()获取调用mstart1时的栈顶地址
save(getcallerpc(), getcallersp())

func save(pc, sp uintptr) {
  _g_ := getg()

  _g_.sched.pc = pc //再次运行时的指令地址
  _g_.sched.sp = sp //再次运行时到栈顶
  _g_.sched.lr = 0
  _g_.sched.ret = 0
  _g_.sched.g = guintptr(unsafe.Pointer(_g_))
  // We need to ensure ctxt is zero, but can't have a write
  // barrier here. However, it should always already be zero.
  // Assert that.
  if _g_.sched.ctxt != nil {
      badctxt()
  }
}

调度核心函数schedule()

func schedule(){
  _g_ := getg()
  var gp *g
  if gp == nil {
    //为了保证调度公平，每进行61次调度就优先从全局队列中获取goroutine
    if _g_.m.p.ptr().schedtick%61 == 0 && sched.runqsize > 0 {
      lock(&sched.lock)
      gp = globrunqget(_g_.m.p.ptr(),1) //从全局队列中获取1个goroutine
      unlock(&sched.lock)
    }
  }
  if gp == nil {
    gp, inheritTime = runqget(_g_.m.p.ptr())
    if gp != nil && _g_.m.spinning {
      throw("schedule: spinning with local work")
    }
  }
  //如果本地和全局都没有找到需要运行的，调用findrunnable从其他工作的线程运行队列中偷取，偷取不到则进入睡眠
  //直到获取到需要运行的goroutine之后findrunnable才返回
  if gp == nil {
    gp,inheritTime = findrunnable() //blocks until work is available
  }
  execute(gp, inheritTime) //切换到gp的代码和栈空间运行
}

func execute() {
  _g_ := getg() //g0
  casgstatus(gp, _Grunnable, _Grunning)
  _g_.m.curg = gp
  gp.m = _g_.m
  gogo(&gp.sched) //gogo完成从g0到gp真正的切换
}

execute函数的第一个参数gp即是需要调度起来运行的goroutine，这里首先把gp的状态从_Grunnable修改为_Grunning，然后把gp和m关联起来，这样通过m就可以找到当前工作线程正在执行哪个goroutine，反之亦然。

完成gp运行前的准备工作之后，execute调用gogo函数完成从g0到gp的的切换：CPU执行权的转让以及栈的切换。

gogo函数通过汇编编写，因为涉及寄存器及函数调用栈的切换，只能靠汇编指令来达成。

  • 把gp.sched的成员恢复到CPU的寄存器完成状态以及栈的切换；
  • 跳转到gp.sched.pc所指的指令地址（runtime.main）处执行

main函数工作流程：

  • 启动一个sysmon系统监控线程，该线程负责整个程序的gc、抢占调度以及netpoll等功能的监控，在抢占调度一章我们再继续分析sysmon是如何协助完成goroutine的抢占调度的；
  • 执行runtime包的初始化；
  • 执行main包以及main包import的所有包的初始化；
  • 执行main.main函数；
  • 从main.main函数返回后调用exit系统调用退出进程；

runtime.main是main函数的入口，通过schedule()->execute()->gogo()调用链的gogo函数中用汇编代码直接跳转过来的，所以不需要返回。

总结来说 从g0切换到main goroutine的流程：

  • 保存g0的调度信息，主要是保存CPU栈顶寄存器SP到g0.sched.sp成员之中；
  • 调用schedule函数寻找需要运行的goroutine，我们这个场景找到的是main goroutine;
  • 调用gogo函数首先从g0栈切换到main goroutine的栈，然后从main goroutine的g结构体对象之中取出sched.pc的值并使用JMP指令跳转到该地址去执行；
  • main goroutine执行完毕直接调用exit系统调用退出进程。

非main goroutine的调度及退出循环

非main gouroutine返回时直接返回goexit的第二条指令，该指令继续调用goexit1函数。goexit1函数通过mcall从当前运行的g2 goroutine切换到g0，然后在g0栈上调用和指定goexit0函数。

mcall函数首先从当前运行的g2切换到g0，包括保存当前g的调度信息，把g0设置到tls中，修改CPU和rsp寄存器使其指向g0的栈；然后以当前运行的g2位参数调用fn函数（此处为gexit0）。

mcall和gogo函数完全相反，gogo实现从g0切换到某个goroutine运行，而mcall从某个goroutine切换到g0来运行。两者代码相似，区别在于gogo切换goroutine时先切换栈，然后通过跳转指令从runtime代码切换到了用户goroutine代码。mcall则只切换了栈，原因在于mcall函数本身就是runtime代码。

从g2切换到g0之后，在g0栈上执行goexit0函数，完成最后的清理操作。把g的状态从_Grunning变为_Gdead，把g的一些字段清空为0，调用dropg函数解除g和m之间的关系。g->m=nil,m->currg=nil，把g放在p的free列表缓存起来方便下次创建g时快读获取，最后调用schedule再次调度

调度循环

schedule()->execute()->gogo()->g2()->goexit()->goexit1()->mcall->goexit0()->schedule()

一轮调度都是从调用schedule函数开始，经过一系列代码的执行到最后再次调用schedule开始进行新一轮的调度。这是一个工作线程的调度循环，同一个Go程序中可能存在多个工作线程，其中每个工作线程都有自己的调度循环。

每调用一次函数都会消耗一定的栈空间，而如果一直这样无返回的调用下去无论g0有多少栈空间终究会耗尽。该调度的关键在于每次执行mcall切换到g0栈时都是切换到g0.sched.sp所指的固定位置，因为从schedule函数开始之后的一系列函数永远都不会返回，所以重用这些函数上一轮调度时所使用的栈内存没有问题。

总结来说，工作线程的执行流程如下：

  • 初始化，调用mstart函数；
  • 调用mstart1函数，在该函数中调用save函数设置g0.sched.sp和g0.sched.pc等调度信息，其中g0.sched.sp指向mstart函数栈帧的栈顶
  • 依次调用schedule->execute->gogo函数执行调度
  • 运行用户的goroutine代码
  • 用户goroutine代码执行过程中调用runtime的某些函数，然后这些函数调用mcall切换到g0.sched.sp所指向的栈并最终再次调用schedule函数进入新一轮的调度，之后工作线程一直循环执行3-5这一调度循环直到进程退出

goroutine的调度策略

schedule函数分三步从运行队列中寻找可运行的goroutine：

  • 从全局队列中寻找goroutine。为了保证调度公平性，每个工作线程经过61次调度就需要优先尝试从全局队列中找到一个goroutine来运行，保证位于全局队列的g也有得到调度的机会。访问全局队列时需要加锁。
  • 从工作线程本地队列中寻找goroutine，如果不需要或不能从全局队列中获取到则从本地队列中获取；
  • 从其他工作线程的本地运行队列中偷取。如果上述两步骤都没获取到可运行的g那么调用findrunnable从其他工作线程的运行队列中偷取。该函数在偷取之前还会再次尝试从全局和当前线程本地队列中查找需要运行的g。

从全局队列中获取

globrunqget(p *p, max int32)函数第一个参数是与当前工作线程绑定的p，第二个参数是最多可以从全局队列中拿多少g到当前工作线程的本地运行队列中。

根据p的数量平分全局队列中的g，最大为全局队列中的p总和。如果该值大于第二个参数max，则重新赋值为max。判断此时该值是否大于本地队列容量的一半，如果仍大于，则重新赋值为本地队列的一半。然后pop从全局队列中依次取出N个g，放入本地队列中。

从本地队列中获取

本地队列分为两个部分，一部分由P的runq，runqhead，runqtail组成的一个无锁循环队列，该队列最多包含256个G；另一部分是p的runnext成员，指向一个指向g结构体对象的指针，最多只包含一个g。

本地队列寻找时通过runqget函数完成，代码首先查看runnext成员是否为空，不为空则返回runnext指向的goroutine，并把runnext成员清零，如果为空则继续从循环队列中查找goroutine。

无论runnext还是从队列中取都使用了CAS，防止其他工作线程窃取。其次对runqhead的操作使用了atomic.LoadAcq, atomic.CasRel。runqtail则不需要因为其只会被当前工作线程修改。

Go语言调度–窃取Goroutine

尽力从各个运行队列中寻找goroutine，如果实在找不到则进入睡眠状态。

工作线程M的spinning，从其他工作线程本地队列中窃取g时的状态称为自旋状态。去其他p的运行队列中窃取goroutine之前把spinning标志设为true，同时增加自旋M的数量。当有空闲P又有goroutine需要运行时，处于自旋状态的M的数量决定了是否需要唤醒或者创建新的工作线程。

盗取本质是遍历allp中的所有p查看其运行队列是否有g，如果有则窃取一半后返回，如果没有则继续遍历。为了保证公平性，遍历并不是固定的从allp[0]开始，而是从随机位置上的p开始，并使用伪随机的方式（随机选取质数作为步长）遍历。

窃取一半时通过runqtail-runqhead/2进行计算后，还需要和队列长度的一半进行判断。因为读取上述两个值的操作不是一个原子操作，需要检测读取过程中是否有其他线程快速增加这两个值。

如果工作线程经过多次努力一直找不到需要运行的g则调用stopm进入睡眠状态，等待被其他工作线程唤醒。stopm调用mput把m结构体对象放入sched的midle空闲队列，并通过notesleep函数让自己进入睡眠状态。

后来再有可运行的g时通过全局的m空闲队列找到处于睡眠状态的m，通过notewakeup进行唤醒。

Goroutine被动调度

goroutine在执行某个操作因条件不满足需要等待而发生的调度。

阻塞时通过runqput(p p, gp g, next bool)函数把goroutine挂入运行队列。首先把gp放在p.runnext成员中，runnext成员中的goroutine会被优先调度起来运行。CAS操作如果此时有其他线程操作runnext成员需要重试。原本runnext的gp放在runq的尾部。如果本地队列满了则通过runqputslow把gp放入全局运行队列。

runqputslow首先用链表把从p的本地队列中取出的一半连同gp一起串联起来，加锁成功后通过globalrunqputbatch把该链表链入全局队列。其中要注意的是加锁是等待所有准备工作完成后才进行，尽量减少冲突。

goroutine对channel进行操作时，chanrecv会判断channel是否有数据可读，如果有取出并返回，如果没有则需要把当前goroutine挂入channel的读取队列中并调用goparkunlock函数阻塞该goroutine。

goparkunlock直接调用gopark，后者调用mcall从当前goroutine切换到g0去执行park_m函数。park_m将当前g的状态设置为_Gwaiting，然后调用dropg函数解除g和m之间的关系。最后调用schedule函数进入调度循环。

工作线程的唤醒及创建

为了充分利用CPU资源，ready函数在唤醒goroutine之后会去判断是否需要启动新工作线程。规则是如果当前有空闲的p而且没有工作线程正在尝试从各个工作线程的本地队列窃取goroutine时，需要把空闲的p唤醒起来工作。

wakep首先通过CAS操作再次确认是否有其他工作线程处于spinning状态，如果没有则调用startm创建一个新的或唤醒一个处于睡眠状态的工作线程出来工作。

startm首先判断是否有空闲的p，如果没有则直接返回。如果有则首先尝试从m的空闲队列中查找处于休眠状态的工作线程，如果找到则notewakeup唤醒，否则调用newm创建一个工作线程与之绑定，把空闲的p利用起来。

Go调度器主动调度

主动调度是指当前正在运行的goroutine通过直接调用runtime.Gosched()函数暂时放弃运行而发生的调度。

用户代码自己控制，根据代码就可以预见什么地方一定会发生调度。

主要调度逻辑在goschedImpl函数中，首先把当前运行g2的状态从_Grunning 切换到_Grunnable，并通过dropg函数解除当前线程m和g2的关系，m.curg=nil,g2.m=nil，然后调用globrunqput函数把g2放入全局队列中。

goroutine运行时间过长而发生的抢占调度

sysmon系统监控线程会定期（10ms）通过retake函数对goroutine发起抢占。根据p的两种不同状态检查是否需要抢占：1）_Prunning 表示对应的goroutine正在运行，如果运行时间超过10ms则需要抢占, 2）_Psyscall表示对应的goroutine正在执行系统调用，此时需要根据多个条件来判断是否需要抢占。

普通运行时间超时

如果监控到运行时间超过10ms，则会调用preemptone函数向该goroutine发出抢占请求。该函数只是简单的设置了被抢占goroutine对应的g结构体中的preempt成员为true，stackguard0成员为stackPreempt（常量）就返回了，并没有真正强制被抢占的goroutine暂停。

被抢占的goroutine会处理响应监控线程提出的抢占请求。在进行一些基本检查后如果可以被抢占则调用gopreempt_m函数完成调度。此函数通过goschedImpl函数完成实际的调度切换工作，和主动调度类似。

系统调用时间超时

如果满足以下条件任意一个就需要对处于PSyscall状态的P进行抢占

  • p的运行队列中有等待运行的goroutine。用来保证当前p的本地队列中goroutine及时调度，因为该p对应的工作线程正处于系统调用，无法调度队列中的goroutine，需要找另外一个工作线程来接管这个p
  • 没有空闲的p。表示其他所有的p都已经和工作线程绑定并且忙于执行，说明系统比较繁忙，需要抢占当前处于系统调用之中而实际上系统调用并不需要的这个p，并把它分配给其他工作线程去调度其他的goroutine。

  • 从上一次监控观察到p对应的m处于系统调用之中到现在超过了10ms。表示只要系统调用超时就对其进行抢占，不管是否真的有goroutine需要调度。

    这里对正在进行系统调用的goroutine的抢占实质上是剥夺与其对应的工作线程所绑定的p，虽然说处于系统调用之中的工作线程并不需要p，但一旦从操作系统内核返回到用户空间之后就必须绑定一个p才能运行go代码，那么，工作线程从系统调用返回之后如果发现它进入系统调用之前所使用的p被监控线程拿走了，该怎么办呢？

    因为工作线程没有绑定p是不能运行goroutine的，所以这里会再次尝试从全局空闲队列找一个p出来绑定，找到了就通过execute函数继续执行当前这个goroutine，如果找不到则把当前goroutine放入全局运行队列，由其它工作线程负责把它调度起来运行，自己则调用stopm函数进入睡眠状态。

    对于运行时间过长的goroutine，系统监控线程首先会提出抢占请求，然后工作线程在适当的时候会去响应这个请求并暂停被抢占goroutine的运行，最后工作线程再调用schedule函数继续去调度其它goroutine；

    而对于系统调用执行时间过长的goroutine，调度器并没有暂停其执行，只是剥夺了正在执行系统调用的工作线程所绑定的p，要等到工作线程从系统调用返回之后绑定p失败的情况下该goroutine才会真正被暂停运行。

Veröffentlicht am

GC的认识

  1. 什么是GC，有什么作用？
    答： GC即垃圾回收，是一种自动内存管理的机制。 当程序向操作系统申请的内存不再需要时，垃圾回收自动将其回收并供其他代码进行内存申请时复用，或者将其归还给操作系统。
    通常垃圾回收的执行过程被划分为两个半独立的组件：
  • 赋值器Mutator：指代用户态的代码。修改对象之间的引用关系，即在对象图上进行操作；
  • 回收器Collector：执行垃圾回收代码。

  1. 根对象是什么？
    答：在垃圾回收中术语又叫做根集合，是垃圾回收器在标记过程中最先检查的对象。包括：

    • 全局变量：程序在编译期间就确定的存在于程序整个声明周期的对象；
    • 执行栈：每个goroutine都包含自己的执行栈，这些执行栈上包含栈上的变量即其指向分配的堆内存块的指针。
    • 寄存器：寄存器的值可能表示为一个指针，可能指向某些赋值器分配的堆内存区块。

  2. 常见的GC实现方式有哪些？
    答： 所有的GC算法其存在的形式可以归结为追踪和引用计数两种形式的混合运用。

    • 追踪式GC，从根对象出发，根据对象之间的引用信息，一步步推进直到扫描完毕整个堆并确定要保留的对象。Go Java V8对JS的实现均为追踪式GC
    • 引用计数GC，每个对象自身包含一个被引用的计数器，当计数器归零时自动得到回收。缺陷较高，在追求高性能时不适用。Python，Object-C等均为引用基数。

目前常见的GC实现方式：

  • 标记清扫： 从根对象出发，将确定存活的进行标记，并清扫可回收的对象；
  • 标记整理：为了解决内存碎片而提出，在标记过程中将对象尽可能整理到一块连续的内存上；
  • 增量式：将标记和清扫的过程分批执行，每次执行很小的部分，从而增量的推进垃圾回收，达到近实时无停顿的目的；
  • 增量整理：在增量式基础上增加整理过程；
  • 分代式：将对象根据存活时间长短进行分类。存活时间小于某个值为年轻代，大于某个值为老年代，永远不参与回收的为永久代。根据分代假设进行回收（一个对象存活时间不长更倾向于被回收）
  • 引用计数：根据对象的自身引用计数来回收，归零时立即回收

Go的GC目前使用的是无分代、不整理、并发的三色标记清扫算法。 原因在于：

  • Go运行时的分配算法基于tcmalloc，基本上不存在碎片问题。并且顺序内存分配器在多线程场景下并不适用。因此整理不会带来实质性的性能提升
  • Go编译器会通过逃逸分析将大部分新生对象存储在栈上（栈直接被回收），只有那些需要长期存在的对象才会被分配到需要垃圾回收的堆上。分代假设并没有带来直接优势。并且Go的垃圾回收器和用户代码并发执行，使得STW的时间和对象的代际、size没有关系。Go团队更关注如何更好的并发执行而不是减少停顿时间这一单一目标。
  1. 三色标记法是什么？
    答： 理解三色标记法的关键是理解对象的三色抽象和波面推进。
    • 白色对象（可能死亡），未被回收器访问到的对象。在开始阶段所有对象均为白色，当回收结束后白色对象均不可达
    • 灰色对象（波面）：已经被回收器访问的对象，但回收器需要对其中的一个或多个指针进行扫描，因为他们还可能指向白色对象
    • 黑色对象（确定存活）：已经被回收器访问的对象且所有字段都已扫描，任何一个指针都不指向白色对象

垃圾回收结束后只有白色和黑色对象。

  1. STW是什么意思？
    答： STOP the World，指在垃圾回收过程中为了保证实现的正确性、防止无止境的内存增长，而不可避免的需要停止赋值器进一步操作对象图的一段过程。
    Go1.14之后STW的时间不会超过半个毫秒。

  2. 如何观察GC？
    答：

    • GODEBUG=gctrace=1
    • go tool trace (调用trace API 可视化展示)
    • debug.ReadGCStats
    • runtime.ReadMemStats

  3. 有了GC，为什么还会发生内存泄露？
    答： 在包含GC的语言中，我们常说的内存泄露是指：预期能很快被释放的内存由于附着在了长期存活的内存上，或生命期意外地被延长，导致预计能够立即回收的内存长时间得不到回收。
    1）预期很快能释放的内存被根对象引用，而没有迅速释放 （比如将某个变量附着在全局变量上，且忽略将其释放）

    var cache = map[interface{}]interface{}
    func keepalloc() {
    for i := 0; i < 1000; i++ {

    m := make([]byte, 1<<10)
cache[i] = m

    }
    }

2) goroutine泄露 （如一个程序不断的产生新的goroutine，且不结束已创建的goroutine并复用这部分内存）

func keepalloc2(){
  for i := 0; i < 10000; i++ {
    go func() {
      select {}
    }()
  }
}
//或者channel泄露导致
var ch = make(chan struct{})
func keepalloc2(){
  for i := 0; i < 10000; i++ {
    go func(){ ch <- struct{}{}}() //没有接收方，goroutine一直阻塞
  }
}

  1. 并发标记清除法的难点是什么？
    答： 难点在于用户代码在回收过程中会并发的更新对象图，从而造成渎职器和回收器对对象图的机构产生不同的认知。
    回收器不会重新扫描黑色对象，在扫描完之后用户代码对该黑色对象修改，导致有些对象可能错误地被回收。 因此难点在于如何保证标记和清除过程的正确性。

  2. 什么是写屏障、混合写屏障，如何实现？
    答： 垃圾回收器的正确性体现在不应出现对象的丢失，也不应错误的回收还不需要回收的对象。当下面两个条件同时满足时会破坏正确性：

  • 条件1，当赋值器修改对象图，导致某一黑色对象引用白色对象；
  • 条件2，从灰色对象出发，到达白色对象的、未经访问过的路径被赋值器破坏。
    只要能够避免其中任何一条件，正确性都能得到满足。因此我们可以将三色不变性所定义的波面根据这两个条件进行削弱：
  • 当满足原有的三色不变性定义的情况成为强三色不变形
  • 当赋值器另黑色对象引用白色对象时，称为弱三色不变形
    当赋值器进一步破坏灰色对象到达白色对象的路径时，即打破弱三色不变形，也就破坏了正确性。

因此可以引入赋值器的颜色：

  • 黑色赋值器：已经由回收器扫描过，不会再次对其进行扫描
  • 灰色赋值器：尚未被回收器扫描过，或尽管已经扫描过，但仍需重新扫描

为了确保强弱三色不变性的并发指针更新操作，需要通过赋值器屏障技术来保证指针的读写操作一致。

因此Go中的写屏障、混合写屏障，其实是指赋值器的写屏障，用来保证赋值器在进行指针操作时不会破坏弱三色不变性。

Dijkstra插入屏障： 避免条件1， 需要标记终止阶段STW时进行重新扫描
Yuasa删除屏障：避免条件2，依然会产生丢失的对象，需要在标记前对整个对象图进行快照

Go在1.8时为了简化GC流程，同时减少标记终止阶段的重新扫描成本，将两种方法进行了混合，形成混合写屏障： 对正在被覆盖的对象进行着色，且如果当前栈未扫描完成，则同样对指针进行着色。

因为着色成本是双倍的，而且编译器需要插入的代码也成倍增加，随之带来的结果就是编译后的二进制文件大小也进一步增加。 Go 1.10 前后，Go 团队随后实现了批量写屏障机制。其基本想法是将需要着色的指针统一写入一个缓存，每当缓存满时统一对缓存中的所有 ptr 指针进行着色。

GC的实现细节

  1. 当前版本的Go1.14以STW为界限，将GC划分为5个阶段
  • GCMark, 标记准备，为并发标记做准备工作，启动写屏障。 STW
  • GCMark， 扫描标记阶段，与赋值器并行执行，写屏障开启。 并发
  • GCMarkTermination， 标记终止阶段，保证一个周期内标记任务完成，停止写屏障。 STW
  • GCoff， 内存清扫阶段，将需要回收的内存归还到堆中，写屏障关闭， 并发
  • GCoff，内存归还阶段，将过多的内存归还给操作系统，写屏障关闭，并发
  1. 触发GC的时机是什么？
    答： 存在两种形式：
  • 主动触发，调用runtime.GC来触发，阻塞式等待当前GC运行完毕；
  • 被动触发
    • 使用系统监控：超过两分钟没有任何GC时，强制触发
    • 使用步调Pacing算法，控制内存增长的比例
  1. 如果内存分配速度超过了标记清除速度怎么办？
    答：目前go实现中，当GC触发后会首先进入并发标记阶段，该阶段会设置一个标志，当mallocgc调用时进行检查。当存在新的内存分配时，会暂停分配内存过快的那些goroutine，将其转去执行一些辅助标记Mark Assist的工作，从而达到放缓继续分配、辅助GC标记工作的目的。

编译器会分析用户代码，并在需要分配内存的位置，将申请内存的操作翻译为 mallocgc 调用。

GC的优化问题

  1. GC关注的指标有哪些？
    答： CPU利用率，GC停顿时间（STW，Mark Assist两部分可能造成），GC停顿频率，GC可扩展性（当堆内存变大时，垃圾回收器性能如何？）

  2. GC如何调优？
    答： GO的GC被设计为极致简洁，与Java GC数十个可控参数相比，严格意义上Go可供用户调整的只有GOGC环境变量。

GC调优：减少用户代码对GC产生的压力，即减少用户代码分配的内存数量，最小化Go的GC对CPU的使用率

所谓 GC 调优的核心思想也就是充分的围绕两点来展开：优化内存的申请速度，尽可能的少申请内存，复用已申请的内存。或者简单来说，不外乎这三个关键字：控制、减少、复用
1） 合理化内存分配速度、提高赋值器的CPU利用率 （goroutine 池的使用）
2） 降低并复用已经申请的内存（使用 sync.Pool 复用需要的 buf， concat 函数可以预先分配一定长度的缓存而后再通过 append 的方式将字符串存储到缓存中）
3） 调整GOGC （治标不治本，更妥当的做法仍然是，定位问题的所在，并从代码层面上进行优化）

GC 调优过程中 go tool pprof 和 go tool trace 可以帮助我们快速定位 GC 导致瓶颈的具体位置

过早优化是万恶之源。

  1. Go的垃圾回收器有哪些相关的API？
  • runtime.GC: 手动触发 GC
  • runtime.ReadMemStats: 读取内存相关的统计信息，其中包含部分 GC 相关的统计信息
  • debug.FreeOSMemory: 手动将内存归还给操作系统
  • debug.ReadGCStats: 读取关于 GC 的相关统计信息
  • debug.SetGCPercent: 设置 GOGC 调步变量
  • debug.SetMaxHeap: 设置 Go 程序堆的上限值

GC的历史及演进

  1. GO历史各版本在GC方面的改进
  • Go1 串行三色标记清扫
  • Go1.3 并行清扫，标记过程需要STW，停顿时间约几百ms
  • Go1.5 并发标记清扫，停顿时间在100ms以内
  • Go1.6 使用bitmap记录回收内存的位置，大幅优化垃圾回收器自身消耗的内存，停顿时间在10ms以内
  • Go1.7 停顿时间在2ms以内
  • Go1.8 混合写屏障，停顿时间在半个ms以内
  • Go1.9 彻底移除了栈的重新扫描过程
  • Go1.12 整合和两个阶段的Mark Termination，但引入了一个严重的GC bug，至今未修复
  • Go1.13 着手解决向操作系统归还内存，提出新的Scavenger
  • Go1.14 替代了仅存活一个版本的Scavenger，全新的页分配器，优化分配内存过程中的速率和现有的扩展性问题，引入异步抢占，解决密集循环导致的STW时间过长的问题
  1. Go GC在演化过程中还有哪些设计？ 为什么没有被采用？
    答：
  • 并发栈重扫：允许灰色赋值器存在的垃圾回收器需要引入重扫过程来保证正确性，除了混合写屏障消除该过程外，还可以通过并发重扫提高性能。没有得以实现： 实现过程相比引入混合写屏障复杂，而且引入混合写屏障可以消除重扫过程，简化垃圾
  • ROC: Request Oriented Collector, 面向请求的回收器，其实也是分代GC的一种重新叙述。它提出一个请求假设：与一个完整请求、休眠goroutine所关联的对象更容易死亡。 但是在实现上由于垃圾回收器必须确保是否有goroutine私有指针被写入公共对象，因此写屏障要一直打开。 昂贵的写屏障以及其带来的缓存未命中是未被采用的原因
  • 传统分代GC：不适用于Go的运行栈机制。年轻代对象其实在栈上就已经死亡，扫描本就该回收的执行栈并没有带来性能提升。
  1. 目前提供GC的语言有哪些？GC和NOGC的优缺点？
    答：目前提供GC的有go，python，java，javascript，objective-c，Swift，没有提供但是支持自行实现GC的有C，C++，也有一些语言在编译器就可以依靠插入清理代码的方式实现精确的清理，如Rust

NOGC：

  • 在仍然有指向内存区域的指针存在情况下释放该内存，会产生悬挂指针。
  • 多重释放同一块内存区域，可能导致不可知的内存损坏。
  • 没有额外的扫描性能开销
  • 精确的手动内存管理，极致的利用机器性能。
  1. GO对比Java，V8中的Javascript GC性能
    答： java和javascript都基于分代假设，每次回收只回收其中一个区域。
  • V8的GC： 将内存分为新生代和老生代。1）新生代的对象通过副垃圾回收器进行回收，采用复制的方式实现垃圾回收，将堆内存一分为2，只有一个处于使用中From，另一个闲置To。分配对象先在From分配，当开始垃圾回收时检查From中存活对象，复制到To空间中，非存活空间被释放。完成复制后From、To角色互换。2）老生代由主垃圾回收器负责，实现标记清扫过程，并且清扫完成后进行整理碎片。
  • Java： G1将堆分为年轻代、老年代、永久代。包括4种操作，从上往下依次执行。1）只对年轻代进行收集整理;2）只对老年代进行收集整理；3）混合年轻代和老年代进行收集整理；4）完成GC对整个堆进行收集整理。在回收过程中G1会对停顿时间进行预测，竭尽所能调整GC策略达到用户代码配置的-XX：MaxGCPauseMillis对停顿时间的要求。
  1. 目前Go GC存在的问题？
    答：
  • Mark Assit停顿时间过长
  • Sweep停顿时间过长
  • 由于GC算法不正确性导致GC被迫重新运行：（能够在 1334 次构建中发生一次）
  • 创建大量Goroutine后导致GC消耗更多的CPU： 通常发生于峰值流量后，大量 goroutine 由于任务等待被休眠，从而运行时不断创建新的 goroutine，旧的 goroutine 由于休眠未被销毁且得不到复用，导致 GC 需要扫描的执行栈越来越多，进而完成 GC 所需的时间越来越长。一个解决办法是使用 goroutine 池来限制创建的 goroutine 数量。

垃圾回收器的设计权衡了很多方面的因素，同时还受语言自身设计的影响，因为语言的设计也直接影响了程序员编写代码的形式，也就自然影响了产生垃圾的方式。但总的来说，他们三者对垃圾回收的实现都需要 STW，并均已达到了用户代码几乎无法感知到的状态（据 Go GC 作者 Austin 宣称 STW 小于 100 微秒）。

Veröffentlicht am

  1. context 如何被取消？

  2. context 是什么？有什么作用？

  3. context.value的查找过程是怎样的？

  4. gomaxprocs调高引起调度性能损耗
    golang gomaxprocs调高引起调度性能损耗
    golang运行时调度依赖PMG抽象，P为逻辑处理器，M为执行线程，G为协程。P的runq中存放可执行的G结构。golang默认的P数量是cpu的物理核心数目。同一时间一个P只能绑定一个M线程，PM绑定后会寻找合适的G运行。

增加P的数量是够可以加大运行时对于协程的吞吐量呢？

大多数golang项目都偏重网络IO，network io在netpoll设计下都是非阻塞的，所涉及的syscall不会阻塞。如果是CPU密集的业务，增加多个P也没用，毕竟CPU计算资源有限，增加P会导致额外的切换开销。因此，多数场景下增加P并不能增加吞吐量。如果业务逻辑中有不少的cgo以及阻塞syscall的操作，那么增加P还是有效果的。因为这类操作可能因为过慢引起阻塞，阻塞期间P被该MG绑定，其他M无法获取P的所有权。虽然findrunnable steal机制里其他P的M可以偷取该P任务，但是在解绑P之前终究还是少了并行通道。

golang在docker中初始化processor是依据/proc/cpuinfo信息的，和宿主机一样都是和物理核数相同。但是容器一般会限定CPU、memory资源，因此最终也只能用到限制的CPU核数。两种方法可以校对：要么在K8S pod中加入限制变量，golang启动时获取CPU信息；要么解析cpu.cfs_period_us cpu.cfs_quota_us配置来计算CPU资源。

如果运行时processor多了会出现什么问题？

一个是运行时findrunnable产生损耗，一个是线程引起上下文切换。findrunnable方法是解决m找到可程的函数，当绑定P本地runq上找不到可执行的G时，尝试从全局链表中拿，再拿不到从netpoll和事件池里拿，最后会从别的P里偷任务。

因此建议gomaxprocs配置为CPU core数量就可以了，默认就是该配置。如果涉及阻塞syscall可以适当调整，但是最好测试用指标验证是否合理。

  1. 深入理解WaitGroup

  2. go 栈内存的内存和逃逸分析

  3. Go指针和unsafe.Pointer有什么区别？

  4. 如何利用unsafe包修改私有成员？

  5. 如何利用unsafe包获取slice和map的长度

  6. 如何实现字符串和btye切片的零拷贝转换？

  7. new和make的区别？

  8. 引用类型有哪些？

  9. go的内存模型中，为什么小对象多了会造成gc压力？

  1. go 并发调度器解析
    GO并发调度器解析之实现一个高性能协程池
  • Goroutine&Scheduler
    goroutine并非传统意义上的协程coroutine的golang实现。现在主流线程模型有三种：用户级线程模型、内核级线程模型、两级线程模型。传统的协程基于用户级线程模型，而goroutine个go scheduler在底层实现上其实是属于两级线程模型。
  • 三种线程模型分析
    三种线程模型之间最大的差异就在于用户线程与内核调度实体KSE（Kernel Scheduler Entity）之间的对应关系。KSE指可以被操作系统内核调度器调度的对象实体，即内核级线程。
    • 用户级线程： 和KSE多对一映射，多个用户线程一般属于单个进程并且多线程调度由用户自己的线程库完成。线程创建、销毁、以及多线程之间的协调操作都是由用户自己的线程库负责。一个进程中所有的线程都只和同一个KSE动态绑定。
      • 调度在用户层面完成，相比于内核调度减少了用户态内核态切换开销，实现比较轻量级。
      • 不能做到真正意义上的并发，假设某个进程上的一个用户线程因为阻塞调用被CPU中断，那么该进程中上所有线程都被阻塞。因此很多协程库会把自己一些阻塞操作重新封装为完全的非阻塞模式，在之前的阻塞点主动让出自己，并以某种方式通知或唤醒其他待执行的用户线程在该KSE上运行。
    • 内核级线程： 和KSE一对一映射，线程调度完全交给内核完成。
      • 实现简单，直接借助操作系统内核的线程和调度器，CPU可以快速切换调度线程，真正做到并发处理
      • 线程创建、销毁、切换调度开销较大
    • 两级线程： 和KSE多对多映射，一个进程可以和多个内核线程KSE关联，即一个进程内的多个线程可以分别绑定一个自己的KSE。区别与内核级线程模型的是，它的进程里的线程并不与KSE唯一绑定，而是多个用户线程映射同一个KSE，当某个KSE因为其绑定的线程阻塞操作被内核调度出CPU时，其关联进程中其余用户线程可以重新和该KSE绑定。 Go语言的runtime调度器就采用这种实现方案，用户调度器实现用户线程到KSE的调度，内核调度器实现KSE到CPU上的调度。
  • GPM模型
    Goroutine栈采用动态扩容方式，初始2KB，随着任务执行按需增长最大可达1GB（32位256M），且完全由golang自己的调度器Go Scheduler来调度。GC会周期性地将不再使用的内存回收，收缩栈空间。因此Go程序可以同时并发成千上万个goroutine得益于它的调度器和高效的内存模型。
    • G：Goroutine，存储Goroutine的运行堆栈、状态以及任务函数，可重用。G需要绑定到P上才能执行
    • P：Processor，逻辑处理器，对于G来说其相当于CPU核，G只有绑定到P中才能被调度。对M来说P提供了相关的执行环境Context，如内存分配状态mcache，任务队列等。P的数量决定了系统内最大可并行的G数量，用户配置GMAXPROCS来决定，但无论用户设置其最大值不超过256.
    • M：Machine，操作系统线程抽象，代表真正执行计算的资源，在绑定有效P后进入schedule循环；循环从Global队列、P的Local队列、以及等待队列中获取G，切换到G的执行栈上并执行G的函数，调用goexit清理后回到M，如此反复。M并不保留G的状态，因此G可以跨M调度。M数量有Go runtime调整，默认最大为1w个。
  • GPM模型调度
    Go调度器工作时会维护两个队列：Global和每个P的Local任务队列。当通过go关键字创建G时，它会被优先放入P的本地队列。为了运行G，M需要持有并绑定一个P，接着M启动系统线程循环从P的本地队列读取G执行。当M执行完本地队列中所有G后，P会尝试从Global队列寻找G来执行，如果Global为空，则随机挑选另外一个P，从其Local队列中拿走一半的G到自己队列。
  1. go 内存分配
    图解Go语言内存分配
    Golang运行时内存分配算法源自Google为C语言开发的TCMalloc算法，ThreadCachingMalloc。把内存多级管理，降低锁的粒度。将可用的堆内存采用二级分配的方式进行管理，每个线程都会自动维护一个独立的内存池，进行内存分配时优先从内存池中分配，不足时再向全局内存池申请。

Go程序启动时首先会向OS申请一块内存（虚拟内存），切成小块自己进行管理。 申请到的内存分配3个区域：X86上为512M spans，16GB bitmaps，512GB arena。

  • arena区域就是我们所谓的堆区，Go动态分配的内存都是在这个区域，它把内存分割成 8KB大小的页，一些页组合起来称为 mspan。
  • bitmap区域标识 arena区域哪些地址保存了对象，并用 4bit标志位表示对象是否包含指针、 GC标记信息. 1 byte对应arena中4个指针大小的内存， 512GB/(4*8B)=16G
  • spans区域存放mspan的指针，每个指针对应一页。spans的大小为512GB/8KB*8B=512M .创建mspan的时候，按页填充对应的spans区域，在回收object时，根据地址很容易就能找到它所属的 mspan。

arena起始地址和bitmap起始地址一样，因为bitmap从高地址向低地址增长。

mspan：Go中内存管理的基本单元，是由一片连续的 8KB的页组成的大块内存。是包含起始地址、mspan规格、页的数量等内容的双端链表。 每个mspan按照它自身的属性SizeClass的大小分割成若干个object，每个object可存储一个对象。 Size_Class= Span_Class/2， 其实每个SizeClass有两个mspan，也就是有两个SpanClass。其中一个分配给含有指针的对象，另一个分配给不含有指针的对象。SizeClass有67种， 对于微小对象（小于16B），分配器会将其进行合并，将几个对象分配到同一个 object中。

内存分配由内存分配器完成。分配器由3种组件构成： mcache, mcentral, mheap。每个工作线程都会绑定一个mcache，本地缓存可用的mspan资源。

  • mcache用 SpanClasses作为索引管理多个用于分配的 mspan，它包含所有规格的 mspan。它是 _NumSizeClasses的2倍，也就是 67*2=134，为什么有一个两倍的关系，前面我们提到过：为了加速之后内存回收的速度，数组里一半的 mspan中分配的对象不包含指针，另一半则包含指针。mcache在初始化的时候是没有任何 mspan资源的，在使用过程中会动态地从mcentral申请，之后会缓存下来。当对象小于等于32KB大小时，使用 mcache的相应规格的 mspan进行分配。
  • mcentral：为所有 mcache提供切分好的 mspan资源。每个 central保存一种特定大小的全局 mspan列表，包括已分配出去的和未分配出去的。
    • 获取： 加锁；从nonempty中找到一个可用的mspan；将其从nonempty中删除；将取出的mspan加入到empty链表；将mspan返回给线程；解锁。
    • 归还： 加锁；将mspan从empty中删除；加入到nonempty链表中；解锁
  • mheap：代表Go程序持有的所有堆空间，Go程序使用一个 mheap的全局对象 _mheap来管理堆内存。当 mcentral没有空闲的 mspan时，会向 mheap申请。而 mheap没有资源时，会向操作系统申请新内存。 mheap主要用于大对象的内存分配，以及管理未切割的 mspan，用于给 mcentral切割成小对象。

Go的内存分配器在分配对象时，根据对象的大小，分成三类：小对象（小于等于16B）、一般对象（大于16B，小于等于32KB）、大对象（大于32KB）。

  • 32KB直接从mheap分配

  • <=16B使用mcache的tiny分配器分配
  • （16B，32KB]，首先计算对象规格大小，使用mcache相应规格大小的mspan分配
    • 如果mcache没有相应规格大小的mspan，则向mcentral申请
    • 如果mcentral没有相应规格大小的mspan，则向mheap申请
    • 如果mheap中也没有合适大小的mspan，则向操作系统申请

Veröffentlicht am

笔记汇总

1. K8S垃圾收集器

详解Kubernetes垃圾收集器的实现原理

垃圾收集器在K8S中以控制器的形式设计实现，删除以前有所有者但是现在所有者不存在的对象。引入垃圾收集器之前，所有的级联删除逻辑都由客户端完成，垃圾收集器的引入使得级联删除实现移动到了服务端。

级联删除： 对象的API中加入了metadata.ownerReferences字段，包含当前对象的所有依赖者。当所有依赖者都被删除，默认情况下该对象也会被删除。

1
2
3
4
5
6
7
8
9
10
type ObjectMeta struct {
	...
	OwnerReferences []OwnerReference
}
type OwnerReference struct {
	APIVersion string
	Kind string
	Name string
	UID types.UID
}

实现原理

GarbageCollector负责处理对象之间的联系并在所有依赖者不存在时将对象删除。其中包含了一个GraphBuilder结构体，该结构体会以Goroutine的形式运行使用Informer监听集群中几乎全部资源变动，一但发生变更事件，就将该事件交给主循环体处理。主循环体根据事件的不同选择将处理对象加入不同的队列，GarbageCollector持有的另外两组队列会负责删除或孤立目标对象。

  • attemptToDeleteItem ： 首先获取待处理对象及其ownerReferences列表，使用classifyReferences将所有者进行分类处理：

    • 所有者还有存在于集群中的，当前对象不会被删除。将已经被删除、等待删除的所有者从对象ownerReferences删除；
    • 当正在被删除的所有者不存在任何依赖且ownerReference.blockOwnerDeletion=true时会阻止依赖方的删除，当前对象会等待ownerReference.blockOwnerDeletion=true的所有对象删除后才会被删除；

    • 当前对象不包含任何依赖，会选择三种不同的策略处理依赖：

      • 当前对象有FinalizerOrphanDependents终结器，DeletePropagationOrphan将对象的所有依赖者变成孤立的；
      • 当前对象有FinalizerDeleteDependents终接器，deletePropagationBackground策略在前台等待所有依赖被删除后才会删除，整个过程是同步的；
      • 默认情况下使用DeletePropagationDefault策略在后台删除当前对象的所有依赖；
  • attemptToOrphanItem

2. Go Select实现原理

Go 语言select实现原理

Go语言中select能够让Goroutine同时等待多个Channel的可读/可写，在Channel发生状态改变之前会一直阻塞当前Goroutine。其与switch不同的是，case中的表达式必须是Channel的收发操作。

  • select 能在 Channel 上进行非阻塞的收发操作；
  • select 在遇到多个 Channel 同时响应时会随机挑选 case 执行；(随机的引入是为了避免饥饿问题)

通常情况下select语句会阻塞当前Goroutine并等待多个Channel中一个达到可以收发的状态，但是如果存在default：

  • 当存在可以收发的Channel时，直接处理该Channel对应的case；
  • 当不存在可以收发的Channel时，执行default中语句；
    非阻塞的Channel发送和接收操作还是很有必要的，在很多场景下我们不希望向Channel发送消息或者从Channel中接收消息会阻塞当前Goroutine，只是想看看 Channel的可读或者可写状态。

编译器在中间代码生成期间会根据select中case的不同对控制语句进行优化，这一过程都发生在 cmd/compile/internal/gc.walkselectcases 函数中：

  • select 不存在任何的 case； 将select{}转换为调用runtime.block，通过gopark让出当前Goroutine对处理器的使用权，导致当前G进入无法被唤醒的永久休眠状态
  • select 只存在一个 case； 将select改写成if条件预计，当case中Channel是空指针时，挂起当前G并永久休眠

  • select 存在两个 case，其中一个 case 是 default；

    • 非阻塞发送：编译器使用if else改写代码，selectnbsend向Channel非阻塞发送数据，即向chansend函数传入false，哪怕不存在接收方或者缓冲区空间不足都不会阻塞当前G，直接返回。
    • 非阻塞接收：根据接收数据返回值数量的不同使用selectnbrecv或者selectnbrecv2对返回值进行处理

  • select 存在多个 case；

    将所有case转换成包含Channel以及类型信息的runtime.scase结构体，调用runtime.selectgo选择一个可执行的scase。runtime.selectgo 函数首先会进行执行必要的初始化操作并决定处理 case 的两个顺序 — 轮询顺序 pollOrder 和加锁顺序 lockOrder：

    • 轮询顺序：通过 runtime.fastrandn 函数引入随机性； (避免Channel饥饿问题保证公平)
    • 加锁顺序：按照 Channel 的地址排序后确定加锁顺序；(避免死锁)

selectgo 处理流程

  • 随机生成一个遍历的轮询顺序pollOrder 并根据Channel地址生成锁定顺序lockOrder；
  • 根据pollOrder遍历所有的 case 查看是否有可以立刻处理的 Channel；
  • 如果存在就直接获取 case 对应的索引并返回；
  • 如果不存在就会创建 runtime.sudog 结构体，将当前 Goroutine 加入到所有相关 Channel 的收发队列，并调用 runtime.gopark 挂起当前 Goroutine 等待调度器的唤醒；
  • 当调度器唤醒当前 Goroutine 时就会再次按照 lockOrder 遍历所有的 case，从中查找需要被处理的 runtime.sudog 结构对应的索引；

###　３.　ETCD九连问
ETCD九连问

ETCD是一个可信的分布式键值对存储服务，为分布式集群存储一些关键数据，协助分布式集群的正常运转。

  • 什么是键值数据库？ 答：一种非关系型数据库，它使用简单的键值方法来存储数据，键作为唯一标识符。
  • KV存储服务能干啥？ 答： 用存储服务为服务中介提供服务。
  • 什么是服务中介？ 答：包含k-v键值对的字典，key是服务名称，value是服务提供者的地址列表。为服务提供者和服务消费者之间建立联系。
  • 服务发现是什么？ 答：服务提供者、消费者和服务中介三者，实现了服务发现机制，同时etcd还提供服务注册中心的功能。通过服务发现让消费者找到服务提供者。
  • 服务注册和服务发现的目的是？答：在微服务和容器化环境中，应用的增加和弹性伸缩发生频率很高，服务地址可能经常发生变化，因此需要服务注册和发现机制。
    • 服务注册：服务提供者的实例（如pod）在启动时或者位置信息发生变化时，向etcd注册自身，在停止时注销自身。如果该实例发生故障，一段时间没有发送心跳之后会被服务注册表注销；
    • 服务发现：服务消费者请求服务，首先被发往一个中央路由器或负载均衡器（Service、Router等），查询服务注册表获取服务者的位置信息将请求转发给提供者。
  • etcd作为分布式键值存储服务，必须要保证分布式系统数据的可用性和一致性。一致性算法有Paxos、Raft，其中Paxos比较复杂很多KV数据库都采用后者。ETCD也不例外。
    • HTTP Server：用于处理用户发送的API请求以及其他ETCD节点的同步与心跳信息请求
    • Store: 用于处理ETCD支持的各类功能的事务，包括数据索引、节点状态变更、监控与反馈、时间处理与执行等
    • Raft：Raft强一致行算法的具体实现
    • WAL：Write Ahead Log，预写式日志，除了内存中存有所有数据状态以及节点索引之外，ETCD通过WAL进行持久化存储，所有数据提交前都会时间记录日志。Snapshot是为了防止数据过多而进行的状态快照，Entry表示存储的具体日志内容。

4. GO STRUCT对齐

合理重排字段可以减少填充，使STRUCT字段排列紧密减少空间浪费。零大小字段指struct{}通常不需要对齐，但是当作为结构体最后一个字段时需要对齐。因为如果有指针指向该字段，返回的地址将在结构体之外。如果此指针一直存活不释放对应的内存会出现内存泄露。（该内存不因结构体释放而释放）因此零大小字段要避免作为 struct 最后一个字段，防止内存浪费。

32 位系统上对 64 位字的原子访问要保证其是 8bytes 对齐的；当然如果不必要的话，还是用加锁（mutex）的方式更清晰简单

一周算法汇总

面试问题汇总:

  1. 为什么redis选择单线程模型

答： Redis从一开始选择使用单线程模型处理客户端的绝大多数网络请求，原因是：

  • 使用单线程模型可维护性高，方便开发和调试；
  • 单线程模型也能并发处理客户端请求； （IO多路复用，通过select函数）
  • Redis服务中运行的绝大多数操作的性能瓶颈都不是CPU；

多线程技术能够帮助我们重复利用CPU的计算资源来并发执行不同的任务，但是CPU资源往往不是Redis服务器的瓶颈。Redis如果不开启AOF备份，所有的Redis操作都会在内存中完成不涉及IO，处理非常快。

普通的Linux服务器上启动Redis也能处理1s 1，000,000个请求。如果这种吞吐量不满足需求，应考虑使用分片的方式将请求发送给不同的Redis来处理。

Redis 4.0之后的版本加入了多线程的支持，是因为新版本中加入了一些可以被其他线程异步处理的删除操作。UNLINK，FLUSHALL ASYNC，FLUSHDB ASYNC。 删除超大键值对时，几十M，几百M的数据不能在几ms时间内处理完，Redis可能会需要在释放内存空间上消耗过多时间，这些操作会阻塞待处理任务，影响Redis的PCT99和可用性。释放内存的工作由后台线程异步进行处理来提升性能。

  1. Kafka如何保证数据不丢？

答： 需要分别从生产者、服务端、消费者三方面处理来保证数据不丢失。

  • 生产者：可以通过配置ACK策略或者retries策略保证数据不丢失：

    • ACK=all或-1，生产者发送消息后，需要等待ISR中所有的副本都成功写入消息之后才能接收来自服务端的成功响应。即发送消息时需要leader向follow同步完数据，ISR队列中所有broker全部保存这条消息后，才向ACK发送消息。
    • 对于可恢复错误（leader选举、网络抖动），配置retries>0进行重试并设置重试时间间隔确保重试时可恢复错误都已恢复；对于不可恢复错误，发生异常时把消息写入DB或者本地缓存文件中，等错误修复后再把数据发送给broker端
  • broker端：设置unclean.leader.election.enable=false，默认值为true，表示当存有最新一条记录的replication宕机时，kafka自己选举一个主节点，true表示允许未同步最新数据的replication所在节点作为主节点，数据会丢失。
  • 消费端：处理好offset保证exactly-once & at-least-once数据。设置enable.auto.commit=false手动提交offset，并保证offset的正确性。

Veröffentlicht am

1207-1213

Go知识图谱

图片链接

代码规范

[曹大博客] (https://mp.weixin.qq.com/s/MRZZOX7cZPIJPelcuihXUw)
主要总结了初级程序员容易犯的代码不规范问题:

  • 命名规范: 业务内部逻辑变量命名讲究单词打全,函数名尽量能让人清晰明了其功能.
  • 魔法数字: 在配置文件中集中维护特殊变量,可以引入各种方便的配置系统.可以即时修改和配置下发无需系统上下线. 如java中常用的disconf,或借助现在流行的etcd/zookeeper自己开发
  • 配置文件长度: 对配置文件进行业务逻辑分类(掌握好粒度,配置文件最好有对应的comment进行检索,将系统模块拆分不同模块管理自己的配置文件)
  • 函数内容长度: 根据功能进行简单的小函数划分
  • 滥用回调:使用消息队列来解耦.如果系统里发生一个事件,其他模块对事件的数据有依赖,那么就让其订阅系统里产生的消息即可.(Kafka)不过可能会由于引入基于消息队列的分布式系统产生可靠性问题,saga pattern可以解决部分问题.
  • 分层结果返回没有明确界限和定义: 设计模式修炼,但是要避免滥用设计模式
  • 公共接口不可重入
  • 访问数据库不做批量: 即使存在数据库连接池,也要尽可能批量操作提升性能
  • 尽量少用if else多层嵌套
  • 数据库查询使用开源builder来减少函数
  • 工作流系统update前判断修改前的状态
  • 考虑线程安全问题:有全局map之类的变量访问时考虑加锁
  • open资源用后关闭

    栈内存管理原理分析

    链接
    介绍了源码runtime/stack.go中是如何管理栈内存的

堆内存管理

C语言申请内存通过调用malloc函数指定分配大小向操作系统直接申请,会涉及用户态和内核态的切换,导致性能下降.
Golang的内存管理基于tmalloc模型设计,但是局部缓存并不分配给进程/线程,而是分配给P;GC是STW,并不是每个进程单独GC.

  • span: golang内存管理的基本单位,管理指定规格(page为单位,67种)的内存块. 最大32KB,超过32KB大小的由特殊的class表示,该classID=0.每个class只包含一个对象.
  • 内存管理单元: 内存分配器器由mcache,mcentral,mheap组成
    • mcache绑定在P上,用来给协程分配对象存储空间,不需要锁.初始化时没有任何mspan资源,使用过程中动态申请,通过双向链表连接;
    • mcentral是公共资源,会有多个mcache向它申请mspan,需要加锁.
    • mheap,当mcentral空间不足会向mheap申请新的页,也需要加锁.
  • 分配原则:
    • tiny对象,直接向mcache的tiny对象分配器申请,空间不足时向mcache的tinySpanClass规格的span链表申请,没有继续向mcentral申请对应规格mspan,依旧没有则向mheap申请,最后都不存在向操作系统申请;
    • 小对象内存分配,先向本线程mcache申请,mspan没有空闲空间->mcentral->mheap->OS page
    • 大对象内存分配,直接向mheap申请spanclass=0,没有向操作系统申请
  • GC改进:
    • 1.12版本对mheap结构添加了reclaimCredit成员变量,每次mcentral向mheap申请新的page创建span时,先扫描arenas里面的heapArena,清理GC需回收的page数量空间,由于扫描不可能刚好相等,多清理的page大小存到reclaimCredit里.下次再次扫描时先抵消这部分不够再扫描.防止mheap使用率过快增长.
    • 1.12版本mheap引入scavengeCredit成员变量，当向操作系统申请内存空间的时候，会先去扫描free这个二叉树堆,span从大到小的扫描，释放所需大小的空间给os，多余释放的存储scavengeCredit中，下次再次扫描的时候会先扣除这个值。

      全局栈内存初始化

      go程序启动时调用stackinit()初始化,涉及两个重要全局变量stackpool/stackLarge, mspanList初始化头尾为nil.

      申请内存

  • _StackMin：值为2048,表示go 代码使用最小的栈空间大小
  • stackalloc()的stacksize 是一个根据当前系统计算出来的值，win64=8kb、win32=4kb、plan9=4kb、其他系统如linux/bsd/drawin=2kb
  • 从空闲池中分配栈空间，如果池为空，则向mheap申请内存，并把多余的空间缓存到池中

    栈扩容

    linux系统下协程初始栈空间大小为仅仅只有2KB很小，仅分配了保障协程运行的最小空间。go的策略是按需申请，动态扩容，尽量减少内存浪费，每次扩容时会调用运行时方法runtime.morestack(SB) ->runtime.newstack(SB) 。

    栈收缩

    栈收缩是由gc触发执行的源码位置runtime/mgcmark.go，收缩时调用方法shrinkstack

深入理解StatefulSet

深入理解StatefulSet

StatefulSet是一种特殊的Deployment，它使用K8S里的两个标准功能Headless Service和PVC实现对拓扑状态和存储状态的维护。通过Headless Service管控每个Pod创建一个固定不变的DNS域名作为Pod在集群的网络标识。加上为Pod编号并严格按照编号顺序进行Pod调度，保证了StatefulSet对维护应用拓扑状态的支持。StatefulSet定义文件中的volumeClainTemplates声明Pod使用的PVC，它创建出来的PVC会以名称编号与Pod进行绑定，借助PVC独立于Pod的生命周期完成对应用存储状态的维护。

分布式事务的实现原理

分布式事务的实现原理

数据库事务拥有ACID四大特性：

  • Atomicity 原子性
  • Consistency 一致性
  • Isolation 隔离性
  • Durability 持久性

为了保证事务能在执行任意过程中回滚(原子性)并且提交的事务会永久保存在数据库中，使用事务日志来存储事务执行过程中数据库的变动，每个事务日志包含事务ID、当前被修改的元素、变动前后的值。当事务尝试对数据库进行修改时，先生成一条日志并刷新到磁盘中（append追加速度比较快），然后才会向数据库写入或更新相应的记录。

MYSQL中常用的存储引擎InnoDB中，事务日志有undo log、redo log两种。

并发执行SQL过程中可能无法保证数据库对隔离性的要求，为了避免并发带来的一致性问题、满足数据库对隔离性的要求，数据库系统往往都会使用并发控制机制来充分利用效率。常用的有：锁、时间戳、MVCC

分布式事务

单机中相对可靠的方法调用以及进程间通信方式没办法使用，由于网络不稳定服务之间的传递会出现障碍。分布式事务就是在不可靠的通信下实现事务的特性，分布式事务也会依赖数据库、Zookeeper、ETCD等服务追踪事务的执行过程，保证事务特性。

  • 2PC： 两阶段提交分为投票阶段和提交阶段，在投票阶段协调者向事务的参与者询问是否可以执行操作的请求，等待参与者相应。参与者执行相应的事务操作并记录重做和回滚日志，所有执行成功的参与者向协调者发送AGGREMENT/ABORT表示执行操作结果。协调者根据投票结果向参与者发送提交或回滚指令。两阶段提交是一种阻塞协议，如果事务执行过程中协调者宕机，事务的一部分参与者将永远无法完成事务，可能出现参与者状态不一致的问题。
  • 3PC：为了解决上述问题，引入超时机制和准备阶段。如果协调者或者参与者在规定时间内没有接收到来自其他节点的响应根据当前的状态选择提交或终止整个事务。当参与者向协调者发送 ACK 后，如果长时间没有得到协调者的响应，在默认情况下，参与者会自动将超时的事务进行提交，不会像两阶段提交中被阻塞住；

MySQL 的 InnoDB 引擎其实能够支持分布式事务，即 XA 事务；XA 事务就是用了2PC实现分布式事务，其中事务管理器为协调者，而资源管理器就是分布式事务的参与者。XA 确实能够保证较强的一致性，但是在 MySQL XA 的执行过程中会对相应的资源加锁，阻塞其他事务对该资源的访问，如果事务长时间没有 COMMIT 或者 ROLLBACK，其实会对数据库造成比较严重的影响。

Saga

两阶段提交其实可以保证事务的强一致性，但是在很多业务场景下，我们其实只需要保证业务的最终一致性，在一定的时间窗口内，多个系统中的数据不一致是可以接受的，在过了时间窗口之后，所有系统都会返回一致的结果。放弃满足ACID，选择实现 BASE(Basic Availability, Soft, Eventual consistency) 事务。

Saga 其实就一种简化的分布式事务解决方案，它将一系列的分布式操作转化成了一系列的本地事务，在每一个本地事务中我们都会更新数据库并且向集群中的其他服务发送一条的新的消息来触发下一个本地的事务；一旦本地的事务因为违反了业务逻辑而失败，那么就会立刻触发一系列的回滚操作来撤回之前本地事务造成的副作用。

Sagas解决长事务问题。

一周算法汇总

lc55_jump-game_Medium
实现

lc51_nqueen_Hard
实现

lc322_coin-change_Medium
实现
lc862_shortest-subarray-with-sum-at-least-k_Hard
实现

lc198_house-robber_Easy
实现
lc1622_fancy-sequence_Hard
实现

面试问题汇总:

  1. new 和 make的区别
    答:
    参考这篇文章Go语言中的make和new
    make是初始化内置的数据结构,如切片,哈希表,channel;
    在编译期间的类型检查阶段,GO语言将代表make关键字的OMAKE节点根据参数类型不同转换为OMAKESLICE,OMAKEMAP,OMAKECHAN三种节点,这些节点调用不同的运行时函数来初始化相应数据结构.

    • slice := make([]int, 0, 100)
    • hash := make(map[int]bool, 10)
    • channel := make(chan int, 5)
      new的作用是根据传入的类型分配一片内存空间,并返回这片内存空间的指针.
      对于new关键字编译器会在中间代码生成阶段先转换为ONEWOBJ类型的阶段,然后根据申请内存空间大小:0返回表示空指针的zerobase变量,反之转换成runtime.newobject函数在堆上申请内存.
      其中runtime.newobject函数会是获取传入类型占用空间的大小,调用runtime.malloc并返回指向这片内存的指针
    • i := new(int)
    • var v int | i := &v

  2. go 引用类型有哪些
    答：
    值类型有int，float， bool， string， 数组， struct
    引用类型有 指针，slice切片，map，channel，函数等
    两者的区别是，值类型变量直接存储值，内存通常在栈中分配；引用类型变量通常存储的是一个地址，这个地址对应的内存空间存储真正的数值，内存通常在堆中分配。

  3. go的内存模型中，为什么小对象多了会造成gc压力
    答： 小对象过多会导致GC三色法消耗过多的GPU

  4. 将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为 10*10/2

  5. golang中selct的多个case同时成立时，选择的是哪一个？
    答： select在遇到多个Channel同时响应时会随机挑选case执行， 这个设计是十多年前select提交引入并一直保留到现在的。如果多个条件满足时我们按顺序执行，那么后面的条件将会得不到执行，随机的引入是为了避免饥饿问题的发生。

  6. golang 中除了使用 sync 锁，还可以如何保证并发安全? atomic 是什么？
    答： golang的auomic院子操作是所有锁机制中效率最高的，能够使用原子操作的地方尽量使用。

  7. sync.Map 对键的类型有什么要求么？
    答： go语言规定键类型的值之间必须支持==和！=操作符判断，而函数类型，字典类型，切片类型不支持判等操作，因此键类型不能是上述几种类型。

  8. 如何避免死锁? golang 中如何检测死锁?
    答：

  9. 不使用 goroutine 怎么实现监听三个 channel，合并三个 channel，变成一个新的 channel，这三个任意有消息的时候都要给 新 channel 传递，都没消息的时候要关闭那个新的 channel？

    func merge(ins …<-chan string) <- chan string {
    var wg sync.WaitGroup
    out := make(chan string)

    p := func (in <-chan string) {

    defer wg.Done()
for c := range in {
  out <-c
}

    }
    }

Veröffentlicht am

虚拟内存是现代系统提供的一种对主存的抽象概念，它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域按需在磁盘和主存之间来回传送数据；为每个进程提供了一致的地址空间，简化了内存管理；并且保护每个进程的地址空间不被其他进程破坏。通过本章学习可以了解虚拟内存是如何工作的，以及如何在程序中使用和管理虚拟内存，避免一些和内存有关的错误出现。
现代系统通过内存映射将虚拟内存和磁盘文件关联，为共享数据、创建新进程以及加载程序提供了一种高效的机制。应用可以使用mmap函数来手工地创建和删除虚拟地址空间的区域。对于运行时才知道大小的数据结构，大多数程序通过动态内存分配器管理虚拟地址空间中的堆区域，并且显式或自动地释放内存。

  • 早期的PC通过物理寻址，现代处理器多采用虚拟寻址来访问主存，虚拟地址在被送到内存之前通过MMU地址翻译转换为物理地址。
  • 虚拟页，VM将虚拟内存分割为大小固定的块，虚拟页有以下三种：
    • 未分配的，没有任何数据与之关联，不占用任何磁盘空间；
    • 缓存的，当前已缓存在物理内存中的已分配页；
    • 未缓存的，未缓存在物理内存中的已分配页
  • DRAM缓存表示虚拟内存系统的缓存，是全相联的，因为虚拟页通常为4K-2M，不命中时替换开销较大，因此替换策略非常重要。因为对磁盘访问时间长，DRAM缓存总是使用写回而非直写。
  • 局部性原则保证了任意时刻，程序将趋向于在一个较小的active page集合上工作，即常驻集合/工作集。如果工作集的大小超出了物理内存大小，程序将产生一种不幸的状态，即抖动。页面将不断地换进换出。
  • 将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称为内存映射，Linux系统提供一个成为mmap的系统调用，允许应用程序自己做内存映射。
  • 正常命中时CPU硬件执行步骤：
    • 处理器生成一个虚拟地址并传送给MMU；
    • MMU生成PTE地址，从高速缓存/主存请求得到它；
    • 高速缓存/主存向MMU返回PTE；
    • MMU构造物理地址，并把它传送给高速缓存/主存；
    • 高速缓存/主存返回所请求的数据字给处理器
  • 当缺页时，需要硬件和操作系统内核写作完成：
    • 前三步相同
    • PTE有效位为0，MMU触发异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序；
    • 缺页处理程序确定出物理内存中的牺牲页，如果该页已经被修改，则把它换出到磁盘；
    • 缺页处理程序页面调入新的页面，并更新内存中的PTE
    • 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。主存将请求字返回给CPU。
  • 频繁读取PTE会使得内存多取一次数据，为了消除开销，现代系统利用TLB（MMU中一个PTE的小缓存）
  • 如果每个进程都在物理内存中保存常用代码的副本会比较浪费，内存映射提供了一种机制控制多个进程共享对象。一个对象可以被映射到虚拟内存的一个区域，作为共享对象或者私有对象。对于共享对象，进程对该区域的任何写操作，其他把该对象映射到虚拟内存的进程也可见。私有对象使用写时复制的技术被映射到虚拟内存中，延迟私有对象中的副本到最后可能的时刻来充分利用物理内存。
  • Fork调用时，内核为新进程创建虚拟内存，创建了当前进程的mm_struct、区域结构和页表的原样副本，将两个进程的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。当fork在新进程中返回后，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当两个进程中的任何一个后来进行写操作时，写时复制都会创建新页面，即为每个进程保持了私有地址空间的抽象概念。
  • 程序使用动态内存分配的最重要原因是直到程序实际运行时才知道某些数据结构的大小，数据大小的最大值可以由可用的虚拟内存数量来限制。
  • 管理和使用虚拟内存中常见的错误类型：间接引用坏指针，读取未初始化的内存、允许栈缓冲区溢出、假设指针和它们指向的对象大小相同，引用指针而不是它指向的对象、误解指针运算、引用不存在的变量、以及引起内存泄漏等。

Veröffentlicht am

本周主要学习了异常控制流ECF（Exception Control Flow）相关知识，它可以发生在计算机系统的各个层次，是操作系统用来实现I/O、进程和虚拟内存的基本机制。应用程序通过ECF和操作系统进行交互，如磁盘写数据、网络读取数据、创建新进程、终止当前进程等。理解ECF可以帮助我们编写有趣的应用程序并且更好得理解并发。C++/Java语言提供的异常处理机制，允许程序运行非本地跳转来相应错误，这些都是ECF的一种应用层形式。

  • 异常是控制流中的突变，用来响应处理器状态中的某些变化。在任何情况下，处理器检测到有事件发生时，它会通过异常表来进行间接过程调用，到异常处理程序来处理。完成处理后根据异常类型有以下3种情况：

    • 处理程序将控制返回给当前指令；
    • 处理程序将控制返回给下一条指令并执行；
    • 处理程序终止被中断的程序

  • 异常和过程调用的区别：

    • 过程调用时，在跳转前处理器将返回地址压栈。异常处理时根据异常的类型返回地址要么是当前指令要么是下一条指令；
    • 处理器也把一些额外的处理器状态压到栈里，在处理程序返回时，重新开始执行被中断的程序会需要这些状态。如X86-64会压入包含当前条件码的EFLAGS寄存器
    • 如果控制从用户程序转移到内核，则压入内核栈中
    • 异常处理程序运行在内核模式下

  • 异常类型： 中断interrupt、陷阱trap、故障fault、终止abort

    • 中断： 来自I/O设备的信号/异步/总是返回到下一条指令
    • 陷阱：有意的异常/同步/总是返回到下一条指令 （用途： 在用户程序和内核之间提供一个像过程一样的接口，叫做系统调用）
    • 故障：潜在的可恢复的错误/同步/可能返回当前指令 （如缺页异常）
    • 终止：不可恢复的错误/同步/不会返回

  • 上下文切换是内核使用的一种较高层形式的异常控制流，用来实现多任务。

  • 父进程通过fork函数创建子进程，子进程得到与父进程用户级虚拟地址空间相同的一份副本，包括代码和数据段、堆、共享库以及用户栈。子进程还获得与父进程打开文件描述符相同的副本，可以读写父进程中打开的任何文件。两者最大的区别在于不同的PID。 fork函数被父进程调用一次，返回两次—- 一次是返回到父进程，一次返回到新创建的子进程。在父进程中fork返回子进程的PID；在子进程中fork返回0.
  • Linux信号是一种更高层的软件形式的异常，允许进程和内核中断其他进程。一个发出来没有被接收的信号叫做待处理信号，在任何时刻一种类型至多只会有一个待处理信号。（后续发送的不会排队等待，被简单丢弃）