【四火】 写在在家办公四周之时

几年前我曾经写过一点对于 “在家办公” 的思考,后来又写了一点,但是从来都没有想到过,长期的在家办公如今已经不是一个可选项,而是一个必选项了。

应该说,我从来都不是一个频繁在家办公的支持者,我是说,在家办公这样的互联网公司特有的 “福利” 当然是好的,但是 “频繁” 在家办公对于团队、项目,甚至个人职业成长等等各方面来说,都不是一件好事。我记得在刚加入亚马逊的时候,我听说亚马逊给了一位工程师这样一个 offer——允许一个月之内四分之三的时间远程办公。当时我觉得这件事情还是挺不可思议的,因为像曾经的 37signals 这样的小公司当然容易做到,但是长期和频繁地在家办公却不是大型互联网公司能玩得转的。

现在整个情况都发生变化了,由于新冠疫情,我们被迫在家办公,或者说,全公司绝大多数人都只能选择在家办公了,而且这件事情目前为止还似乎在漆黑的隧道里,还没有看到头。

在家办公的好处

虽然一般情况下,我更希望到公司去办公,而不是在家,但是不可否认在家办公是有很多好处的。

首先,在家办公会让自己更自由。开某些会的时候,可以躺在床上说话,一边说一边闭目休息(比如某些 1 on 1 沟通会);脖子酸了可以趴一会儿;家里有需要帮助和处理的事情也可以很方便地离开一会儿去处理。

其次,在家办公省掉了通勤的时间。不用考虑通勤的时间消耗,就意味着可以把闹铃设到一个更晚的时间,每天可以用于自己支配的时间更充裕。

最后,在家办公也能减少一些打扰。没有人来直接打扰你,这可以算一个原因,但这一条是有争议的,因为既然你在工作,你需要 “在线”,那么你的 Slack 很可能就不会消停……

在家办公的挑战

对于团队来说,面对面沟通和合作所带来的的凝聚力,是在家办公所无法带来的。想象一下,和你团队里的兄弟姐妹做一次 pair coding/review,或者是坐下来喝杯咖啡,再或者打局乒乓球,在 Happy Hour 时间聊一下。现在这些基本上都没有了,有的只有生硬和冷冰冰的一个又一个工作上的会议。

对于项目来说,地理位置上的密切合作,所带来的的沟通高效率,也是在家办公所无法带来的。现在大家似乎都慢慢习惯了对这些远程沟通工具的使用,比如 Zoom 电话会议,可是依然,很多会议还会面临着诸多远程沟通才会有的问题,比如会前调试设备,会中时不时会有杂七杂八的声音,会有人掉线。直接沟通无疑是最高效的,Zoom 这样的工具可以让沟通得以进行,但是看不到手势,看不到表情,连板书也不那么自然,还是损失了很多沟通的信息。

对个人职业发展来说,在家办公也失去了很多能力锻炼的机会。比方说,英语能力本来就不够强大的情况下,面对面的沟通可以化简掉很多的问题,可是电话沟通就会对听说能力要求直接上了一个很大的台阶,保证沟通中信息的传达变成了一件很有挑战性的事情。对我个人来说,已经在西雅图工作好几年了,因此这不算是一个大问题,但是我知道身边有很多初入职场的工程师,英文能力还较为生疏,沟通就更可能成为一个问题。

在家办公的一点技巧

接着聊一点我们可以做的,能够改善在家办公之弊端的措施。

硬件方面,显然,如今的在家办公不是一个 10 分钟的事情,也不是一个一两个钟头的事情,而是长时间,比方说,一天 7、8 个小时都需要持续发生的事情,是一个不能够轻易将就的事情。因此让自己在家办公时自己的身体尽量舒适就显得很有意义。对我来说,我不需要大的显示器,也不需要 laptop 有多高端的配置,但是,人体工学桌椅是很有帮助的,我可以坐一会,站一会。脖子不容易酸,也不容易疲劳。

环境方面,尽可能保证一个安静的房间,是一个很有助益的因素。除此以外,在家的诱惑太多,干扰太多,一个降噪耳机可能能够帮助排除干扰。我有时候也会捧着笔记本电脑,临时地挪到另外的一个更加安静的房间,去开完电话会议。

沟通的技巧方面,我觉得在重要的会议前,简单地罗列一些会议的安排和要点是非常有帮助的,这可能并非特定针对于在家办公的场景,但毫无疑问在家办公让其变得更为重要。开会的时候,有了这样的提纲,就可以专注于要解决的问题,而讨论的时候,也因为有了要点和上下文,效率更高。

最后,还是希望疫情快过去吧。在家呆得已经发霉了,以往生活中喜欢做的事情,比如旅行、打球,或者是看电影,似乎这些不管什么都无法正常进行了。Social distancing 已经让本来就在疏远的人际,越来越远了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2JqK1YQ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【喵神】 使用 protocol 和 callAsFunction 改进 Delegate

2018 年 3 月的时候我写过一篇在 Swift 中如何改进 Delegate Pattern 的文章,主要思想是用遮蔽变量 (shadow variable) 声明的方式,来保证 self 变量可以被常时地标记为 weak。本文中,为了保证没有看过原文的读者能处在同一频道,我会先 (再次) 简单介绍一下这种方法。然后,结合 Swift 5.2 的新特性提出一些小的改进方式。

Delegate

简单说,为了避免繁琐老式的 protocol 定义和实现,我们可能更倾向于选择提供闭包的方式完成回调。比如在一个收集用户输入的自定义 view 中,提供一个外部可以设置的函数类型变量 onConfirmInput,并在合适的时候调用它:

class TextInputView: UIView {

    @IBOutlet weak var inputTextField: UITextField!
    var onConfirmInput: ((String?) -> Void)?

    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput?(inputTextField.text)
    }
}

TextInputView 的 controller 中,检测 input 确定事件就不需要一堆 textInputView.delegate = selftextInputView(_:didConfirmText:) 之类 的麻烦事了,可以直接设置 onConfirmInput

class ViewController: UIViewController {

    @IBOutlet weak var textLabel: UILabel!

    override func viewDidLoad() {
        super.viewDidLoad()
        let inputView = TextInputView(frame: /*...*/)
        inputView.onConfirmInput = { text in 
            self.textLabel.text = text
        }
        view.addSubview(inputView)
    }
}

但是这引入了一个 retain cycle!TextInputView.onConfirmInput 持有 self,而 self 通过 view 持有 TextInputView 这个 sub view,内存将会无法释放。

当然,解决方法也很简单,我们只需要在设置 onConfirmInput 的时候使用 [weak self] 来将闭包中的 self 换为弱引用即可:

inputView.onConfirmInput = { [weak self] text in
    self?.textLabel.text = text
}

这为使用 onConfirmInput 这样的闭包变量加上了一个前提:你大概率需要将 self 标记为 weak 以避免犯错,否则你将写出一个内存泄漏。这个泄漏无法在编译期间定位,运行时也不会有任何警告或者错误,这类问题也极易带到最终产品中。在开发界有一句话是真理:

如果一个问题可能发生,那么它必然会发生。

一个简单的 Delegate 类型可以解决这个问题:

class Delegate<Input, Output> {
    private var block: ((Input) -> Output?)?
    func delegate<T: AnyObject>(on target: T, block: ((T, Input) -> Output)?) {
        self.block = { [weak target] input in
            guard let target = target else { return nil }
            return block?(target, input)
        }
    }

    func call(_ input: Input) -> Output? {
        return block?(input)
    }
}

通过设置 block 时就将 target (通常是 self) 做 weak 化处理,并且在调用 block 时提供一个 weak 后的 target 的变量,就可以保证在调用侧不会意外地持有 target。举个例子,上面的 TextInputView 可以重写为:

class TextInputView: UIView {
    //...
    let onConfirmInput = Delegate<String?, Void>()
    
    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput.call(inputTextField.text)
    }
}

使用时,通过 delegate(on:) 完成订阅:

inputView.onConfirmInput.delegate(on: self) { (self, text) in
    self.textLabel.text = text
}

闭包的输入参数 (self, text) 和闭包 body self.textLabel.text 中的 self并不是原来的代表 controller 的 self,而是由 Delegateself 标为 weak 后的参数。因此,直接在闭包中使用这个遮蔽变量 self,也不会造成循环引用。

到这里为止的原始版本 Delegate 可以在这个 Gist 里找到,加上空行一共就 21 行代码。

问题和改进

上面的实现有三个小瑕疵,我们对它们进行一些分析和改进。

1. 更自然i的调用

现在,对 delegate 的调用时不如闭包变量那样自然,每次需要去使用 call(_:) 或者 call()。虽然不是什么大不了的事情,但是如果能直接使用类似 onConfirmInput(inputTextField.text) 的形式,会更简单。

Swift 5.2 中引入的 callAsFunction,它可以让我们直接以“调用实例”的方式 call 一个方法。使用起来很简单,只需要创建一个名称为 callAsFunction 的实例方法就可以了:

struct Adder {
    let value: Int
    func callAsFunction(_ input: Int) -> Int {
      return input + value
    }
}

let add2 = Adder(value: 2)
add2(1)
// 3

这个特性非常适合把 Delegate.call 简化,只需要加入对应的 callAsFunction 实现,并调用 block 就行了:

public class Delegate<Input, Output> {
    // ...
    
    func callAsFunction(_ input: Input) -> Output? {
        return block?(input)
    }
}

class TextInputView: UIView {
    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput(inputTextField.text)
    }
}

现在,onConfirmInput 的调用看起来就和一个闭包完全一样了。

类似于 callAsFunction 的直接在实例上调用方法的方式,在 Python 中有很多应用。在 Swift 语言中添加这个特性能让习惯于 Python 的开发者更容易地迁移到像是 Swift for TensorFlow 这样的项目。而这个提案的提出和审核相关人员,也基本是 Swift for TensorFlow 的成员。

2. 双层可选值

如果 Delegate<Input, Output> 中的 Output 是一个可选值的话,那么 call 之后的结果将会是双重可选的 Output??

let onReturnOptional = Delegate<Int, Int?>()
let value = onReturnOptional.call(1)
// value : Int??

这可以让我们区分出 block 没有被设置的情况和 Delegate 确实返回 nil 的情况:当 onReturnOptional.delegate(on:block:) 没有被调用过 (blocknil) 时,value 是简单的 nil。但如果 delegate 被设置了,但是闭包返回的是 nil 时,value 的值将为 .some(nil)。在实际使用上这很容易造成困惑,绝大多数情况下,我们希望把 .none.some(.none).some(.some(value)) 这样的返回值展平到单层 Optional.none.some(value)

要解决这个问题,可以对 Delegate 进行扩展,为那些 OutputOptional 情况提供重载的 call(_:) 实现。不过 Optional 是带有泛型参数的类型,所以我们没有办法写出像是
extension Delegate where Output == Optional 这样的条件扩展。一个“取巧”的方式是自定义一个新的 OptionalProtocol,让 extension 基于 where Output: OptionalProtocol 来做条件扩展:

public protocol OptionalProtocol {
    static var createNil: Self { get }
}

extension Optional : OptionalProtocol {
    public static var createNil: Optional<Wrapped> {
         return nil
    }
}

extension Delegate where Output: OptionalProtocol {
    public func call(_ input: Input) -> Output {
        if let result = block?(input) {
            return result
        } else {
            return .createNil
        }
    }
}

这样,即使 Output 为可选值,block?(input) 调用所得到的结果也可以经过 if let 解包,并返回单层的 result 或是 nil

3. 遮蔽失效

由于使用了遮蔽变量 self,在闭包中的 self 其实是这个遮蔽变量,而非原本的 self。这样要求我们比较小心,否则可能造成意外的循环引用。比如下面的例子:

inputView.onConfirmInput.delegate(on: self) { (_, text) in
    self.textLabel.text = text
}

上面的代码编译和使用都没有问题,但是由于我们把 (self, text) 换成了 (_, text),这导致闭包内部 self.textLabel.text 中的 self 直接参照了真正的 self,这是一个强引用,进而内存泄露。

这种错误和 [weak self] 声明一样,没有办法得到编译器的提示,所以也很难完全避免。也许一个可行方案是不要用 (self, text) 这样的隐式遮蔽,而是将参数名明确写成不一样的形式,比如 (weakSelf, text),然后在闭包中只使用 weakSelf。但这么做其实和 self 遮蔽差距不大,依然摆脱不了用“人为规定”来强制统一代码规则。当然,你也可以依靠使用 linter 和添加对应规则来提醒自己,但是这些方式也都不是非常理想。如果你有什么好的想法或者建议,十分欢迎交流和指教。

March 12, 2020 at 09:00AM via OneV’s Den https://ift.tt/2TGNAjC

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 与程序员相关的CPU缓存知识

好久没有写一些微观方面的文章了,今天写一篇关于CPU Cache相关的文章,这篇文章会讲述一些多核 CPU 的系统架构以及其原理,包括对程序性能上的影响,以及在进行并发编程的时候需要注意到的一些问题。这篇文章我会尽量地写简单和通俗易懂一些,主要是讲清楚相关的原理和问题,而对于一些细节和延伸阅读我会在文章最好给出相关的资源。

本文比较长,主要分成这么几个部分:基础知识、缓存的命中、缓存的一致性、相关的代码示例和延伸阅读。

因为无论你写什么样的代码都会交给CPU来执行,所以,如果你想写出性能比较高的代码,这篇文章中的技术还是应该认真学习的。

基础知识

首先,我们都知道现在的CPU多核技术,都会有几级缓存,老的CPU会有两级内存(L1和L2),新的CPU会有三级内存(L1,L2,L3 ),如下图所示:

其中:

  • L1缓分成两种,一种是指令缓存,一种是数据缓存。L2缓存和L3缓存不分指令和数据。
  • L1和L2缓存在第一个CPU核中,L3则是所有CPU核心共享的内存。
  • L1、L2、L3的越离CPU近就越小,速度也越快,越离CPU远,速度也越慢。

再往后面就是内存,内存的后面就是硬盘。我们来看一些他们的速度:

  • L1 的存取速度:
  • L2 的存取速度:
  • L3 的存取速度:
  • RAM内存的存取速度

我们可以看到,L1的速度是RAM的27倍,但是L1/L2的大小基本上也就是KB级别的,L3会是MB级别的。例如:Intel Core i7-8700K ,是一个6核的CPU,每核上的L1是64KB(数据和指令各32KB),L2 是 256K,L3有12MB(我的苹果电脑是 Intel Core i9-8950HK,和Core i7-8700K的Cache大小一样)。

于是我们的数据就从内存向上,先到L3,再到L2,再到L1,最后到寄存器进行CPU计算。为什么会设计成三层?这里有下面几个方面的考虑:

  • 一个方面是物理速度,如果你要更在的容量就需要更多的晶体管,除了芯片的体积会变大,更重要的是大量的晶体管会导致速度下降,因为访问速度和要访问的晶体管的位置成反比,也就是当信号路径变长时,通信速度会变慢。这部分是物理问题。
  • 另外一个问题是,多核技术中,数据的状态需要在多个CPU中进行同步,并且,我们可以看到,cache和RAM的速度差距太大,所以,多级不同尺寸的缓存有利于提高整体的性能。

这个世界永远是平衡的,一面变得有多光鲜,另一面也会变得有多黑暗。建立这么多级的缓存,一定就会引入其它的问题,这里有两个比较重要的问题,

  • 一个是比较简单的缓存的命中率的问题。
  • 另一个是比较复杂的缓存更新的一致性问题。

尤其是第二个问题,在多核技术下,这就很像分布式的系统了,要对多个地方进行更新。

缓存的命中

