[翻译]区块链是怎么回事?做一个应用带你了解

How does blockchain really work? I built an app to show you.

Wikipedia 上对区块链的描述:

维护不断增长的记录(称作区块)的分布式数据库。

听上去很简单,但到底是怎么回事呢?

我们用一款开源命令行界面 Blockchain CLI 来详细说明区块链。

我也构建了一个浏览器可以访问的在线版

安装命令行界面

首先请确保安装 Node.js

然后在终端里运行下面命令:

npm install blockchain-cli -g
blockchain

你将看到 👋 Welcome to Blockchain CLI!blockchain → 提示已准备好接受命令。

区块是什么样子的?

你可以在命令行中输入 blockchainbc 来查看你当前的区块链。你将看到下图类似的区块。

  • 索引(区块):这是哪个区块?(初始区块索引为 0)
  • 哈希:区块有效吗?
  • 前个哈希:之前一个区块有效吗?
  • 时间戳:区块什么时候添加的?
  • 数据:区块中存的什么信息?
  • 随机数(Nonce):我们重复了多少次才找到有效的区块?

初始区块

每个区块链都会以一个 🏆 Genesis Block 作为开始。你接下来将会看到每个区块都关联前一个区块。所以我们开采第一个区块前,要有初始区块。

当一个新的区块被开采出来会发生什么?

让我们来开采我们的第一个区块,在提示框输入 mine freeCodeCamp♥︎ 命令。
区块链根据最后一个区块生成当前索引和前个哈希。我们现在的区块链最后一个区块就是初始区块。

  • 索引:o+1 = 1
  • 前个哈希:0000018035a828da0…
  • 时间戳:区块什么时候添加的?
  • 数据:freeCodeCamp❤
  • 哈希:??
  • 随机数(Nonce):??

哈希值如何计算?

哈希值是固定长度的数值,用来标识唯一数据。

哈希通过将索引、前个哈希、时间戳、数据、随机数作为输入后计算得出。

CryptoJS.SHA256(index + previousHash + timestamp + data + nonce)

SHA256 算法通过给定的输入,计算出一个唯一的哈希。相同的输入总会生成相同的哈希。

你注意到哈希开头的四个 0 了吗?

开头的四个 0 是有效哈希的基本要求。开头 0 的个数被称为难度值(difficulty)。

function isValidHashDifficulty(hash, difficulty) {
  for (var i = 0, b = hash.length; i < b; i ++) {
      if (hash[i] !== '0') {
          break;
      }
  }
  return i >= difficulty;
}

这就是众所周知的工作量证明系统

什么是随机数?

随机数是用来寻找有效哈希的一个数字。

let nonce = 0;
let hash;
let input;
while(!isValidHashDifficulty(hash)) {     
  nonce = nonce + 1;
  input = index + previousHash + timestamp + data + nonce;
  hash = CryptoJS.SHA256(input)
}

随机数不断迭代,直到哈希有效。在我们的例子中,有效的哈希值至少要四个 0 开头。寻找有效哈希对应随机数的过程就称为开采(挖矿)。

随着难度值的提升,有效哈希的数量逐步减少,我们需要投入更多资源来找到一个有效哈希。

为什么这很重要?

因为它确保了区块链不可变。

如果我们有一个这样的区块链 A → B → C,有人想修改区块 A 上的数据。会发生下面情况:

  1. 修改区块 A 上的数据。
  2. 区块 A 的哈希变动,因为计算哈希所用的数据变化了。
  3. 区块 A 无效,因为它的哈希不是四个 0 开头。
  4. 区块 B 的哈希变动,因为计算区块 B 的哈希所用到的区块 A 的哈希值变化了。
  5. 区块 B 无效,因为它的哈希不是四个 0 开头。
  6. 区块 C 的哈希变动,因为计算区块 C 的哈希所用到的区块 B 的哈希值变化了。
  7. 区块 C 无效,因为它的哈希不是四个 0 开头。

修改一个区块的唯一方式就是重新开采这个区块以及它之后的所有区块。因为新的区块不断增加,基本不可能修改区块链。

我希望这份说明对你有帮助。
如果你想检出例子的在线版本,移步 http://blockchaindemo.io

[翻译]惊叹!这个盲人程序员是这样写代码的

Software development 450 words per minute

我认为你第一次看到我的工作间肯定这样想 —— “总感觉少些什么”。没有显示器和鼠标,却有个人敲打着键盘,不知注视着哪里。

这就是我,我同事可以证明我没问题。我是位于坦佩雷(芬兰西南部一座城市)的 Vincit 写字楼中的一名软件开发者。我双目失明。这篇文章中我将讲述有关我工作中的事情。

你真的什么都看不到吗?

准确来说,我觉察到阳光和其他明亮的光线,不过也仅限这些。其实,这对我的工作也并没有什么帮助。

你工作内容是什么?

和大部分人一样:忙时写代码,闲时和同事吹逼。我做全栈项目,主攻后端。兼职访问顾问 – 或称监管,随你如何称呼。

你如何使用电脑?

我用的电脑是一台运行 Windows 10 的普通笔记本。是其中的软件让一切变得神奇。我使用一款叫做屏幕阅读器的程序来访问电脑。屏幕阅读器监听屏幕上的变化并通过盲文(需要单独的盲文设备)或合成的声音来展示给用户。这并不是你如今听到的各种智能助理的合成声音。我使用一种机械声音,每分钟能说 450 个单词。相比较而言,英语正常语速每分钟 120-150 个单词。我有一个怪癖:我既说英语也说芬兰语,我用芬兰语合成器读英语,因为老旧的屏幕阅读器在语言之间切换不够智能,所以我习惯这样做。下面是个例子是阅读这个段落,我能听懂。

https://www.vincit.fi/wp-content/uploads/2017/08/mpsample.mp3?_=1

下面是英语合成器发出的声音:

https://www.vincit.fi/wp-content/uploads/2017/08/essample.mp3?_=2

鼠标对于我来说并不是非常有用,所以我仅仅通过键盘工作。在座的各位应该十分熟悉我用到的命令:方向键和 tab 键控制窗口内的移动,alt+tab 切换窗口等等。屏幕阅读器也有很多自己的快捷键,比如阅读活动窗口的不同区域或开关一些功能特性。

有趣的是阅读网页和其他格式化文档。你看,屏幕阅读器分块呈现信息。每一块可能是一行,也可能是一个单词、一个字母,亦或是文本的片段。举个例子,我在网页中按向下的方向键,我听到页面的下一行。我并不能像正常人一样用眼睛从屏幕上阅读内容。相反,我听到一块一块的内容,或跳过我不感兴趣的部分。

语音或盲文并不能描绘出窗口的显示布局。信息以线性方式呈现给我。如果你把网页复制粘贴进记事本,你就能明白我看到的网页是什么样子的。就是剥离大部分格式的多行文本。然而屏幕阅读器可以获取网页上的 HTML 语法,所以我也能知道超链接、标题、表单等等。事实上,如果非复选框元素展示成复选框样式,我并不能知道这是复选框。我之后将写一篇文章详细讲述这些内容,记住我刚刚举的是个“反人类”例子。
(译者注:突然感到自责和羞愧,深深明白了一个道理:不要用各种有含意义的传统标签 hack 布局和样式,也不要因为 css 的强大而懒得使用各种有含义的传统标签。共勉)

我花费大量时间工作在命令行上。事实上我通常用浏览器和编辑器,很少用其他图形应用程序。相比那些为鼠标用户打造的图形界面,我发现用命令行处理手边的工作更加高效。

既然我如此热爱命令行,为什么我却要选择 Windows 这个并不以命令行出名的操作系统呢?答案很简单:Windows 是最方便的操作系统。NVDA是我所选择的屏幕阅读器,它是开源的并且维护比其他阅读器更频繁。如果上天再我一次机会,我可能会选 Mac 系统,因为我认为它是易用性和功能性平衡的典范。不幸的是 Mac 系统上的屏幕阅读器 VoiceOver 经历了漫长的发布周期从而被遗忘,并且它的导航模型和我独特的工作方式并不协调。当然这里也有一个 Gnome 桌面上的屏幕阅读器,虽然用户很少,依然被很好地维护着,不过还有一些不完善的地方和我日常工作不协调。所以,我选择 Windows。由 GNU 诞生的 Git Bash 和其他命令行工具弥补了 Windows 内置命令行的缺陷。

你如何写代码?

我花费好长时间才明白为什么大家觉得这个问题是个很高深的问题。记得我上面说过一行一行地阅读文本吗?我也是通过这种方式读代码。通常我会跳过无用的行,或仅听半行来获取内容,但当我需要知道完整信息的时候,我不得不像读小说一样读完所有东西。我当然无法阅读整个代码库。这种情况下我会在脑中抽象一部分代码:这个组件输入 x 返回 y,并不用关心细节逻辑。

这种阅读方式让我和正常同事的工作方式有些区别。举个例子,当代码审查时,我喜欢看原始 diff 输出,并列窗口显示 diff 对我并不适用,而且还容易让人分心。有修改的代码行上用符号 + 和 – 比用不同背景色标注也要好太多,并不是因为我不能获知颜色名字,而是因为在新增的一行中,读“加”这个字比读“带复杂阴影的高亮红色”用更短的时间。(嘿,我说你呢 Gerrit (一款代码审查工具))

你或许会认为缩进和其他代码格式和我无关,因为都是基本的视觉问题。并不是这样,正确的缩进对我的帮助和正常开发者一样。当我用盲文(比语音更加高效)读代码时,我像其他正常程序员一样清楚代码结构。当我进入一段有缩进或无缩进的代码时,我也会得到语音提醒。这些信息帮助我在脑中描绘代码结构。事实上我学的第一门语言就是 Python (PHP 不算),它强制使用代码缩进,这对我来说并不是问题。我有众多理由来强烈建议使用整洁统一的代码风格,其中之一就是不要让我的生活变得更加艰难了,好吗。

你喜欢哪款编辑器?

