参考：

https://blog.csdn.net/u013007900/article/details/79008993

https://blog.csdn.net/u013007900/article/details/79049187

技术面试的系统设计题（一）

本文为课程翻译和学习笔记，课程地址System Design for Tech Interviews。
关于课后题，这儿就不公布答案了。应该还是比较简单的。

二八定律是一个非常重要的准则。

• 系统每个月需要处理的数据是100×106">100×106">100×106100×106
  
  • 推特一个月产生15×109">15×10915×109的推文
  • 每个月需要进行缩短的新URL只占了10%，总计1.5×109">1.5×1091.5×109
  • TOP3以下的缩短URL网站只处理了20%的数据，也就是300×106">300×106300×106的数据
  • 我们的系统，需要处理100×106">100×106100×106的数据
  • 5年之内会产生6×109">6×109">6×1096×109条URL，占用空间3TB；hash表占用空间36GB
    
    • 每个缩短的URL占用500 bytes和6 bytes的hash

• 系统需要处理的请求是每个月1×109">1×1091×109

  • 考虑URL的寿命，平均为1~2周，这儿可以假设10天
  • 每天有一个请求
  • 100 mln×10 days×1 click/day=1 bln">100 mln×10 days×1 click/day=1 bln100 mln×10 days×1 click/day=1 bln
  • 请求的分类：10%是进行缩短，90%是进行重定向
    
    • 每秒有400+的请求，40是进行缩短，360是进行重定向

• 每秒需要写入的新数据：40×(500+6)=20 K">40×(500+6)=20 K40×(500+6)=20 K

• 每秒需要读取的数据：360×506=180 K">360×506=180 K360×506=180 K

关于这些限制的估计，人为主观因素有较大影响，不过在面试的时候除非估计得特别离谱，面试官一般不太会纠结于这方面，基本按照二八原则来估计就行了。

具体的估算过程见下图。

md5

结合随机数，并将结果转化为base62编码，base62编码非常适用于tiny URL

取前6 bytes

hashed_ulr = convert_to_base62(md5(origin_value+random_salt))[:6]

An Unorthodox Approach To Database Design : The Coming Of The Shard

视频地址
课件地址

比较建议看一看视频，视频里面讲的非常杂乱，感觉没有什么逻辑，所以我整理的也是乱七八糟。他说的东西也是非常基础的，但是巩固一下也是很不错的。

具体的一些技术方面的大致情况可以看看这篇博文，里面讲到了Web服务器从基础到复杂的扩展过程。比这个课更有逻辑。

垂直扩展

对于一台服务器使用更多的更好的硬件，如下资源

• CPU
  
  • cores, L2 Cache, …
• Disk
  
  • 接口：PATA, SATA, SAS, …
  • RAID
• RAM

限制：没有那么多物理资源

水平扩展

不同于垂直扩展那样选用最贵最好的服务器，水平扩展接受了便宜的硬件设施，但是用了更多的便宜且更慢的服务器实现了扩展。也就是，使用了大规模的集群分布式。

负载均衡

通过Load Balancer将服务集群黑盒化，那么对于外界而言，他们始终以为访问的是一个服务器。

Load Balancer具有一个公开的IP地址，而后端服务器不需要公开的IP地址，而是用内网IP地址。类似NAT协议那样。

关于负载均衡的算法由很多，比如，Round Robin算法（一种以轮询的方式依次将一个域名解析到多个IP地址的调度不同服务器的计算方法。）

开源的DNS系统BIND对于同样的域名请求，可能会返回不同的IP地址。

• 软件
  
  • ELB
  • HAProxy
  • LVS
• 硬件
  
  • Barracuda
  • Cisco
  • Citrix
  • F5

共享存储

RR可能会导致服务器1总是受到请求，从而导致堵塞。即，因为负载均衡算法的缺陷，导致负载均衡效果不理想。

sticky session问题：如果你登陆一个网址好多次，你的cookies和session等信息会分布在不同的机器上。那么如果你的请求被分发到一个新的机器上，那么这些就不复存在了，你必须重新登陆，重新添加购物车，这明显是不行的。

为了让负载均衡器能够明白每一个Server所处的状态，为了让所有Server的信息都保持一致，我们会使用共享存储的设计。

但是同样的共享存储也是有一定缺陷的：