在说明这两个问题之前。我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己进的地方,对于CPU来说,它是不会一个字节一个字节的加载的,因为这非常没有效率,一般来说都是要一块一块的加载的,在CPU的缓存技术中,这个术语叫“Cache Line”(有的中文编译成“缓存线”),一般来说,一个主流的CPU的Cache Line 是 64 Bytes(也有的CPU用32Bytes和128Bytes),也就是16个32位的整型。也就是说,CPU从内存中捞数据上来的最小数据单位。

比如:Cache Line是最小单位(64Bytes),所以先把Cache分布多个Cache Line,比如:L1有32KB,那么,32KB/64B = 500 个 Cache Line。

一方面,缓存需要把内存里的数据放到放进来,英文叫 CPU Associativity。Cache的数据放置的策略决定了内存中的数据块会拷贝到CPU Cache中的哪个位置,因为Cache的大小远远小于内存,所以,需要有一种地址关联的算法,能够让内存中的数据可以被映射到cache中来。这个有点像内存管理的方法。

基本上来说,我们会有如下的一些方法。

  • 一种方法是,任何一个内存地址的数据可以被缓存在任何一个Cache Line里,这种方法是最灵活的,但是,如果我们要知道一个内存是否存在于Cache中,我们就需要进行O(n)复杂度的Cache遍历,这是很没有效率的。
  • 另一种方法,为了降低缓存搜索算法,我们需要使用像Hash Table这样的数据结构,最简单的hash table就是做“求模运算”,比如:我们的L1 Cache有500个Cache Line,那么,公式:`(内存地址 mod 500)x 64` 就可以直接找到所在的Cache地址的偏移了。但是,这样的方式需要我们的程序对内存地址的访问要非常地平均,这成了一种非常理想的情况了。
  • 为了避免上述的两种方案的问题,于是就要容忍一定的hash冲突,也就出现了 N-Way 关联。也就是把连续的N个Cache Line绑成一组,然后,先把找到相关的组,然后再在这个组内找到相关的Cache Line。

那么,Cache的命中率会成为程序运行性能非常关键的事,所以,了解上面的这些东西,会有利于我们知道在什么情况下有可以导致缓存的失效。

对于 N-Way 关联我们取个例子,并多说一些细节(因为后面会用到),Intel 大多数处理器的L1 Cache都是32KB,8-Way 组相联,Cache Line 是64 Bytes。于是,

  • 32KB的可以分成,32KB / 64 = 512 条 Cache Line。
  • 因为有8 Way,于是会每一Way 有 512 / 8 = 64 条 Cache Line。
  • 于是每一路就有 64 x 64 = 4096 Byts 的内存。

为了方便索引内存地址,

  • Tag:每条 Cache Line 前都会有一个独立分配的 24 bits来存的 tag,其就是内存地址的前24bits
  • Index:内存地址后续的6个bits则是在这一Way的是Cache Line 索引,2^6 = 64 刚好可以索引64条Cache Line
  • Offset:再往后的6bits用于表示在Cache Line 里的偏移量

如下图所示:(更多的细节可以读一下《Cache: a place for concealment and safekeeping》)

(图片来自《Cache: a place for concealment and safekeeping》)

这意味着:

  • L1 Cache 可映射 36bits 的内存地址,一共 2^36 = 64GB的内存
  • 因为只要头24bits相同就会被映射到同一个Way中,所以,每4096个地址会放在一Way中。
  • 当CPU要访问一个内存的时候,通过这个内存的前24bits 和中间的6bits可以直接定位相应的Cache Line。

此外,当有数据没有命中缓存的时候,CPU就会以最小为Cache Line的单元向内存更新数据。当然,CPU并不一定只是更新64Bytes,因为访问主存是在是太慢了,所以,一般都会多更新一些。好的CPU会有一些预测的技术,如果找到一种pattern的话,就会预先加载更多的内存,包括指令也可以预加载。这叫 Prefetching 技术 (参看,Wikipedia 的 Cache Prefetching纽约州立大学的 Memory Prefetching)。比如,你在for-loop访问一个连续的数组,你的步长是一个固定的数,内存就可以做到prefetching。(注:指令也是以预加载的方式执行,参看本站的《代码执行的效率》中的第三个示例)

缓存的一致性

对于主流的CPU来说,缓存的写操作基本上是两种策略(参看本站《缓存更新的套路》),

  • 一种是Write Back,写操作只要在cache上,然后再flush到内存上。
  • 一种是Write Through,写操作同时写到cache和内存上。

为了提高写的性能,一般来说,主流的CPU(如:Intel Core i7/i9)采用的是Write Back的策略,因为直接写内存实在是太慢了。

好了,现在问题来了,如果有一个数据 x 在 CPU 第0核的缓存上被更新了,那么其它CPU核上对于这个数据 x 的值也要被更新,这就是缓存一致性的问题。(当然,对于我们上层的程序我们不用关心CPU多个核的缓存是怎么同步的,这对上层都是透明的)

一般来说,在CPU硬件上,会有两种方法来解决这个问题。

  • Directory 协议。这种方法的典型实现是要设计一个集中式控制器,它是主存储器控制器的一部分。其中有一个目录存储在主存储器中,其中包含有关各种本地缓存内容的全局状态信息。当单个CPU Cache 发出读写请求时,这个集中式控制器会检查并发出必要的命令,以在主存和CPU Cache之间或在CPU Cache自身之间进行数据同步和传输。
  • Snoopy 协议。这种协议更像是一种数据通知的总线型的技术。CPU Cache通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话,可以通过广播机制将共享数据的状态通知给其它CPU Cache。这个协议要求每个CPU Cache 都可以“窥探”数据事件的通知并做出相应的反应。

因为Directory协议是一个中心式的,会有性能瓶颈,而且会增加整体设计的复杂度。而Snoopy协议更像是微服务+消息通讯,所以,现在基本都是使用Snoopy的总线的设计。

这里,我想多写一些细节,因为这种微观的东西,不自然就就会更分布式系统相关联,在分布式系统中我们一般用Paxos/Raft这样的分布式一致性的算法。而在CPU的微观世界里,则不必使用这样的算法,原因是因为CPU的多个核的硬件不必考虑网络会断会延迟的问题。所以,CPU的多核心缓存间的同步的核心就是要管理好数据的状态就好了。

这里介绍几个状态协议,先从最简单的开始,MESI协议,这个协议跟那个著名的足球运动员梅西没什么关系,其主要表示缓存数据有四个状态:Modified(已修改), Exclusive(独占的),Shared(共享的),Invalid(无效的)。

这些状态的状态机如下所示:

下面是个示例(如果你想看一下动画演示的话,这里有一个网页(MESI Interactive Animations),你可以进行交互操作,这个动画演示中使用的Write Through算法):

当前操作 CPU0 CPU1 Memory 说明
1) CPU0 read(x)  x=1 (E) x=1 只有一个CPU有 x 变量,
所以,状态是 Exclusive
2) CPU1 read(x)  x=1 (S) x=1(S) x=1 有两个CPU都读取 x 变量,
所以状态变成 Shared
3) CPU0 write(x,9)  x=9 (M) x=1(I) x=1 变量改变,在CPU0中状态
变成 Modified,在CPU1中
状态变成 Invalid
4) 变量 x 写回内存  x=9 (M) X=1(I) x=9 目前的状态不变
5) CPU1  read(x)  x=9 (S) x=9(S) x=9 变量同步到所有的Cache中,
状态回到Shared

 

MESI 这种协议在数据更新后,会标记其它共享的CPU缓存的数据拷贝为Invalid状态,然后当其它CPU再次read的时候,就会出现 cache misses 的问题,此时再从内存中更新数据。可见,从内存中更新数据意味着20倍速度的降低。我们能不直接从我隔壁的CPU缓存中更新?是的,这就可以增加很多速度了,但是状态控制也就变麻烦了。还需要多来一个状态:Owner(宿主),用于标记,我是更新数据的源。于是,现了 MOESI 协议

MOESI协议的状态机和演示我就不贴了,我们只需要理解MOESI协议允许 CPU Cache 间同步数据,于是也降低了对内存的操作,性能是非常大的提升,但是控制逻辑也非常复杂。

顺便说一下,与 MOESI 协议类似的一个协议是 MESIF,其中的 F 是 Forward,同样是把更新过的数据转发给别的 CPU Cache 但是,MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样—— Owner状态下的数据是dirty的,还没有写回内存,Forward状态下的数据是clean的,可以丢弃而不用另行通知。