剧透一下:这个答案并不是以 V 或者 E 开头(我虽然通过命令行用 Vim 来写 git commit 信息和其他备注。我认为我在这场圣战中是中立的)(译者注:Vim 和 Emacs 梗)一年前我认为 Notepad++ 最棒,它是轻量级的做工精细的文本编辑器。然而一年前我还没有接触大规模 Java 项目,当我接触这种项目时,意味着我应该在 Notepad++ 和理智之间做个选择。最后我选择理智,抛弃 Notepad++ 转投 IntelliJ IDEA 的怀抱。从那之后 IntelliJ IDEA 便是我首选编辑器。我曾对各种 IDE 有深深怨念,它们大多数在纯键盘流操作下麻烦又低效。如果我视力没问题,我肯定早就跳到 IDE 阵营了。

但你可能会问,为什么当初选 Notepad++。还有其他很多更先进的轻量级编辑器,比如 Sublime 或 Atom。原因很简单:屏幕阅读器无法访问它们。Vim 一类的文本编辑器也是如此,我使用的屏幕阅读器对命令行程序的支持有问题,在这些编辑器上无法处理多于 commit 信息的文本。很遗憾,可用性决定了我能够使用的工具。即使我不能高效工作,也不是什么大问题。

你编写过前端代码吗?

你应该认为前端开发和视觉有关,注定与盲人程序员无缘。基本上是这样。我从来不自己做概念原型,我做都是有界面,需要随后加入功能的项目。

然而,我也做过 Angular 和 React 工作任务。怎么会这样?如今很多 APP 基于浏览器。举个例子,我曾花费两周时间为一个 Angular APP 增加国际化支持。我并不需要做任何视觉上的改动。

我发现对于我这类开发者开说,像 Bootstrap 这类的库简直是上天的礼物。正因为栅格系统(Bootstrap的响应式布局解决方案),我可以自己构建一个粗糙的界面。尽管如此,我做的有关界面的改动在呈现给用户之前仍然要有一双眼睛检查。所以,总而言之,我可以在一定程度上做些前端开发,至少不是和表现层太相关。

有什么其他没有提到的东西?

其实这篇文章有很多东西没有表达出来。正如上文所承诺,我将全力以赴写一篇文章,有关制作易访问网页的艺术,因为一言未尽是我讨厌的事情之一。我不会半途而废的,敬请期待。

[翻译]每个程序员都该知道的五大定律

5 laws every developer should know

定律-或称法则,可以指导我们并让我们在同伴的错误中学习。这篇文章中,我将介绍我每次设计或实现软件时出现在我脑海的五大定律。其中有些和开发有关,有些和系统组织有关。它们可以帮助你成为合格的软件工程师。

墨菲定律

“凡事可能出错,就一定出错。”

这条定律来源于 Edward Murphy —— 一名航天工程师在 50 年代初对火箭测试失败的回应。这条定律给我们的启示是永远在系统关键地方使用防御性设计,因为系统某些地方总会出错!

这条定律很容易引入软件工程领域。当你将软件暴露给终端用户,他们会创造性地输入一些出人意料的内容,使系统宕机。所以你需要让你的软件足够健壮,能够检测并警告非预期行为。

当你在机器上运行软件时,任何地方都有可能发生问题 —— 从硬盘上的系统到数据中心的电力供应。所以你必须确保你设计的架构在每个层级都可以应对故障。

我曾经有机会领略过几次墨菲定律。
举个例子,我曾经在一个批处理框架中使用字符串“null”来表示空值,我并不认为这有问题,直到有个名字叫“Null”的用户提交了一个交易订单,我们的报表流程中断了几个小时……
还有一次,在另一个项目中。当所有东西都准备好部署到生产环境了,突然 Azure 基础设施故障导致我们运行自动化脚本的服务器宕机了。

现实世界中的经验教训提醒着我生活的艰难 —— “凡事可能出错,就一定出错”。
所以,心中牢记墨菲定律,设计健壮的软件。

Knuth定律

“在(至少大部分)编程中,过早优化是万恶之源。”

这条定律也是 Donald Knuth 的经典语录之一,它告诫我们不要过早优化应用程序中的代码,直到必须优化时再优化。

的确,简单易读的源码可以满足 99% 的性能需要,并能提高应用的可维护性。最开始使用简单的解决方案也让后期性能出现问题时更容易迭代和改进。

垃圾自动回收的编程语言中,字符串的连接常常是过早优化的例子。在 Java 或 C# 中,String 对象是不可变的,我们学会使用其他结构动态创建字符串,比如 StringBuilder。但事实上直到你分析完个应用程序前,你并不知道 String 对象创建了多少次并对性能的产生多大影响。所以首先编写尽可能整洁的代码,之后在必须的时候再优化,往往这样做更有意义。

然而,这条规则并不应该阻止你去学习编程语言的性能权衡和正确的数据结构。并且,正如所有其他性能问题,你在优化前要测量开销。

North定律

“每一个决定都是一次权衡”

好吧,我承认这是取自 Dan North 的演讲 Decisions,Decisions,它目前还不是公认的定律。
但这条语录影响了我做的每个决定,所以我把它放在这。

开发者日复一日的生活中,我们每天都做无数个大大小小的决定。从命名变量到自动化(手动)任务,再到定义平台架构。

这条语录强调无论你做的选择是什么,你总会放弃一个或多个选项

但这不是最重要的。
最重要的是理智地做出决定,了解其他选项,清楚你为什么不选择它们。你要始终根据当前你掌握的信息来权衡并做出决定。

但是如果后来你了解到新的信息,并发现之前的决定是错误的,这也没关系。关键是记清楚你为什么做出那个决定,重新评估新的选项之后再做出新的理智的决定。

重复一遍

“每一个决定都是一次权衡”

所以,做出选择并对所有选项心知肚明。

Conway定律

“系统设计的架构受限于生产设计,反映出公司组织的沟通架构”

在 60 年代,一位名叫 Melvin Conway 的工程师注意到公司组织结构影响到他们开发的系统的设计。他用一篇论文描述了这个观点,并命名为“Conway定律”。

这条定律很适用于软件开发领域,甚至体现到代码层面上。交付软件组件的各个团队组织结构直接影响到组件的设计。

举个例子,一个集中式的开发者团队会开发出各组件耦合的整体应用。另一方面,分布式的团队会开发出单独的(微)服务,每一部分关注点分离清晰。

这些设计没有好坏之分,但它们都是受到团队沟通方式的影响。在全球有大量独立开发者的开源项目,通常是模块化和可重用库,这就是很有说服力的例子。

如今,将大的集成应用解耦成微服务已成趋势。这很棒,因为这可以加速交付使用项目。但你也应该牢记 Conway定律,在公司组织构建中投入与技术开发同样多的工作。

琐碎定律(帕金森琐碎定律)

“组织成员投入大量精力到琐碎的事情上。”

这条定律论点是在会议中花费的时间与事情的价值成反比。的确是这样,人们更愿意把注意力和观点放在他们熟悉的事物上,而不是复杂的问题上。

帕金森给出一个例子,一场会议中,成员们讨论两件事:为公司建核反应堆和为员工建车棚。建反应堆是一件巨大而复杂的任务,没有人能完全掌控全局。他们完全信赖流程和系统专家,并很快接受了项目。

另一边,建车棚是一般人都可以做的,每个人都可以对颜色有意见。事实上,每个会议成员都会表达自己的意见,使得建车棚的决议所花费的时间远远超过建反应堆的。

这条定律在软件行业十分出名,这个故事随后也被称为车棚效应

举个例子,开发者会花费更多时间到讨论正确缩进或函数命名,而不是讨论类的职责或应用架构。这是因为每个人都能认知几个字符的变动,但项目架构的变动则需要巨大的认知负载

你能注意到的车棚效应的另一个例子是 Scrum 演示。不要误会我,我喜欢演示,我认为这是一个很好的机会来面对用户并获得对应用程序的反馈。但通常 Scrum 演示过程中的讨论会转向琐碎问题,而不是审视全局。这些讨论也很重要,但你应该注意权衡更重要更复杂的问题。

一旦你了解这种规律,你将在会议和交流中发觉这种行为。
我并不是让你在每次讨论中避免“小”问题,提高你的意识可以帮助你关注真正的问题,并为这些会议做好准备。

结论

这五条定律只是我们行业中总结出的教训中一些例子。随着软件开发经验的增长,我们将会学会更多。
尽管其中某些定律现在看起来是常识,我始终坚信了解这些原则可以帮助你识别这些模式并做出反应。

[翻译]有哪些奇怪的排序算法

原文https://www.quora.com/What-is-the-strangest-sorting-algorithm

下面是Nipun Ramakrishnan的回答

睡眠排序

另一个搞笑算法流传于 4chan 的 /prog/ 板块。无从查证具体出自哪位程序员,伪代码如下

procedure printNumber(n)
    sleep n seconds
    print n
end

for arg in args
    run printNumber(arg) in background
end
wait for all processes to finish

算法运行如下:
对于数组中每个元素 x,开启一个新程序:
* 休眠 x 秒
* 打印 x
所有元素同时开始计时。
只适用于非负数字。

下面是Ryan Turner的回答

Bogo 排序(猴子排序)

Bogo 排序,名字很奇怪。它是愚蠢排序中的一员。
主要来说,算法就是你把元素随机排列。
如果没有排好序,再次把元素随机排列。
如果还没有排好序,你懂的。下面是个例子:
4, 7, 9, 6, 5, 5, 2, 1 (未排序)
2, 5, 4, 7, 5, 9, 6, 1 (随机排列)
1, 4, 5, 6, 9, 7, 5, 2 (再次随机排列)
1, 2, 4, 5, 5, 6, 7, 9 (天呐,真幸运)
你不停地随机排序,直到得到一个有序数组。
毫无疑问这是最低效的排序算法之一,除非你非常非常幸运。它时间复杂度是令人窒息的 O(n!),而且随着元素数量增加,很有 O(∞) 的趋势。

下面是Tyler Schroeder的回答

量子 Bogo 排序

我是量子 Bogo 排序的粉丝:

  • 随机排列数组中元素。
  • 如果数组没有排好序,摧毁当前宇宙(这一步就拜托你了)
  • 存活的宇宙将会有排好序的数组。
    时间复杂度仅仅 O(n)
    注意:这种算法依赖于量子力学的平行宇宙理论的可靠性。如果量子力学的平行宇宙理论不准确,这个算法时间复杂度达不到 O(n)

下面是Yi Wang的回答

