0. 如何判断一门语言的好坏

没有评论

我在组内推广 Kotlin 遇到不少挑战，虽然我自己觉得它确实是一门优秀的语言，有着丰富的特性，能提高我们开发效率，减少 bug 的出现，但同事们并不觉得。而且他们的观点往往不是“Kotlin 并没有比 Java 好多少”，而是“Kotlin 就没比 Java 好“。Kotlin 语法不习惯；Kotlin 这样强推这么多年，也不温不火，说明 Kotlin 不行。

所以本着“先问是不是，再问为什么”的原则，我们在讨论“Kotlin 比 Java 好在哪里之前”，必须先说清楚“Kotlin 比 Java 好吗”这个问题。

关于判断语言是否优秀，我们听过最多的可能就是“XXX 是最好的语言”了。不过这种旧世界的观点，在大家充分学习了网络上的编程知识之后，现在都成为大家调侃的段子了。现在，我们更喜欢“编程语言没有优劣之分”，“没有最好的编程语言，只有最适合的应用场景”这样的论调。这听起来就很有哲理，很编程正确嘛！如果把这些的观点套在 Java 和 Kotlin 身上，也可以得到“要根据具体场景，有些场景确实 Java 更好”的观点。

不过今天，我们不谈这些和稀泥的观点。这篇文章会告诉大家，客观准确评判一门语言好坏的标准。

无论如何，编程语言是给人使用的，那我们就从人本身特点出来来讲这个逻辑。我们人是靠大脑思考的，而大脑有个致命的缺点：容量有限，且有一定错误率。这就导致我们程序员在编写状态复杂，流程冗长的代码的时候，容易出现错误。这是人大脑的特点决定的，无法避免。

但劳动人民的智慧是无穷的，程序员们想出各种办法来降低自己犯错概率。从机器码到汇编，到面向流程，到面向对象，到设计模式，编码规范，高级语法特性，不断有新编程技术的出现，让程序员们可以写更简单的代码。也就是用更抽象的表达来表示同样的意图。

阿拉伯人：30 加 42 等于 72。

法国人: 30 加 40又2 等于 60又10又2。

你能想象，用汇编去实现你现在要的一个业务，需要多长时间？写出来会有多少个 bug 吗？当你用 Python 快速实现了一个算法并开始验证的时候，别人可能还在用 C++ 吭哧吭哧地写着 std::vector 的 for 循环；当你用 Swift 快速实现了一个 iOS demo 的时候， 别人可能还在用 objective-C 吭哧吭哧的写着头文件声明；当你用 Go 的协程快速实现了并发处理时，别人可能还在用 Java 吭哧吭哧地实现一个线程池。又或者说，用 C++ 和 Java 实现同一个需求，C++ 你需要花费额外的精力关注内存管理，数组越界，类型安全等问题，这样你留给业务本身的精力就少了，开发变慢了，bug 也更容易出现了。

Java：你知道单例线程安全的四种写法吗？

Kotlin：你是说 by lazy 吗？

编程语言是为了实现业务而存在的，那我们就应该选择一门实现业务编写效率高，维护成本低的编程语言。

编写效率高意味着同样的功能我可以用更少的代码实现；同时 sdk 功能齐全，轮子多，大部分基础组件不需要重复开发。没错就像 Python 那样。Kotlin 相比 Java，他的语法表达更简洁，更容易写出低耦合，高内聚的代码；且和 Java 互操作的特性，可以直接使用 Java 的轮子，大大缩短了建设 Kotlin 生态的过程。

维护成本低分为几个方面，分别是：bug 少，代码简洁易懂，对需求变更友善。