需要说明的是,AMD用MOESI,Intel用MESIF。所以,F 状态主要是针对 CPU L3 Cache 设计的(前面我们说过,L3是所有CPU核心共享的)。(相关的比较可以参看StackOverlow上这个问题的答案

程序性能

了解了我们上面的这些东西后,我们来看一下对于程序的影响。

示例一

首先,假设我们有一个64M长的数组,设想一下下面的两个循环:

const int LEN = 64*1024*1024;
int *arr = new int[LEN];

for (int i = 0; i < LEN; i += 2) arr[i] *= i;

for (int i = 0; i < LEN; i += 8) arr[i] *= i;

按我们的想法来看,第二个循环要比第一个循环少4倍的计算量,其应该也是要快4倍的。但实际跑下来并不是,在我的机器上,第一个循环需要127毫秒,第二个循环则需要121毫秒,相差无几。这里最主要的原因就是 Cache Line,因为CPU会以一个Cache Line 64Bytes最小时单位加载,也就是16个32bits的整型,所以,无论你步长是2还是8,都差不多。而后面的乘法其实是不耗CPU时间的。

示例二

我们再来看一个与缓存命中率有关的代码,我们以一定的步长increment 来访问一个连续的数组。

for (int i = 0; i < 10000000; i++) {
    for (int j = 0; j < size; j += increment) {
        memory[j] += j;
    }
}

我们测试一下,在下表中, 表头是步长,也就是每次跳多少个整数,而纵向是这个数组可以跳几次(你可以理解为要几条Cache Line),于是表中的任何一项代表了这个数组有多少,而且步长是多少。比如:横轴是 512,纵轴是4,意思是,这个数组有 4*512 = 2048 个长度,访问时按512步长访问,也就是访问其中的这几项:[0, 512, 1024, 1536] 这四项。

表中同的项是,是循环1000万次的时间,单位是“微秒”(除以1000后是毫秒)

| count |   1    |   16  |  512  | 1024  |
------------------------------------------
|     1 |  17539 | 16726 | 15143 | 14477 |
|     2 |  15420 | 14648 | 13552 | 13343 |
|     3 |  14716 | 14463 | 15086 | 17509 |
|     4 |  18976 | 18829 | 18961 | 21645 |
|     5 |  23693 | 23436 | 74349 | 29796 |
|     6 |  23264 | 23707 | 27005 | 44103 |
|     7 |  28574 | 28979 | 33169 | 58759 |
|     8 |  33155 | 34405 | 39339 | 65182 |
|     9 |  37088 | 37788 | 49863 |156745 |
|    10 |  41543 | 42103 | 58533 |215278 |
|    11 |  47638 | 50329 | 66620 |335603 |
|    12 |  49759 | 51228 | 75087 |305075 |
|    13 |  53938 | 53924 | 77790 |366879 |
|    14 |  58422 | 59565 | 90501 |466368 |
|    15 |  62161 | 64129 | 90814 |525780 |
|    16 |  67061 | 66663 | 98734 |440558 |
|    17 |  71132 | 69753 |171203 |506631 |
|    18 |  74102 | 73130 |293947 |550920 |

我们可以看到,从[9,1024] 以后,时间显注上升。包括[17,512] 和 [18,512] 也显注上升。这是因为,我机器的 L1 Cache 是 32KB, 8 Way 的,前面说过,8 Way的一个组有64个Cache Line,也就是4096个字节,而1024个整型正好是 4096 Bytes,所以,一旦过了这个界,每个步长都无法命中 L1 Cache,每次都是 Cache Miss,所以,导致访问时间一下子就上升了。而 [16, 512]也是一样的,其中的几步开始导致L1 Cache开始失效。

示例三

接下来,我们再来看个示例。下面是一个二维数组的两种遍历方式,一个逐行遍历,一个是逐列遍历,这两种方式在理论上来说,寻址和计算量都是一样的,执行时间应该也是一样的。

const int row = 1024;
const int col = 512
int matrix[row][col];

//逐行遍历
int sum_row=0;
for(int r=0; r<row; r++) {
    for(int c=0; c<col; c++){
        sum_row += matrix[r];
    }
}

//逐列遍历
int sum_col=0;
for(int c=0; c<col; c++) {
    for(int r=0; r<row; r++){
        sum_col += matrix[r];
    }
}

然而,并不是,在我的机器上,得到下面的结果。

  • 逐行遍历:0.081ms
  • 逐列遍历:1.069ms

执行时间有十几倍的差距。其中的原因,就是逐列遍历对于CPU Cache 的运作方式并不友好,所以,付出巨大的代价。

示例四

接下来,我们来看一下多核下的性能问题,参看如下的代码。两个线程在操作一个数组的两个不同的元素(无需加锁),线程循环1000万次,做加法操作。在下面的代码中,我高亮了一行,就是p2指针,要么是p[1],或是 p[18],理论上来说,无论访问哪两个数组元素,都应该是一样的执行时间。

void fn (int* data) {
    for(int i = 0; i < 10*1024*1024; ++i)
        *data += rand();
}

int p[32];

int *p1 = &p[0];
int *p2 = &p[1]; // int *p2 = &p[30];

thread t1(fn, p1);
thread t2(fn, p2);

然而,并不是,在我的机器上执行下来的结果是:

  • 对于 p[0]p[1] :560ms
  • 对于 p[0]p[30]:104ms

这是因为 p[0]p[1] 在同一条 Cache Line 上,而 p[0]p[30] 则不可能在同一条Cache Line 上 ,CPU的缓冲最小的更新单位是Cache Line,所以,这导致虽然两个线程在写不同的数据,但是因为这两个数据在同一条Cache Line上,就会导致缓存需要不断进在两个CPU的L1/L2中进行同步,从而导致了5倍的时间差异

示例五

接下来,我们再来看一下另外一段代码:我们想统计一下一个数组中的奇数个数,但是这个数组太大了,我们希望可以用多线程来完成,这个统计。下面的代码中,我们为每一个线程传入一个 id ,然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。

int total_size = 16 * 1024 * 1024; //数组长度
int* test_data = new test_data[total_size]; //数组
int nthread = 6; //线程数(因为我的机器是6核的)
int result[nthread]; //收集结果的数组

void thread_func (int id) {
    result[id] = 0;
    int chunk_size = total_size / nthread + 1;
    int start = id * chunk_size;
    int end = min(start + chunk_size, total_size);

    for ( int i = start; i < end; ++i ) {
        if (test_data[i] % 2 != 0 ) ++result[id];
    }
}

然而,在执行过程中,你会发现,6个线程居然跑不过1个线程。因为根据上面的例子你知道 result[] 这个数组中的数据在一个Cache Line中,所以,所有的线程都会对这个 Cache Line 进行写操作,导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line,所以,导致 6 个线程还跑不过一个线程的结果。这叫 False Sharing。

优化也很简单,使用一个线程内的变量。

void thread_func (int id) {
    result[id] = 0; 
    int chunk_size = total_size / nthread + 1;
    int start = id * chunk_size;
    int end = min(start + chunk_size, total_size);

    int c = 0; //使用临时变量,没有cache line的同步了
    for ( int i = start; i < end; ++i ) {
        if (test_data[i] % 2 != 0 ) ++c;
    }
    result[id] = c;
}

我们把两个程序分别在 1 到 32 个线程上跑一下,得出的结果画一张图如下所示:

上图中,我们可以看到,灰色的曲线就是第一种方法,橙色的就是第二种(用局部变量的)方法。当只有一个线程的时候,两个方法相当,而且第二种方法还略差一点,但是在线程数增加的时候的时候,你会发现,第二种方法的性能提高的非常快。直到到达6个线程的时候,开始变得稳定(前面说过,我的CPU是6核的)。而第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是CPU Cache 友好的。

篇幅问题,示例就写到这里,相关的代码参看我的Github相关仓库

延伸阅读

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 March 02, 2020 at 03:43AM
from 酷 壳 – CoolShell https://ift.tt/2VAUecw

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月15日典范条目

1879S Morgan Dollar NGC MS67plus Reverse.png

摩根銀元美國鑄幣局於1878至1904年間生產的一種1美元硬幣,之後還在1921年再度投產。國會通過《1873年鑄幣法案》為自由鑄造銀幣運動劃上句點,坐姿自由女神銀元因此停產,摩根銀元則是此後美國發行的第一種標準銀元。硬幣由鑄幣局助理雕刻師喬治·T·摩根設計並以他命名,其正面刻有自由女神肖像,背面則刻有展開翅膀的老鷹,爪子上還抓有箭和橄欖枝。國會於1876年秋通過布蘭德-阿利森法,授權發行新銀元,並要求財政部每個月按市場價購買200至400萬美元白銀並打造成銀幣。1890年,國會又通過謝爾曼收購白銀法,其中把財政部每個月要購買的白銀量大幅提升到14萬公斤,但在銀元生產上則只要求鑄幣局再繼續一年。這一法案之後在1893年廢除。1898年,國會通過新法案,要求之前根據謝爾曼收購白銀法買下的所有銀錠都要打造成銀元,鑄幣局於是繼續生產到1904年才把庫存的銀錠用完,摩根銀元也暫時停產。1918年通過的皮特曼法案授權將數以百萬計的銀元熔解後再重新鑄造,摩根銀元於是又在1921年再次投產,同年末,新設計的和平銀元面世,摩根銀元的設計正式退出歷史舞台。

February 15, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2vx1vza

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月14日典范条目

Tropical Storm Edouard 2002.jpg

2002年热带风暴爱德华2002年大西洋飓风季的第五个热带风暴。爱德华于9月1日从佛罗里达州以东的一片对流区和冷锋发展成热带气旋,在弱转向气流的影响下,系统向北漂移并沿顺时针路径循环向西移动。虽然有中等到较强风切变的不利影响,风暴还是在9月3日达到风速每小时约100公里的最高强度,但又在接下来向西行进的过程中快速减弱。9月5日,爱德华在佛罗里达州东北部实现登陆,并在穿越该州后于9月6日消散,其残留被热带风暴费伊的环流吸收。热带风暴爱德华给佛罗里达州带去了中等程度降水,其中该州西部降雨量超过175毫米。虽然登陆时系统仍有热带风暴强度,但其在陆地上行进时的风速很小。此外虽有多条道路被雨水淹没,但此次风暴没有造成人员伤亡,总体破坏也很小。

February 14, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2vxnaXQ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月13日典范条目

Florida counties map.png

美國佛羅里達州一共有67個,於1821年成為美國領土時只有兩個郡,即以薩瓦尼河(Suwanee River)為界,西部為艾斯康比亞郡,東部為聖約翰斯郡,後來成立的其它所有郡都曾是這兩個郡的一部分。佛羅里達於1845年成為美國的第27個,1925年由阿拉楚阿郡析置的吉爾克里斯特郡是全州最年輕的郡。佛羅里達州的郡是州政府的分支。1968年,各郡獲得了自行發放特許狀的權力。除了瓦古拉郡郡城克勞福德維爾外,佛羅里達州的其他所有郡城都是註冊成立的自治市

February 13, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2OLug1O

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 技术面试中,什么样的问题才是好问题?

其实很久以前就想谈一谈这个话题了,但是最近才有了足够的动机。因为从最近参加的很多 debrief 来看,我认为身边大多数的软件工程师面试中,在通过技术问题来考察候选人这方面,很多都做得不够好。比方说,我看到对于一些经验丰富的软件工程师候选人的面试,一些面试官依然是草率地扔出一道算法题让做了事,并且认为能不能够比较清晰完整地将代码写出来,是工程师级别裁定的最重要的标准。而这样的做法我认为是非常不妥的。

首先,我要明确的是,这个问题,指的是技术面试中俗称的 “主要问题”,具体来说,就是面试官会拿出一个问题和候选人讨论,并通过由此开始双方的互相沟通和问题发散来达到考察的目的,因此,这个 “问题”,从某种角度说,更像一个 “话题”。这个过程通常在每轮面试中会持续几十分钟(如果你对这种面试方式感兴趣,你可以看一下这个简单的介绍)。下面的讨论,都是建立在这种面试风格和方式之上的。

其次,作为一个 disclaimer,我想说,以下内容来自于我的认识,并且是针对于技术面试这一个狭窄范围内的认识,自然带有主观的倾向性和认知的局限性,它并不是来自任何公司或组织的标准。

好,下面我就来尝试把这个问题讲清楚、讲透彻。我认为这并不是一件容易的事情,因此如果你对其有不同的看法,欢迎和我一起讨论。

典型案例

我先来举这样一个典型的例子,这里面包含了若干个值得商榷的方面,你可以看看是不是似曾相识:

在和候选人谈论完项目和经历以后,面试还有 40 分钟,于是面试官问:你能否实现一个 LRU 队列?

于是候选人想了一下,就开始做题了,也就是在白板上大写特写,于是面试官也就开始忙自己的事儿了。等到 40 分钟后,候选人写了一白板,但是显然,他在这过程中遇到了一些困难,最后虽然实现了,但是代码写得有些复杂,也遗漏了两、三个重要的 corner case。

于是面试之后,面试官在评语中写道,“候选人能力一般,算法题实现起来磕磕绊绊,最后的代码偏臃肿,而且有明显的 bug”。

在往下阅读以前,请你想一想,这样的面试形式有哪些值得商榷的地方?

技术面试的目的

好,我先卖个关子,先不回答上面的问题,而是先谈一谈,对于软件工程师候选人来说,我们为什么要进行这样的技术面试。事实上,有很多考察项,完全不需要技术面试这样麻烦的途径,就可以很容易、很高效地实现;而下面我说的这些方面,这些对于软件工程师来说至关重要的方面,技术面试却是合理考察的唯一可行途径。

技术能力方面

通常不同轮次的面试,会考察不同的技术点,这个对于不同的团队和职位,是不一样的。

举例来说,对于某业务平台团队的一个高级工程师的职位,五轮面试中,一轮考察项目和经验,一轮考察系统设计,两轮考察具体问题的解决,特别包括算法和数据结构,还有一轮考察面向对象设计等其它内容,这其中,后三轮都包括白板编码的考察。

对于一个有经验的工程师候选人来说,我认为这就是一个比较立体、综合,也是一种比较合理的技术考察点的划分方式。并且,这五轮中有四轮都会花费大量的时间,通过我今天将谈到的技术问题,来对候选人进行技术能力方面的评估。这里,有这样几个非常常见的技术方面的考察项:

  1. 分析问题,整理需求的能力。问题在一开始可能很模糊,但是优秀的且有经验的工程师可以识别出核心的诉求来,这个 “识别” 的能力,下文我还会详述。这里的诉求可能有多个,但是考虑到时间的关系,面试过程中往往只会从某个角度覆盖其中一两个。
  2. 根据需求来设计系统的能力。这里既包括功能性需求,又包括非功能性需求,前者是必须要涉及到的,但是后者也经常也放在一起考量。其实这一点可大可小,它未必一定指系统设计中,功能是否得到实现,并且这个过程中,可能会涉及到系统的扩展性、可用性、一致性等等方面。
  3. 将核心逻辑实现的能力。如今,考察比重容易被高估的算法和数据结构就大体上属于这一部分。它也有功能和非功能的两个角度——功能上算法能否实现需求,非功能上算法是否具备足够的性能,编码是否遵循最佳实践,代码是否具备良好的可扩展性等等。而编码能力,指的是在思路达成一致以后,核心逻辑能不能落到纸面(代码)上。毕竟,“空谈误国,实战兴邦”。
  4. 经验和其它工程能力。这部分相对更为灵活。比如对测试能力的考察,即可以做怎样的测试来实现对于功能需求和非功能需求正确性的保证。对于特定的团队和项目来说,有时候会特别专注于特定的技术能力,比如前端的团队,是需要考察前端的基础技能的。

考虑到时间和覆盖面、覆盖深度的权衡,上面这四点有时候不能在一轮面试中完全覆盖,往往也会包括三点。比如,系统设计的面试可以着重覆盖 1、2、4 点,而编码为主的面试可以着重覆盖 1、3、4 点。

非技术能力方面

和技术能力考察所不同的是,非技术能力考察在不同面试官中的特异性更大,换言之,每个人的角度和标准都可能不相同。但我觉得下面这几条是特别重要,因而必须要覆盖到的:

  1. 沟通合作的能力。如果不计时间成本,最理想的面试是什么?其实就是一起工作。工作中才会有足够多必要的沟通,无论是正面的品质还是负面的问题都会无所遁形。可是面试的时间有限,我们没有办法实现真正的工作氛围,但依然可以模拟工作中一起考察、分析和解决问题的过程,而这个过程,就是要通过 “沟通” 串起来的。沟通是一个大的话题,具体的考察项有很多,比如,能不能接受建议?能不能讨论想法?有些候选人一旦进入自己的思考模式就听不进别的话了,于是一个点要反复强调几遍;而有的则是缺少 backbone,稍微追问一下,也不思考,就立马改变主意。
  2. 热情和兴趣。热情和兴趣的影响是巨大的,都说兴趣是最好的老师,这部分是很难 “教出来” 的。对于初级工程师来说更是如此。热情和兴趣不但会影响到他/她自己的未来发展,也会影响到整个团队的氛围。
  3. 学习能力。学习能力很大程度决定了候选人在新的岗位上进步的潜力。同样的基础和基本的问题解决能力,有的候选人能够 “一点就透”,触类旁通,这在一定程度上就反映了学习的能力。毫无疑问,软件工程师每天都在面对新问题,入职以后就会发现,不止问题是新的,代码是新的,类库是新的,工具是新的,在成熟到能够有一定产出之前,这一步一定是学习。

技术能力和非技术能力,哪个更占主导?事实上,这二者都很重要,并且二者各自又具备不同的特点。当然相对来说,非技术能力更加难以提高,因而这方面的问题要更加引起重视。比方说,要让一个对于软件领域缺乏热情和兴趣的候选人,在入职以后改头换面,是几乎不可能的一件事情。

其它方面

上面说的是技术面试中对于 “能力” 的考察。其实,还有一些考察项,严格来说并不能算是 “能力”,因此我就没有归类在上面,也不是本文的重点,但这并不是说它们不重要。

比如,候选人是否具备正直的品格。在 OCI,debrief 的结果,通常有 hire 和 no hire 两种,但是有一种情况,可以归结到一个特殊的 “never hire” 里面去,这样的候选人没有面试冷冻期,不会有职位和级别的讨论,就是一个 “永不考虑” 聘用——这就是品格问题。品格问题会导致 never hire 的出现,比如候选人对当前的所在职位说谎了。

再比如,和团队的契合程度。不同的团队,接纳候选人的程度和要求都是不一样的。一个典型的例子是,有时候我们发现,有的候选人在投票的边界线上,即本身是具备相当的潜力的,但是由于相对缺乏领域经验,且某些方面显示出方法明显不得要领。如果团队中有成熟、有经验的工程师可以带着,且团队有一定的空间允许他花更长的时间学习和成长,那么最后的结论就是 hire,否则就是 no hire。你也可以看出,很多时候这样的决定都不是非黑即白的,影响的因素是多方面的。

再再比如,性格不兼容导致的风险。我遇到过一例,候选人在面试过程中,在多轮面试中都表现出高傲和自满的个性来。于是这成为了一个担心招聘进来以后,风险过高的重要方面。于是最后我们放弃了这个候选人,尽管这个候选人的技术方面是没有问题的。有人可能会说,聪明人都是有个性的。但其实 “有个性” 和 “难相处” 却有着微妙的差别,而且再包容的团队,也有自己的底线。我们当然不希望错过优秀的人才,但是这并不是不计代价的。

从这几个方面也能看出,这些 “非能力” 的考察项,往往具备着或 0 或 1 的 “red flag” 的特点。面试官一般不会花心思在这部分的考察上,但如果发现这方面的问题,且经过了明确。那结果往往就会是一个明确的否决票,而这个否决票是和级别、职位无关的。

回看那个案例

讲完了技术面试的目的,再来回看那个案例。那个案例中,所记叙的面试过程,对于技术面试的技术能力和非技术能力的考察,是否有覆盖呢?我们不妨一条一条看吧:

技术能力方面:

  1. 分析问题,整理需求的能力。这一条考察的程度明显是不够的,给出的问题,是一个明确的、具体的算法题,也就是要实现一个 LRU 队列。也许这其中存在着问题分析和需求整理的空间,但对于具体算法题来说,这个空间显然并不大,而且候选人闷头就写了,这方面无从考察。对于一个初级工程师的面试来说可能还好一些,我通常没有微词;可对于一个要去面试一个经验丰富的工程师,我是很不赞成纯算法题面试的,而这就是其中的一个重要原因。
  2. 根据需求来设计系统的能力。这一点的覆盖基本为 0。上来就写代码了,不清楚思考的过程,也更谈不上什么系统设计了。
  3. 将核心逻辑实现的能力。这条确实是这种面试方式能够覆盖的部分,因为整个过程,就是候选人思考并编码实现的过程,只不过,面试官能得到的只有一个 “结果”,而非整个 “过程”。这样的数据,能反映出来在核心逻辑实现方面的价值,就要大打折扣了。
  4. 经验和其它工程能力。也许能够从代码的实现上获知一部分,但这一条考察的程度也显然是很不够的。

再来看非技术能力方面:

  1. 沟通合作的能力。这是最大的问题,因为这方面是远远不足的,整个过程没有沟通,没有合作,只有默默地做题。
  2. 热情和兴趣。这个过程很难从这个角度获取足够的候选人在热情和兴趣方面展示出来的信息。
  3. 学习能力。同上。

也就是说,除了 “将核心逻辑实现的能力” 可能还勉强过得去,这样的面试方式,并无法全面、合理地考察候选人作为软件工程师的综合素质。

事实上,如果你联想实际工作。如果你的团队中有这样一个工程师,拿到一句简单的需求,不确认问题,不沟通设计,不讨论方案,直接就开始埋头苦干,就算能写出可以工作的代码来,这是不是依然是一件无比恐怖的事情?显然,我们的面试要尽可能避免这样的事情在真实世界中发生。我们要找的是软件工程师,不是只会刷题编码者。

这也是我把这个案例,放在开头,作为反面案例的原因之一。

等等,“之一”!难道还有别的原因?

是的,这还没完,这个案例还有着其它弊端,我想再卖个关子——而现在,你可以想一想,再往下看。

怎样的问题才是 “好” 问题?

终于要正面回答标题中的问题了,到底怎样的问题才能真正称得上 “好” 问题呢?下面是我认为最重要的几条衡量标准。

从模糊到清晰

首先,这个问题在一开始要足够模糊,以便让候选人可以逐层递进,逐步细化,寻根究底。这个过程,其实就是将 “具体问题” 经过分析、归纳、思考、抽象并将其映射成为一个 “软件问题” 的过程。在问题变得清晰的过程中,理想的情况是,候选人可以表现出主动性,即候选人可以在多数情况下引领讨论的思路,而不是面试官。面试官需要顺着候选人的思路,逐步框定下问题的讨论范畴,并明确到其核心实现是确实可以用软件的办法实现的。

在这样的状态下,候选人可以以自然的状态,具备相当自由度地发挥自己的能力。从这个过程中,可以观察得到太多候选人的不同角度的特质了。通过这种方式,也可以很大程度避免了已经知道 “标准答案” 的面试官,由于思路的局限性,而给面试施加的源自于主观偏好的影响。

这就好像是开放世界的 RPG 游戏,有多个不同的路径都可以完成任务,玩家可以决策并决定主角的走向,但是这一切始终还要在游戏设计者的掌控之内。这当然是说的理想状态,有时候会有偏差,但我们朝着这个方向努力。这也对面试官驾驭不同的状况有着很高的要求,毕竟,面试官要对这个问题前前后后足够的熟悉,以便应对各种不同的细化场景。有一个常见的方式,是可以从一个自己已经足够熟悉的问题开始,比如自己曾经多年工作涉及的某类系统。

我来举一个具体例子。比如,有这样一个问题:

怎样设计一个流量控制系统?

这就是一个模糊到没法再模糊的问题了。不知你会不会产生下面这样的问题:

  • 什么系统需要流量控制?
  • 现在的流量是多少?
  • 需要支持到什么时间精度?
  • 流量控制的规则怎么定义?
  • 超过流量的请求怎么处理?
  • ……

其实,这些都或多或少是需要面试官和候选人一起逐步思考、分析和明确的。在这个过程中,可以考察的内容太多太多了。

事实上,针对不同程度的候选人,上述这个问题给出的最原始的模糊程度是不一样的,问题越是模糊,这部分对于候选人的要求也就越高。对于一个工作十多年的,有着多年系统设计经验的工程师来说,上面这些问题大致都应该是他/她能够主动提问,或是主动引领明确的。

值得一提的是,理想的问题最好还有一些隐藏的 “坑”,能否把这些坑识别出来,也是对于工程能力方面,一个很好的小的考察点。比方说,优秀的候选人应该想到,流量控制可以基于绝对时间窗口,或是相对时间窗口来进行的,但是要真正保护系统,相对时间窗口才是最理想的。当然在实现难度上,相对时间窗口,往往会更难一些。

而对于一个没有工作经验,并将要研究生毕业的候选人来说,问这样一个模糊的问题,往往带来了过大的难度,不但不容易推进面试的进程,还可能给候选人带来沮丧的心理。我们不希望看到,候选人拿到问题以后就懵了,如果发现候选人推进有困难,面试官需要介入并帮助。

因此根据候选人的程度,这需要面试官主动回答这些问题,或是直接缩小或明确问题的范畴,当这个问题的范畴缩到最小时,这可以是一个直接存在多种解法的算法题。极端地说,这个问题可以一直缩小到这样的程度:

假定说有这样一个 API,名字叫做 isAllowed,这个 API 在系统每次收到请求的时候就调用,传入的是请求对象,传出 boolean 值表示是否允许这次调用——如果最近一分钟内调用次数小于 10000 次就允许,反之则不允许。你能否将这个 API 实现出来?

如果候选人还一脸迷茫,可以提供这样的参考 API:

class RateLimiter {
    public boolean isAllowed(Request req) {
        // TODO
    }
}

你看,这只是一个将问题明确、细化和分解的过程,并没有涉及到实际实现代码该用的算法。但是,上面提的那些问题,要么都通过这个例子明确了,要么都给出具体数字了,这本身,就将一个模糊的问题,降低难度明确为一个具体的算法问题了。

不止一个解

前面一步已经谈到了有不同的方式可将模糊的 “实际问题” 映射到了一个可解的 “软件问题”,那么现在,这个 “软件问题” 依然没有标准答案。可能有几个参考答案,它们互相比较起来各有优劣。大多数情况下,候选人的思路,都在这几个参考答案的思路之中,但有时也能看到特立独行的新奇思路。

如同前一步所说的那样,对于不同级别的软件工程师职位来说,需求分析、系统设计等等这些方面的要求可能有着很大的差别;但是在这一步,对于数据结构和算法这样的基础能力,却是接近的。

对于这里谈到的流量控的算法来说,实现方式是有很多种的,代码复杂程度,控制精度,时间复杂度和空间复杂度等等都有着非常大的区别。当然此时涉及到的,已经基本只是算法层面的话题了,就算法本身而言,我在极客时间专栏中对其中的几个典型方法做了一些介绍,感兴趣的话可以阅读。

我可以再举一个我曾经经常在面试中拿来使用的例子:

某社交网站有两百万的注册用户,每个用户都有积分属性,且积分根据用户在社交网站上的行为而不断有小幅度的频繁变更(比如登陆一次就+1 分,评论一次就+2 分等等),怎样设计一种算法,能够高效、准确地实时获取指定用户在所有用户中基于积分的排名?

上面的问题从模糊逐步落实到实现上的时候,异步、定时地排序,是最容易想到的方案,而题目表述中的 “高效” 和 “实时” 这两个修饰词让这个问题变得困难。这个过程中,我见到的不错的办法就至少有七、八种,比方说,下面这个推进问题解决的例子:

  1. 候选人:在需要的时候进行排序,方案是……
  2. 面试官:好,这样的方式下,时间、空间复杂度是多少?
  3. 候选人:……(说着说着自己意识到时间消耗可能巨大)
  4. 面试官:对,不仅时间、空间都消耗巨大,CPU 也是,你能否优化?
  5. 候选人:……(提出了一些优化思路,但是他自己对它们的实时性也不满意)
  6. 面试官:好,有换个角度更进一步优化的方式吗?
  7. 候选人:对了,可以让数据一直是排好序的!
  8. 面试官:好主意,那你怎么设计数据结构呢?
  9. 候选人:我可以使用一个 map 来保存用户 id 到积分的映射,再把积分从小到大按序放在数组中,这样二分查找就可以找到对应积分所处的排名。
  10. 面试官:听起来不错,那么这时候获取排名的复杂度是多少?
  11. 候选人:……
  12. 面试官:对,每当用户的积分小幅变化的时候,你怎么维持这个数组依然有序?
  13. 候选人:从数组中拿掉一个老的积分,再放入一个新的积分……
  14. 面试官:这个变更影响的数据量有多少,时间复杂度又是如何?
  15. 候选人:……
  16. 面试官:不错,可这个方法有什么问题吗?
  17. 候选人:(恍然大悟)如果新添加一个用户,新的积分会出现在数组头部,数组内的所有数据都要向后移动一个单位!
  18. 面试官:没错,那你打算怎么优化?
  19. 候选人:可以把数组内的积分从大到小排序,这样新添加的用户所对应的积分总在尾部。
  20. 面试官:很好,这个方法还有什么问题吗?
  21. 候选人:……(意识到在某些情况下,有很多用户拥有相同的积分,这时时间复杂度会退化)
  22. 面试官:那样的话,你怎么优化?
  23. 候选人:数组的元素除了记录当前积分,还记录有多少个用户具有这个积分,从而消除相同积分的重复元素……
  24. 面试官:很好,可这个方法会带来一个问题,你能想到吗?
  25. 候选人:对了,如果积分变化以后,新的积分是没有出现过的,那么添加到数组里,就是一个新元素,于是所有比它小的积分全部都要向后移动一个单位。
  26. 面试官:非常好,那么你怎么优化?
  27. 候选人:如果使用链表来代替数组就可以避免这个问题,(突然意识到)可是链表我就没法二分查找了……
  28. 面试官:没错,那什么样的数据结构和链表在这方面具有一定相似性,又能够具备二分查找相似的时间复杂度?
  29. 候选人:……(这一步能回答出来答案就很多了,很多都是很不错的思路,比如有用跳表的,有用二叉搜索树的等等)

这只是一个简化了的片段,实际的沟通的内容远比这部分内容多,但是从中也依然可以管中窥豹,看出问题解决的过程是怎样逐步推进的。

从这里也可以看出,无论是从实际问题细化到软件问题,还是求解这个软件问题,都存在着多条通往罗马的道路,看起来很美好,但这样的问题设计和面试把控并不容易。但既然大家都是软件工程师,是未来有可能一起工作的工程师,面试官的能力和可能就和候选人接近,于是,为了保证面试的效果,就一定要精心准备这样的问题,而不能指望随机和临场想出来一个 “好” 的问题提问。

围绕问题的解决要完整

这个问题的分析、讨论和解答过程要完整。对,其实这一点说的已经不是问题本身了,而是攻克这个问题的过程了。

这指的是整个过程要努力让候选人能够抵达 “踮踮脚能够到” 的难度,并且能够完成从确认、分析、讨论、编码、验证和改进等一个过程。这让整个面试显得完整,同时带来了这样两大好处:

  • 对于面试官来讲,这样一个完整的过程,可以更全面地考察候选人,避免陷入视角过窄和一叶障目的情境。同时,“踮踮脚能够到” 的难度,又可以给整个考察的进程具备较为合理的预期。
  • 对于候选人来讲,心态可以得到一定程度的平复,不沮丧,能够 “完整地” 面试完一轮,能够收获信心。别忘了,面试是双向的,给候选人一个良好的印象是很重要的。

前文我举的这个将问题从模糊到逐步清晰化的这个例子,就是一个需要面试官根据候选人情况动态调整的例子。在候选人能够经过思考而快速推进问题解决进展的时候,要让出主动权,以被动回答和鼓励为主;但在候选人卡壳的时候,要夺回主动权,及时给出提示和引导。

在落到数据结构和算法上面的时候,极少有候选人能够在叙述思路的时候直接给出最优解的。这时候,如果时间充裕,特别是在候选人进展非常顺利的时候,可以不断提示、追问以要求 “代码前优化”,一步一步优化到他/她的问题解决的能力边界,这就是其中的一个探寻其 “踮踮脚能够到” 的这个问题的解决能力的一个办法。但这个过程的前提,是一定要给编码留足时间。当然,如果候选人不能在限定时间内给出清晰的优化后思路,那不妨就退一步到原先那个算法角度不那么 “好”,但是思路清晰的解法上,并落实到代码。

比方说,对于前文所述的那个流量控制的问题,候选人在还有半个小时的时候就想到了使用一个时间复杂度为 O(N) 的解,而面试官认为时间还比较充裕,那就可以尝试挑战一下候选人 “能否再优化一下复杂度?”。

有些时候,由于前面的过程磕磕绊绊,时间剩下不多了,依然只有时间复杂度较高的 brute force 的解法,那么将这个解法实现了,其实也是一个不错的选择。有时候时间实在比较紧张,可以要求实现一部分核心代码,这些都比由于时间太短而代码写了一半匆匆收尾要好得多。我的经验是,在讨论充分,思路清晰的情况下,代码完成的时间,一般只需要 10 到 15 分钟,这样的代码量对于面试来说是比较合理的。

当然,相较而言,一种更为糟糕的结果是,一直到最后,讨论的深度依然离编码尚远,甚至依然停留在一个很高的泛泛而谈的层面。

如果在编码完成之后,尚有时间,优秀的候选人会拿实际的例子去验证代码的正确性。而面试官也可以和候选人讨论 “代码后优化”,比如以下的问题:

  • 你能否进一步优化算法以提高时间/空间复杂度?
  • 如果是工业级别的代码,你觉得代码还有哪些问题?
  • 你该怎样去设计测试,来保证这段代码的正确性 ?

对考察项的覆盖兼有深度和广度

这个问题要能够考察前文所述的技术能力和非技术能力。

这里说的覆盖,不一定要全部覆盖,但是要覆盖其中的大部分,并且对于每一个考察项要具备一定的考察深度。我见到过不少其它的面试风格,但我认为这样就着一个模糊的主要问题(话题)逐步展开的方式是最好的。因为它可以兼具广度和深度的平衡。具体来说:

面试很容易走向的一个极端就是考虑广度,但缺乏深度。比如一种风格是绝大部分的面试时间用来询问候选人的项目和经验,让候选人自己介绍,而面试官跟进追问。这原本是一种很好的方式,但是由于候选人对自己的项目通常远比面试官熟悉得多,除非明确的同一领域,否则面试官较难对于其中的内容挖掘到足够的深度,从而识别出候选人是真正做事的人,还是夸夸其谈的人。这也是这种方式理论可行,但实际开展难度较大的原因之一。

另一个极端,自然就是考虑深度,但缺乏广度。比如给出一个过于具体的问题,缺乏发挥和迂回的空间,对这个问题所涉及的很小一部分深度挖掘,甚至纠缠于某个特殊而单一的 case 很长时间,但是却只能覆盖很少的考察角度。

由于深度和广度都是可控的,那么这样的可以拿来问不同经验和不同技术背景的工程师候选人。这样对于面试官来说,可以获得足够的数据,便于在遇到新的候选人的时候,能够进行横向比较,做出更准确的评估。比方说,过去某级别的候选人能够在面对这个问题的时候,能够达到什么样的级别,而如今这个候选人有着类似表现,这就可以以过去的那个例子来作为参考比较了。

“不好” 的问题

现在,让我们再次回到文章开头那个例子问题,除了已经提到的考察项的覆盖不够,它还有哪些问题呢?参考上文已经提到了 “好” 问题的标准,我觉得其中的这样两条是违背的:

从模糊到清晰。显然,问题给出的时候就已经相对比较清晰了,这样的方式并不能模拟软件工程师日常面对的许多模糊而困难的实际问题。我已经提到,对于经验丰富的候选人来说,这样的问题无法重现将实际问题映射到软件问题这样的一个重要思考过程。

另一个是,围绕问题的解决要完整。示例问题的考察过程中,只有缺乏互动的编码环节,没有其它过程,没有编码前的分析、思考和优化,也没有编码后的测试、改进和优化。考虑到 LRU 完整算法是一个实现代码量偏大的问题,拿来放到面试中做一个完整实现,由于会消耗过多的时间,挤压其它时间,因此显得有些过了。

其它 “不好” 的问题

前面说了过于清晰的纯算法题的 “不好” 之处,也说了 “好” 问题的例子,最后我想再来说几类其它的且典型的 “不好” 的例子。

依赖于语言或框架

而这里说的依赖不好,是因为考虑到候选人不同的技术背景,如果没有特殊的需要,避免这样的依赖,以避免产生不应有的错误的衡量数据。

比方说,问一个关于 JVM 的问题,这个问题可以问,特别是在候选人强调其具备一定 Java 背景的前提下。但是这样的问题不能成为 “主菜”,尤其是候选人不一定具备很强的 Java 背景,这样的方式会导致考察的偏颇。

过于复杂的规则或背景知识

这主要是基于面试的有限时间考虑的,过于复杂的规则或背景知识,容易把时间消耗到澄清它们上面;另外,有些背景知识并非是所有人都熟知的,这就会引起考察标准的非预期。我给一个经典的反面例子:

设计一个算法,把一个小于一百万的正整数,使用罗马数字来表示。

这个问题描述简洁,但是拿来做技术面试中的主要问题,其中一个不妥之处就是,不是所有人都很清楚一百万内的罗马数字表示法的。对于不清楚的人来说,要搞清楚这个表示法的规则,就已经是一件有些复杂和耗时的事情了。显然,这个罗马数字表示法的知识点,不应该成为考察和衡量的标准。

当然,有时候有些问题的背景知识是冷门的,但是表述简洁,那么这样的话只要 面试官能够主动、迅速地说清楚,拿来使用是没问题的。

知识性问题

我想特别谈一谈,对于知识性问题的提问。在讨论问题的过程中,如果涉及到关联的具体知识,那么提问一些基础知识是一个不错的选择,这是考察候选人 CS 基础是否牢靠的方式。比如候选人提到使用 HashMap,而他/她最熟悉的编程语言是 C++,那么询问在 C++中 HashMap 是怎样实现的就是一个可行的问题。而且,由于这样的问题是嵌套在前述的这个大流量控制问题的解决过程中的,更显得自然而不突兀。

反之,如果这样的知识性问题较为冷门或浅表,和当前的讨论中的问题无关,或是不在候选人的知识体系内,这样的问题就值得商榷了。比如,仅仅因为自己的项目组使用 Spring,面试官就询问候选人 Spring 的 bean 的单例和多例分别是怎样配置的,而恰巧候选人又是 C++背景,对于这部分并不熟悉,这样的问题除了给候选人造成困扰以外,意义就不太大了。

如果把知识性问题作为主要问题来提问,我认为是不适合的。因为一方面它不具备普适性,另一方面它又具备太强的随机性。

这里不具备普适性这一条,指的是不同技术背景的软件工程师候选人都要能够适合参与这个问题的解答。举例来说,如果问 “Tomcat 的线程池的配置策略?”,这就是一个不具备普适性的问题,这是一个偏重 “知识性” 的问题,如果候选人没有使用过 Tomcat,或是只是略有了解,很可能就栽了。

而具备太强的随机性这一条,指的是一旦待考察的问题具体以后,这个问题就容易从对 “能力” 的考察变成了对 “知识” 的考察,而这个知识,又恰恰是比较容易随机的。也就是说,我们不希望候选人 “恰巧” 知道或不知道某一个细小的知识点,来决定他/她是否通过这项考察。

无论如何,知识性的问题作为考察的辅助方式可以,但不应成为主角。我还是觉得我们应当能把更多的时间,留给主要问题的解决过程本身。

关于 “技术面试中,什么样的问题才是好问题?”,我就说这么多吧。也欢迎你分享你的看法,我们一起讨论。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/38fQVuV

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月12日典范条目

PatNixon.jpg

塞尔玛·凯瑟琳·“帕特”·瑞安·尼克松第37任美国总统理查德·尼克松的妻子,于1969至1974年间担任第一夫人。帕特·尼克松生于内华达州伊利。1940年,她嫁给了当时还是律师的理查德·尼克松。在1968年美国总统选举成为第一夫人后,帕特·尼克松推动了包括志愿服务在内的多项慈善活动。她陪同丈夫一起出访中华人民共和国苏联,而独立出访非洲和南美洲更带来了“夫人大使”的声誉。她还是第一位进入过战斗区域的第一夫人。这些访问为她赢得了媒体和受访国的好评。她担任第一夫人直到丈夫因水门事件而于1974年辞职时为止。在之后的生活中,她与丈夫回到加利福尼亚州,之后搬到新泽西州。1976年和1983年,她出现了两次中风。1992年,她被诊断出患有肺癌,于1993年逝世,享年81岁。

February 12, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2UUL0Yz

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月11日典范条目

Governorates of Lebanon.svg

黎巴嫩的行政區劃共有三級,其中省屬於第一級行政區劃,而縣和市鎮則分別作為與第二級行政區劃與第三級行政區劃。黎巴嫩各省由總督管治,而各省總督由黎巴嫩部長會議任命。根據《2003年7月16日第522號法令》,阿卡省與巴勒貝克-希爾米勒省分別從北黎巴嫩省和貝卡省析出,使黎巴嫩管轄的省份的數目由6個增加至8個。在黎巴嫩的8個省中,除作為首都的貝魯特省不轄縣、阿卡省僅轄一個縣(阿卡縣)外,所有省均下轄多於一個縣,而下轄縣數量最多的省為北黎巴嫩省黎巴嫩山省,均轄6個縣。在黎巴嫩的8個省中,除貝魯特省不轄市鎮外,所有省均有下轄市鎮,而下轄市鎮數量最多的省為黎巴嫩山省,轄326個市鎮。在黎巴嫩的8個省中,人口最少的是阿卡省,人口僅有281,843人,而人口最多的是黎巴嫩山省,人口達1,101,817人;面積最小的是貝魯特省,面積僅19.8平方公里,而面積最大的是巴勒貝克-希爾米勒省,面積3,009平方公里;人口密度最低的是巴勒貝克-希爾米勒省,平均每一平方公里僅有人口121.473人,而人口密度最高的是貝魯特省,平均每一平方公里有人口36,947.879人。

February 11, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/38rLn0F

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月10日典范条目

1878 three-dollar piece obverse.jpg

3美元金币美国铸币局于1854至1889年间生产的一种金币,由该局首席雕刻师詹姆斯·B·朗埃克设计,1853年2月21日获得授权。硬币正面刻有头戴美洲原住民公主头饰的自由女神头像,背面的中间是面值和年份,周围有玉米小麦棉花烟草组成的花环。部分来源认为,这种金币是为了方便人们大量购买邮票。朗埃克在设计金币时想了多种办法确保新币和2.5美元金币有显著区别,不但采用的坯饼更薄,而且设计图案也是别具一格。金币投产后的第一年就出产了超过10万枚,但其流通程度非常有限。虽然美国西岸部分地区不接受纸币,只能使用金币和银币,但东部的情况截然不同,特别是在经济内战爆发而陷入动荡后,3美元金币基本上在东部的商品交易中难得一见,并且此后再也没有出现过大范围流通。3美元金币于1889年停产,国会再在次年中止其发行授权。这种硬币存在多种年份版本,其中许多的铸造量都很少,但最为罕见的品种还是旧金山铸币局1870年打造的1870-S版,确认存在的仅有一枚。

February 10, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/37bFFhT

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月9日典范条目

Tropical Cyclone 01B 2003.jpg

2003年5月,一场正式名称为“第一号特强气旋风暴鲍勃”的热带气旋斯里兰卡引发56年来最严重的洪涝灾害。系统于5月10日在孟加拉湾上空发展形成,是2003年北印度洋气旋季的首场风暴。由于外界环境有利,系统在向西北方向移动的过程中稳步加强。于5月13日达到持续风速每小时140公里的最高强度,气旋在孟加拉湾中部上空向北飘移,因风切变增多而逐渐减弱。风暴转向东进,于5月16日退化成强烈低气压,然后蜿蜒向东北方向移动并重新增强成气旋风暴。系统从缅甸西部登岸,于次日在陆地上空消散。气旋在孟加拉湾中部基本停止前进期间给斯里兰卡西南部带去倾盆大雨,引发的洪灾和山体滑坡导致2万4750户民宅被毁,另有3万2426套受到一定程度破坏,致使约80万人无家可归。风暴一共造成260人死亡,经济损失约1亿3500万美元。气旋还令印度的安达曼-尼科巴群岛及该国孟加拉湾沿岸地区降下小雨。除此以外,风暴把水分推离印度大陆,可能因此引发旷日持久的热浪,夺走1400人的生命,缅甸也出现暴雨。

February 09, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2Ssudcs

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月8日典范条目

源於公元一世紀或二世紀的安息帝國陶製人面噴水器

安息帝國古波斯地區主要的政治及文化勢力。由阿爾沙克一世建立。全盛時期的安息帝國疆域北達今土耳其東南的幼發拉底河,東抵伊朗。安息帝國座落在地中海羅馬帝國與中國漢朝之間的貿易路線絲綢之路之上,使帝國成為了商貿中心。法爾斯伊什塔克爾的統治者阿爾達希爾一世叛變,在公元224年殺害了安息帝國最後一位統治者阿爾達班五世。阿爾達希爾一世建立了薩珊王朝,不過安息帝國的分支阿薩息斯王朝則仍在亞美尼亞繼續其統治。安息帝國是一個由不同文化組成的國家,她在很大程度上吸納了包括波斯文化希臘文化及地區文化的藝術、建築、宗教信仰及皇室標記。

February 08, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/374Ilhj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月7日典范条目

MMI Chapel.jpg

马里昂军事学院于1842年在美國阿拉巴马州马里昂市創校,在该国仅有的4所军事初级学院中历史最为悠久。马里昂军事学院是南方院校协会的成员之一,有“美国伊顿”之称,曾被评为卓越荣誉军事学校、最佳军事初级学院、阿拉巴马州校友收入最高的社区学院等。马里昂的军校学员团绰号猛虎营。自建校一百余年以来,包括一位美利坚联盟国准将在内的美军各个军种共有超过200名将军毕业于该校。1916年,马里昂军事学院成为了首批引进美国陆军陆军预备军官训练团的学校之一。大约在同一时期,又开设了联邦军校的预备课程。二战时期,学校从仅有的两栋建筑逐步扩建至今日之规模。1968年,美国陆军提前授衔计划进入了马里昂军事学院。2006年,马里昂转型为州立,并成为了阿拉巴马州法定的官方军校。马里昂军事学院的校园經相关机构认证为阿拉巴马州历史地标。校内有两处国家史迹名录,分别是军校礼拜堂和拉夫雷斯楼和校长官邸。此外,阿拉巴马军事名人堂也位于校内。马里昂军事学院每年都会以主要游行队伍的身份参加美国历史最悠久的老兵节庆祝活动——伯明翰老兵节游行。

February 07, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2SnXULI

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月6日典范条目

Karl Marx 001.jpg

卡爾·馬克思猶太裔德國哲學家經濟學家社會學家政治學家革命理論家新聞從業員歷史學者革命社會主義者。馬克思在經濟學上的工作解釋絕大多數工人和資本家間的關係,並且奠定後來諸多經濟思想的基礎。馬克思亦是社會學與社會科學的鼻祖之一,在他一生中出版了大量著作,其中最著名的分別有1848年發表的《共產黨宣言》和1867年至1894年出版的《資本論》。馬克思關於社會、經濟與政治的理論被統稱為馬克思主義,主張人類社會是在控制生產資料的統治階級與提供勞動生產的勞動階級間不斷的階級鬥爭中發展而成。馬克思認為國家是為維護統治階級的利益而運轉,而這又常常被視為大眾的公共意志。他同時也預言如之前存在過的社會經濟體系一樣,資本主義的內部矛盾會導致它自身的滅亡,並會被新的社會主義社會形態所取代;而資產階級和無產階級之間存在的矛盾,將會由工人階級奪取政治權力而終結,最終建立工人自由人聯合體所管理、沒有階級制度的共產主義社會。

February 06, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/39cEujI

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月5日典范条目

1981-S SBA$ Type Two Deep Cameo.jpg

蘇珊·安東尼銀元是1979至1981年間出產的一種1美元硬幣,1981年時因公眾反響不佳而停產,1999年又再度生產。這種硬幣的誕生是為取代過於臃腫的艾森豪威爾銀元,鑄幣局測試過多種形狀和材質,但都遭到當時對鑄幣立法有強大影響的自動售貨機製造業遊說集團反對,最終決定採用的一種內邊框有11個面的圓形坯餅。硬幣由美國鑄幣局首席雕刻師弗蘭克·加斯帕羅設計,他起初設計的正面是自由女神頭像,但多位國會議員和多個組織呼籲在硬幣上描繪一位真實存在過的美國女性,最終入選為硬幣主題的民權活動家蘇珊·安東尼。硬幣反面則根據國會法案要求,保留艾森豪威爾銀元的設計。由於流通量小,大部分安東尼銀元成色甚佳,但這也導致它們缺乏收藏價值,價格比面值高不了多少。鑄幣局打造有多個年份的精製幣,其中個別版本或品種價格更高。

February 05, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/3blCjMC

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月4日典范条目

Tropical Storm Chantal aug 21 2001 1645Z.jpg

热带风暴尚塔尔2001年大西洋飓风季英语2001 Atlantic hurricane season的一场在8月穿越了加勒比海北大西洋热带气旋。尚塔尔于8月14日由热带大西洋的一股东风波发展而成,其存在的大部分时间里都在快速向西移动,退化成东风波后穿越了向风群岛。尚塔尔在加勒比海两次达到时速110公里的最高风速,并且气象部门两次都预测风暴将达到飓风强度,但风切变和之后与陆地的相互作用都令风暴没能强化成飓风。到了8月21日,尚塔尔移动到了墨西哥伯利兹边界海岸附近登陆,并于次日消散。风暴在向风群岛引发的闪电导致特立尼达岛有两人间接死亡。尚塔尔给行进路途上的各地带去了小到中等程度的降雨,其中墨西哥的金塔纳罗奥州因此出现了大面积的泥石流。伯利兹因大浪、狂风和降雨所受到的经济损失共计为400万美元,总体上这场风暴所造成的损失很小。

February 04, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2UkqDDw

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 别让自己“墙”了自己

这一两周与几个朋友聊天,有年轻的90后,也有大叔级的70后,这些人在我看来都是很有能力的人,但是一些喜好过于强烈,让我不经意地回顾了我工作20年来身边的人,有发展得好的,也有发展的不好的,有些人是很可惜的,因为限制他们的不是其它人,也不是环境,而是自己,所以,很想写下这篇文章。(注:这篇文章可能会是一篇说教的文章,所以,可能会让你看着犯困,所以,我会尽量地短一些,而且尽可能多讲故事,少道理,这里的故事,全是真实发生的)

几个故事

2019年年初,我面试了一个很年轻的小伙子(93/94年出生),这个小伙子特别有灵性,也很聪明,计算机专业出生,也很喜欢技术,基础和学习能力也很好。在我这20年来认识的人中,如果他能呆在北京、上海、深圳这样的城市,我保证不出三年,他会成为他们同龄人中非常出色的技术人员,如果有个好的舞台有一个好的团队带他,他的未来会非常成功。然而,这个小伙子有两大喜好:1)只愿呆在一个毫无IT的环境的三/四线城市,2)对技术有非常大的偏好,只喜欢Go语言,非常不喜欢其它的语言,比如:Java。

