ARTS(23)

1 Algorithm

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

这个问题只要需要考虑数字反转后,Int32 类型的数据是否会出现 overflow,因此需要单独判断。

func reverse(x int) int {
    min, max := bound()
    if x == 0 {
        return x
    }
    if x > 0 {
        digits := make([]int, 0)
        for x > 0 {
            digits = append(digits, x % 10)
            x = x / 10
        }
        result := 0
        for i :=0; i < len(digits); i++ {
            result = result * 10 + digits[i]
            if result > int(max) {
                return 0
            }
        }
        return result
    }else{
        digits := make([]int, 0)
        for x < 0 {
            digits = append(digits, x % 10)
            x = x / 10
        }
        result := 0
        for i :=0; i < len(digits); i++ {
            result = result * (10) + digits[i]
            if result < int(min) {
                return 0
            }
        }
        return result 
    }
}

func bound() (int32, int32) {
    a := ^uint32(0)
    max := a >> 1
    min := - max - 1
    return int32(min), int32(max)
}

2 Review

Scaling webapps for newbs & non-techies

拓展Web应用程序
这是一篇关于拓展原则的基本总结:从单个服务到一个能够服务上百万用户的网络应用程序。它主要对于一些新手而言的,如果你已经部署过很多这样类似的服务,这篇文章不适合你。

拓展
假设你已经开发完成你的网站,一个在线的购物网站,一个社交网络等等。你将它部署在网络上,事情好像一切如果你预期一样。每天有上百个访问者进入的你的网站,每个相应请求都非常快,每一个订单都能够快速的被处理。
但是事情发生的改变,你的网站变得非常成功。
越来越多的用户像潮水一样涌过来,每一分每一秒都有成千上万的用户。现在对于你的生意而言的坏消息的是:你的基础设施需要拓展了,也就意味着它能够需要做到如下几点

  • 能够同时服务多个用户
  • 高可用并且不会宕机
  • 服务全球的用户

如何拓展
在几年之前,这篇文章可能还会讨论一些 垂直水平 拓展。从本质上来讲 垂直 拓展就是在一台性能更高的机器上运行同样的事情,而 水平 拓展也就意味着在不同的处理器上同时运行。
如今没有人再会提起 垂直 扩展,理由也很简单

  • 计算机拥有更高的能力费用非常高
  • 计算机更高的能力将取决于硬件的限制
  • 多核 CPU 意味着在同一个计算机上并行执行,那为什么不一开始就并行执行呢?

所以只有 水平 拓展越来越受到欢迎,那么它需要哪些步骤?

2.1 单个服务和数据库


这个是你刚刚开始的后端架构,一个应用程序服务器来运行业务逻辑,用一个数据库保存所需的数据,但是这个对于大需求的架构是不友好的。

2.2 增加反向代理


为了适合更大的规模的拓展,首先增加了一个反向代理。把它想象成酒店的前台。你当然可以直接告诉客户去哪个房间,但是想要知道客户是否有权限进入特定的房间,也需要确定该房间是否的确存在。你需要一个友好的发声,来告诉客人如何去处理这些事情。这些都是反向代理所做的工作。通常这些应该是我们的服务向外部网络发起请求,但是这次请求是从外部网络向我们的服务发送的,所以我们称之为反向代理。
这些代理需要完成以下的任务

  • 健康检查:确保我们的事实的服务仍然还在而且还在运行着
  • 路由: 将这些请求发送给正确的终端
  • 权限检查: 确保用户的确拥有访问服务的权限
  • 防火墙:确保用户只能够访问允许的的部分网络

2.3 负载均衡器


