本文为容器化技术系列文章的第二篇。本文将把容器技术与文件系统，压缩文件相结合，并且实现commit命令，用于保存镜像文件。

  本文将介绍简易正则转nfa的一个python实现。

  容器化技术作为当今热门的技术，已经形成的成熟的应用以及活跃的生态。越来越多的程序采用容器技术来进行封装。容器技术极大地改善了程序，简化了程序部署。其轻量化的特性也被许多解决方案所青睐。
  本文旨在从零开始，构建一个类docker的容器应用，并且实际运行，同时对其中的原理进行剖析。

  本文为容器化技术系列文章的第一篇。本文将介绍容器化中的隔离，限制的原理，并且实际编写一个类docker应用，并且实际执行docker run命令。

前置知识：

• 网络

计算机网络复习

主要考点

选择题/填空题/简答题/综合计算

• 物理传输介质种类：

  1. 引导型传输媒体：
     • 双绞线 同轴电缆 光缆
  2. 非导引型传输媒体：
     • 地面微波 卫星通信

• 网络协议定义，三要素：

  1. 定义：为进行网络中数据交换而定义的规则或标准
  2. 三要素：
     • 语法：数据与控制信息的结构或格式
     • 语义：发出何种控制信息，完成何种动作，作出何种响应
     • 同步：事件实现顺序的说明

• CSMA/CD，CSMA/CA工作原理：

  1. CSMA/CD：载波监听多点介入/碰撞检测
     • 多点接入：总线型网络
     • 载波监听：检测传输过程中是否有其他计算机发送，就是不停检测信道
     • 碰撞检测：边发送边监听。检测到电压变化幅度过大则停止检测
     • 使用该协议，只能半双工通信
     • 在检测到空闲后，推迟一个随机的时间，然后重传
  2. CSMA/CA：载波监听多点介入/碰撞避免
     • 碰撞避免：减少碰撞发生的概率
     • 发送数据之前先检测信道，检测为空闲则等待一个帧调节时间后发送，目的接受后则在等待一个短帧间隔后发送ACK，然后开始通信。源站还需要将占用时间发送给其他站。然后在忙变空闲后，在等待一个帧调节时间后进入争用窗口期，所有发送的站都要执行退避算法，随机选择一个时间间隙开启计时器，遇到忙则冻结。

• 子网路由与主机路由区别：

  • 路由到子网和路由到主机

• 数据链路层功能，透明传输实现：

  • 链路是从一个节点到相邻结点的一段物理线路 数据链路则是在链路基础上增加必要的硬件软件
  • 向该层用户提供透明可靠的基本服务
  • 三个问题：封装成帧 透明传输 差错检测
    1. 封装成帧：规定数据最大传送单元MTU，添加首部SOH，尾部EOT 转义数据报
    2. 透明传输：转义数据报 添加ESC字符转义
    3. 差错检测：CRC 仅检测不纠错

• MAC地址/IP地址：

  1. 硬件地址，又称为物理地址与MAC地址，就是适配器地址或者适配器标识符。单个站地址 多播地址 全球管理 本地管理
  2. IP地址：网络层以及以上使用地址，逻辑地址，路由器只根据IP进行选择 链路层只能看见MAC帧，IP层屏蔽了许多细节
  3. ARP：使用ARP高速缓存 建立ARP映射表 动态更新
  4. ARP过程：广播ARP请求分组 得到ARP响应 写入映射表

• TCP链接，三次握手四次挥手：

  1. 三次握手
     • 客户打开链接 创建传输控制模块TCB
     • 客户向服务器发送SYN=1以及自己的序号X
     • 服务器返回SYN=1 ACK=1 自己的序号Y ack数字X+1
     • 客户机返回ACK=1 序号x+1 ack=y+1 并可以传输数据
  2. 四次挥手：
     • 客户主动关闭，向服务发送FIN与序号
     • 服务器照旧发送ACK与seq ack
     • 服务器向客户确认FIN 发送ACK seq ack与上次ack相同
     • 客户照旧确认
     • 客户等待2MSL后关闭
  3. 可靠传输实现：
     • 滑动窗口：以字节为单位。通过窗口滑动和累计确认来实现。有缓存用于存储乱序到达或者接受但未被读取的数据
     • RTT计算：RTT_new = (1-a)RTT_old + a(RTT_sample) a=0.125
     • 超时时间RTO计算：RTO = RTT + 4(RTTd) RTTd_init = 0.5(RTT) RTTd_new = (1-b)RTTd_old + b(abs(RTT_new-RTT_sample)) b=0.25
     • 选择确认：头部加上确认边界，防止重传浪费