他的这两个喜好,足以让一个未来会很优秀的人毁掉,因为,这个时代没有限制他,他的能力也没有限制他,但是他的意识完完全全地限制了他。

  • 他把自己最宝贵的青春放在了很烂的项目上,就算能用一些新的技术,他也只能算是自娱自乐,在实验室中玩玩具罢了。
  • 他把自己的技术栈封闭起来,而直接放弃了这个时代最具工业化的技术Java,对于一个好的程序员来说,同时掌握几门语言和技术完全是没什么问题,但是自己封闭了自己的视野。

实在是非常可惜,我本来是可以为他介绍到一些很不错的公司的,但是他这样的习性,等于自己把自己未来的门给关上了,虽然我跟他长谈过,但是我也没有办法叫醒不想醒的人……

  • 视野、环境和舞台,对一个人的限制是非常大的。井蛙不知道大海,被空限维度所限制;夏虫不知道冬天,是被时间维度所限制;圈奍的动物没有斗志,是被自己意识所限制。
  • 偏见和不开放,对一个人的限制是真正有毁灭性的。主动让自己成为一个瞎子和聋子,主动把自己的能力阉割掉,这是一件令人痛心的事。想想大清的闭关锁国是如何让世界第一的北洋水师给毁掉的……

我还有个同学,他的技术并不差,就算呆在昆明这种很落后的地方,他也非常地好学,学习英文,学习各种新技术,对技术没有任何的偏好,喜欢C/C++/Java/Python/Shell,同样喜欢前端Javascript,对基础知识非常地踏实,他在技术上没有限制自己的潜力,有什么就学什么。后来,我带他玩Docker/Go/K8S……分布式架构,他也上手的很快……像他这样的人,技术能力完全没得说,比我还大一岁,44岁了,还是一样的天天追代码细节,看Youtube的各种大会,翻github里的各种issue和pull request……

