容器镜像与持久化

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

Read more

容器化技术

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

Read more

计算机网络复习

前置知识:

  • 网络

计算机网络复习

主要考点

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

  • 物理传输介质种类:

    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++实现线程池

前言

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

Read more

2020 6.824 lab1解析

前置知识:

  • go
  • linux

2020 6.824 lab1解析

前言

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

Read more

git的使用

前置知识:

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的概念对开发还是有意义的。

Bomb Lab解析

前置知识:

  • 汇编
  • GDB

Bomb Lab解析

前言

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

Read more

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

前置知识:

  • 数学

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

题目要求

给定一个极其大的数据流,大到无法存入内存,要求在所有数据中随机选取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。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×