1. 如果所有系统都使用一块硬盘，如果这块硬盘挂了，那么所有的服务器都不能使用了。
2. 如果按照功能进行分机和存储相应的数据，如，处理用户登录请求和用户cookies的记录，视频媒体等存储。如果最关键的那台服务器宕机了，整个服务也就都没有用了。

于是，我们可以使用增加硬盘数量实现备份。比如，我们同时用两块硬盘存储同一份数据的两个副本，这样虽然增加了一些overhead，但是能够实现备份。（关于这点还有很多论文去解释和设计相应的系统，比如raft一致性协议等等）。

同时我们也可以使用两块硬盘存储一份数据的不同部分，当一块在写的时候，我们可以写另一块。并行地运行写入程序。

Cacheing

HTML文件

简单地将HTML存储下来，或者以HTML模板的形式存储一些不怎么需要更改的内容。

SQL Cache

查询的缓存，可见其他数据库的设计情况。

Memcached

其他第三方内存数据库，用于缓存。还有比如，reids等等。

但是也需要一些别的协议或者机制来维护这类的缓存，如，同步问题， 垃圾回收

主从模式

多主机模式

负载均衡+复制

有些类似数据库读写分离或者数据库的备份

数据分块存储

Capistrano解决了。这需要一些学习，特别是如果你的Ruby不够熟练中。

在将您的会话“外包”并从所有服务器都能访问的代码块提供相同的代码后，就可以从这些服务器之一（AWS称之为AMI - Amazon Machine Image）创建映像文件。将此AMI用作“超级克隆”所有的新实例都基于。每当你开始一个新的实例/克隆，只要做一个最新的代码的初始部署就足够了！

数据库

现在，所需的更改比仅添加更多克隆的服务器更为激进，甚至可能需要一些勇气。你可以选择2个路径：

路径＃1：是坚持使用MySQL，并保持野蛮的运行。聘请数据库管理员告诉他做主从复制和读写分离（从从机读取，写入主机），并通过添加RAM来升级主服务器。在几个月的时间里，你的数据库管理员会想出“分片”，“反规范化”和“SQL调优”这样的词汇，并且会在接下来的几周里担心必要的加班。那时，每一个新的动作来保持你的数据库运行将比以前更昂贵和耗时。如果您选择了Path＃2，而您的数据集仍然很小并且易于迁移，那么您可能会变得更好。

路径＃2：从头开始正确反规范化，并且在任何数据库查询中不再包含连接。你可以使用MySQL，像NoSQL数据库一样使用它，或者你可以切换到一个更好，更容易扩展的NoSQL数据库，比如MongoDB或者CouchDB。现在需要在应用程序代码中完成联接。越早执行此步骤，您将来必须更改的代码越少。但即使您成功切换到最新，最好的NoSQL数据库，并让您的应用程序执行数据集连接，您的数据库请求很快也会变得越来越慢。你将需要引入一个缓存。（关于这一点，我不是很赞同，还是要根据应用场景分类，不是所有的场景适合使用NoSQL的，而且不同的NoSQL适用的地方也不同，HBase和Redis就很不一样）

缓存

对于“缓存”，这儿指像Memcached或Redis这样的内存缓存（或者说，内存数据库）。不要执行基于硬盘文件的缓存，它会使服务器的克隆和自动扩展付出高昂的代价。

内存缓存通常是一个简单的KV键值存储，它应该作为应用程序和数据存储之间的缓冲层。无论何时您的应用程序必须读取数据，它应该首先尝试从缓存中检索数据。只有当它不在缓存中时，才会尝试从主数据源获取数据。

缓存将每个数据集保存在RAM中，所以能够尽可能快地处理请求。例如，Redis可以在标准服务器上托管时每秒执行几十万次读取操作。还写操作，特别是增量。

有两种缓存数据的模式。一个旧的和一个新的：

＃1 - 缓存的数据库查询

这仍然是最常用的缓存模式。每当您对数据库执行查询时，都会将结果数据集存储在缓存中。key是我们查询的hash值。下次运行查询时，首先检查它是否已经在缓存中。

这种模式有几个问题。主要问题是数据到期。缓存复杂查询时，很难删除缓存的结果。当一条数据发生变化时（例如一个表格单元格），您需要删除可能包含该表格单元格的所有缓存查询。这样将会非常混乱。

＃2 - 缓存的对象

这是我强烈的建议，我总是喜欢这种模式。一般来说，将数据视为一个对象，就像你已经在你的代码（类，实例等）中做的那样。让您的类从您的数据库中组合一个数据集，然后将该类的完整实例或组合数据集存储在缓存中。