我同学这人,拥有了成为一个技术牛人几乎的条件:基础知识过硬,细节扎得深,面很广,学习能力强,有英文能力,逻辑思维能力不错,非常的自律,执行力也很强,抓得住重点……然而,只有一个小问题,就是没有到大公司历练过,我三番五次叫他从昆明出来,但是最终他都呆在昆明这个城市没有出来,因为有所谓的家庭约束。然而,我身边还有好些人,把自己家从北京搬到上海,从上海搬到深圳,从厦门搬到深圳……这样的人大有人在……像他这样的能力,在哪个公司都会是主力和骨干,对于一个公司的主力和骨干来说,家庭上的这些问题都是小问题都是有很多解的……

另外,我这个同学还是一个比较悲观的人,任何事情都是先想到不好的事,他关注负面的东西会胜于正面的东西,而且他还有一定的社交恐惧,怕与人相处和交流,时间越长越害怕,甚至有时候直接跟我说,“我就是不想改变”这样的话……其实,我以前也是一个很害怕与人交流的人,面试的时候,我根本不敢正眼看面试官一眼,也不知道与人怎么交流。但是,我与他不一样,我努力克服,不断地面试,与人面对面的交流,到一线技术客服接用户的电话,在公司里做分享,慢慢地到外面分享……3-5年就完全克服掉了。