大部分 反向代理 还有其他的功能,他们可以充当负载均衡器。负载均衡器是一个非常简单的概念:想象一下假设在一分钟内有 100 用户正在在你的在线购物网站上准备付款。不幸地是你的付款系统服务只能同时处理50付款请求。那怎么解决呢?最简单的就是同时运行两个付款服务。
负载均衡器的工作就是将受到的付款请求分隔开到两个服务中。第一个请求去左边的付款服务,第二个请求去右边的付款服务,第三个请求再一次去左边的付款服务,依次类推。
但是如果你有 500 个用户需要同时进行付款。确切的说是你将你的付款服务扩展 10 份让负载均衡器分发这些到来的请求。

2.4 数据库增长


使用负载均衡器可以允许你将负载分配到不同的服务器上,但是你能定位到问题吗?当我们使用成百上千的服务来处理我们的请求,他们都将对同一个数据库进行数据存储和读取。
所有我们能不能将数据库按照同样的方式进行扩展?不幸的是这样是不可以的,原因在于一致性。系统的所有的子部分都要对数据进行一致性保证。数据不一致性将会导致非常严重的问题,比如订单被执行多次,两笔 90$ 的扣款户还剩 100$ 账户中扣除。所以我们该如何在数据库增长的时候也保证一致性?
我们可以将数据库拆分成过个部分,其中一个分部只负责数据的存储,另一部分负责数据的读取。这种方式也叫做主/从配置也或者叫做读写配置。这个假设了服务读的几率比服务写数据多得多。好的消息是,这个解决方案保证了数据的一致性因为只有一个实例进行写操作,数据流也只有一个方向:从写到读。这个解决方案的缺陷也是只有一个实例进行写操作,对于中小型的 web 项目足够了,但是对于像 Facebook 这样的项目不能奏效,在下面我们将会继续讨论如何将我们的数据库进行拓展。

2.5 微服务


到目前为止,我们涉及到的都是单个服务处理全部事情:处理付款,订单,存货清单、服务网站和用户账户管理等等。
这个并不是坏事情,单个服务意味着低的复杂度而且减低开发的难度。但是随着规模的扩展,事情开始变得复杂起来而且也不高效。

  • 服务的不同的部分使用不同的内容。对于每个用户登录而言,可能需要上百个页面需要处理,而且这些往往来自同一个服务
  • 随着我们的开发团队增长,越来越多的开发者在同一个服务上工作。这也就意味着相互影响越来越大
  • 拥有一个单个服务意味着所有的工作都需要即是完成,尽管我们需要新的版本。这对我们的依赖关系对服务的升级带来巨大的影响,比如一个团队很快的完成的功能,但是别的团队才完成了工作的一半。

面对这个挑战的解决方案的是调整开发团队的架构图:微服务。这个观点非常简单,就是按照将服务的功能拆分成更小的单元,单独部署这些服务,这些微服务之间相互交流。这个有很多好处:

  • 每一个服务都可以单独扩展,可以很容易适应需求
  • 开发团队可以独立工作,对自己的微服务的生命周期负责即可
  • 每个微服务可以使用自己的资源,比如拥有自己的数据库来避免上述的的问题

2.6 缓存和CDN


怎讲让工作更有效率呢?当然是不进行工作!
大部分 web 应用程序包含了很多静态资源,这些资源都不会发生改变的:比如图片,JS 和 CSS 文件。特定产品的预渲染的的页面等等。我们可以使用缓存而不是每次请求过来都让服务重新计算这些。
和缓存常常一起提及的概念叫做 内容分发网络 或者叫 CDN 。它是分布在全球的巨大的缓存数组。他们可以允许我们将我们的内容发送给用户,而且这些内容在物理空间里用户比我们服务还要近,这样我们需要从全球加载我们的资源。

2.7 消息队列


不知道你是否去过游乐场?是否自己走到售票窗口来购票?如果没有,假设你在一个队列中排队。政府机构、邮局和游乐场入口都是 sub-capacity parallelism 概念很好实例。是的,他们是并行的,多个售票窗口同时在售票,而且从来没有看到有足够的窗口来同时满足每一个人立即处理,而是从队列开始的。
在大型的 web 应用程序中,也保留同样的概念。每分钟都有成千上万的图片上传到 Instagram, FacebookCo 网站中。他们每一个都需要处理,调整大小,分析和打标签等等。这些都是非常耗时的操作,与其让用户等待所有操作完成,服务端在接受到图片后只做了如下三件事

  • 它存储最原始的、未处理的图片
  • 想上传者确认上传完毕。
  • 表明这些图片需要的处理