• TCP拥塞控制算法，计算：

  1. 拥塞控制：防止过多的数据注入到网络中全局性的过程 流量控制是点到点通信量控制
  2. 开环控制：设计网络时候将拥塞因素考虑周到;闭环控制：检测网络系统拥塞状态，将信息传达到可采取行动的地方 调整网络解决问题
  3. 慢开始：幂函数开始 直至达到门限
  4. 拥塞避免：每过一个RTT则增加1
  5. 快重传：收到一个即使顺序不对也确认
  6. 快恢复：3ACK后减半开始拥塞避免
  7. 3ACK减半 超时则归为1 门限都减半
  8. AMQ：主动队列管理 小于最小门限则保留 超过最大门限则丢弃 在中间则随机丢弃

• IP子网相关计算，超网：

  1. IP可以分为网络号，子网号，主机号
  2. IP可以划分为A，B，C类，对应255.0.0.0 255.255.0.0 255.255.255.0
  3. 子网掩码与地址取AND，得到网络号地址。子网号位数决定子网数量，通常去掉全0和全1。子网主机数同理。
  4. 每一个CIDR地址数都是2的整数幂次倍数，相当包含网络数为2的网络数位数减去CIDR位数幂次

• CRC计算：

  • 被除数左移除数位数-1位，处以被除数，得到余数并加上。
  • 余数为0则没有差错

• RIP路由计算：

  • 基于距离向量的路由选择协议
  • 距离为跳数
  • 仅和相邻路由器交换信息，交换信息为自己的路由表，按照固定时间间隔交换
  • 距离算法：将表距离加1,下一跳转为目标主机，更新
  • 实现简单 开销较小 好消息传得快 坏消息传的慢
  • 网络规模小，最多为15 收敛慢

• 网络拓补结构：

  1. 边缘部分，核心部分
  2. 边缘部分：用户直接使用的，处于互联网的所有主机，又叫端系统。通信方式可分为CS方式和P2P方式
     • 客户-服务方式：服务请求方和服务提供方。客户想服务器请求，不需要特殊硬件和复杂操作系统。服务可同时接受多个请求，需要很强大性能与软件支持。
     • P2P：对等连接方法
  3. 核心部分：给端系统提供服务的。路由器，交换机等。
  4. 局域网可分为星形网 环状网 总线网

• 交换技术种类：

  • 电路交换特点：端到端建立专用物理通路 建立链接 通话 释放链接 在通话全部时间里，两个用户始终占用端到端通信资源
  • 分组交换特点：采用存储转发技术 整块发送报文 将报文加上必要头部发送 需要传输路径
  • 电路交换时延：电路建立连接时间S+报文总量X/数据率B+链路个数K multiply 链路传播时延B
  • 分组交换时延：发送完最后一个分组结束 即经过k-1次转发 时延=数据总长度x/数据率b+（k-1）分组长度p/数据率b+k(传播时延b)

• 编码技术种类：

  • 不归零制：正电平为1 负电平为0
  • 归零制：正脉冲为1 负脉冲为0
  • 曼彻斯特编码：向下跳变为1 向上跳变为0
  • 差分曼彻斯特：从边界开始跳变为0 边界不跳变为1
  • 调幅：载波的振幅 01表示不同振幅
  • 调频：载波的频率 01对应不同频率
  • 调相：初始相位随基带变化而变化
  • 一般采用混合调制 正交振幅调制

• 信道复用技术：

  • 频分复用：占用不同的频道带宽
  • 时分复用：在不同时间占用同样的频带宽度 切分时间为固定长度组
  • 统计时分复用：先集中器，再分配时间
  • 波分复用：光的频分复用
  • 码分复用：用户之间正交

• 网络互连，互连的设备，层次：

  • 计算机，集线器，路由器，交换机等，手机等智能机器
  • 网络将许多计算机连接在一起 互连网将许多网络通过路由器连接在一起
  • 多ISP结构互联网，有主干ISP 地区ISP 本地ISP
  • 互联网交换就诶点IXP允许两个网络直接相连而不必经过最上层主干ISP

• OSI IEEE体系结构分层：

  • OSI七层模型：应用层 表示层 会话层 传输层 网络层 数据链路层 物理层
  • OSI缺点：缺少实际经验 商业驱动 实现复杂 效率地下 制定周期长 运作不合理
  • 实际运用为TCP/IP标准
  • IEEE：802.11 数据链路层分为逻辑链路控制子层 介质访问控制子层

• 面向连接，无连接应用，区别：

  • 通信前建立连接，完成后释放连接/尽最大努力
  • 传输控制协议TCP：提供面向连接的，可靠的数据传输服务，传输单位为报文段
  • 用户数据报协议UDP：无连接的，尽最大努力的数据传输服务，传输单位为用户数据报

• 网络定义，网络分类：

  • 计算机网络主要是由一些通用的 可编程的硬件互联而成 这些硬件并非专门用来实现某一特定目的 可编程的硬件能用来传输不同类型数据 并且支持广泛和日益增长的应用
  • 广域网WAN：几十到几千公里;城域网MAN：一个城市;局域网LAN：用于微型计算机或工作站相连;个人区域网PAN：个人使用的电子设备互联
  • 公用网：电信公司建造大型网络;专用网：特殊业务服务，如军队网络。