bug 少。国外有对千行 bug 数量进行了研究，研究提出 bug 数量和所使用的语言没有直接关系，和语法表达流畅性有关系^[https://stackoverflow.com/questions/2898571/basis-for-claim-that-the-number-of-bugs-per-line-of-code-is-constant-regardless], ^[https://stackoverflow.com/questions/2898571/basis-for-claim-that-the-number-of-bugs-per-line-of-code-is-constant-regardless]。 我觉得可以理解为，人大脑的犯错频率是比较固定的，使用时长越长，出现的“bug”也就越多。如果你能通过选择一门语言，更快的实现指定功能，那么 bug 数量会相应减少。

代码简洁易懂。Kotlin 需要编写的代码更少，是因为 Kotlin 对语意有更精简的表达，你在习惯之后可以比 Java 更快的阅读完同样的功能。这点在后面我会继续说明。

对需求变更友善。这是代码简洁易懂的自然延伸，所谓 less is more 嘛。

Pythonista：人生苦短，我用 Python。

Androider：以前我没得选，现在我想做个 Kotlin boy。

PS：我也了解到很多同学拒绝 Kotlin 的理由是“不习惯”。比如说语法用着不习惯，看着也不习惯，很难看懂云云。我想说的是，无论是编程语言还是其他工作外的事，千万要忌讳用“习惯”作为理由。那些 30 多岁的外企程序员，失业中年危机，不就是“习惯”习出来的么？习惯会让你避开新的东西，而能让你能力，事业，资产产生“增量”的，往往就是这些新的东西。新的东西最容易产生“增量”。

我们判断一个东西好不好，有没有价值，有没有必要去投入，不要用“习惯”。要把好与不好列出来。就像我这样，我说 Kotlin 好，我把好的理由讲给你听，你觉得没道理，你可以针对这些点进行反驳，或者提出新的观点，然后和我进行讨论。用“不习惯”作为理由来拒绝，只会让自己错失“增量”的机会。

版权所有，转载请注明出处：
https://sickworm.com/?p=1766

Kotlin 从拒绝到真香

没有评论

《Kotlin 从拒绝到真香》是一系列介绍 Kotlin 好用的特性的文章。文章会以某一个经典的 Java 使用场景开始，提供相应的 Kotlin 实现代码，并讲解其中用到的特性。

文章主要面向 Android 开发者。如果你正在考虑是否使用 Kotlin 来代替 Java 作为 Android 开发语言，这些文章会非常适合你。笔者所在团队正积极使用 Kotlin，并有计划的使用 Kotlin 重构项目代码。但对团队成员来说，使用 Kotlin 并不是强制的。笔者团队内推广 Kotlin 的过程中也遇到了部分同事“拒绝”Kotlin，而这些文章正是我在推广和不断尝试说服他们的过程中逐渐积累起来的“真香”部分。

文章不求鞭辟入里，但尽可能保证有趣不枯燥。如果恰好你也喜欢这些文章，请务必 star 它！

作为 Android 开发者的你肯定已经拥有了 Android Studio，但我还是建议你下载一个 JetBains CE 或其他版本，这样你可以方便的创建一个 Kotlin 文件并运行它。大部分例子中，我们只需要 kotlin 的环境就可以了。
https://play.kotlinlang.org 是一个在线 Kotlin playground，使用它可以方便快速的运行一小段代码。

版权所有，转载请注明出处：
https://sickworm.com/?p=1760

Merkle Patricia Trie（翻译）

没有评论

原文：https://github.com/ethereum/wiki/wiki/Patricia-Tree

改良的 Merkle Patricia Trie 规范（又称为 Merkle Patricia Tree）

Merkle Patricia Trie（下简称 MPT 树，Trie 又称前缀树或字典树）尝试提供一种加密认证的数据结构，其可用于存储任意类型的的键值对。本文仅讨论键值对为字符串的情况（对于其他类型，只需要使用某种序列化方式将其转换为字符串即可）。这些键值对是完全确定的，这意味着两颗具有相同键值对的 Patricia 前缀树，它们的数据是保证完全一致的，因此也拥有相同的根哈希（root hash）。MPT 树提供优秀的 O(log(n)) 时间复杂度的插入，查询和删除性能。此外 MPT 树也比一些基于比较的替代方案（如红黑前缀树）更好理解和实现。

主要技术指标：Merkle Patricia Trie

但是，radix 树有一个较大的缺点：存储效率很低。举个例子，如果你只存储一个路径/值对，而这个路径长64个字符（32 字节的半字节（Hex）表示，正如以太坊的状态树一样），你将需要近 1K 的额外空间，一层一个字符地存储这个路径，并在需要删除它的时候花上整整 64 步。本文的 Patricia 树正是用来解决这个问题的。

改进

MPT 树通过提高原本的数据结构的复杂度，来尝试解决效率问题。MPT 树的节点可分为 4 种类型：

  1. NULL 空节点，用于表示空字符串
  2. branch 分支节点，具有 17 个项 [v0 ... v15, vt]
  3. leaf 叶子节点，具有 2 个项 [ encodedPath, value ]
  4. extension 扩展节点，具有 2 个项 [ encodedPath, key ]

在使用长为 64 个字符的路径的情况下，在遍历前缀树的前面几层的节点之后，后面层的节点很大可能都不再是发散的路径，而是一条单一路径。如果此时还按照前面的节点一样配置 index（Hex 字符集，共 16 个），则除了其中 1 个 index 不为空之外（即目标路径的下一个字符），剩余 15 个 index都是空的。这样做显然是不明智的。所以我们使用扩展节点 [ encodedPath, key ] 来快速处理这种单一路径。其中，encodePath 包含要跳过的”局部路径”（partial path，使用了下面提到的紧凑编码），key 用于下一次的数据库查询。

对于用 encodePath 第一个半字节就可以确定的叶子节点，上面提到的情况同样存在，且跳过的”局部路径”即完整路径的剩余部分。此时 value 即目标值。

当遍历半字节路径时，我们可能最终得到一个奇数个半字节的遍历路径。但因为所有的数据是以 bytes 格式存储的，因此不可能区分下面这种情况：半字节 1，和半字节 01 （两者都应该存储为 <01>）。所以如果要指定奇数长度，则在局部路径加上前缀标记。

规范：带可选终结符的十六进制序列的紧凑编码

上面提到，局部路径的首位半字节用于标记一个 2 项节点的属性：奇数剩余路径长度/偶数奇数剩余路径长度 和 叶子节点/扩展节点 。定义如下：

 HEX 值     位值     |     节点局部路径类型           路径长度
----------------------------------------------------------
   0        0000    |        扩展节点                偶数        
   1        0001    |        扩展节点                奇数         
   2        0010    |    终止节点 （叶子节点）         偶数        
   3        0011    |    终止节点 （叶子节点）         奇数

对于偶数剩余路径长度（0 或 2），将始终跟随另一个“填充”的半字节 0。

def compact_encode(hexarray):
    term = 1 if hexarray[-1] == 16 else 0 
    if term: hexarray = hexarray[:-1]
    oddlen = len(hexarray) % 2
    flags = 2 * term + oddlen
    if oddlen:
        hexarray = [flags] + hexarray
    else:
        hexarray = [flags] + [0] + hexarray
    // hexarray now has an even length whose first nibble is the flags.
    o = ''
    for i in range(0,len(hexarray),2):
        o += chr(16 * hexarray[i] + hexarray[i+1])
    return o

示例：

> [ 1, 2, 3, 4, 5, ...]
'11 23 45'
> [ 0, 1, 2, 3, 4, 5, ...]
'00 01 23 45'
> [ 0, f, 1, c, b, 8, 10]
'20 0f 1c b8'
> [ f, 1, c, b, 8, 10]
'3f 1c b8'

以下是在 MPT 树中获取节点的扩展代码：

def get_helper(node,path):
    if path == []: return node
    if node = '': return ''
    curnode = rlp.decode(node if len(node) < 32 else db.get(node))
    if len(curnode) == 2:
        (k2, v2) = curnode
        k2 = compact_decode(k2)
        if k2 == path[:len(k2)]:
            return get_helper(v2, path[len(k2):])
        else:
            return ''
    elif len(curnode) == 17:
        return get_helper(curnode[path[0]],path[1:])

def get(node,path):
    path2 = []
    for i in range(len(path)):
        path2.push(int(ord(path[i]) / 16))
        path2.push(ord(path[i]) % 16)
    path2.push(16)
    return get_helper(node,path2)

《计算机网络：自顶向下方法》笔记（6）：无线网络和移动网络

没有评论

无线网络和移动网络

无线网络的分类根据：1. 分组是否跨越多个无线跳，2. 是否有基站这样的基础设施

  • 单跳 + 有基础设施：普通的室内 Wifi，3G，4G 网络
  • 单跳 + 无基础设施：蓝牙，具有自组织模式的 802.11
  • 多跳 + 有基础设施：无线网状网络。结点为了与某基站通信，需要通过其他无线结点做中继。
  • 多跳 + 无基础设施：移动自组织网络（MANET），车载自组织网络（VANET）。

无线链路的网络特征：信号强度递减，其他信号源干扰，多路径传播。

CDMA，码分多址，对每一个数据比特都进行编码，如 1 编码为（1,1,-1,1,1,1,-1,-1）（实际要长得多），0编码相反。编码后发送到无线链路，每个比特发送都需要 1 比特时隙时间。当无干扰时，接收方通过编码序列（1,1,-1,1,1,1,-1,-1）可以得到原数据比特。当有干扰时，CMDA 认为链路信号是叠加的，不同设备使用不同的编码，信号叠加后，如果编码是精心挑选的，接收方仍可通过编码序列恢复算法恢复特定设备的原数据比特。

WiFi，也称 IEEE 802.11 无线 LAN，从 90 年代研发的许多无线 LAN 标准和技术中胜出。现有几套相关标准：b，a，g。

  • 802.11b，2.4GHz，85MHz 频段，最大速率 11Mbps
  • 802.11a，5GHz，700Mhz 频段，最大速率 54Mbps
  • 802.11g，2.4Ghz，85MHz 频段，最大速率 54Mbps
  • 802.11n，多输出多输入（MIMO），可达几百 Mbps
  • 其他，如 802.11i，使用更安全的加密算法 AES 设计加密协议

这三个标准都是用相同的媒体访问协议 CSMA/CA，使用相同的帧格式，都具有降低传输速率以到达更远距离的能力，都允许“基础设施模式”和“自组织模式”两种模式。但物理层有重要区别。

802.11b 频段和 2.4G 电话与微波炉一样；802.11a 频率高，所以传输距离短，受多径传播影响更大。g 是 b 的速率升级版，向后兼容。

802.11b/g 定义了 11 个部分重叠的信道，仅当 2 个信道间隔 4 个信道以上时才无重叠。

802.11 要求每个 AP 周期性地发送信标帧（beacon frame），包含 AP SSID 和 MAC 地址。设备接收到信标帧后，一般选最高信号强度用于关联。

802.11 的链路层协议，CSMA/CA，带碰撞避免（CA）的载波侦听多路访问，每个站点在传输之前侦听信道，一侦听到该信道则抑制传输。因为无线设备实现碰撞检测因物理特性原因效果不好。

以太网使用碰撞检测；802.11 使用碰撞避免，并使用确认重传（ARQ）来保证较高误比特率下的效率。

802.11 帧：

帧控制 2 | 持续期 2 | 地址1 6 | 地址2 6 | 地址3 6 | 序号控制 2 | 地址 4 | 有效载荷 0~2312 | CRC 4

地址 2：传输该帧的站点的 MAC 地址

地址 1：要接收该帧的站点的 MAC 地址

地址 3：当设备和路由器中间隔着 AP 时，用于定位目的 MAC 地址

当设备移动时，会从一个 BSS 移动到另一个 BSS。如果 BSS 属于同一个子网（此时接入点 AP 是交换机），则 IP 地址不变，TCP 连接保持连接。如果不属于同一个子网（此时接入点 AP 是路由器）

802.11 还有几个特性：

  1. 速率适应：当结点离基站近时，信噪比高，使用高速率；远时信噪比低，发送失败率高，此时用低速率。速率变化的条件是一个结点连续发送两个帧而没有收到确认，则降低速率；如果连续 10 个帧收到确认，则提高速率。策略和 TCP 相似。

  2. 功率管理：结点想要休眠时，会发送帧通知接入点，接入点会缓存休眠结点的所有帧，以后再传输。结点会在信标帧发送前唤醒自己（250us 就能唤醒，而信标帧 100ms 发送一次），然后接入点会在信标帧发送的同时把缓存的帧一并发过来。结点无发送接收帧的情况下，99% 时间都在休眠。

蓝牙，802.15.1 无线个人区域网络（WPAN），2.4 GHz，时隙长度 625us，79 个信道。时隙之间以一个已知的伪随机方式变更信道，称为跳频扩展频谱（FHSS）。速度可达 4Mbps。蓝牙是自组织网络，会建立可多达 8 个设备的皮可网（piconet），其中一个被指定为主设备，其余为从设备。主设备控制皮客网，时钟以主设备为准，奇数时隙中发送，从设备收到后在下一个时隙会回复主设备。蓝牙还可以有多达 255 个寄放设备。

ZigBee，802.14.5，比蓝牙更低功耗，低速率，低成本。ZigBee 定义了 20kbps，40kbps，100kbps，250kbps 的信道速率。

蜂窝因特网，称为 GSM，1G 是模拟 FDMA 系统，专门用于语音通信，2G 是 FDM/TDM，扩展了对数据（因特网）的支持（2.5 G）。3G 4G 提高速率。

移动 IP，是指移动结点在切换不同的接入点时，通讯保持连接无需断开的解决方案。每个移动结点都有一个归属网络（home network），归属网络中执行移动管理功能的实体叫归属代理（home agent）。移动结点当前所在的网络叫外部网络（foreign network），或被访网络（visited network）。与该结点通信的实体叫通信者（correspondent）。

外部代理的作用就是为移动结点创建一个转交地址（Care-Of Address，COA），COA 用于将数据报通过外部代理重新路由选择到移动结点。即封装一层转发过去。

版权所有，转载请注明出处：
https://sickworm.com/?p=1741

《计算机网络：自顶向下方法》笔记（5）：链路层

没有评论

链路层

链路层协议的任何设备称为结点（node）

沿着通信路径连接相邻结点的通信信道称为链路（link）

链路层协议功能：

  • 成帧（framing）。把数据报（segment）封装成帧。

  • 链路接入。媒体访问控制（Medium Access Control，MAC）用于协调多个结点共享单个广播链路时候的帧传输。

  • 可靠交付。通过确认和重传保证无差错移动每个网络层的数据报。对于差错率低的链路，如光线，同轴电缆等，则不提供可靠交付，由上层保证可靠交付。

  • 差错检测和纠正。（通过校验和）

链路层使用更复杂的 CRC 差错检测是因为其使用了专门的硬件实现。

有两种网络链路：点对点（point-to-point link）链路和广播链路（boardcast link）。

点对点链路使用点对点协议（point-to-point protocol, PPP）和高级数据链路控制协议（high-level data link control, HDLC）。

广播链路涉及协调多个发送和接收结点对一个共享广播信道的访问，也就是多路访问问题（multiple access problem）。对应的协议叫多路访问协议（multiple access protocol）。

多路访问协议可分为三大类：信道划分协议（channel partitioning protocol），随机接入协议（random access protocol），轮流协议（taking-turns protocol）。

信道划分协议：
时分多路复用（Time Devision Multiple，TDM）将时间平均分为多个片，每个信道一个片。优点是公平，简单，缺点是只有一个分组时速度仍然是 R/N，造成资源浪费。
频分多路复用（Frequency Devision Multiple，FDM），把频率分片，优缺点和 TDM 一样。
码分多址（Code Division Mupltiple Access，CDMA），不同节点分配不同的精心选择的编码，使得不同结点可以同时传输。

随机接入协议：
节点总是以全速 R 进行发送，当发生碰撞时，结点会反复等待一个随机时延然后重发，直到无碰撞通过为止。

轮流协议：
轮询协议（polling protocol），其中一个结点指定为主结点，主节点以循环方式轮询（poll）每个结点。优点避免碰撞和随机时延，缺点引入了轮询时延。
令牌传递协议（token-passing protocol）。一个称为令牌（token）的小点的特殊帧在结点之前以某种固定次序进行交换。当结点需要发送帧时，才会持有该令牌，否则会立刻传递给下一个。优点是效率高，缺点是不能兼容单点故障。

—- 20190713 —-

MAC 地址与硬件设备绑定，不会发生变化。

主机和路由器接口除了 IP 地址还有 MAC 地址的原因是：

  • 局域网是为任意网络层协议涉及的，不仅用于 IP 和因特网。

  • IP 是变化的，则 IP 地址必须存在 RAM，且在上电时初始化

  • 保持各层独立。

ARP（地址解析协议，Address Resolution Protocol），IP 转 MAC 地址的转换协议。每台主机或路由器在其内存中具有一个 ARP 表（ARP table），这张表包含 IP 地址到 MAC 地址的映射关系。因为涉及 IP，所以这是一个网络层协议。

如果表中没有对应 IP 地址的记录，则发送一个 ARP 分组（ARP packet）来查询。ARP packet 的目标地址是 MAC 广播地址 FF-FF-FF-FF-FF-FF。子网的所有其他适配器都会收到。如果查询的 IP 地址和自己的 IP 地址匹配，则回复一个相应 ARP packet。

网络层跨网传输时，数据报会首先发送到路由器对应的 MAC 地址，再由路由器转发出去。

以太网是目前为止最流行的有线局域网技术，其他技术还有 FDDI 和 ATM。

以太网一开始在 70 年代是通过同轴电缆总线来互相连接，到了 90 年代后期进化为集线器，使用星行拓扑结构；21 世纪早期进化为交换机（switch）。交换机是“无碰撞的”，是储存转发分组的交换机。

以太网帧结构：

前同步码（8） | 目的地址（6） | 源地址（6） | 类型（2） | 数据（46~1500） | CRC（4）

前同步码用于唤醒适配器，并与发送方时钟同步，是固定的值。前 7 字节 10101010，最后 1 字节 10101011。类型字段用于记录网络层协议。

以太坊是无连接的。

交换机两个功能：过滤（filtering）决定是否要转发这个帧，转发（forwarding）决定帧应该被导向到哪个接口。过滤和转发通过交换机表（switch table）完成。

交换机表内容包含：mac 地址，输出接口，表项建立的时间

当一个帧到达交换机，交换机会查找该帧的目的地址对应的表项。这可能有三种情况：

  1. 没有对应项，此时向所有接口转发（即广播）该帧，后续处理属于自学习功能。

  2. 有表项，但输出接口和收到的接口一致。此时丢弃。

  3. 有表项，且接口不一致。此时转发。

自学习：交换机表一开始可能是空的，但经过一定时间后，交换机可以自行建立出一个可行的交换机表。

交换机可以消除碰撞，兼容不同链路，并且使安全性管理功能称为可能。

交换机和路由器比较：交换机即插即用，性能好，但是是扁平的，单局域网的，不能阻止广播风暴；路由器是分层次的，允许以丰富的拓扑结构构建因特网，但速度慢一些。

虚拟局域网（Virtual Local Network，VLAN）可以提供交换机局域网没有的，流量隔离，不同局域网共享一个交换机，管理用户的功能。

版权所有，转载请注明出处：
https://sickworm.com/?p=1735

《计算机网络：自顶向下方法》笔记（4）：网络层

没有评论

网络层

网络层的功能是：分组从一台发送主机移动到另一台接收主机。细分为两个子功能：转发（forwarding）和路由选择（routing）。涉及的协议是：IP，NAT，ICMP。

转发：分组从一个输入链路到达路由器的时候，将其移动到一条合适的输出链路。

路由选择：从发送主机到接收主机的端到端的路由器选择。

每个路由器都有一张转发表，转发表指示一个分组应该移动到哪条输出链路。

某些计算机网络中还有第三种功能，连接建立（connection setup）。因为某些网络体系结构中（包括 ATM，帧中继的体系结构）属于虚电路网络。和因特网的数据报网络不一样，虚电路网络提供恒定速率和连接功能。

转发表的修改是通过路有选择算法进行修改的，这通常每 1 到 5 分钟左右更新一次转发表。

虚电路的概念来源于电话界，呼叫简历和每次呼叫的状态都要在网络中的路由器位置。这显然要复杂的多。复杂的原因是端系统设备（电话）是“哑巴”，他们本身不负责维持过于复杂的状态。而在因特网中，连接状态是由端设备（电脑）维持的，电脑会维护网络层之上的运输层 TCP 的连接。

当路由某个输出端口的分组转移速度赶不上其他输入端口的速度之和时，未处理的分组会放入缓存。当缓存满的时候，就会被路由器丢弃，出现丢包。

IPv4 数据格式：

版本 4bits
首部长度 4 bits
服务类型（TOS） 8bits  // 第七章
数据报长度（16 bits）
标识 16bits
标志 3bits
片偏移 13bits // 这三个与 IP 分片有关
寿命（TTL） 8bits  // 每经过一个路由会减 1
上层协议 8bits // 最终到达目的地才有用，指示了该报文应该交给哪个传输层协议。协议号绑定网络层和运输层，就像运输层的端口号绑定运输层和应用层
首部校验和 16bits
源地址 32bits
目的地址 32bits
选项（可选）
数据 n bits

版权所有，转载请注明出处：
https://sickworm.com/?p=1728

《计算机网络：自顶向下方法》笔记（3）：运输层

没有评论

运输层

运输层协议为运行在不同主机上的应用进程之间提供了逻辑通信（logic communication）功能。运输层分组成为报文段（segment）。

TCP 为应用程序提供了几种附加服务。可靠数据传输（reliable data transfer），拥塞控制（congesion control）。

多路复用与多路分解

接收运输层报文段中并交付到正确的套接字的工作称为多路分解（demultiplexing）。

将各个套接字的数据封装并传递到网络层成为多路复用（multiplexing）。

UDP

UDP 是无连接的，他在 IP 层上只增加了多路复用与多路分解（即端口号 port）；和差错检测（即校验和 checksum）。

UDP 适合应用的特征：无需连接建立，无连接状态，希望保文尽量精简，不希望过分延迟，且能容忍一些数据丢失。

UDP 校验公式是：每16位为一组相加，溢出回卷，最后结果的反码即是校验和。接收方同样计算出结果与反码相加结果应为 16 位全 1。

UDP 提供差错检测是因为底层链路不一定每一条链路都提供了差错检测，以及内存复制也可能出现差错。

—————— 20190615 ————————

TCP

TCP 是面向连接的（connection-oriented），提供的是全双工服务（full-duplex service），点对点（point-to-point）

TCP 报文包含：32 bits 序号（sequence number，seq），32 bits 确认号（acknowledgment number，ack），16 bits 接收窗口（receive windows），4 bits 首部长度（header length，以 32 bits 为单位），可选变长选项（options），6 bits 标记位（flag）。若 options 为空，则 TCP 头部长度为 20 字节。

累计确认：TCP 只会确认流中第一个丢失字节为止的字节。如 TCP 接收到 0～535 和 900～1000 的报文段，则 TCP 仍在等待 536 的报文段，A 给 B 的下一个报文段的 ack 将包含 536。

报文段的序号就是该报文段数据字段首字节的序号。

seq 即自己的当前报文的首字节序号，ack 即期望的对方的 seq。

TCP 超时时间基于 RTT 的一种计算方法可以是：

// 估算 RTT
EstimatedRTT = 0.875 EstimatedRTT + 0.125 Sample RTT。
// 偏差 RTT
DevRTT = 0.75 DevRTT + 0.25 |SampleRTT - EstimatedRTT|
// TCP 超时时间
TimeoutInterval = EstimatedRTT + 4 DevRTT

而没收到 RTT 时 TimeoutInterval 建议值为 1 秒，超时翻倍。

当接收端发现数据流出现空间隔（可能是中间报文超市或重新排序造成的），此时可以立即发送一个冗余 ACK（duplicate ACK）。如果发送方收到 3 个冗余 ACK，它把这个当作一种指示，即这个被确认 3 次的保文已经丢失。此时 TCP 就执行快速重传（fast restransmit）。

发送方发送 1, 2…N 的报文到接收方，且除 n（n<N）之外的所有报文都接收成功。此时 TCP n 报文超时，TCP 只会重传 n 这个报文段。GBN 风格的重传机制则会重传 n, n+1 … N 的报文段。

对 TCP 提出的一种修改意见是所谓的选择确认（selective actknowledgment）。它允许 TCP 接收方有选择地确认失序报文段，而不是累计地确认最后一个正确接收的有序报文段。此时 TCP 就更像 SR 协议。

TCP 通过让发送方维护一个发送窗口（receive window）来实现流量控制服务（flow-control service），接收方会在回复报文里携带 rwnd 变量，表示当前接收窗口（receive window）的剩余空间。

当接收方缓存空间已满，但接收方没有数据要返回的时候，是不会发送报文给发送方的。此时发送方无法得知 rwnd 变量的情况。TCP 规范要求：接收方接收窗口为 0 时，发送方持续发送 1 字节报文段，直到被接收方确认，返回非 0 rwnd。

握手过程中 SYN = 1，完成握手后 SYN = 0。三次握手的第三阶段已经可以携带数据给 server 了。

  • 第一阶段：SYN = 1，seq = 随机数 client_isn

  • 第二阶段（返回）：SYN = 1，seq = 随机数 server_isn，ack = client_isn + 1

  • 第三阶段：SYN = 0，seq = client_isn + 1，ack = server_isn + 1

断开过程需要 4 次握手，因为发起方收到回复时，被动方可能还有数据要继续发。被动方发完后会发送属于它的断开，此时发起方收到后，再次回复，此时双方才真正断开。

TCP 丢包事件定义为：超时或收到接收方 3 个冗余 ACK

TCP 使用确认（ACK）来触发增大它的拥塞窗口长度，确认的快就增大得快

慢启动：在 TCP 慢启动状态下，cwnd 初始值是 1 个 MSS。 MSS 是初始窗口大小的参考值，是控制拥塞的字段。如果 MSS 初始值为 500 字节，RTT 200ms，则速率大约为 20kbps（1s 发 2500 bytes，即 20k bits）。当报文段被确认后， cwnd 会翻倍，即 2 个 MSS，4 个 MSS 地增长。报文段出现丢失的时候，进入拥塞避免（丢包）或快速恢复（3 个 冗余 ACK）状态。

拥塞避免：cwnd 降低为原来的一半。每次确认增加 1 个 MSS，丢包时状态切换和慢启动一致。

快速恢复：cwnd 降低为原来的一半 + 3 个 MSS。每次确认增加 1 个 MSS，丢包时状态切换和慢启动一致。

某些协议如 DCCP，SCTP 和 TFRC 明确地提供了超过 TCP 和 UDP 的强化能力，但多年来已经郑敏 TCP 和 UDP 是“足够好”的，未来“更好”的协议是否会取代 TCP 和 UDP，这将取决于技术，社会和商业考虑的复杂组合。

版权所有，转载请注明出处：
https://sickworm.com/?p=1722

《计算机网络：自顶向下方法》笔记（2）：应用层

没有评论

2.应用层

套接字是应用程序进程和运输层协议之间的接口。

运输层协议特性：可靠数据传输，吞吐量，时延，安全性

运输层提供了 TCP 和 UDP 两种运输服务。TCP 是面向连接的，并提供了可靠的数据传输服务。UDP 不是面向连接的，切不提供可靠数据传输服务。

往返时间 RTT（Round-Trip Time），表示一个短分组从客户到服务器再反悔到客户所花费的时间。RTT 包括分组传播时延，排队时延和处理时延。

HTTP

HTTP 基于 TCP，无需关心数据丢失的问题。HTTP 是个无状态协议，并不会保存关于客户的任何信息。（基于 HTTP 可以实现有状态协议，如 Cookie）。HTTP 请求响应时间大概是 2 个 RTT 加服务器传输 HTML 文件的时间，包含 TCP 三次握手和最后返回数据。HTTP 可使用持续连接模式（keep-alive），这样多次 HTTP 请求可以节省 3 次握手的时间。

HTTP GET 请求报文：

GET /somedir/page.html HTTP/1.1     // 1 请求行，request line
Host: www.someschool.edu            // 2～4 首部行，header line。Host 知名对象所在主机，用于 Web 代理高速缓存
Connection: close                   // 不使用持续连接（使用则为 keep-alive）
User-agent: Mozilla/5.0             // 浏览器类型
Accept-language: fr                 // 语言
// 再附加一个回车换行符（CR LF）结束

HTTP GET 响应报文：

HTTP/1.1 200 OK                     // 1 状态行，status line
Connection: close                   // 2～6 首部行，header line
Date: Tue, 09 Aug 2011 15:44:04 GMT // 服务器产生并发送改响应报文的日期和时间
Server: Apache/2.2.3 (CentOS)       // 服务器类型
Last-Modified: Tue, 09 Aug 2011 15:11:03 GMT // 被发送对象创建或最后修改的时期和时间，用于对象缓存
Content-Length: 6821                // 被发送对象中的字节数
Conent-Type: text/html              // 被发送对象类型
// 再附加一个回车换行符（CR LF）结束 header line
(data data data data data ...)      // 实体体，entity body
// 再附加一个回车换行符结束

条件 GET 方法即在 header line 加入 “If-Modified-Since”，来充分利用本机缓存。如果服务器没有更新该对象，则返回 304 Not Modified，且 entity body 为空；若更新对象则返回正常 200 OK，并带有 entity body。

——- 2019.06.01 ——–

FTP

FTP 使用了两个并行的 TCP 连接来传输文件，一个是控制连接（constrol connnection），一个是数据连接（data connection）。

FTP 协议使用一个独立的控制连接，所以也称 FTP 的控制信息是带外（out-of-band）传送的。HTTP 请求/回复和文件是在同一个 TCP 连接中的，所以 HTTP 是带内（in-band）发送控制信息的。

FTP 控制连接是一直保持的，文件传输每次都建立一个新连接。FTP 会保留用户的状态（state），包括账户，当前目录。状态大大限制了 FTP 的同事维持的会话总数。

FTP 和 HTTP 一样都是可读的。

SMTP

SMTP 是电子邮件使用的服务器间传输协议之一，基于 TCP。HTTP 主要是拉协议（pull protocol），即数据请求方发起链接。SMTP 基本上是推协议（push protocol），即数据发送方发起链接。

SMTP 要求每个报文使用 7 比特 ASCII 码格式。

POP3 / IMAP

POP3（Post Office Protocol——Version 3），IMAP（Internet Mail Access Protocol）协议用于从邮件服务器上取回邮件。

POP3 认证（authorization）后，提供 list，retr，dele，quit 四种命令，完成拉取邮件列表，读取，删除，关闭链接等功能。POP3 的客户端通过这几条命令的组合，可以实现“下载并删除”和“下载并保留”两种模式。

IMAP 比 POP3 复杂，但提供了文件目录功能，可以把邮件分类；也允许只获取部分邮件，如只获取邮件头。

DNS

DNS 是一种主机名到 IP 地址转换的目录服务，是应用层协议。

DNS 还提供了主机别名（host aliasing），邮件服务器别名（mail server aliasing），负载分配（load distribution）功能。

  • 主机别名（host aliasing）：提供一个比原主机名（又称规范主机名，canonical hostname）更好记的别名

  • 邮件服务器别名（mail server aliasing）：功能同主机别名

  • 负载分配（load distribution）：IP 地址集合与同一个规范主机名相联系。

DNS 服务器大致分为三种：根 DNS 服务器，顶级域（Top-Level Domain，LTD，com，org 等就是顶级域名） DNS 服务器和权威 DNS 服务器。

根 DNS 服务器：标号 A 到 M，每个根服务器都是一个集群，2011 年秋季一共有 247 个 根服务器。

还有一类 DNS 是本地 DNS 服务器，每个 ISP 都有一台本地 DNS 服务器（也叫默认名字服务器）。主要为了更高的性能。

迭代查询：请求主机会先访问根 DNS 服务器，得到顶级域 DNS 服务器 IP 地址，再访问顶级域 DNS 服务器得到权威 DNS 服务器 IP 地址，最后从权威 DNS 服务器获取查询的域名对应的 IP 地址。

递归查询：请求主机会先访问根 DNS 服务器，根 DNS 服务器询问顶级域 DNS 服务器，顶级域 DNS 服务器询问权威 DNS 服务器，权威 DNS 服务器返回查询的域名对应的 IP 地址，再沿路返回。

实践中，一般从请求主机到本地 DNS 服务器是递归的，其余是迭代的。

DNS 缓存用于改善时延性能并减少 DNS 报文数量。一般由本地 DNS 服务器做缓存。

DNS 记录和报文

DNS 服务器存储了资源记录（Resource Record，RR）来提供主机名到 IP 地址的映射。格式为：（Name，Value，Type，TTL），TTL 为记录的缓存的生存时间。

  • TYPE = A 时，NAME 为主机名，VALUE 为 IP 地址
  • TYPE = NS 时，NAME 为域，VALUE 为权威 DNS 服务器主机名，用于指向该域应该向哪个 DNS 服务器查询
  • TYPE = CNAME 时，NAME 为别名，VALUE 为规范主机名
  • TYPE = MX 时，NAME 为邮件服务器别名，VALUE 为规范主机名

DNS 只有查询和回答两种报文。

DNS 报文格式：

id[2]   // 用于标识该查询
flag[2] // 包含：查询 or 回答；希望递归；支持递归；等
questionCount[2] // 问题数
responseCount[2] // 回答 RR 数
authorityCount[2] //权威 RR 数
additionalCount[2] // 附加 RR 数

questionRR[questionLen * questionCount] // 查询的名字和类型字段
responseRR[rrLen * responseCount] // 对查询的响应中的 RR
authorityRR[rrLen * authorityCount] // 权威服务器记录
additionalRR[rrLen * additionalCount] // 附加信息

questionLen = len(NAME) + len(TYPE)
rrLen = len(NAME) + len(TYPE) + len(VALUE)

以前 DNS 服务器中的内容都是静态配置的，直到最近才添加了一个新的 UPDATE 选项，允许通过 DNS 报文对数据库中的内容进行动态添加或者删除。

P2P

BitTorrent 协议是一个非常流行的 P2P 文件共享协议。BitTorrent 设有追踪服务器（tracker），当一个对等方想要加入 P2P 网络时，则向追踪服务器注册自己，并周期性地通知追踪服务器自己仍在网络中。

当一个对等方 Alice 加入 P2P 网络时，追踪器会随机从对等方集合选择一个子集的 IP 地址（如 50 个）返回。Alice 将自行连接这些 IP 地址。连接上后 Alice 会从连接上的对等方中获取文件的块列表，并根据一定策略从各个对等方中同步过来完整的文件内容。

P2P 网络的数据库实现可以是分布式散列表（Distributed Hash Table，DHT），BitTorrent 正是使用了 Kademlia DHT 来产生一个分布式跟踪器。这个数据库会存储一系列的键值对，其中 key 为文件名，value 为存储了该文件的对等方 IP 地址。当新的对等方请求下载某个文件时，数据库可以返回持有该文件对等方 IP 地址子集以供下载。

简单粗暴的办法可以是每个对等方都维护一个完整的 DHT 数据库。但这对存储和同步的压力会很大。一种精确有效的办法是：为每个对等方分配一个 [0, 2^n – 1] 之间的标识符，对每一个文件都进行 hash，hash 的取值范围也是 [0, 2^n – 1]。然后该文件选择临近的标识符对应的对等方来存储。

那么当我们知道一个文件的 hash 值，需要找到最近的对等方时，应该如何寻找呢？遍历显然是不可取的。其中一个解决方案是 DHT 网络将所有节点组织成一个环形网络，一个对等方只和自己的直接后继和直接前任联系。然后增加一些捷径路径，来大大降低请求需要的报文数量。而捷径的数量选择需要严格的数学论证。目前研究可知，捷径数量和报文数量（与经过的对等方成正比）数量均为 O(log N)。

当某个对等方突然离开时，以该对等方为第 N 后继的节点，会用第 N + 1 个后继代替第 N 后继，然后用新的第 N 后继（旧的第 N + 1 后继）的直接后继作为第 N + 1 个后继。

版权所有，转载请注明出处：
https://sickworm.com/?p=1717

《计算机网络：自顶向下方法》笔记（1）：计算机网络和因特网

没有评论

1. 计算机网络和因特网

网络传输基于协议运行。一个协议定义了在两个或多个通信尸体之间交换的保温格式和次序，以及报文发送/或接收一条报文或其他事件锁所采取的动作。

因特网是一个特定的计算机网络，也是目前最大的计算机网络。

客户端经过一个接入 ISP(Internet Service Providers，网络服务提供商) 与因特网相连。接入 ISP 的接入技术包括 DSL，电缆，FTTH，Wifi，蜂窝等。接入 ISP 不必是电信运营商，也可以是公司，学校这样的单位。

现在的 ISP 网络结构是：客户端接入到低层 ISP，低层 ISP 接入到高层 ISP，较高层 ISP 彼此互联。

分组交换网的时延种类包括，节点处理时延，排队时延，传输时延，传播时延。传输时延与发送速率（带宽）有关，传播时延与物理链路（材料特性）和节点间距离有关。

因特网协议栈：

  • 应用层（如 HTTP）分组：message（报文）
  • 传输层（如 TCP）分组：segment（报文段）
  • 网络层（IP）分组：datagram（数据报）
  • 链路层（如 WiFi，以太网）分组：帧（frame）
  • 物理层：与具体传输媒体有关

OSI 参考模型：比 TCP/IP 在应用层和传输层之间增加了，表示层（represent）和会话层（session）。TCP/IP 协议决定让这两层交给应用开发者处理。

版权所有，转载请注明出处：
https://sickworm.com/?p=1715

Java 设计模式总结

没有评论

创建类模式

1. 单例模式

特点：全局唯一，所有类共享一个实例化对象

使用场景：一个类独占一个唯一资源时考虑使用。如蓝牙等 IO 类，或者根，管理器等虚拟类。其他情况应慎重使用。

2. 工厂模式

特点：用户无需知道实例构造方法，方便用户实例化

使用场景：直接实例化一个对象较为复杂（需要多步）时；一个对象（接口）对应多种实现，而用户无需关注具体实现类是哪个时。

3. 抽象工厂模式

特点： 工厂的工厂

使用场景：存在多个平行的工厂模式实现类时。

4. 建造者模式

特点： 一个 Builder 类对应一个类，通过链式调用不断添加参数，在最后调用 build() 实例化对应类。

使用场景：创建一个对象比较复杂，且某些设置可选时。

5. 原型模式

特点：输入一个实例（称为原型），返回一个实例的复制。

使用场景：克隆一个对象，或创建一个模拟这个对象的行为的对象。

行为类模式

6. 模板方法模式

特点：即 Java 抽象类

使用场景：需要把策略抽象出来，但又与具体实现密切相关时可用。抽象类其实不是必须的，可以用组合代替（把策略抽取为一个单独的类）。

7. 中介者模式

特点：俗话说的：封一层。用于精简接口和类之间的操作。

使用场景：某个流程较为复杂，涉及多个类的交互。

8. 观察者模式

特点：观察类设置监听器给被观察类，在观察类发生了监听器想监听的事件时，被观察类主动调用观察类的监听器。

使用场景：凡是需要关注事件的，都可以使用。

9. 访问者模式

特点： 将被访问类对象传入到访问类，访问类调用这个对象

使用场景：一个对象中存在着一些与本对象不相干（或者关系较弱）的操作，为了避免这些操作污染这个对象，则可以使用访问者模式来把这些操作封装到访问者中去。

10. 命令模式

特点： 发送者对象发送请求对象，接收者对象返回结果。请求对象内含实现方法（Runnable 算得上是一种命令模式？）。调用，接收和实现分散 在 3 个类中。

使用场景：一个请求一个响应的模式比较适合命令模式。

11. 责任链模式

特点：事件（请求）处理类（Handler）对象连成一条链，链的顺序表示优先级。事件到达时按优先级流水线处理。

使用场景：一个请求可能被多个不同的对象接收，但存在接收优先级时。如多层 UI 布局的点击事件。

12. 策略模式

特点：一个算法接口或类，被多个子类实现/继承。各个子类可以根据需求互相替换。即：多种算法，处理一种数据。

使用场景：多个子类继承于同一个父类/接口，基本就算策略模式。

13. 解释器模式

特点：解析特定格式数据，并执行数据所代表的操作。通常使用状态机实现。

使用场景：需要创造并解析自定义数据格式时。

14. 备忘录模式

特点：每一步都被记录，操作可还原。常见实现有 log 记录，merkle 树。

使用场景：当操作有回滚的需求时。

版权所有，转载请注明出处：
https://sickworm.com/?p=1699