听起来很理论，我知道，但看看你通常的代码。例如，您有一个名为“Product”的类，它有一个名为“data”的属性。这是包含产品的价格，文本，图片和客户评论的数组。属性“data”由类中的几个方法填充，执行多个难以缓存的数据库请求，因为许多事情相互关联。

现在，请执行以下操作：当您的类完成数据数组的“组装”时，直接将数据数组或更好的类的完整实例存储在缓存中！这样，只要有事情发生变化，就可以轻松地摆脱对象，并使代码的整体操作更加快速和合理。

最好的部分是：它使异步处理成为可能！应用程序只访问最新的缓存对象，几乎从不接触数据库！

缓存对象的一些想法：

1. 用户会话（user sessions）从不使用数据库
2. 完全呈现的博客文章
3. 活动流
4. 用户< - >朋友关系

一般来说，我更喜欢Redis的Memcached，因为我喜欢Redis的额外数据库特性，如持久性和内置的数据结构，如列表和集合。有了Redis和一个聪明的钥匙，你甚至有可能完全摆脱一个数据库。但是如果你只是需要缓存，就可以使用Memcached。

异步（Asynchronism）

请想象一下，你想在你最喜欢的面包店买面包。所以你走进面包店，点了一个面包，但那里没有面包！相反，在你点了的两个小时之后，你的面包才能被做好。这很烦人，不是吗？

为了避免这样的“请稍等” - 情况，需要完成异步。面包店有什么好处，也许对你的网络服务或网络应用也有好处。

一般来说，有两种方法/范例可以完成不同步。

异步＃1

让我们想想前面的面包店例子。异步处理的第一种方式是“晚上烘烤面包，早上卖”的方式。没有等待时间。提到一个网络应用程序，这意味着提前完成耗时的工作，并以较低的请求时间完成完成的工作。

很多时候，这个范例被用来将动态内容转化为静态内容。一个网站的页面（可能是用一个巨大的框架或CMS构建的）在每次更改时都被预先渲染并作为静态HTML文件存储在本地。通常这些计算任务是定期完成的，也可能是由cronjob每小时调用一次的脚本。整体通用数据的预先计算可以极大地改善网站和网络应用程序，并使其具有很高的可扩展性和性能。试想一下，如果脚本会将这些预渲染的HTML页面上传到AWS S3或Cloudfront或其他付款云网络，就可以想象网站的可扩展性！您的网站将可以达到超级响应，可以处理数以每小时百万计的游客！

异步＃2

回到面包店。不幸的是，有时顾客有特殊的要求，比如生日蛋糕-“生日快乐，小明”！面包店无法预见到这种客户的意愿，所以当客户在面包店时要开始工作，并告诉他在第二天回来。引用一个Web服务，意味着异步处理任务。

这是一个典型的工作流程：

用户来到您的网站，并开始一个非常计算密集的任务，这将需要几分钟时间完成。因此，您的网站前端将作业发送到任务队列，并立即发回给用户：您的任务正在被执行（或者等待执行），请继续浏览页面。任务队伍被一群worker检查，如果有新的任务出现，那么worker就干这个任务，几分钟后发出一个信号表明任务已经完成。前端不断地检查新的“任务已经完成” - 信号，看到任务完成并通知用户。（这只是一个简单的例子，检查的机制也有很多，可以参见数据库并发执行里面如何执行查询任务的。）

如果你现在想深入细节和实际的技术设计，我建议你看看RabbitMQ网站上的前3个教程。 RabbitMQ是帮助实现异步处理的许多系统之一。你也可以使用ActiveMQ或简单的Redis列表。基本的想法是有一个worker可以处理的任务或任务队列。

异步似乎很复杂，但绝对值得您花时间来了解它并自己实现。后端变得几乎可以无限扩展，前端变得活泼，这对整体用户体验是有利的。

如果你做了一些耗时的事情，试着总是异步地做。

https://www.hiredintech.com/classrooms/system-design/lesson/61

master/slave replication, master/master replication）

索引查询非常快

映射表

• hash: varchar(6)
• origin: varchar(512)

在hash属性上建立聚集索引（36GB+），我们希望将这个索引存在内存中。

• 垂直扩展MySQL服务器
• 数据分片：5片数据，600GBs数据，8GB索引
• 读写分离，主从复制（从多台从机读取，写入主机，由主机更新数据到从机）