• DNS作用：

  • DNS根服务器采用任播技术 即相同IP但物理位置不同 因而总能找到最近的服务器
  • 递归查询 迭代查询
  • 将域名解析为IP

• 动态网页实现技术：

  • CGI通用网关接口：定义动态文档如何创建，输入数据如何提供给应用程序 输出结果如何使用
  • CGI程序又叫CGI脚本
  • 服务器推送技术 TCP开销大
  • 活动文档技术 把工作交给浏览器

• HTML，XML区别：

  • HTML：超文本标记语言 展示文档
  • XML：可扩展标记语言 用于数据存储，传输等。

前置知识：

• c++
• 操作系统

C++实现线程池

前言

  本文使用C++基本库，实现了固定线程数量的线程池。

前置知识：

• go
• linux

2020 6.824 lab1解析

前言

  本系列主要是对mit课程6.824的lab进行解析，包括部分原理的讲解以及代码的实现。主要使用go来进行编写。本文讲解的是lab1，根据给定的代码框架来实现MapReduce结构。

前置知识：

• 无

git的使用

前言

我发现我这个废物到现在没有系统性学习git，于是写了本文。主要用于加强记忆，备忘。

介绍

git，又叫分布式版本控制系统。版本管理系统，意味着对项目的版本进行管理，可以退回到历史版本，也可以在历史版本基础上开发新版本，可以将分支的版本合并到主要版本从而便于开发。分布式意味着每台电脑上都是完整的版本，而非版本的一部分。

基本概念

git主要有三个主要的基本概念：工作区， 版本库，暂存区。
工作区：即工作目录，主要进行开发的位置。
版本库：一般在工作目录中的隐藏文件夹.git目录中，git用于管理的工作目录。
暂存区：类似于存放项目内文件的各种类修改操作。存放于index文件中。具体实现可以参考原理，本文不过多概述。

git常用命令

git init：初始化工作目录，创建.git文件夹从而便于开始管理。
git add：接文件名，在工作目录中搜索对应文件名，并且将文件存入暂存区。
git commit：提交所有或者部分暂存区文件到仓库。一般加-m参数来写提交注释。一定要写提交注释。
git status：查看仓库当前状态。
git diff：查看未提交记录与提交过的具体文件差别。
git log：查看log。
git reset：有三种模式。可以使用–hard来更新工作区，暂存区，仓库所有文件到目标commit记录（参数为commit 的sha1）或者回退到之前几个版本（参数为HEAD^。尖号数量代表往前几个版本），通常用于回滚版本。另外两种模式可参照对应文档。
git reflog：查看命令的日志。
git checkout –filename：将工作区的文件修改撤销掉，换成最新的暂存区内或者版本库内的文件。
git reset HEAD file：撤销暂存区的文件修改。
git rm：版本库中删除对应文件。如果确实删除后需要提交。
git clone：从对应库中拷贝项目。
git mv：移动或者重命名对应文件。
git branch：创建分支。
git checkout：移动到分支。
git merge：合并分支。如果出现冲突则手动解决冲突后git add对应文件。
git push：将文件推到远程库。
git pull：将远程库拉到本地库并覆盖。
git stash：将当前目录保存起来，之后可以切换分支改bug，改完后用git stash pop来恢复现场。
git rebase：将多个commit记录合并并接到另一个分支之后。用于整合commit记录。

总结

主要包含了git的常用命令以及基本概念，各种参数不全面，各种功能描述也可能不全面或者有误，但主要功能基本准确。现在虽然ide帮我们做了很多，但学习一些git的概念对开发还是有意义的。

前置知识：

• 汇编
• GDB

Bomb Lab解析

前言

Bomb lab是《深入理解计算机系统》配套实验之一。可执行程序包含着“炸弹”，必须输入六个正确的字符串来进行拆弹。字符串必须通过对程序的汇编码进行分析来得到。本文通过分析拆弹流程，对反汇编技术技巧进行总结。

前置知识：

• 数学

面向面试编程-蓄水池算法

题目要求

给定一个极其大的数据流，大到无法存入内存，要求在所有数据中随机选取k个元素。

解法：蓄水池算法

假设读取第i个数据，从1开始计数。如果i小于等于k，则存入蓄水池。如果i大于k，则随机取从1到i之间的随机数m，如果m处于1到k中，那么将i元素替换蓄水池中m元素。
证明
对于蓄水池中的元素，被选中的概率是不被蓄水池外的元素替换掉的概率。即k×(k+1)×…×(N-1)/((k+1)×(k+2)×…×(N)) = k/N。
对于蓄水池外的元素，假设位置i，那么概率为选中的概率乘以不被后面元素替代的概率。即(k/i)×(i/(i+1))×…×((N-1)/N) = k/N。