其实,很多事情,完全是有解的,也没有必要担心,自己的心理障碍也是可以克服的,重点就是自己愿不愿意,只要愿意完成了一半,接下来就是不断的摸爬滚打坚持了。

  • 不限制自己的人,会穷举各种方法来解决问题,限制自己的人,只会找各式各样的问题或借口。
  • 不限制自己的人,会努力改变自己的问题和缺陷,限制自己的人,会放任自己。

另外几个故事

我还有另外几个故事(活到四十多,能看到好多人十几年的发展过程,感觉有点上帝视角了)

我还有一个以前团队里的一个小伙,人是很聪明,但就完全就是野路子,他对技术没有什么偏好,一个PHP程序员,做那个Discuz!论坛,公司被并购了,转成Java,开始研究Java的各种细节,对技术从来没有什么偏见,有什么就玩什么,每做一个项目,就算是一样的他都要用新的技术做一遍,然后跟着我做云计算,我教他TCP,教他C/C++,Docker/Go,等等,一点就通,他是我见过学习能力最强的人。但是,有一个事他一直与我的想法不一样,就是我希望他先把软件设计好,再写代码,他非常不能理解,他习惯于直接动手开干,然后有什么问题就整什么问题,我也很难教育他。

有一天,他电话面了一下Facebook,电话面了15分钟后对方就放弃了,他受到了严重的打击。然后,他就开始找菲利宾人练英文口语了,我也让他做算法题,然后,他才发现,一道连算法都不是的纯编程题都提交几次都过不了,等他做完了Leetcode最初的那151道题后,整个人都改变了,写代码前认认真真地在纸上把程序的状态,处理时序以及可能遇到的一些条件先罗列出来,然后,进行逻辑设计后,再写,从此,他就开启他更大的天地了。我后来把他推荐给了微软,先在中国的Bing,在中国升好2-3级,然后去了美国的Azure,现在听说他准备要跟 k8s 的 co-founder Brendan Burns 混了(虽然,他现在还在印度人手下,但是,我真的不知道他未来能玩多大,因为今年他才33岁,而且非常聪明)

他以前是把自己封闭起来的,我叫他出来,他也不出来,后来因为一些办公室政治的原因不得不来找我,于是我就带着他玩了两年,跟他讲了很多外面的世界是怎么玩的,他这个人也是一个相当不善于社交的人,但是心是开放的,愿意接受新的东西,虽然对技术也有一定偏见,比如不喜欢Windows,但是也不会不喜欢到完全封闭。后来我跟他说,微软的技术相当的强的,你看到的技术只是表面,深层次的东西都是相通的,直到他到了微软后发现各种牛逼的东西,对微软系统的技术的态度也有了改变,而且我让他跟我说很多微软那边的事,我发现,他对技术了解的维度已经是越来越高级的了……

还是我以前团队的一个小伙,他是一个前端,他说前端的东西没什么意思,想来找我做后端,我也一点点带他……后来,我说,你如果想要玩得好,你必需来北京,无论现在你觉得过得有多好,你都要放弃掉,然后,尽最大可能出去经历一下世界最顶尖的公司,我甚至跟他说,如果他女朋友不跟来的话,就先分开一段时间,先自己立业,他来北京的时候,他之前的同事都等着看他的笑话,我说,那些人连想都不敢想,不必管他们。于是,他去了Amazon,再过了一年去了西雅图,我跟他说,接下来就是去AWS,然后,如果有足够的野心,用自己的年轻这个资本去硅谷创业公司赌一把……未来他怎么样我不知道,但至少他没有限制自己,他的未来不会有封顶……

也是我的同学,我跟他在大学是上下铺,后来他去了人民大学读计算机博士,大学的时候做国产数据库kingbase,然后去了一家外企,天天被派到用户那边做数据分析,后来,他想回科研单位做国产数据库,我说,别啊,你的技术比我好太多,还有博士理论加持,你不去国外顶尖公司玩玩,你不知道自己有多强的,于是他跟公司申请去了国外做核心,后来因为Hadoop的原因,公司的产品最终成为了历史,于是我说,你来了美国么,你一定要去AWS,于是他就去了AWS的Aurora团队,成为了AWS明星级产品的中坚力量,天天在改MySQL的核心源码,干了两年,被提升为Principle Software Engineer ……

这里我到不是说出国有多牛,也许你只关注能挣多少钱,但是我想说,他们之所以能有这样的际遇,除了他们本来就有实力,还更因为他们从来不给自己设制什么限制,就是那种“艺多不压身”,有什么就学什么,有更高的就去向更高的迈进,其它的像家庭什么的问题其实都是会有解的,真的不必担心太多……

 别限制了自己

上面的这些故事,也许你能看得懂,也许你看得不一定能懂,这里,让我来做个总结吧

  • 做有价值的事。这个世界对计算机人才的要求是供不应求的,所以,不要让自己为自己找各式各样的借口,让自己活在“玩玩具”、“搬砖”和“使蛮力加班”的境地。其实,我发现这世界上有能力的人并不少,但是有品味的人的确很少。所谓的有价值,就是,别人愿付高价的,高技术门槛的,有创造力的,有颠覆性的……
  • 扩大自己的眼界,开放自己的内心。人要变得开放,千万不要做一个狭隘的民族主义者,做一个开放的人,把目光放在全人类这个维度,不断地把自己融入到世界上,而不是把自己封闭起来,这里,你的英文语言能力对你能不能融入世界是起决定性的作用。开放自己的心态,正视自己的缺点,你才可能往前迈进。你的视野决定了你的知不知道要去哪,你的开放决定了你想不想去
  • 站在更高的维度。面的维度会超过点的维点,空间的维度会超过面的维度,在更高维度上思考和学习,你会获得更多。整天在焦虑那些低维度的事(比如自己的薪水、工作的地点、稳不稳定、有没有户口……),只会让你变得越来越平庸,只要你站在更高的维度(比如: 眼界有没有扩大、可能性是不是更多、竞争力是不是更强、能不能解决更大更难的问题、能创造多大的价值……),时间会让你明白那些低维度的东西全都不是事儿。技术学习上也一样,站在学习编程语气特性的维度和站在学习编程范式、设计模式的维度是两种完全不一样的学习方式。
  • 精于计算得失。很多人其实不是很懂计算。绝大多数人都是在算计自己会失去多少,而不会算会得到多少。而一般的人也总是在算短期内会失去什么,优秀则总是会算我投入后未来会有什么样的回报,前者在算计今天,目光短浅,而后者则是舍在今天,得在明天,计算的是未来。精于计算得失的,就懂得什么是投资,不懂的只会投机。对于赚钱,你可以投机,但是对于自己最好还是投资。
  • 勇于跳出传统的束缚。有时候,跳出传统并不是一件很容易的事,因为大多数人都会对未知有恐惧的心理。比如:我看到很多人才都被大公司垄断了,其实,有能力的人都不需要加入大公司,有能力的人是少数,这些少数的人应该是所有的公司share着用的,这样一来,对于所有的人都是利益最大化的。这样的事现在也有,比如:律师、设计师……。但是,绝大多数有能力的技术人员是不敢走出这步。我在2015年到2016年实践过一年半,有过这些实践,做“鸡”的比“二奶”好多了,收入也好很多很多(不好意思开车了)……

孟子说过几句话——

井蛙不可以语于海者,拘于虚也;//空间局限

夏虫不可以语于冰者,笃于时也;//时间局限

曲士不可以语于道者,束于教也。//认识局限

别自己墙了自己,人最可悲的就是自己限制自己,想都不敢想,共勉!

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 December 01, 2019 at 07:10PM
from 酷 壳 – CoolShell https://ift.tt/2L8vNxh

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 RSA 背后的算法

RSA这篇文章我本来是想写了放到极客时间上我写的专栏里面的,但是专栏的内容是需要仔细斟酌的。这篇文章我认为还是偏难,不适合整个专栏的内容和难度的定位,因此我把它稍微加工了一下,放到我这个博客上。

在专栏中的第 36 讲的选修课堂(该讲预计在 12 月初发布)中,我介绍了 Diffie–Hellman 密钥交换这一算法,它可以说是质数在加密技术中的一个应用,并且是通过其中的 “模幂运算” 来实现的。今天,我来介绍质数的另一个应用,RSA 背后的算法。我在互联网上搜索了一下,我发现基本没有能把它背后的实现原理用浅显的中文叙述讲清楚的,但我还是想试一试,看看能不能尽可能避开那些难懂的术语,用尽量形象和易于理解的方式,把 RSA 背后的原理讲清楚。

在专栏的第 02 讲,我们讲了非对称性加密,比如通过公钥加密的数据,能且只能通过私钥来解密,可是这是怎样实现的呢?这就要讲 RSA 加密技术的原理了。现在,假定我们要通过 RSA 来进行安全的通信,于是你要使用我发布的公钥来对数据加密,加密以后发给我,我拿到加密数据以后使用对应的私钥解密,而攻击者截获了这个加密数据并尝试破解。

模幂等式

我们在介绍 Diffie–Hellman 密钥交换的时候讲到了这个模幂等式:

gᵃ mod p = A

从难度上看它具有如下三个特性:

  • 特性 ①:已知 g、a 和 p,求 A 容易;
  • 特性 ②:已知 g、p 和 A,求 a 困难;
  • 特性 ③:已知 a、p 和 A,求 g 也困难。

再看看上面我们介绍的模幂公式关于离散对数求解的三种难易程度不同的情况吧,我们在 Diffie–Hellman 密钥交换中应用了特性 ① 和特性 ②,而在 RSA 中,我们还要应用特性 ① 和特性 ③

观察特性 ①,我们可以利用它来设计 RSA 加密,即让 g 代表需要被加密的实际值,而 a、p 可以公开。于是你就求出它的 a 次幂,并取 p 模,得到了 “密文” A,把它发给我。这个过程中,如果 A 被截获,那么根据特性 ③,已知 A、p 和 a,攻击者是很难求解出 g 来的。我们已经说过了,这符合 “正向计算简单,逆向求解困难” 这一特性,这一点很适合用来加密。

但是和前面的 Diffie–Hellman 密钥交换不同的是,我们并不是要让所有人都求解这个 g 困难,因为密文是发给我的,我得很容易求解这个 g 才行啊,要不然就像是用一把没人拥有钥匙的锁来加密,这把锁就失去意义了。

我们再来观察一下这个模幂等式:

gᵃ mod p = A

藉由 Diffie–Hellman 密钥交换带来的灵感,如果我们构造这样一个和上式形式一致,但变量具有一定对称性的等式:

Aᵈ mod p = g

这其实是什么?这不就是将加密的数据 A,经过模幂运算以后,得到了原始的未加密数据 g 了吗?也就是说,既然 a 是公钥,那么这里的 d 就是所谓的 “私钥” 啊

好,我们把后面这个公式的 A 通过前面那个公式来带入,得到:(gᵃ mod p)ᵈ mod p = g,根据我们前面介绍模幂运算时提到的联等公式,它就可以化简为:

gᵃᵈ mod p = g

因此这个式子,就表示出了公钥、私钥,以及被加密数之间的关系。

接下去,我们来思考怎样生成这个私钥 d。

欧拉函数

为了继续进行后面的分析,我们需要一点知识储备,首先是欧拉函数。欧拉函数 φ(x) 表示,有多少不大于 x 的正整数中,与 x 互质的数目(即公因数只有 1)。

举例来说,要计算 φ(4),你看不大于 4 的正整数包括 1、2、3、4,其中:

  • 1 和 4 互质;
  • 2 不和 4 互质,因为它们有公因数 2;
  • 3 和 4 互质;
  • 4 不和 4 互质,因为它们有公因数 4。

所以 φ(4) = 2。

欧拉函数 φ(x) 一般很难计算,但是如果 x 是质数,情况就不同了,因为质数和任何比它小的正整数互质,比如 φ(5) = 4,这四个数分别是 1、2、3、4,因此,在 x 是质数的情况下:

φ(x) = x – 1

同时,如果 x 是一个可以因式分解的合数,比如 x = m*n,欧拉函数还具备这样的特性:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这个公式我们后面还会用到。

欧拉定理

有了欧拉函数的知识,我们进一步了解欧拉定理。欧拉定理指的是,对于正整数且互质的 g 和 x,有如下性质:

gᵠ⁽ᴾ⁾ ≡ 1 (mod p)

其中的三横线不是表示 “恒等”,而是表示 “同余”,上面的意思是,g 的 φ(p) 次幂,除以 p 所得的余数,和 1 除以 p 所得的余数,二者相同。

举例来说,当 g=3,p=5,根据前面学的欧拉函数有 φ(5)=4,那么 gᵠ⁽ᴾ⁾=81,81 除以 5 余 1;1 除以 5 也余 1,同余关系成立。

密钥生成

由于 1ᵏ ≡ 1 (mod p),我们可以给指数上的欧拉函数赋予正整数系数 k,gᵏᵠ⁽ᴾ⁾ ≡ 1 (mod p),我们再给两边乘以 g,得到 gᵏᵠ⁽ᴾ⁾⁺¹ ≡ g (mod p)。当 g 小于 p 的时候,g 除以 p 的余数就是 g,因此这个同余式可以写成:

gᵏᵠ⁽ᴾ⁾⁺¹ mod p = g

再联想前面的:

gᵃᵈ mod p = g

你看,这两个式子的形式是一样的,这就意味着,kφ(p)+1 = ad。因此,这个私钥就是:

d = (kφ(p)+1)/a

这意味着什么?这意味着如果能够求得 φ(p) 的值,那么这个私钥就求解出来了。但是,怎样求解 φ(p) 呢?这里,我希望:

  • 密钥是我生成的,因此我求解这个 φ(p) 要非常容易,这样我就可以很容易计算出密钥来;
  • p 是公开的,攻击者仅仅知道 p,求解 φ(p) 要非常困难才行,那样才能保证加密的安全性。

你看,这是不是又一个需要 “正向计算简单,逆向求解困难” 特性的问题?

回想一下前面我们学习欧拉函数的时候,我讲到了,如果 m、n 是质数,那么欧拉函数可以这样求得:

φ(m*n) = φ(m) * φ(n) = (m-1) * (n-1)

这正是我需要的!