打印店页码排序

这并不是我发明的,我从别处看到的。
一个学生去打印店打印材料。他需要两份,但并没有直接打印两份,而是将每一页打印了两次,像下面这样:
需要的页码顺序: 1 2 3 4 … N; 1 2 3 4 … N
手上的页码顺序: 1 1 2 2 3 3 4 4 …. N N
他开始对打印材料排序,取一页放在左边,然后取一页放在右边。打印店老板看不下去了,直接把材料拿过来。
老板首先取一页放在左边,然后两页放在右边,再然后两页左边,两页右边……
排序速度瞬间翻倍 ……
(网友评论:这是归纳,不是排序)

下面是其他网友的回答

慢排序

这是一个非常幽默却没什么用的排序算法。它基于“合而不治”的原则(分治算法基本思想“分而治之”的反义词,文字游戏),它由 Andrei Broder 和 Jorge Stolfi 于 1986 年发表在论文《Pessimal Algorithms and Simplexity Analysis(最坏排序和简单性分析)》中,伪代码如下:

function slowSort(array,start,end){
    if( start >= end ) return; //已经不能再慢了
    middle = floor( (start+end)/2 );

    //递归
    slowSort(array,start,middle);
    slowSort(array,middle+1,end);

    //比较得出最大值放在队尾
    if( array[end] < array[middle] )
        swap array[end] and array[middle]

    //去掉最大值之后再排序
    slowsort(array,start,end-1);
}
  • 递归排序好前一半
  • 递归排序好后一半
  • 比较中间和队尾的值,得到整个数组的最大值,将最大值放到队尾。
  • 去掉最大值,递归整个数组

Stack 排序

从 StackOverflow 上搜索标题含有“数组排序”的帖子,复制粘贴并运行其中的代码片段,直到数组排好序。我认为这种排序算法事实上验证了整个数组。它被发表在xkcd网站上,这里有一个在线版的具体实现stacksort

随机排序

运行如下:
创建一个随机程序。
传入数组并运行随机程序。
如果程序的输出恰好是排好序的,完成。
否则重复上面过程。

太阳能比特翻转排序

太阳发出的阿尔法粒子偶尔能够翻转内存中的比特位,所以这种算法主要基于希望这种翻转能够使元素正确排序。运行方式如下:

检查数组是否排好序。
如果排好序,返回这个数组。
如果没有,等 10 秒钟并祈祷太阳辐射使得比特位翻转,而且使得数组排好序,重复第一步。

意大利面排序

这是一种线性时间算法,是需要 O(n) 空间的稳定排序。它需要并行处理器。简单来说,假设我们排序一列自然数。排序方法需要使用很多根生的意大利面条。

将数据按比例转换成表示意大利面条长度的数字。
在每根面条上写下数字,并将面条折断成数字表示的长度。
把所有面条攥成一捆并把底部在平面上敲击。
取出最突出的一根面条,也就是最长的一根,获取上面的数字,转换成原始的数据并记录下来。
重复这个过程直到处理完所有意大利面。

指鹿为马排序

这个算法时间复杂度 O(n)。
聚集一帮人并向他们展示数组。
询问他们这个数组是否是排序好的。
干掉其中认为没有排序好的人。
重复几次,直到所有人同意这个数组是排序好的。

智能设计排序