需要处理的内容被不同的服务所订阅,每一个开始自己任务,每完成一个完成 to-do 中的一项。系统将需要完成的内容的标签称之为 消息队列。使用这些队列有很多好处和优势:

  • 它将任务和处理者进行了解耦。有时需要很多图片需要处理,有时候只需要一点。有时候需要很多处理者,有时候只需要一两个即可。通过简单地将任务积压而且直接处理他们我们可以确保我们系统的响应能力而且没有任何任务丢失。
  • 它允许拓展我们的需求。一开始就启动很多处理器很耗时,所以当很多用户开始上传图片的时候,这个就非常迟了。通过将任务添加到消息队列中可以延迟我们额外计算资源的需求。

好了,如果你跟到这里,那么你的系统可以服务很大的流量了。但是如果你想让你的服务支撑更大的。下面这些选项就可以忙你。

2.8 分片


什么是分片?

分片是将应用程序并行执行的技术,通过将它们划分成一个单元,每一个只负责特定的键或者命名空间。

那么究竟是意味着是什么?事实上非常简单:比如 Facebook 想要服务二百万的用户?那么将你的架构划分成26个小型 Facebook。每一个用来服务的用户按照字母表的顺序,比如 Aaron Abrahams,你将会被分配到 Z, 因为你叫 Zacharias Zuckerbereg
分片没有必要按照字母,也可以按照任何要素进行划分:地区、使用频率等等。你也可以将你的数据库、服务或者任何内容进行分片操作。

2.9 负载均衡器的负载均衡器


目前为止,我们只使用了一个负载均衡器。哪怕一开始你就购买了性能很强大的负载均衡器的硬件,但是针对大量的请求仍然还是不够的。
幸运的是,在全球范围内,有一个去中心化的稳定的负载均衡器的就出现了,而且都是免费的。这一层叫做 DNS, 它用来将注册的域名比如 arcentry.com 和 IP地址关联起来。这个注册允许多个IP地址和同一个域名关联起来,完成了不同的负载均衡。

3 Tips

3.1 内存使用

  • VSS- Virtual Set Size 虚拟耗用内存(包含共享库占用的内存)
  • RSS- Resident Set Size 实际使用物理内存(包含共享库占用的内存)
  • PSS- Proportional Set Size 实际使用的物理内存(比例分配共享库占用的内存)
  • USS- Unique Set Size 进程独自占用的物理内存(不包含共享库占用的内存)

3.2 孤儿进程和僵尸进程

  • 孤儿进程

一个父进程退出,而它的一个或多个子进程还在运行,那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养,并由init进程对它们完成状态收集工作。

  • 僵尸进程

一个进程使用fork创建子进程,如果子进程退出,而父进程并没有调用wait或waitpid获取子进程的状态信息,那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。

3.3 取余

整数的除法取整有三种方式

  • 向上取整,也叫 ceiling 取整,比如 17 / 10 = 2, 5 / 2= 3,-9 / 4 = -2
  • 向下取整,也叫 floor 取整, 比如 17 / 10 = 15 / 2 = 2, -9 / 4 = -3
  • 向零取整,也叫 truncate 取整, 比如 17 / 10 = 1, 5 / 2 =2, -9 / 4 = -2

既然已经知道如何除法取整,那么模 $r$:
$$r = a - (a / b) \times b$$
不同的编程语言采用不同的除法取整方式

  • C/JAVA 语言采用 truncate 方式
  • Python 语言采用 Floor 方式

4 Share

在开发过程中出现任何问题,一定要查看最原始的日志。

Comments
Write a Comment