你想,如果我选取两个非常非常大的质数 m 和 n,选择 p 的时候,就让它等于 m 和 n 的乘积,那么 φ(p) = φ(m*n) = (m-1) * (n-1),这个正向计算是很简单的,也就是说,因为我知道 m、n,密钥的生成是很容易的一件事情。

可是,攻击者拿不到 m、n,就只能硬生生地尝试去给 p 因式分解才能得到 m、n,而对于一个超大质数的因式分解,这个过程是极其困难的。纵观整个 RSA 的原理,其中涉及到了两个和质数相关的 “正向计算简单,逆向求解困难” 的特性:

  • 一个是前面介绍的模幂等式逆向求底数;
  • 另一个就是这里介绍的超大质数的因式分解。

这也就是 RSA 安全性的基本原理。

当然,随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3585sa8

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 Unix 50 年:Ken Thompson 的密码

50年前,除了Apollo上天之外,还有一个大事的发生,就是Unix操作系统的诞生,若干年前我写过《Unix的传奇,上篇下篇》,Unix是我入行前十年伴我成长的操作系统,虽然现在Linux早已接过了Unix的时代交接棒,但是,Unix文化对我个人的技术观影响是非常大的(注:《Unix编程艺术》是一本对影响我很深的书),而对于 Ken Thompson 和 Dennis Ritchie 这两位 Unix 的缔造者,也是计算机圈中的神一般的人物。今天,Dennis已经去逝,Ken在Google里跟 Rob Pike和 Robert Griesemer 这两位大神在开发Go语言。

P.S. 今年,我一直想写篇Unix 50周年纪念的文章,但一直无从下手,因为不想写过大的命题,如果能写个轶事最好不过。正好过完国庆节,技术圈里有个“热搜”——Ken Thompson的密码。但一直没有时间,所以拖到今天才写下来。

正文开始,2014年,有个叫Leah Neukirchen的程序员(blog)在 BSD 3 的源代码中的 /etc/passwd 看到了早年Unix黑客们的被 hash了的密码,该文件如下所示:

root:OVCPatZ8RFmFY:0:10:Ernie Co-vax,4156427925:/:
daemon:*:1:1:The devil himself:/:
bill:.2xvLVqGHJm8M:8:10:& Joy,4156424948:/usr/bill:/bin/csh
ozalp:m5syt3.lB5LAE:40:10:& Babaoglu,4156423806:/usr/ozalp:/bin/csh
sklower:8PYh/dUBQT9Ss:2:10:Keith &,4156424972:/usr/staff/sklower:/bin/csh
kridle:4BkcEieEtjWXI:3:10:Bob &,4156426744:/usr/staff/kridle:/bin/csh
kurt:olqH1vDqH38aw:4:10:& Shoens,4156420572:/usr/staff/kurt:/bin/csh
schmidt:FH83PFo4z55cU:7:10:Eric &,4156424951:/usr/staff/schmidt:/bin/csh
hpk:9ycwM8mmmcp4Q:9:10:Howard Katseff,2019495337:/usr/staff/hpk:/bin/csh
tbl:cBWEbG59spEmM:10:10:Tom London,2019492006:/usr/staff/tbl:
jfr:X.ZNnZrciWauE:11:10:John Reiser:/usr/staff/jfr:
mark:Pb1AmSpsVPG0Y:12:10:& Horton,4156428311:/usr/staff/mark:/bin/csh
dmr:gfVwhuAMF0Trw:42:10:Dennis Ritchie:/usr/staff/dmr:
ken:ZghOT0eRm4U9s:52:10:& Thompson:/usr/staff/ken:
sif:IIVxQSvq1V9R2:53:10:Stuart Feldman:/usr/staff/sif:
scj:IL2bmGECQJgbk:60:10:Steve Johnson:/usr/staff/scj:
pjw:N33.MCNcTh5Qw:61:10:Peter J. Weinberger,2015827214:/usr/staff/pjw:/bin/csh
bwk:ymVglQZjbWYDE:62:10:Brian W. Kernighan,2015826021:/usr/staff/bwk:
uucp:P0CHBwE/mB51k:66:10:UNIX-to-UNIX Copy:/usr/spool/uucp:/usr/lib/uucp/uucico
srb:c8UdIntIZCUIA:68:10:Steve Bourne,2015825829:/usr/staff/srb:
finger::199:199:The & Program:/usr/ucb:/usr/ucb/finger
who::199:199:The & Program:/usr/ucb:/bin/who
w::199:199:The & Program:/usr/ucb:/usr/ucb/w
mckusick:AAZk9Aj5/Ue0E:201:10:Kirk &,4156424948:/usr/staff/mckusick:/bin/csh
peter:Nc3IkFJyW2u7E:202:10:& Kessler,4156424948:/usr/staff/peter:/bin/csh
henry:lj1vXnxTAPnDc:203:10:Robert &,4156424948:/usr/staff/henry:/bin/csh
jkf:9ULn5cWTc0b9E:209:10:John Foderaro,4156424972:/usr/staff/jkf:/bin/csh
fateman:E9i8fWghn1p/I:300:10:Richard &,4156421879:/usr/staff/fateman:/bin/csh
fabry:d9B17PTU2RTlM:305:10:Bob &,4156422714:/usr/staff/fabry:/bin/csh
network:9EZLtSYjeEABE:501:50:*:/usr/net/network:/usr/net/network/nsh
tty::504:50::/:/bin/tty我

(注,以前Unix是一个服务器,所有人都用一个终端到服务器上进行操作,于是,这个服务上的 /etc/password 下保存着所有的人的登录密码,能让所有的人都能读到,为了不让别人猜到,这个文件中的密码保存(第二列)被做过哈希处理)

这位程序员一看,这些个用户不就是Dennis Ritchie, Ken Thompson, Brian W. Kernighan, Steve Bourne, Bill Joy 这些神人的密码吗?!于是,他想看看这些人用什么样的密码。考虑到当时的加密算法用的是基于DES的 crypt(3) 算法(这个算法今天还在用,像Perl/PHP/Python/Ruby都提供crypt() 函数),而且当时的密码最长只支持8个长度,所以,感觉还是很容易暴力破解的。

一般来说,暴力破解的这种hash密码的工具主要是用hashcatjohn ,很快,Leah 破解了大多数人的密码,因为大多数都使用的是比较弱的密码,比如: Brian W. Kernighanbwk)使用了 /.,/., 这样的密码,而 Dennis Ritchiedmr)则使用了 dmac 这样的密码。然后,在破解到 Ken Thompson的密码时,搞不定了,花了好几天穷举完了所有的小写字母+数字都没有找到。

因为这个crypt的算法也是Ken Thompson 和 Robert Morris 写的,他们在40年前就发现,原来的hash算法太快了,这样很容易被暴力穷举,于是在第七版的Unix(1979年发布),他们把算法改成DES的算法,就是要让这个算法变慢。详细地说,用户密码被截断为八个字符,每个字符仅被压缩为7位。这形成56位DES密钥。然后,该密钥用于加密全零位块,然后再次使用相同的密钥对密文进行加密,依此类推,总共进行了25次DES加密。感觉跟区块链的“挖矿”有点像。在最早的Unix计算机上,这个算法需要花了整整一秒钟的时间来计算密码哈希

这几十年来,计算机的计算速度根据摩尔定律至少double了20次,所以,DES算法已经很容被攻击了,然而,对于Ken Thompson的密码,在2014年还是很不容易被破解的,因为,如果要加上所有的大小写字符数字和其它特殊字符,那么,在2014年,就算用最快的GPU来穷举所有的8位长度的密码,也需要花上至少2年以上的时间

在2019年10月份,在 The Unix Heritage Society 这个社区中,这个事又被人问起来,说以前有个人破解这些密码,不知道有没有全破解出来了?于是Leah看到了,就回应说,那个人是我,但是还是没干出来……于是好些人进来留言。

5天后,2019年10月08日,一个来自澳大利亚的程序员Nigel Williams说,Ken的密码我破解出来了,哈希串ZghOT0eRm4U9s 明文是 p/q2-q4!(果然是有数字有特殊字符),小伙说,我在 AMD Radeon Vega 64 的 GPU上运行了 hashcat 这个命令,干了我 4天多,每秒钟的“配速”是930MH/s (每秒钟9亿3千万次hash运算)。然后,Ken Thompson 也留言到 “恭喜” ,这样,Ken 的密码在40年后被破解了……

马上,就有人问到,这个密码是不是国际象棋的走棋?嗯,很像中国象棋中的“车五进一”,“马三退一”,这个密码中的 p 代表 pawn 小兵,从 q2 的位置走到 q4,这个看来是国际象棋中的开局进兵——用来做登录密码,非常合适。而且,Ken Thompson 在 Unix中写下的一个国际象棋的程序 Belle,在1978年首次参加计算机协会的北美计算机国际象棋锦标赛时,它获得了第一个冠军头衔,其搜索深度为八层。之后又赢得了四次冠军。1983年,它也成为第一台获得国际象棋“大师”称号的计算机。所以,Ken用这个做密码相当make sense!