无论你的数组状态是什么样的,它都算是排好序的。
解释:原始输入按照某种顺序的概率是 1/(n!)。概率是如此小,(当前的顺序)归结于运气成分显然是荒谬的,所以它是按照“智能设计”排序过的。所以完全可以说数组已经排好序了,只是不是我们传统意义上的“升序”。如果按照我们传统观点对它进行操作,只会让它乱序。(“智能设计”涉及宗教和哲学,不过多解释

互联网排序

这是一种冒泡排序,但每次比较都依靠互联网的搜索。比如 “0.211 和 0.75 哪个大?”

委员会排序

排序一个包含 N 个自然数的数组,首先用纸打印出 N 份整个数组。
然后在办公室周围选择几个恰好路过的倒霉委员。每个委员对应数组中的一个数字。
给每个委员一份打印的数组,并让他们通过开会或其他手段,来决定自己代表的数字应该在有序数组中的位置。
当这些委员有结论并答复你时,数组自然排好序了。

[翻译]十行HTML代码实现增强现实

原文Augmented Reality in 10 Lines of HTML

你想通过网络实现增强现实吗?现在你只需要 10 行 HTML 代码!真的!让我带你看一看代码,非常简单。

我们最近发布了AR.js。你不需要安装任何应用,用你的手机通过网络就能体验到强大的增强现实。但让我们更进一步,看一下如何让你也创作出自己的增强现实体验。多亏了神奇的a-frame,最短的 AR.js 只有 10 行 HTML 代码。你可以在codepen看到在线版:

<!-- Augmented Reality on the Web in 10 lines of html! https://github.com/jeromeetienne/ar.js --> 
<script src="https://aframe.io/releases/0.5.0/aframe.min.js"></script>
<script src="https://rawgit.com/jeromeetienne/ar.js/master/aframe/build/aframe-ar.js"></script>
<script>THREEx.ArToolkitContext.baseURL = 'https://rawgit.com/jeromeetienne/ar.js/master/three.js/'</script>
<body style='margin : 0px; overflow: hidden;'>
    <a-scene embedded artoolkit='sourceType: webcam;'>
        <a-box position='0 0.5 0' material='opacity: 0.5;'></a-box>
        <a-marker-camera preset='hiro'></a-marker-camera>
    </a-scene>
</body>

我们来一行一行看.

引入库

<script src="https://aframe.io/releases/0.5.0/aframe.min.js"></script>
<script src="https://rawgit.com/jeromeetienne/ar.js/master/aframe/build/aframe-ar.js"></script>
<script>THREEx.ArToolkitContext.baseURL = 'https://rawgit.com/jeromeetienne/ar.js/master/three.js/'</script>

首先,你需要引入a-frame,一款MozillaVR引领的开发 VR 体验的利器。A-frame 包含了 three.js。然后你只需要为 a-frame 引入 AR.js。AR.js能让 AR 中的 3d 显示在你的手机上高速运行,哪怕是 2、3 年前的旧手机。

定义 Body

<body style='margin : 0px; overflow: hidden;'>
    <!-- ... -->
</body>

这一步,国际惯例。就像你在所有 HTML 页面中做的一样,定义 body。

创建 3d 场景

<a-scene embedded artoolkit='sourceType: webcam;'>
    <!-- put your 3d content here -->
</a-scene>

然后,我们将要创建我们的 a-farme 场景。我们当然也需要加入 ARToolkit 组件。ARToolkit是一个开源库,我们通过它来实现摄像头定位。

添加简单的内容

<a-box position='0 0.5 0' material='opacity: 0.5;'></a-box>

一旦我们创建了 3d 场景,我们可以开始向里面添加对象。在这行代码中,我们添加了一个简单的盒子。然后我们修改了它的材质,让它变得透明。我们也改变了它的位置,所以它出现在 AR 标识(AR marker)的上方。

增加 AR 摄像头

<a-marker-camera preset='hiro'></a-marker-camera>

在最后一步,我们增加一个摄像头。我们预设一个 ‘hiro’(来自Hiro marker)最后,我们让它像你手机一样移动。是不是很简单?

恭喜!你完成了。你仅用了 10 行 HTML 代码实现了增强现实,手机上也能运行飞快,而且免费。

[翻译]理解 JavaScript 作用域

Understanding Scope in JavaScript

简介

JavaScript 有个特性称为作用域。尽管对于很多开发新手来说,作用域的概念不容易理解,我会尽可能地从最简单的角度向你解释它们。理解作用域能让你编写更优雅、错误更少的代码,并能帮助你实现强大的设计模式。

什么是作用域?

作用域是你的代码在运行时,各个变量、函数和对象的可访问性。换句话说,作用域决定了你的代码里的变量和其他资源各个区域中的可见性。

为什么是作用域?最小访问原则

那么,限制变量的可见性,不允许你代码中所有的东西在任意地方都可用的好处是什么?其中一个优势,是作用域为你的代码提供了一个安全层级。计算机安全中,有个常规的原则是:用户只能访问他们当前需要的东西。

想想计算机管理员吧。他们在公司各个系统上拥有很多控制权,看起来甚至可以给予他们拥有全部权限的账号。假设你有一家公司,拥有三个管理员,他们都有系统的全部访问权限,并且一切运转正常。但是突然发生了一点意外,你的一个系统遭到恶意病毒攻击。现在你不知道这谁出的问题了吧?你这才意识到你应该只给他们基本用户的账号,并且只在需要时赋予他们完全的访问权。这能帮助你跟踪变化并记录每个人的操作。这叫做最小访问原则。眼熟吗?这个原则也应用于编程语言设计,在大多数编程语言(包括 JavaScript)中称为作用域,接下来我们就要学习它。

在你的编程旅途中,你会意识到作用域在你的代码中可以提升性能,跟踪 bug 并减少 bug。作用域还解决不同范围的同名变量命名问题。记住不要弄混作用域和上下文。他们是不同的特性。

JavaScript中的作用域

在 JavaScript 中有两种作用域

  • 全局作用域
  • 局部作用域

当变量定义在一个函数中时,变量就在局部作用域中,而定义在函数之外的变量则从属于全局作用域。每个函数在调用的时候会创建一个新的作用域。

全局作用域

当你在文档中(document)编写 JavaScript 时,你就已经在全局作用域中了。JavaScript 文档中(document)只有一个全局作用域。定义在函数之外的变量会被保存在全局作用域中。

// the scope is by default global
var name = 'Hammad';

全局作用域里的变量能够在其他作用域中被访问和修改。

var name = 'Hammad';

console.log(name); // logs 'Hammad'

function logName() {
    console.log(name); // 'name' is accessible here and everywhere else
}

logName(); // logs 'Hammad'

局部作用域

定义在函数中的变量就在局部作用域中。并且函数在每次调用时都有一个不同的作用域。这意味着同名变量可以用在不同的函数中。因为这些变量绑定在不同的函数中,拥有不同作用域,彼此之间不能访问。

// Global Scope
function someFunction() {
    // Local Scope ##1
    function someOtherFunction() {
        // Local Scope ##2
    }
}

// Global Scope
function anotherFunction() {
    // Local Scope ##3
}
// Global Scope

块级声明

块级声明包括ifswitch,以及forwhile循环,和函数不同,它们不会创建新的作用域。在块级声明中定义的变量从属于该块所在的作用域。

if (true) {
    // this 'if' conditional block doesn't create a new scope
    var name = 'Hammad'; // name is still in the global scope
}

console.log(name); // logs 'Hammad'

ECMAScript 6 引入了letconst关键字。这些关键字可以代替var

var name = 'Hammad';

let likes = 'Coding';
const skills = 'Javascript and PHP';

var关键字不同,letconst关键字支持在块级声明中创建使用局部作用域。

if (true) {
    // this 'if' conditional block doesn't create a scope

    // name is in the global scope because of the 'var' keyword
    var name = 'Hammad';
    // likes is in the local scope because of the 'let' keyword
    let likes = 'Coding';
    // skills is in the local scope because of the 'const' keyword
    const skills = 'JavaScript and PHP';
}

console.log(name); // logs 'Hammad'
console.log(likes); // Uncaught ReferenceError: likes is not defined
console.log(skills); // Uncaught ReferenceError: skills is not defined

一个应用中全局作用域的生存周期与该应用相同。局部作用域只在该函数调用执行期间存在。

上下文(Context)

很多开发者经常弄混作用域和上下文,似乎两者是一个概念。但并非如此。作用域是我们上面讲到的那些,而上下文通常涉及到你代码某些特殊部分中的this值。作用域指的是变量的可见性,而上下文指的是在相同的作用域中的this的值。我们当然也可以使用函数方法改变上下文,这个之后我们再讨论。在全局作用域中,上下文总是 Window 对象。

// logs: Window {speechSynthesis: SpeechSynthesis, caches: CacheStorage, localStorage: Storage…}
console.log(this);

function logFunction() {
    console.log(this);
}
// logs: Window {speechSynthesis: SpeechSynthesis, caches: CacheStorage, localStorage: Storage…}
// because logFunction() is not a property of an object
logFunction(); 

如果作用域定义在一个对象的方法中,上下文就是这个方法所在的那个对象

class User {
    logName() {
        console.log(this);
    }
}

(new User).logName(); // logs User {}

(new User).logName()是创建对象关联到变量并调用logName方法的一种简便形式。通过这种方式你并不需要创建一个新的变量。

你可能注意到一点,就是如果你使用new关键字调用函数时上下文的值会有差异。上下文会设置为被调用的函数的实例。考虑一下上面的这个例子,用new关键字调用的函数。

function logFunction() {
    console.log(this);
}

new logFunction(); // logs logFunction {}

当在严格模式(strict mode)中调用函数时,上下文默认是 undefined。

执行环境

为了解决掉我们从上面学习中会出现的各种困惑,“执行环境(context)”这个词中的“环境(context)”指的是作用域而并非上下文。这是一个怪异的命名约定,但由于 JavaScript 的文档如此,我们只好也这样约定。

JavaScript 是一种单线程语言,所以它同一时间只能执行单个任务。其他任务排列在执行环境中。当 JavaScript 解析器开始执行你的代码,环境(作用域)默认设为全局。全局环境添加到你的执行环境中,事实上这是执行环境里的第一个环境。

之后,每个函数调用都会添加它的环境到执行环境中。无论是函数内部还是其他地方调用函数,都会是相同的过程。

每个函数都会创建它自己的执行环境。

当浏览器执行完环境中的代码,这个环境会从执行环境中弹出,执行环境中当前环境的状态会转移到父级环境。浏览器总是先执行在执行栈顶的执行环境(事实上就是你代码最里层的作用域)。

全局环境只能有一个,函数环境可以有任意多个。
执行环境有两个阶段:创建和执行。

创建阶段

第一阶段是创建阶段,是函数刚被调用但代码并未执行的时候。创建阶段主要发生了 3 件事。

  • 创建变量对象
  • 创建作用域链
  • 设置上下文(this)的值

变量对象

变量对象(Variable Object)也称为活动对象(activation object),包含所有变量、函数和其他在执行环境中定义的声明。当函数调用时,解析器扫描所有资源,包括函数参数、变量和其他声明。当所有东西装填进一个对象,这个对象就是变量对象。

'variableObject': {
    // contains function arguments, inner variable and function declarations
}

作用域链

在执行环境创建阶段,作用域链在变量对象之后创建。作用域链包含变量对象。作用域链用于解析变量。当解析一个变量时,JavaScript 开始从最内层沿着父级寻找所需的变量或其他资源。作用域链包含自己执行环境以及所有父级环境中包含的变量对象。

'scopeChain': {
    // contains its own variable object and other variable objects of the parent execution contexts
}

执行环境对象

执行环境可以用下面抽象对象表示:

executionContextObject = {
    'scopeChain': {}, // contains its own variableObject and other variableObject of the parent execution contexts
    'variableObject': {}, // contains function arguments, inner variable and function declarations
    'this': valueOfThis
}

代码执行阶段

执行环境的第二个阶段就是代码执行阶段,进行其他赋值操作并且代码最终被执行。

词法作用域

词法作用域的意思是在函数嵌套中,内层函数可以访问父级作用域的变量等资源。这意味着子函数词法绑定到了父级执行环境。词法作用域有时和静态作用域有关。

function grandfather() {
    var name = 'Hammad';
    // likes is not accessible here
    function parent() {
        // name is accessible here
        // likes is not accessible here
        function child() {
            // Innermost level of the scope chain
            // name is also accessible here
            var likes = 'Coding';
        }
    }
}

你可能注意到了词法作用域是向前的,意思是子执行环境可以访问name。但不是由父级向后的,意味着父级不能访问likes。这也告诉了我们,在不同执行环境中同名变量优先级在执行栈由上到下增加。一个变量和另一个变量同名,内层函数(执行栈顶的环境)有更高的优先级。

闭包

闭包的概念和我们刚学习的词法作用域紧密相关。当内部函数试着访问外部函数的作用域链(词法作用域之外的变量)时产生闭包。闭包包括他们自己的作用域链、父级作用域链和全局作用域。

闭包不仅能访问外部函数的变量,也能访问外部函数的参数。

即使函数已经return,闭包仍然能访问外部函数的变量。这意味着return的函数允许持续访问外部函数的所有资源。

当你的外部函数return一个内部函数,调用外部函数时return的函数并不会被调用。你必须先用一个单独的变量保存外部函数的调用,然后将这个变量当做函数来调用。看下面这个例子:

function greet() {
    name = 'Hammad';
    return function () {
        console.log('Hi ' + name);
    }
}

greet(); // nothing happens, no errors

// the returned function from greet() gets saved in greetLetter
greetLetter = greet();

 // calling greetLetter calls the returned function from the greet() function
greetLetter(); // logs 'Hi Hammad'

值得注意的是,即使在greet函数return后,greetLetter函数仍可以访问greet函数的name变量。如果不使用变量赋值来调用greet函数return的函数,一种方法是使用()两次()(),如下所示:

function greet() {
    name = 'Hammad';
    return function () {
        console.log('Hi ' + name);
    }
}

greet()(); // logs 'Hi Hammad'

共有作用域和私有作用域

在许多其他编程语言中,你可以通过 public、private 和 protected 作用域来设置类中变量和方法的可见性。看下面这个 PHP 的例子

// Public Scope
public $property;
public function method() {
  // ...
}

// Private Sccpe
private $property;
private function method() {
  // ...
}

// Protected Scope
protected $property;
protected function method() {
  // ...
}

将函数从公有(全局)作用域中封装,使它们免受攻击。但在 JavaScript 中,没有 共有作用域和私有作用域。然而我们可以用闭包实现这一特性。为了使每个函数从全局中分离出去,我们要将它们封装进如下所示的函数中:

(function () {
  // private scope
})();

函数结尾的括号告诉解析器立即执行此函数。我们可以在其中加入变量和函数,外部无法访问。但如果我们想在外部访问它们,也就是说我们希望它们一部分是公开的,一部分是私有的。我们可以使用闭包的一种形式,称为模块模式(Module Pattern),它允许我们用一个对象中的公有作用域和私有作用域来划分函数。

模块模式

模块模式如下所示:

var Module = (function() {
    function privateMethod() {
        // do something
    }

    return {
        publicMethod: function() {
            // can call privateMethod();
        }
    };
})();

Module 的return语句包含了我们的公共函数。私有函数并没有被return。函数没有被return确保了它们在 Module 命名空间无法访问。但我们的共有函数可以访问我们的私有函数,方便它们使用有用的函数、AJAX 调用或其他东西。

Module.publicMethod(); // works
Module.privateMethod(); // Uncaught ReferenceError: privateMethod is not defined

一种习惯是以下划线作为开始命名私有函数,并返回包含共有函数的匿名对象。这使它们在很长的对象中很容易被管理。向下面这样:

var Module = (function () {
    function _privateMethod() {
        // do something
    }
    function publicMethod() {
        // do something
    }
    return {
        publicMethod: publicMethod,
    }
})();

立即执行函数表达式(IIFE)

另一种形式的闭包是立即执行函数表达式(Immediately-Invoked Function Expression,IIFE)。这是一种在 window 上下文中自调用的匿名函数,也就是说this的值是window。它暴露了一个单一全局接口用来交互。如下所示:

(function(window) {
    // do anything
})(this);

使用 .call(), .apply() 和 .bind() 改变上下文

Call 和 Apply 函数来改变函数调用时的上下文。这带给你神奇的编程能力(和终极统治世界的能力)。你只需要使用 call 和 apply 函数并把上下文当做第一个参数传入,而不是使用括号来调用函数。函数自己的参数可以在上下文后面传入。

function hello() {
    // do something...
}

hello(); // the way you usually call it
hello.call(context); // here you can pass the context(value of this) as the first argument
hello.apply(context); // here you can pass the context(value of this) as the first argument

.call().apply()的区别是 Call 中其他参数用逗号分隔传入,而 Apply 允许你传入一个参数数组。

function introduce(name, interest) {
    console.log('Hi! I\'m '+ name +' and I like '+ interest +'.');
    console.log('The value of this is '+ this +'.')
}

introduce('Hammad', 'Coding'); // the way you usually call it
introduce.call(window, 'Batman', 'to save Gotham'); // pass the arguments one by one after the contextt
introduce.apply('Hi', ['Bruce Wayne', 'businesses']); // pass the arguments in an array after the context

// Output:
// Hi! I'm Hammad and I like Coding.
// The value of this is [object Window].
// Hi! I'm Batman and I like to save Gotham.
// The value of this is [object Window].
// Hi! I'm Bruce Wayne and I like businesses.
// The value of this is Hi.

Call 比 Apply 的效率高一点。

下面这个例子列举文档中所有项目,然后依次在控制台打印出来。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Things to learn</title>
</head>
<body>
    <h1>Things to Learn to Rule the World</h1>
    <ul>
        <li>Learn PHP</li>
        <li>Learn Laravel</li>
        <li>Learn JavaScript</li>
        <li>Learn VueJS</li>
        <li>Learn CLI</li>
        <li>Learn Git</li>
        <li>Learn Astral Projection</li>
    </ul>
    <script>
        // Saves a NodeList of all list items on the page in listItems
        var listItems = document.querySelectorAll('ul li');
        // Loops through each of the Node in the listItems NodeList and logs its content
        for (var i = 0; i < listItems.length; i++) {
          (function () {
            console.log(this.innerHTML);
          }).call(listItems[i]);
        }

        // Output logs:
        // Learn PHP
        // Learn Laravel
        // Learn JavaScript
        // Learn VueJS
        // Learn CLI
        // Learn Git
        // Learn Astral Projection
    </script>
</body>
</html>

HTML文档中仅包含一个无序列表。JavaScript 从 DOM 中选取它们。列表项会被从头到尾循环一遍。在循环时,我们把列表项的内容输出到控制台。

输出语句包含在由括号包裹的函数中,然后调用call函数。相应的列表项传入 call 函数,确保控制台输出正确对象的 innerHTML。

对象可以有方法,同样函数对象也可以有方法。事实上,JavaScript 函数有 4 个内置方法:

  • Function.prototype.apply()
  • Function.prototype.bind() (Introduced in ECMAScript 5 (ES5))
  • Function.prototype.call()
  • Function.prototype.toString()

Function.prototype.toString()返回函数代码的字符串表示。

到现在为止,我们讨论了.call().apply()toString()。与 Call 和 Apply 不同,Bind 并不是自己调用函数,它只是在函数调用之前绑定上下文和其他参数。在上面提到的例子中使用 Bind:

(function introduce(name, interest) {
    console.log('Hi! I\'m '+ name +' and I like '+ interest +'.');
    console.log('The value of this is '+ this +'.')
}).bind(window, 'Hammad', 'Cosmology')();

// logs:
// Hi! I'm Hammad and I like Cosmology.
// The value of this is [object Window].

Bind 像call函数一样用逗号分隔其他传入参数,不像apply那样用数组传入参数。

结论

这些概念是 JavaScript 的基础,如果你想钻研更深的话,理解这些很重要。我希望你对 JavaScript 作用域及相关概念有了更好地理解。如果有东西不清楚,可以在评论区提问。

作用域常伴你的代码左右,享受编码!

[翻译]大规模 Web 服务:负载均衡

原文https://blog.vivekpanyam.com/scaling-a-web-service-load-balancing/

Facebook 这类网站如何处理数十亿请求并保持高可用性呢,答案是负载均衡,本文将对其一探究竟。

什么是负载均衡

负载均衡是许多协同工作资源(通常是计算机)的分配策略。它们通常用于提高容量和可靠性。

为了便于讨论负载均衡,对于服务扩展我假设以下两点:

  • 我可以运行任意数量实例
  • 任何请求可以到达任意实例

第一个假设表明服务是无状态的(或者像 Redis 集群一样可以共享状态)。第二个假设实际中并不是必须的(比如粘性负载均衡),但在这片文章中做这样的假设便于讨论。

下面是我将要讨论的负载均衡技术:

  1. 应用层(OSI 第七层)负载均衡(HTTP、HTTPS、WS)
  2. 传输层(OSI 第四层)负载均衡(TCP、UDP)
  3. 网络层(OSI 第三层)负载均衡
  4. DNS 负载均衡
  5. 多个子域手动负载均衡
  6. 任播(Anycast)

最后还有一些其他知识点:

  • 延迟和吞吐量
  • 服务器直接返回

这些技术大致按照「网站流量增大时需要的操作步骤」排序。比如,应用层的负载均衡是首先要做的事(远远早于任播)。前三条技术提高吞吐量和可用性,但存在单点故障。其余的三条技术在提高吞吐量的同时避免了单点故障。

为了帮助我们理解负载均衡,我们来看一个简单的服务扩展。

注意:每种扩展技术都采用了非技术的比喻(在商店购物)。这些比喻仅仅是描述技术背后的思想,并不完全准确。

服务

我们假设我们正在构建大规模的服务。就像下图所示:

这个系统并不能处理大量通信,并且如果它宕机,整个应用就停了。

比喻:

  • 你走向商店唯一一条结账的队伍。
  • 你购买你的商品,如果那里没有收银员,你无法完成购买。

应用层(OSI 第七层)负载均衡

为了承载更大的通信量,首先用到的就是应用层负载均衡。应用层是 OSI 第七层。它包括 HTTP、HTTPS 和 WebSockets。一款非常流行又久经考验的应用层负载均衡器就是 Nginx。让我们看看它如何帮助我们扩展服务:

请注意,通过这种技术,我们能负载均衡数十或上百服务器实例。上面图片只展示两个作为例子。

比喻

  • 商店员工引领你到一个特别的(有收银员的)结账队伍
  • 你购买你的商品

工具:

  • Nginx
  • HAProxy

注意:

  • 我们要在这里停止使用 SSL(分发时不用 SSL)

传输层(OSI 第四层)负载均衡(TCP、UDP)

上一条技术帮助我们承载大量通信,但如果我们需要承载更大的通信量,传输层负载均衡非常有用。传输层是 OSI 第四层,包括 TCP 和 UDP。流行的传输层负载均衡器有 HAProxy(这个也用于应用层负载均衡)和 IPVS。让我们看看它们如何帮助我们扩展服务:

应用层负载均衡+传输层负载均衡能处理大多数情况下的通信量。然而我们我们仍要担心可用性。单点故障有可能出现在传输层的负载均衡器。我们在下面一节的 DNS 负载均衡解决这个问题。

比喻:

  • 根据客户会员卡卡号有不同结账区域。举个例子,如果你的会员卡卡号是偶数,去电器区附近的结账台,否则就去食品区附近的结账台。
  • 一旦你到达正确的结账区域,商店员工引领你到一个特别的结账队伍
  • 你购买你的商品

工具:

  • HAProxy
  • IPVS

网络层(OSI 第三层)负载均衡

如果我们要继续扩展,我们需要增加网络层负载均衡。这比上面两条技术更复杂。网络层是 OSI 第三层,包括 IPv4 和 IPv6。下面是网络层负载均衡:

为了搞清楚它如何工作,我们需要一点等价路由的知识(ECMP)。当有多条等价链路到达相同地址时,我们使用等价路由。简单来说,它允许路由器或交换机通过不同链接发送数据包(支持高吞吐量),最终到达同一地址。

我们可以利用这一点来实现网络层负载均衡,因为在我们看来,每个传输层负载均衡器是相同的。这意味着我们可以把从网络层负载均衡器到传输层负载均衡器的链接看做相同目的地的链路。如果我们把所有负载均衡器绑定到相同 IP 地址,我们可以使用等价路由在传输层负载均衡器之间分配通信。

比喻:

  • 街对面有两家彼此分开却又一模一样的商店,你去哪一家完全取决于你的习惯。
  • 一旦你到达了商店,根据客户会员卡卡号有不同结账区域。举个例子,如果你的会员卡卡号是偶数,去电器区附近的结账台,否则就去食品区附近的结账台。
  • 一旦你到达正确的结账区域,商店员工引领你到一个特别的结账队伍
  • 你购买你的商品

工具:

  • 通常在机柜里交换机内部的硬件中处理。

太长不阅:

  • 除非你的服务规模相当大或有自己的硬件,否则你不需要它。

DNS 负载均衡

DNS 是将名称转换为 IP 地址的系统。举个例子,它可以把 example.com 转换为 93.184.216.34 。它当然也可以返回多个 IP 地址,像下面这样:

如果返回了多个 IP,客户端通常会使用第一个可用的地址(然而一些应用只看第一个返回的 IP)。

目前有很多 DNS 负载均衡技术,比如 GeoDNS 和轮询调度(round-robin)。GeoDNS 基于不同请求者而返回不同响应。这让我们可以将客户端路由到其最近的服务器或数据中心。轮询调度会循环所有可用的 IP 地址,对于每个响应会返回不同的 IP。如果多个 IP 可用,这两种技术仅仅改变响应里的 IP 顺序。

下图展示 DNS 负载均衡如何工作:

在这个例子中,不同的用户被路由到不同的服务集群(随机或基于地理位置)。

现在这里不再有单点故障的可能性(假设有多台 DNS 服务器)。为了进一步提高可靠性,我们可以在不同数据中心运行多个服务集群。

比喻:

  • 你在网上查询购物中心,返回的列表把最近的购物中心放在第一个。你查看通往每个购物中心的路,然后选择列表中第一个营业的购物中心。
  • 街对面有两家彼此分开却又一模一样的商店,你去哪一家完全取决于你的习惯。
  • 一旦你到达了商店,根据客户会员卡卡号有不同结账区域。举个例子,如果你的会员卡卡号是偶数,去电器区附近的结账台,否则就去食品区附近的结账台。
  • 一旦你到达正确的结账区域,商店员工引领你到一个特别的结账队伍
  • 你购买你的商品

手动负载均衡和路由

如果你的内容在许多数据中心或服务间共享,而我们需要路由到其中特定的一个,那么这条技术就很有用了。比如 cat.jpg 储存在伦敦的集群中,但其他集群中没有。相似的,dog.jpg 储存在纽约的集群中,其他数据中心或集群中没有。举个例子,这很可能发生在内容刚刚上传,还未在数据中心之间复制的时候。

然而,用户获取内容时不应该等待复制完成。这意味着我们的应用需要临时把所有 cat.jpg 请求发送到伦敦,所有 dog.jpg 请求发送到纽约。所以我们需要用 https://lon-1e.static.example.net/cat.jpg 代替 https://cdn.example.net/cat.jpg。对 dog.jpg 来说也一样。

为了实现这一点,我们需要为每个数据中心设置子域(最好细分到每个集群每台机器)。除了上面的 DNS 负载均衡,这一点也很有必要。

注意:我们的应用需要保持追踪内容的位置,以便重写请求。

比喻:

  • 你拨打公司电话询问哪个购物中心提供猫粮。
  • 你查看列表上的购物中心路线,然后选择第一个营业的。
  • 街对面有两家彼此分开却又一模一样的商店,你去哪一家完全取决于你的习惯。
  • 一旦你到达了商店,根据客户会员卡卡号有不同结账区域。举个例子,如果你的会员卡卡号是偶数,去电器区附近的结账台,否则就去食品区附近的结账台。
  • 一旦你到达正确的结账区域,商店员工引领你到一个特别的结账队伍
  • 你购买你的商品

任播(Anycast)

这篇文章讨论的最后一种技术就是任播。首先来看一点背景知识:

大多数网路使用单播。这本质上意味着每台计算机拥有独一无二的 IP 地址。有另一种称为任播的理论。通过任播,一些机器可以使用相同的 IP 地址和路由,并把请求发送到最近的一台机器。我们可以把这种技术和上面所讲的技术结合起来,构建出高可靠性和可用性,能承载巨大通信量的系统。

任播根本上来说是允许互联网为我们处理部分负载均衡。

比喻:

  • 你告诉别人你打算去商店,他们把你带到最近的位置。
  • 街对面有两家彼此分开却又一模一样的商店,你去哪一家完全取决于你的习惯。
  • 一旦你到达了商店,根据客户会员卡卡号有不同结账区域。举个例子,如果你的会员卡卡号是偶数,去电器区附近的结账台,否则就去食品区附近的结账台。
  • 一旦你到达正确的结账区域,商店员工引领你到一个特别的结账队伍
  • 你购买你的商品

杂项

延迟和吞吐量

顺便一提的是,这些技术也可以提升低延迟服务的吞吐量。增加服务数量而不是让每个服务处理更多的通信。这样我们就可以得到低延迟、高吞吐量的系统。

服务器直接返回

在传统负载均衡系统中,请求穿过负载均衡的所有层级,响应也同样穿过它们。降低负载均衡通信量的一个优化点就是服务器直接返回。这意味着服务端的响应不通过负载均衡。如果服务端的响应十分巨大,这点尤其有用。

[翻译]Reddit 的愚人节项目 r/Place 是怎么做出来的

How We Built r/Place

每年的愚人节,我们喜欢创建项目来探索人类大规模的交流互动,而不是做一些恶作剧。今年我们提出了 r/Place,这是一个协作的画板,每个用户每 5 分钟只能修改一个小块。这一限制弱化了个体的重要性,强化了大量用户协作完成复杂创作的必要性。每个小块的变化实时传递给观察者。

许多开发团队(前端、后端、移动端)协作开发这个项目,项目大部分基于 Reddit 已有的技术。这篇文章从技术角度详细描述我们如何完成 r/Place。

且慢。如果你想查看我们的代码,在这里。如果你对构建 r/Place 这一类项目感兴趣,我们欢迎你

需求

定义愚人节项目的需求十分重要,因为它一旦发布即面向所有 Reddit 用户,没有增长过程。如果它一开始并不能完美运作,似乎就不能吸引足够的用户来创作并获得有趣的体验。

  • 画板必须有 1000×1000 个小块,所以它会非常大。
  • 所有客户端必须和当前画板状态同步,并显示一致,否则用户基于不同版本的画板难以协作。
  • 我们必须支持至少 100000 的并发同步用户。
  • 用户每 5 分钟可以修改一个小块,所以我们必须支持平均每 5 分钟 100000 个小块的更新(每秒 333 个更新)。
  • 项目的设计必须遵循这一点,即使 r/Place 流量巨大,也不能影响站点其他功能。
  • 配置必须有足够弹性,应对意外的瓶颈或故障。这意味着画板的大小和小块的使用间隔可以在运行时调节,以防数据量过大或更新过于频繁。
  • API 必须开放和透明,reddit 社区如果对此有兴趣,可以在此之上构建项目(机器人、扩展、数据收集、外部可视化等等)。

后端

实施决策

后端最大的挑战就是保持所有客户端与画板状态同步。我们的解决方案是初始化客户端状态时立刻实时监听小块的变化,然后请求整个画板状态。只要我们在生成画板的时候有实时的小块更改,那么响应返回的整个画板状态就会有几秒的延迟。当客户端接收到整个画板状态,把在等待请求时的小块变化在画板上重演。之后接收到所有小块变化实时绘制在画板上。

为了让这个策略正常实施,我们需要尽可能快的请求到画板的整体状态。我们的初步方案是用单行Cassandra储存整个画板,每个针对整个画板的请求可以读取整行。行中的每列格式如下所示:

(x, y): {‘timestamp’: epochms, ‘author’: user_name, ‘color’: color}

因为画板包含一百万个小块,这意味着我们不得不读取有一百万列的行。在我们的生产集群上这种读取花费 30 秒,慢到无法接受,所以我们不能过度依赖 Cassandra。

我们下一个方案使用 redis 储存整个画板。我们使用 bitfield 处理一百万个 4 位的整型。每个 4 位的整型可以编码 4 位的颜色,横纵(x,y)坐标可以在 bitfield 里用偏移量表示(offset = x + 1000y)。我们可以通过读取整个 bitfield 来获取整个画板的状态。我们可以通过在 bitfield 中更新指定偏移量上的值,来更新单独的小块(不再需要加锁或读/改/写)。我们仍然需要在 Cassandra 中储存所有的细节,让用户可以检查单独的小块,看一看何时何人更改了它。我们也计划用 Cassandra 备份整个画板,以防 redis 失效。从 redis 中读取整个画板不超过 100ms,这已经足够快了。

插图展示了我们如何用 redis 储存 2×2 画板的颜色:

我们非常关心 redis 读取最大带宽。如果很多客户端同时链接或刷新,它们会同时请求整个画板的状态,全部都触发 redis 的读取操作。因为画板是全局共享状态,显而易见的解决方案是使用缓存。我们决定在 CDN 层(Fastly)使用缓存,因为实现简单,并且缓存离客户端更近可以提高响应速度。对整个画板的请求被 Fastly 缓存下来并设置 1 秒的超时时间。我们也添加了 stale-while-revalidate 这个控制缓存的头信息,来应对画板缓存过期导致超过预期的大量请求。Fastly 维护着大约 33 处独立缓存 POPs(接入点),所以我们预期每秒最多有 33 个针对整个画板的请求。

我们使用我们的 websocket 服务 向所有客户端推送更新。我们已经成功地在 reddit live 生产环境中应用过它,来处理超过 100000 的并发用户,比如 live PM notifications 功能或其他特性。wesocket 服务也曾是我们过去愚人节项目的基础,比如 The ButtonRobin 两个项目。对于 r/Place 项目,客户端维护一个 websocket 链接来接收实时的小块变化更新。

API

检索整个画板

请求首先到达 Fastly。如果那里有一份未过期的画板副本,它会立刻返回从而不需要访问 reddit 应用服务器。否则如果缓存未命中或副本过时,reddit 应用会从 redis 中读取整个画板然后返回到 Fastly 中并缓存,并返回给客户端。

reddit 应用测量的请求速率和响应时间:

注意,请求速率从没超过 33 个/秒,说明 Fastly 缓存非常给力,阻止了大量直接访问 reddit 应用的请求。

当请求访问 reddit 应用时,redis 的读取操作非常迅速。

绘制一个小块

绘制一个小块的步骤如下:

  1. 从 Cassandra 读取用户上一次更改小块的时间戳。如果和当前时间间隔比冷却时间(5 分钟)短,拒绝绘制请求,返回给用户一个错误。
  2. 向 redis 和 Cassandra 写入小块详情。
  3. 向 Cassandra 写入用户上一次修改小块的时间戳。
  4. 让 websocket 服务向所有链接的客户端发送新的小块。

Cassandra 的所有读写操作的一致性设置为 QUORUM 级别,来确保强一致性。

我们当然也有竞态条件允许用户一次更改多个小块。在步骤 1-3 中并没有锁,因此批量小块修改的操作通过步骤 1 的检查之后将在步骤 2 中进行修改。看起来一些用户发现了这个漏洞或一些机器脚本不遵守速率限制,所以大概有 15000 个小块被利用这个漏洞进行更改(占全部更改小块的 0.09%)

reddit 应用测量的请求速率和响应时间:

我们经历了更改小块最大速率大概 200/s。这比我们估算的最大速率 333/s 要低(平均每 5 分钟 100000 个用户更改小块)。

获取单个小块详情

直接从 Cassandra 请求单个小块。

reddit 应用测量的请求速率和响应时间:

这个服务端点用的很多。除了客户端频繁的请求之外,有人编写抓取工具每次检索整个画板的一个小块。由于这个服务端点没有在 CDN 缓存,所有请求被 reddit 应用程序处理。

在整个项目中,这些请求的响应时间非常迅速稳定。

Websockets

我们并没有在 websocket 服务中为 r/Place 做单独指标,但是我们可以估计并减去项目开始前后的基本使用量。

websocket 服务总连接数:

r/Place 开始前的基本使用量大概有 20000 个连接,而峰值 100000 个链接,所以高峰期我们大概有 80000 个用户连接到 r/Place。

Websocket 服务带宽:

高峰期 r/Place 的 websocket 服务吞吐量超过 4gbps(24个实例,每个 150 Mbps)

前端:Web和移动端

构建 r/Place 的前端工程涉及到了跨平台开发的众多挑战。我们期望 r/Place 在我们所有主流平台上拥有无缝体验,包括桌面web、移动web、iOS 和 Android。

r/Place 的 UI 需要做三件很重要的事:

  1. 实时展示画板状态。
  2. 让用户和画板交互方便容易
  3. 在我们所有平台上正常运行,包括移动端 app。

UI 的主要焦点集中在了 canvas,并且 Canvas API 完全能胜任要求。我们使用一个 1000 x 1000 的 <canvas> 元素,把每个小块当做一个像素进行绘制。

绘制 canvas

canvas 需要实时展示整个画板的状态。我们需要在页面载入的时候绘制整个画板的状态,然后更新通过 websocket 传输过来的画板状态。通过 CanvasRenderingContext2D 接口,有三种方式更新 canvas 元素。

  1. drawImage() 将一个存在的图像绘制进 canvas。
  2. 通过众多图形绘制的方法来绘制各种形状,比如用 fillRect() 绘制一个有颜色的矩形。
  3. 构造一个 ImageData 对象,然后用 putImageData() 方法将它绘制进 canvas。

第一种选项并不适合我们,因为我们并没有画板的图像格式,还剩下 2、3 选项。用fillRect()方法更新单独的小块非常简洁:当 websocket 通知更新时,只需要在(x,y)位置处绘制一个 1 x 1 的矩形。一般来说这很棒,但并不适合绘制画板的初始状态。putImageData()方法显然更合适,我们可以在 ImageData 对象中定义每个像素的颜色,然后一次性绘制整个 canvas。

绘制画板的初始状态

我们使用putImageData()方法,前提需要将画板状态定义成 Uint8ClampedArray 形式,每个值用 8 位无符号整型表示 0-255 之间的数字。每一个值表示单个颜色通道(红、绿、蓝、alpha),每个像素需要 4 个值组成的数组。一个 2 x 2 的 canvas 需要一个 16 字节的数组,前 4 字节表示 canvas 左上角的像素,最后 4 字节表示右下角像素。

插图展示了 canvas 像素和 Uint8ClampedArray 映射关系:

对于 r/Place 的 canvas,数组大小是四百万字节,也就是 4MB。

在后端,画板状态储存格式是 4 位的 bitfield。每个颜色用 0 到 15 之间的数字表示,这允许我们将 2 像素的颜色信息打包进 1 个字节(1字节=8位)。为了在客户端配合使用,我们需要做 3 件事:

  1. 将二进制数据从我们的 API 拉取到客户端。
  2. “解压”数据
  3. 将 4 位颜色映射成可用的 32 位颜色。

为了拉取二进制数据,我们在支持 Fetch API 的浏览器中使用此 API。在不支持的浏览器中,我们使用 XMLHttpRequest,并把 responseType 设置为 “arraybuffer”

我们从 API 接收到的二进制数据中,每个字节有 2 像素的颜色数据。TypedArray 的构造函数允许操作的最小单位是 1 字节。这在客户端上并不方便使用,所以我们做的第一件事就是“解压”,让数据更容易处理。方式很简洁,我们遍历打包的数据并按照高位低位分割比特位,将它们复制到另一个数组的不同字节中。最后,4 位的颜色值映射成可用的 32 位颜色。

API Response 0x47 0xE9
Unpacked 0x04 0x07 0x0E 0x09
Mapped to 32bit colors 0xFFA7D1FF 0xA06A42FF 0xCF6EE4FF 0x94E044FF

ImageData这种数据结构需要使用putImageData方法,最终结果要求是可读的Uint8ClampedArray格式并且颜色通道字节要按照 RGBA 这种顺序。这意味着我们要做另一遍“解压”,将每个颜色拆分成颜色通道字节并按顺序排列。每个像素要做 4 次操作,这不是很方便,但幸运的是有其他方式。

TypeArray对象们本质上是ArrayBuffer的数组视图,实际上表示二进制数据。它们共同的一点就是多个TypeArray实例可以基于一个ArrayBuffer实例进行读写。我们不必将 4 个值写入 8 位的数组,我们可以直接把单个值写入一个 32 位的数组。使用Uint32Array写入值,我们可以通过更新数组单个索引来轻松更新单个小块颜色。我们唯一需要做的就是把我们的颜色字节逆序储存(ABGR),这样一来使用Uint8ClampedArray读取数据时可以自动把字节填入正确位置。

0 1 2 3
0xFFD1A7FF 0xFF426AA0 0xFFE46ECF 0xFF44E094
255 167 209 255 160 106 66 255 207 110 228 255 148 224 68 255
r g b a r g b a r g b a r g b a

处理 websocket 更新

响应每个像素更新时,用drawRect()方法绘制它们很方便,但这有个缺点:当大量更新在同一时间来到,会影响浏览器性能。我们知道画板状态更新十分频繁,所以我们需要处理这个问题。

我们希望在一个时间点前后的 websocket 更新能够批量绘制一次,而不是每次 websocket 更新来到就立刻重新绘制 canvas。我们做了以下两点改变:

  1. 因为我们发现了使用putImageData()一次更新多个像素这条明路,所以我们不再使用drawRect()
  2. 我们把绘制 canvas 操作放到requestAnimationFrame循环中。

把绘制移到动作循环中,我们可以及时将 websocket 更新写入ArrayBuffer,然后延迟绘制。每一帧(大概 16ms)间的 websocket 更新会再一次绘制中批量执行。因为我们使用requestAnimationFrame,这意味着每次绘制时间不能太长(不超过 16ms),只有 canvas 的刷新速率受影响(而不是拖慢整个浏览器)。

Canvas 的交互

还有非常重要的一点,canvas 需要方便用户的交互。用户与 canvas 核心交互方式是更改上面的小块。在 100% 缩放下,精确地选择绘制单个像素很不方便,而且容易出错。所以我们需要放大显示(放大很多)。我们也需要方便的平移 canvas,因为在多数浏览器上它太大了(尤其是放大后)。

视角缩放

用户只能每五分钟绘制一次小块,所以选错小块非常令人不爽。我们需要把 canvas 放大到每个小块都成为一个相当大的目标。这在触摸设备上尤其重要。我们使用 40x 的放大比例,给每个小块 40 x 40 的目标区域。为了应用缩放,我们把<canvas>元素包裹进一个<div>,并给 div 设置 CSS 属性transform: scale(40, 40)。这样一来,小块的布置变得非常方便,但整个画板的显示并不理想(尤其是在小屏幕上),所以我们混合使用两种缩放级别:40x 用于绘制,4x 用于显示。

使用 CSS 来放大 canvas 使得绘制画板的代码和缩放代码相分离,但不巧这种方式也带来一些问题。当放大一个图片(或 canvas),浏览器默认使用“平滑”算法处理图片。这适用于一些场景,但也彻底毁灭了像素艺术并把它变得混乱模糊。好消息是有另一个 CSS image-rendering 允许我们命令浏览器不这么做。坏消息并不是所有浏览器完全支持这个属性。

坏消息,变得模糊:

我们需要在那些浏览器上用其他方式放大 canvas。我之前提到过绘制 canvas 有三种方式。其中第一个是drawImage()方法,它可以把一个存在的图像或另一个 canvas 绘制进一个 canvas。它也支持在绘制的时候放大或缩小图像,虽然放大的时候会和在 CSS 中放大一样出现模糊问题,但是可以通过关闭 CanvasRenderingContext2D.imageSmoothingEnabled 标识,这种跨浏览器兼容性的方式来解决。

所以修复模糊 canvas 问题的答案就是在渲染过程中增加额外一步。我们引入了另一个<canvas>元素,它大小位置适应于容器元素(比如画板的可见区域)。每次重新绘制 canvas 后,我们使用drawImage()把它的一部分绘制到新的、有合适缩放比例的 canvas。因为额外的步骤给渲染过程带来微小的开销,所以我们只在不支持image-renderingCSS 属性的浏览器上这样做。

视角平移

canvas 是一个相当大的图像,尤其是放大之后,所以我们需要提供一些方式操作它。为了调整 canvas 在屏幕上的位置,我们采取和解决缩放问题一样的方式:我们将<canvas>包裹进另一个<div>,并在它上面应用 CSS 属性transform: translate(x, y)。使用单独的 div 使得应用在 canvas 上的变换操作更容易控制,这对于防止视角在缩放时产生移动非常重要。

我们最后支持多种方式调整视角位置,包括:

  • 点击拖拽
  • 点击移动
  • 键盘导航

每种操作需要一点不同的实现方式。

点击拖拽

最基本的导航方式就是点击拖拽(或触摸拖拽)。我们保存了mousedown事件的 x、y 坐标。对于每次mousemove事件,我们计算鼠标相对于起点的偏移量,然后把偏移量加到已存在的 canvas 偏移量中。视角位置立刻改变,让人感觉这种到导航方式很灵敏。

点击移动

我们也支持点击一个小块,使得小块定位到屏幕中心。为了实现这个功能,我们需要跟踪mousedownmouseup事件,为了区别“点击”和“拖动”。如果鼠标移动距离达不到“拖动”的标准,我们会根据鼠标位置和屏幕中心的距离来调整视角位置。和点击拖动不同,视角位置的更新使用了缓动函数(easing function)。我们没有立刻设定新的位置,而是把它保存成“目标”位置。在动画循环中(每次绘制 canvas 的循环),我们使用缓动函数移动当前视角逐渐接近目标。这避免了视角移动太突然。

键盘导航

我们也支持键盘导航,既可以使用 WASD 键也可以使用方向键。四个键控制内置 移动向量。没有按键按下时,向量默认是 (0, 0),每个按键按下时会增加或减少向量的 x 或 y 轴 1 个单位。举个例子,按下“右”和“上”键会把移动向量设置成 (1,-1)。这个移动向量随后应用在动画循环中,来移动视角。

在动画循环中,移动速度是基于当前缩放级别而计算出来的,公式如下:

movementSpeed = maxZoom / currentZoom * speedMultiplier

在缩小状态下,键盘导航移动速度更快,这样显得更自然。

移动向量单位化并乘以移动速度,然后应用到当前视角位置。我们用单位向量来确保对角线移动和正交移动拥有相同速度,这也显得更自然。最后我们对移动向量自身的变化也使用了缓动函数。这使得移动方向和速度变化的更平滑,视角变得流畅生动。

移动应用支持

在 iOS 和 Android 的移动应用嵌入 canvas 过程中,我们遇到一些挑战。首先,我们需要认证用户,然后用户才能更改小块。和基于 session 的 web 认证不同,移动应用中我们使用 OAuth。这意味着应用需要为 webview 提供当前登录用户的访问令牌。最安全的方式就是用 JavaScript 在应用调用 webview 时注入 oauth 认证头信息(这也允许我们设置其他需要的头信息)。问题就简化为在每个 api 调用中传递认证头信息了。

r.place.injectHeaders({‘Authorization’: ‘Bearer <access token>’});

在 iOS 端,当你可以更改 canvas 中的下一个小块时,我们实现了消息提醒功能。因为小块的变更完全在 webview 中,所以我们需要实现向原生应用的回调。辛运的是在 iOS 8 及以上版本中只需要一个简单的 JavaScript 调用:

webkit.messageHandlers.tilePlacedHandler.postMessage(this.cooldown / 1000);

应用中的委派方法根据传入的冷却计时器,会随后调度发送一条通知。

我们学到了什么

你总会疏漏一些事

我们完美计划好了任何事情,我们知道上线时,没有什么可能出错的地方。我们对前端和后端分别进行了负载测试,我们不可能再遇到其他错误。

真的吗?

上线过程很顺利。经历了一个黎明,r/Place 人气迅速上升,我们 websocket 实例的链接数量和通信量也随之增加:

并没有什么惊喜,所有和我们预期的一样。奇怪的是,我们怀疑限制了这些服务器实例的网络带宽,因为我们预计会有更大的流量。查看了一下 CPU 的实例情况,却显示出一幅不同的图片:

服务器实例是 8 核的,所以很明显它们快到上限了。为什么它们突然表现的如此不同?我们将原因归结于 r/Place 的工作负载类型不同于以往项目。毕竟这里有很多微小的消息,我们一般发送大型消息,比如直播帖子的更新和通知。我们也没有处理过大量用户接收相同消息的情况,所以有很多地方都不同。

这没什么大不了,我们预计只需要调用和测量它一天而已。待命的运维数量是服务器实例的两倍,而且他们两耳不闻窗外事,一心只顾服务器。

然后,发生了这个:

这幅图看上去可能并没什么,但事实上这是我们生产环境的 Rabbit MQ 实例,不仅处理 websocket 消息,也处理 reddit.com 所有底层的依赖项。这不容乐观,一点都不。

经过了各种调查、束手无策和升级实例,我们把问题锁定在管理接口。它总是有点慢,随后我们意识到,我们为了获取项目状态用 rabbit diamond collector 会频繁查询接口。我们认为创建新的 websocket 实例时创建了额外的 exchange (RabbitMq 中概念),再加上这些 exchange 的消息吞吐量,导致了管理界面在查询和记录时,rabbit 卡住了。我们把它关掉,情况好多了。

但我们不想在一片黑暗之中(关掉了状态显示程序),所以我们迅速做了一个手工艺术品——监控脚本,帮助我们观察整个项目:

$ cat s****y_diamond.sh

#!/bin/bash

/usr/sbin/rabbitmqctl list_queues | /usr/bin/awk '$2~/[0-9]/{print "servers.foo.bar.rabbit.rabbitmq.queues." $1 ".messages " $2 " " systime()}' | /bin/grep -v 'amq.gen' | /bin/nc 10.1.2.3 2013

如果你好奇为什么我们不断调整修改像素(小块)的超时时间(冷却时间),那么现在你就知道了。我们试着减轻服务器压力以便整个项目顺利运行。这也是为什么在某个时间段,一些像素的呈现花费较长时间。

所以不幸的是,你当时坚信如下的信息:

10K upvotes to reduce the cooldown even further! ADMIN APPROVED

尽管调整完看 r/Place/new 版块很有意思,但调整完全出于技术原因:

或许这也是调整的部分动机。

机器人终归是机器人

我们在项目的末期经历了一点小波折。一般来说,我们经常遇到的问题之一便是客户端重试行为。众多客户端在遇到问题时便不停地重试。这意味着站点一旦有点小问题,对于那些没有对故障进行回退编程的一些客户端,很容易引发重试风暴。

当我们关闭 r/Place 时,很多机器人端点请求时返回非 200 的响应码。像这样的代码不是十分友好。值得庆幸的是,在 Fastly 层很容易拦截它们。

创造点其他东西

如果没有庞大团队的协作,项目不会这么成功。我们很感谢 u/gooeyblob、u/egonkasper、u/eggplanticarus、u/spladug、u/thephilthe、u/d3fect 等人对 r/Place 团队的贡献,让愚人节的尝试变成现实。

正如我们之前提到的,如果你对为百万用户创造特殊体验感兴趣,看一看我们的招聘页

从 Date 和 Timestamp 看 Java 继承特性和 equals() 方法约定间的冲突

Java 的继承是面向对象最显著的一个特性。Date 和 Timestamp 是 Java 中的两个和时间有关的类。Timestamp 继承自 Date。

equals() 方法是 Java 中最常用的方法之一,在 Object 中定义,任何对象都有的方法,我们在自定义类的时候,一般都会重写此方法。

equals() 方法的约定

首先讲一讲重写 equals() 方法时要注意的约定

  1. 自反性(reflexive),对于任何非 null 的引用值 x,x.equals(x)必须返回true。
  2. 对称性(symmetric),对于任何非 null 的引用值 x 和 y,当且仅当y.equals(x)返回true时,x.equals(y)必须返回true。
  3. 传递性(transitive),对于任何非 null 的引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 也返回 true,那么 x.equals(z) 也必须返回 true。
  4. 一致性(consistent),对于任何非 null 的引用值 x 和 y,只要 equals 的比较操作在对象中所有的信息没有被修改,多次调用 x.equals(y) 就会一致地返回 true,或者一致地返回 false。
  5. 对于任意非 null 的引用值 x,x.equals(null) 必须返回false。

这几条简单易懂。一般我们重写 equals() 方法会先判断类型是否一致,然后根据类中的成员域来判断。比如下面这个简化的 Date 类。

public class Date{
    private transient long fastTime;
    public Date(long date) {
        fastTime = date;
    }
    public long getTime() {
        return fastTime;
    }
    public boolean equals(Object obj) {
        return obj instanceof Date && getTime() == ((Date) obj).getTime();
    }
}

equals 方法首先判断是否是 Date 类型,然后判断 fastTime 字段值是否一致。

继承

我们再来看一下简化的 Timestamp 类

public class Timestamp extends Date {
    private int nanos;
    public Timestamp(long time) {
        super((time/1000)*1000);
        nanos = (int)((time%1000) * 1000000);
    }
    public boolean equals(Object ts) {
        if (ts instanceof Timestamp) {
            if (super.equals(ts)) {
                if  (nanos == ts.nanos) {
                    return true;
                } 
            } 
        } 
        return false;
    }
}

Timestamp 在 Date 的基础上增加了一个 nanos 字段。所以它的 equals 方法首先判断是否是 Timestamp 类型,然后调用父类 equals 方法判断 fastTime 字段,最后判断 nanos 字段。

我们看下面一段代码。

继承破坏约定

Date date = new Date(1000);
Timestamp timestamp1 = new Timestamp(1000);
timestamp1.setNanos(1);
Timestamp timestamp2 = new Timestamp(1000);
timestamp2.setNanos(2);
System.out.println(date.equals(timestamp1));//true
System.out.println(date.equals(timestamp2));//true
System.out.println(timestamp1.equals(date));//false
System.out.println(timestamp1.equals(timestamp2));//false

很明显,正是因为继承关系,导致 equals 方法的对称性和传递性遭到破坏。事实上,Java 源码中 Timestamp 的注释里已经提到了这个问题。

Note: This type is a composite of a java.util.Date and a separate nanoseconds value. Only integral seconds are stored in the java.util.Date component. The fractional seconds – the nanos – are separate. The Timestamp.equals(Object) method never returns true when passed an object that isn’t an instance of java.sql.Timestamp, because the nanos component of a date is unknown. As a result, the Timestamp.equals(Object) method is not symmetric with respect to the java.util.Date.equals(Object) method. Also, the hashCode method uses the underlying java.util.Date implementation and therefore does not include nanos in its computation.
Due to the differences between the Timestamp class and the java.util.Date class mentioned above, it is recommended that code not view Timestamp values generically as an instance of java.util.Date. The inheritance relationship between Timestamp and java.util.Date really denotes implementation inheritance, and not type inheritance.

重点在最后一句。不建议把 Timestamp 实例当做 Date 的实例。它们这种继承关系只是实现层面上的继承,并非类型层面上的继承。

当我们感觉到问题的时候,就应该开始思考如何解决了。

getClass()

首先想到的就是 instanceof 来判断类型时无法识别继承关系,而用 getClass() 方法可以准确获知类型。
我们用这种思路实现一个 equals() 方法。

public boolean equals(Object obj) {
     if(obj == null || obj.getClass() != this.getClass()){
        return false;
     }
     //other conditions
}

这个 equals 能够很刻薄地判断两个对象是否相等,并能够严格遵守 equals 的各项约定。但是它却违背了面向对象思想的一项很重要的原则,里氏替换原则。

里氏替换原则(Liskov Substitution Principle LSP)面向对象设计的基本原则之一。 里氏替换原则中说,任何基类可以出现的地方,子类一定可以出现。 LSP是继承复用的基石,只有当衍生类可以替换掉基类,软件单位的功能不受到影响时,基类才能真正被复用,而衍生类也能够在基类的基础上增加新的行为。

这种 equals 方法显然使得子类替换父类受影响,这种行为和继承的思想理念相违背。

用组合而不是继承

还有另一种方法,便是放弃继承。
再设计模式中,常常被人提及的就是“组合优先于继承”
上面例子中我们可以把 Date 当做 Timestamp 的一个域,就解决了 equals 的问题。

public class Timestamp{
    private int nanos;
    private Date date;
    public Timestamp(long time) {
        date = new Date(time);
        nanos = (int)((time%1000) * 1000000);
    }
    public boolean equals(Object ts) {
        if (ts instanceof Timestamp) {
            if  (nanos == ((Timestamp)ts).nanos && date.equals(((Timestamp)ts).date)) {
                return true;
            } 
        } else {
            return false;
        }
    }
}

总结

我们并没有完美的解决方案调和 Java 的继承特性和 equals 方法约定,它们之间的冲突依然还在。

参考《Effective Java》