Ken在贝尔实验室调程序(图片来源:IEEE SPECTRUM

当然,还有一个人的密码是所有人里最难破解的,这个人就是Bill Joy,他最初作为加州大学伯克利分校的研究生,在校期间着手改进Unix 内核,并管理BSD发行版。他最著名的贡献是ex和vi编辑器以及C shell。在Sun公司成立6个月后,他正式成为公司的联合创始人,他在Sun公司的推动了NFS,SPARC处理器,以及Java语言。他还是一个风险投资人员。

在Ken的密被破解后两周(2019年10月19日),有人号称已经破解了Bill的密码,他在邮件组中这样写到

一开始,我使用了大小写字符和数字,8位长度来破解所有的组合,花了我6天的时间,失败了。然后,我开始尝试只用小写字母和控制字符,结果在40分钟内就破解了。但是因为Bill现健在,所以,只要bill同意他才公布这个密码。

在密码里存控制字符?这脑洞,Ctrl+C么?破解者还说,他在一个有三个结点的DELL 的HPC集群上完成这个工作,每个结点包括两个 Tesla V100 nVidia GPU 的显卡,一共30720个CUDA核…… 关于这个显卡多少钱,你可以上网搜吧…… 相当于一块劳力士吧……(我估计这组机器平时是用来挖矿的……[狗头])

好了,我们来看一下这个 /etc/passwd 中的这些人的密码是什么样的,但最主要的是向这些为人类做过巨大贡献的程序员科学家们致敬

  • Ken Thompson
    除了是Unix、B语言和Go语言作者之外,他还贡献过正则表达式,QED/ed编辑器,UTF-8编码定义,以及计算机国际象棋Belle……

    登录名 哈希串 密码
    ken ZghOT0eRm4U9s p/q2-q4!
  • Dennis Ritchie
    Unix和C语言之父,与Ken于1983年获图灵奖,1990年美国国家海明奖章,于2011年去世。

    登录名 哈希串 密码
    dmr gfVwhuAMF0Trw dmac
  • Brian W. Kernighan
    AWK的作者,是AWK中的“K”,也是与Dennis写的K&C的C语言编程书中的“K”,他还编写了很多Unix的其它程序,如:ditroff,而且,。设计了著名的启发式算法

    登录名 哈希串 密码
    bwk ymVglQZjbWYDE /.,/.,
  • Stephen R. Bourne
    Bourne shell(sh)的作者,Unix Shell作者,同时也是Unix调试器的作者。

    登录名 哈希串 密码
    srb c8UdIntIZCUIA bourne
  • Eric Schmidt
    你可能知道他是Google的CEO,苹果的董事,但是你可能不知道,他当年是是贝尔实施室的实习生,他对Unix的词法分析器 Lex 进行为了完全的重写。他的密码是中的wendy应该是他的妻子。

    登录名 哈希串 密码
    schmidt FH83PFo4z55cU wendy!!!
  • Stuart Feldman
    他除了是Unix系统小组的成员,他还是第一个Fortran 77 编译器的作者,也是 make 的作者。他还是楼上Shmidt慈善基金会的科学负责人,在Google/IBM Research任过职,也担任过ACM的主席。

    登录名 哈希串 密码
    sif IIVxQSvq1V9R2 axolotl
  • Mark Horton
    Unix贡献者,包括vi和curses,后来变性为女性,新的名字叫Mary Ann Horton。原来的照片在Unix Guru Universe

    登录名 哈希串 密码
    mark Pb1AmSpsVPG0Y uio
  • Kirk McKusick
    BSD贡献者,主要负责文件系统UFS以及fsck命令,同时也是gprof的贡献者,公开的同性恋者。

    登录名 哈希串 密码
    mckusick AAZk9Aj5/Ue0E foobar
  • Richard Fateman
    他在伯克利的VAX UNIX系统的开发工作中发挥了重要作用,以及开发了 Franz Lisp

    登录名 哈希串 密码
    fateman E9i8fWghn1p/I apr1744
  • Peter Kessler
    这位老兄能在网上查到的资料基本没有,可以查到他是 gprof 的贡献者,以及有名字的gprof的一篇论文

    登录名 哈希串 密码
    peter Nc3IkFJyW2u7E ...hello
  • Kurt Shoens
    BSD电子邮件开发者。Unix早期版本中使用 uuxsendmail 来进行远程消息传递,1978年,Kurt为Unix编写了一个邮件用户代理 Berkeley Mail。相关的历史可以参看这篇文章

    登录名 哈希串 密码
    kurt olqH1vDqH38aw sacristy
  • John Foderaro
    他为Berkeley的Lisp语言编写原始的编译器,Lisp语言是一种类似于数据代数的语言,在计算机历史上有和C语言一样的作用。后来他成立了Franz公司,主要开发和部署图形搜索解决方案。

    登录名 哈希串 密码
    jkf 9ULn5cWTc0b9E sherril.
  • Peter J. Weinberger
    他就是AWK中的那个“A”,同时也是Fortan编译器f77的贡献者,后来是Renaissance Technologies (一家对冲基金)的CTO,现在在Google工作,

    登录名 哈希串 密码
    pjw N33.MCNcTh5Qw uucpuucp
  • John Reiser
    他主要工作是将Unix和C移植到了DEC VAX上,这个机器在学术界相当流行(陈皓注:我在1994年上大学的时候,就是在这个机器上学习的C语言)。这扩大了Unix和C的影响力。

    登录名 哈希串 密码
    jfr X.ZNnZrciWauE 5%ghj
  • Steve Johnson
    曾在贝尔实验室和AT&T工作近20年。他以Yacc,Lint,spell和Portable C编译器而闻名。后来他去了硅谷,加入了一些创业公司,主要从事编译器的工作,以及2D和3D图形,大规模并行系统和嵌入式系统的开发工作。现在他在Wave Computing从事机器学习的工作。

    登录名 哈希串 密码
    scj IL2bmGECQJgbk pdq;dq
  • Bob Kridle
    这位老兄的资料在没有太多,只能在 Berkeley Unix 20 年 上看到他跟Ken Thompson混过一段时间。

    登录名 哈希串 密码
    kridle 4BkcEieEtjWXI jilland1
  • Keith Sklower
    BSD 的一个程序员。从他的主页上可以看到他目前在Berkeley大学,信息分析师,主要研究一些网络通信相关的技术。

    登录名 哈希串 密码
    sklower 8PYh/dUBQT9Ss theik!!!
  • Robert Henry
    网上的资料不多,只在Life with Unix这本电子书中查到,他写了 error

    登录名 哈希串 密码
    henry lj1vXnxTAPnDc sn74193n
  • Howard Katseff
    网上的资料不多,只在Life with Unix这本电子书中查到,他写了 sdblast

    登录名 哈希串 密码
    hpk 9ycwM8mmmcp4Q graduat;
  • Özalp Babaoğlu
    土耳其计算机科学家,1981年在Berkeley担任 BSD Unix的首席设计师,曾经与Sun的创造人Bill Joy在BSD上实现了虚拟内存。

    登录名 哈希串 密码
    ozalp m5syt3.lB5LAE 12ucdort
  • Bob Fabry
    他主要推动美国国防部高级研究计划局DARPA采用了Unix系统

    登录名 哈希串 密码
    fabry d9B17PTU2RTlM 561cml..
  • Tom London
    他和John Reiser在把Unix移植到了VAX-11机上。

    登录名 哈希串 密码
    tbl cBWEbG59spEmM ..pnn521

最后,再首尾呼应一下,在我的技术生涯中,Unix文化对我个人的技术观影响是非常大的,我个人认为 Unix 就像摇滚乐一样,上世纪60年代-80年代,是整个人类最经典最光亮的时代,值得我们每个人向那个时代的人和事致敬!

————————————————————————

P.S.

你可以浏览 Github 的 unix-history-repo 目录(注:本文给的这个链接不在master分支上),这个repo是40年前的代码,涵盖了从1970年创建时的2.5万行内核和26条命令到2017年为止广泛使用的2700万行系统。1.1GB的存储库包含大约一百万次提交和两千多次合并。通过这个链接你可以了解一下这个代码的历史!

下载这些代码需要你的1.5GB的硬盘空间,你可以查看各个大神写的代码,包括 Ken Thompson 和 Dennis的,以及相关的注释。

根据这些,你还可以找到 Ken Thompson的 Github账号 https://github.com/ken 以及别人为dmr建的github帐号 https://github.com/dmr-1941-2011

P.S.S

下面是一些和Unix相关的维基百科资料

还有Unix的社区:TUHS: The Unix Heritage Society – The Unix Tree

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 November 03, 2019 at 02:12PM
from 酷 壳 – CoolShell https://ift.tt/36qwY42

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 HTTP的前世今生

HTTP (Hypertext transfer protocol) 翻译成中文是超文本传输协议,是互联网上重要的一个协议,由欧洲核子研究委员会CERN的英国工程师 Tim Berners-Lee v发明的,同时,他也是WWW的发明人,最初的主要是用于传递通过HTML封装过的数据。在1991年发布了HTTP 0.9版,在1996年发布1.0版,1997年是1.1版,1.1版也是到今天为止传输最广泛的版本(初始RFC 2068 在1997年发布, 然后在1999年被 RFC 2616 取代,再在2014年被 RFC 7230 /7231/7232/7233/7234/7235取代),2015年发布了2.0版,其极大的优化了HTTP/1.1的性能和安全性,而2018年发布的3.0版,继续优化HTTP/2,激进地使用UDP取代TCP协议,目前,HTTP/3 在2019年9月26日 被 Chrome,Firefox,和Cloudflare支持,所以我想写下这篇文章,简单地说一下HTTP的前世今生,让大家学到一些知识,并希望可以在推动一下HTTP标准协议的发展。

HTTP 0.9 / 1.0

0.9和1.0这两个版本,就是最传统的 request – response的模式了,HTTP 0.9版本的协议简单到极点,请求时,不支持请求头,只支持 GET 方法,没了。HTTP 1.0 扩展了0.9版,其中主要增加了几个变化:

  • 在请求中加入了HTTP版本号,如:GET /coolshell/index.html HTTP/1.0
  • HTTP 开始有 header了,不管是request还是response 都有header了。
  • 增加了HTTP Status Code 标识相关的状态码。
  • 还有 Content-Type 可以传输其它的文件了。

我们可以看到,HTTP 1.0 开始让这个协议变得很文明了,一种工程文明。因为:

  • 一个协议有没有版本管理,是一个工程化的象征。
  • header是协议可以说是把元数据和业务数据解耦,也可以说是控制逻辑和业务逻辑的分离。
  • Status Code 的出现可以上请求双方以及第三方的监控或管理程序有了统一的认识。最关键是还是控制错误和业务错误的分离。

(注:国内很多公司HTTP无论对错只返回200,这种把HTTP Status Code 全部抹掉完全是一种工程界的倒退)

但是,HTTP1.0性能上有一个很大的问题,那就是每请注一个资源都要新建一个TCP链接,而且是串行请求,所以,就算网络变快了,打开网页的速度也还是很慢。所以,HTTP 1.0 应该是一个必需要淘汰的协议了。

 HTTP/1.1

HTTP/1.1 主要解决了HTTP 1.0的网络性能的问题,以及增加了一些新的东西:

  • 可以设置 keepalive 来让HTTP重用TCP链接,重用TCP链接可以省到广域网上的TCP的三次握手的巨大开销。这是所谓的“HTTP 长链接” 或是 “请求响应式的HTTP 持久链接”。英文叫 HTTP Persisten connection.
  • 然后支持pipeline网络传输,只要第一个请求发出去了,不必等其回来,就可以发第二个请求出去,可以减少整体的响应时间。(注:非幂等的POST 方法或是有依赖的请求是不能被pipeline化的)
  • 支持 Chunked responses ,也就是说,在Response的时候,不必说明 Content-Length 这样,客户端就不能断连接,直到收到服务端的EOF标识。这种技术又叫 “服务端Push模型”,或是 “服务端Push式的HTTP 持久链接
  • 还增加了 cache control 机制。
  • 协议头注增加了 Language, Encoding, Type 等等头,让客户端可以跟服务器端进行更多的协商。
  • 还正式加入了一个很重要的头—— HOST这样的话,服务器就知道你要请求哪个网站了。因为可以有多个域名解析到同一个IP上,要区分用户是请求的哪个域名,就需要在HTTP的协议中加入域名的信息,而不是被DNS转换过的IP信息。
  • 正式加入了 OPTIONS 方法,其主要用于 CORS – Cross Origin Resource Sharing 应用。

HTTP/1.1应该分成两个时代,一个是2014年前,一个是2014年后,因为2014年HTTP/1.1有了一组RFC(7230 /7231/7232/7233/7234/7235),这组RFC又叫“HTTP/2 预览版”。其中影响HTTP发展的是两个大的需求:

  • 一个需要是加大了HTTP的安全性,这样就可以让HTTP应用得广泛,比如,使用TLS协议。
  • 另一个是让HTTP可以支持更多的应用,在HTTP/1.1 下,HTTP已经支持四种网络协议:
    • 传统的短链接。
    • 可重用TCP的的长链接模型。
    • 服务端push的模型。
    • WebSocket模型。

自从2005年以来,整个世界的应用API越来多,这些都造就了整个世界在推动HTTP的前进,我们可以看到,自2014的HTTP/1.1 以来,这个世界基本的应用协议的标准基本上都是向HTTP看齐了,也许2014年前,还有一些专用的RPC协议,但是2014年以后,HTTP协议的增强,让我们实在找不出什么理由不向标准靠拢,还要重新发明轮子了。

HTTP/2

虽然 HTTP/1.1 已经开始变成应用层通讯协议的一等公民了,但是还是有性能问题,虽然HTTP/1.1 可以重用TCP链接,但是请求还是一个一个串行的发的,需要保证其顺序。然而,大量的网页请求中都是些资源类的东西,这些东西占了整个HTTP请求中最多的传输数据量。所以,理论上来说,如果能够并行这些请求,那就会增加更大的网络吞吐和性能。

另外,HTTP/1.1传输数据时,是以文本的方式,借助耗CPU的zip压缩的方式减少网络带宽,但是耗了前端和后端的CPU。这也是为什么很多RPC协议诟病HTTP的一个原因,就是数据传输的成本比较大。

其实,在2010年时,Google 就在搞一个实验型的协议,这个协议叫SPDY,这个协议成为了HTTP/2的基础(也可以说成HTTP/2就是SPDY的复刻)。HTTP/2基本上解决了之前的这些性能问题,其和HTTP/1.1最主要的不同是:

  • HTTP/2是一个二进制协议,增加了数据传输的效率。
  • HTTP/2是可以在一个TCP链接中并发请求多个HTTP请求,移除了HTTP/1.1中的串行请求。
  • HTTP/2会压缩头,如果你同时发出多个请求,他们的头是一样的或是相似的,那么,协议会帮你消除重复的部分。这就是所谓的HPACK算法(参看RFC 7541 附录A)
  • HTTP/2允许服务端在客户端放cache,又叫服务端push,也就是说,你没有请求的东西,我服务端可以先送给你放在你的本地缓存中。比如,你请求X,我服务端知道X依赖于Y,虽然你没有的请求Y,但我把把Y跟着X的请求一起返回客户端。

对于这些性能上的改善,在Medium上有篇文章你可看一下相关的细节说明和测试“HTTP/2: the difference between HTTP/1.1, benefits and how to use it

当然,还需要注意到的是HTTP/2的协议复杂度比之前所有的HTTP协议的复杂度都上升了许多许多,其内部还有很多看不见的东西,比如其需要维护一个“优先级树”来用于来做一些资源和请求的调度和控制。如此复杂的协议,自然会产生一些不同的声音,或是降低协议的可维护和可推展性。所以也有一些争议。尽管如此,HTTP/2还是很快地被世界所采用。

HTTP/2 是2015年推出的,其发布后,Google 宣布移除对SPDY的支持,拥抱标准的 HTTP/2。过了一年后,就有8.7%的网站开启了HTTP/2,根据 这份报告 ,截止至本文发布时(2019年10月1日 ), 在全世界范围内已经有41%的网站开启了HTTP/2。

HTTP/2的官方组织在 Github 上维护了一份各种语言对HTTP/2的实现列表,大家可以去看看。

我们可以看到,HTTP/2 在性能上对HTTP有质的提高,所以,HTTP/2 被采用的也很快,所以,如果你在你的公司内负责架构的话,HTTP/2是你一个非常重要的需要推动的一个事,除了因为性能上的问题,推荐标准也是架构师的主要职责,因为,你企业内部的架构越标准,你可以使用到开源软件,或是开发方式就会越有效率,跟随着工业办的标准的发展,你的企业会非常自然的享受到标准所带来的红利。

HTTP/3

然而,这个世界没有完美的解决方案,HTTP/2也不例外,其主要的问题是:苦干个HTTP的请求在复用一个TCP的连接,底层的TCP协议是不知道上层有多少个HTTP的请求的,所以,一旦发生丢包,造成的问题就是所有的HTTP请求都必需等待这个丢了的包被重传回来,那怕丢的那个包不是我这个HTTP请求的。因为TCP底层是没有这个知识了。

这个问题又叫Head-of-Line Blocking问题,这也是一个比较经典的流量调度的问题。这个问题最早主要的发生的交换机上。下图来自Wikipedia。

图中,左边的是输入队列,其中的1,2,3,4表示四个队列,四个队列中的1,2,3,4要去的右边的output的端口号。此时,第一个队列和第三个队列都要写右边的第四个端口,然后,一个时刻只能处理一个包,所以,一个队列只能在那等另一个队列写完后。然后,其此时的3号或1号端口是空闲的,而队列中的要去1和3号端号的数据,被第四号端口给block住了。这就是所谓的HOL blocking问题。

HTTP/1.1中的pipeline中如果有一个请求block了,那么队列后请求也统统被block住了;HTTP/2 多请求复用一个TCP连接,一理发生丢包,就会block住所有的HTTP请求。这样的问题很讨厌。好像基本无解了。

是的TCP是无解了,但是UDP是有解的 !于是HTTP/3破天荒地把HTTP地底层的TCP协议改成了UDP!

然后又是Google 家的协议进入了标准 – QUIC (Quick UDP Internet Connections)。接下来是QUIC协议的几个重要的特性,为了讲清楚这些特性,我需要带着问题来讲(注:下面的网络知识,如果你看不懂的话,你需要学习一下《TCP/IP详解》一书(在我写blog的这15年里,这本书推荐了无数次了),或是看一下本站的《TCP的那些事》。):

  • 首先是上面的Head-of-Line blocking问题,在UDP的世界中,这个就没了。
  • TCP是一个无私的协议,也就是说,如果网络上出殃拥塞,大家都会丢包,于是大家都会进入拥塞控制的算法中。QUIC才不管这个,是个相对比较激进的协议。QUIC有一套自己的丢包重传和拥塞控制的协,一开始QUIC是重新实现一TCP 的 CUBIC算法,但是随着BBR算法的成熟(BBR也在借鉴CUBIC算法的数学模型),QUIC也可以使用BBR算法。多扯几名,从模型来说,以前的TCP的拥塞控制算法玩的是数学模型,而新型的TCP拥塞控制算法是以BBR为代表的测量模型,理论上来说,后者会更好,但QUIC的团队在一开始觉得BBR不如CUBIC的算法好,所以没有用。现在的BBR 2.x借鉴了CUBIC数学模型让拥塞控制更公平。这里有文章大家可以一读“TCP BBR : Magic dust for network performance.
  • 接下来,现在要建议一个HTTP的连接,先是TCP的三次握手,然后是TLS的三次握手,要整出六次网络交互,一个链接才建好,虽说HTTP/1.1和HTTP/2的连接复用解决这个问题,但是基于UDP后,UDP也得要实现这个事。于是QUIC直接把TCP的和TLS的合并成了三次握手。

 

所以,QUIC是一个在UDP之上的伪TCP +TLS +HTTP/2的多路复用的协议。

但是其于UDP还是有一些挑战的,这个挑战主要来自互联网上的各种网络设备,这些设备根本不知道是什么QUIC,他们看QUIC就只能看到的就是UDP,所以,在一些情况下,UDP就是有问题的,

  • 比如在NAT的环境下,如果是TCP的话,NAT路由或是代理服务器,可以通过记录TCP的四元组(源地址、源端口,目标地址,目标端口)来做连接映射的,然而,在UDP的情况下不行了。于是,QUIC引入了个叫connection id的不透明的ID来标识一个链接,用这种业务ID很爽的一个事是,如果你从你的3G/4G的网络切到WiFi网络(或是反过来),你的链接不会断,因为我们用的是connection id,而不是四元组。
  • 然而就算引用了connection id,也还是会有总理 ,比如一些不够“聪明”的等价路由交换机,这些交换机会通过四元组来做hash把你的请求的IP转到后端的实际的服务器上,然而,他们不懂connection id,只懂四元组,这么导致属于同一个connection id但是四元组不同的网络包就转到了不同的服务器上,这就是导致数据不能传到同一台服务器上,数据不完整,链接只能断了。所以,你需要更聪明的算法(可以参看 Facebook 的 Katran 开源项目 )

好了,就算搞定上面的东西,还有一些业务层的事没解,这个事就是 HTTP/2的头压缩算法 HPACK,HPACK需要维护一个动态的字典表来分析请求的头中哪些是重复的,HPACK的这个数据结构需要在encoder和decoder端同步这个东西。在TCP上,这种同步是透明的,然而在UDP上这个事不好干了。所以,这个事也必需要重新设计了,基于QUIC的QPACK就出来了,利用两个附加的QUIC steam,一个用来发送这个字典表的更新给对方,另一个用来ack对方发过来的update。

目前看下来,HTTP/3目前看上去没有太多的业务上的东西,更多是HTTP/2 + QUIC协议。但,HTTP/3 因为动到了底层协议,所以,在普及方面上可能会比 HTTP/2要慢。但是,试想一下,QUIC这个协议真对TCP是个威胁,如果QUIC成熟了,TCP是不是会有可能成为历史?

未来十年,让我们看看UDP是否能够逆袭TCP……

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 October 01, 2019 at 07:21PM
from 酷 壳 – CoolShell https://ift.tt/2mAAPcE

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share