需求​

1. 数据大小：值的数据大小过大，无法保存在内存中，我们应该利用外部存储来存储它们。然而，我们仍然可以将数据键保存在内存中。
2. 单主机解决方案。没有分布式设计。
3. 优化写入。

解决方案​

• 内存哈希表索引 + 索引提示文件 + 数据文件
• 仅追加以优化写入。仅有一个活动数据文件用于写入。并将活动数据压缩到旧的数据文件中以供读取。

组件​

1. 内存中的 HashMap<Key, <FildId, ValueOffset, ValueSize, Timestamp>>

2. 数据文件布局

|crc|timestamp|key_size|value_size|key|value|
...

3. （索引）提示文件，内存哈希表可以从中恢复

操作​

删除：通过内存哈希表获取位置，如果存在，则前往磁盘上的位置将值设置为一个魔法数字。

获取：通过内存哈希表获取位置，然后前往磁盘上的位置获取值。

放置：追加到活动数据文件并更新内存哈希表。

定期压缩策略

• 复制最新条目：内存哈希表始终是最新的。停止并复制到新文件中。时间复杂度为 O(n)，n 是有效条目的数量。

  • 优点：对于过期或删除的条目效率高。
  • 缺点：如果过期的条目很少，会消耗存储空间。可能会使空间翻倍。（可以通过让一个辅助节点定期进行压缩工作来解决，例如，Hadoop 辅助名称节点）。

• 扫描并移动：对于每个条目，如果是最新的，移动到已验证部分的尾部。时间复杂度为 O(n)，n 是所有条目的数量。

  • 优点：
    • 缩小大小
    • 不需要额外的存储空间
  • 缺点：
    • 复杂，需要通过事务同步哈希表和存储。可能会影响性能。

后续问题

• 如何检测可以压缩的记录？
  • 使用时间戳。
• 如果一个哈希表无法适应单台机器的内存怎么办？
  • 一致性哈希，Chord DHT，查询时间复杂度为 O(logn)，使用指针表，而不是这里的 O(1) 使用哈希表。

这些关键词和句子模板帮助你影响他人。

• 我不确定这是否适合你，但 ...

  • 以非侵入的方式推荐

• 开放的心态

  • “你是否愿意做某事？”这鼓励人们采取行动。
  • 或者如果你在批评某事或某人，但仍想表现出同情，你可以说“我在帮助某人保持开放的心态。”

• 你知道什么关于

• 如果……你会有什么感觉？

  • 人们是如何被激励的？
    • 避免损失
    • 获得潜在收益
  • 情感优先于逻辑
  • 人们首先根据感觉做出决定。==有趣的是，当我们为自己做决定时，我们应该避免有害的情绪。（作者：雷·达里奥）==

• 想象一下

  • 通过讲故事在他人心中创造画面。

• 什么时候是个好时机？

  • 你想法未被听到的最大原因之一是别人告诉你他们根本没有时间考虑。
  • 前言促使对方假设会有一个好时机，而“否”不是一个选项。

• 我猜你还没来得及

  • 通过推动负面情景，你让人们提升到积极的状态，或者告诉你他们将如何解决他们说要做的事情。

• 简单的替换

  • 你有任何问题吗？ => 你对我有什么问题？当强调“问题”而不是“你”（受众）时，受众会问更少的问题。

• 在我看来，你有三个选择……在这三个选择中，哪个对你来说更容易？

• 有两种类型的人，…

  • 这可能帮助人们做出最终决定。

• 我敢打赌你有点像我

  • 这通常会导致对方舒适地同意你。

• 如果……那么……

  • 人们喜欢听到有逻辑支持的内容，无论它是否真的有意义……

• 别担心

  • 在高压情境中尤其有用，当面对一个惊慌失措的人时，它能让人放松。

• 大多数人

  • 当你告诉人们大多数人会怎么做时，他们的大脑会说：“我就是大多数人，所以也许我也应该这样做。”

• 好消息

  • “好消息是……”使人们以乐观的态度向前看，并消除谈话中的负面能量
  • 通过用“好消息是……”带来更多积极性，并回应“太好了”，你很快就会开始改变人们的想法平衡。

• 接下来会发生什么

  • 用一个容易回答的问题结束一个过程是获得快速反应和积极结果的关键。
    • 问题越容易回答，你获得决定的过程就越简单。

• 你为什么这么说

  • 谈判成功的关键在于在对话中保持控制，==控制权在于提问的人。==
  • 所以当我们遇到反对意见时
    • 我没有时间
    • 现在不是合适的时机
    • 我想多看看
    • 我现在没有钱
    • 在我做出决定之前，我需要和其他人谈谈。
  • 通过将你面临的每一个反对意见视为一个问题，你可以通过反问迅速重新掌控对话。

• 在你下定决心之前

  • 在你说“否”之前，争取最后的机会。

增长黑客营销的四大步骤​

1. 产品研发阶段，捕捉并扩大PMF（产品—市场契合度）
2. 找到并培育种子用户
3. 植入病毒式增长因素
4. 以数据为支撑，以实现产品最优化为目标，重复以上步骤

用户增长如何以PMF开始​

1. ==产品—市场契合度==是指产品满足市场强烈需求的程度。

2. 从最简可行产品开始，并在用户反馈中进步。

3. 使用已得的数据和信息支持提升PMF。

4. 尽可能早的了解客户的需求

   1. 例如，亚马逊员工在项目开始之前便提供内部通讯稿以收集反馈。
   2. 例如，沃纳·威格尔建议为你正在开发的产品编写常见问题解答/关键用户体验/用户手册=概念+操作+参考。

5. 用苏格拉底反诘法找出答案

   1. 这个产品是给谁用的?他们为什么要用它？我又为什么要用它？
   2. 是什么让你喜欢上了这个产品？又是什么阻碍了你把产品介绍给别人？这个产品缺失了什么？而它的亮点又是什么？

带领公司从优秀走向卓越等同于通过如下三个因素，推动巨大的飞轮，实现==突破==

1. 纪律严明训练有素的人
   1. 五级领导力:卓越的领导者>富有成效的领导者>能干的管理者>乐于奉献的团队成员>能力精干的人
   2. 先人后事
2. 纪律严明训练有素的想法
   1. 直面残酷的现实
   2. 先做个刺猬，再做个狐狸
3. 纪律严明训练有素的行为
   1. 训练有素的文化
   2. 技术是发展动力的加速器

领导一家公司从优秀跃升到卓越 = 推动一个巨大的飞轮以实现突破，包含：

1. 纪律严明的人
   1. 第五级领导力：高管 > 有效领导者 > 能干的经理 > 贡献团队成员 > 高度胜任的个人
   2. 先人后事
2. 纪律严明的思想
   1. 面对残酷的事实
   2. 先做刺猬后做狐狸
3. 纪律严明的行动
   1. 纪律文化
   2. 技术加速器

1. 针对几百或一千个关键人物，而不是数百万。

   1. 例如，Dropbox在初次推出时通过一个有趣的演示视频开始。人们可以注册，但需要在等待名单上才能使用。使用一些==新颖且令人兴奋==的东西来吸引用户。
   2. 例如，eBay在2012年与Gogo合作，在航班期间为ebay.com提供免费wifi接入。聪明之处在于，它可以跟踪数据，以查看这是否有益，从而可以继续合作。

2. 不要针对所有人——要针对正确的人。

   1. 例如，Uber在奥斯汀的SXSW会议上提供了几年的免费乘车服务，吸引了成千上万的科技迷和高收入年轻人。

   2. 黑客技巧

      • 向媒体网站推销，让他们写关于我们的文章。
      • 在Hacker News、Quora、Reddit上发帖。
      • 写博客。
      • Kickstarter。
      • www.helpareporter.com与记者联系。
      • 邀请用户免费或提供一些激励。

   3. ==噱头==

      • 创建“仅限邀请”的独特氛围。
      • 创建虚假用户，使其看起来比实际更活跃。（Reddit就是这样做的）
      • 专门为单一平台提供服务（PayPal和eBay）
      • 按小组向用户推出（Facebook和大学）
      • 邀请有影响力的人物为他们的受众和声誉助力。
      • 在电子商务网站上设置子域名进行捐赠（亚马逊）。

3. 专注于新用户注册（获取）而不是品牌认知。

4. 增长技巧 = 市场营销 + 工程

   1. 例如，Airbnb制作工具以便在Craigslist上进行交叉发布。
   2. 肖恩·埃利斯：“专注于客户获取而非‘认知’需要纪律……在某种规模下，品牌认知/建立是有意义的。然而，在头一两年，这完全是浪费资金。”
   3. 无效的行动
      1. 大规模的发布活动
      2. 建立它，他们就会来。（亚伦·施瓦茨：用户必须被吸引进来。）

1. 针对几百或一千个关键人物，而不是数百万人
   1. 例如，Dropbox在首次发布时以一个有趣的演示视频开始。人们可以注册但需要等待使用它。用一些==新颖且令人兴奋的==东西来吸引用户
   2. 又如，2012年eBay与Gogo合作，在航班飞行期间提供免费无线网络连接ebay.com。它的高明之处在于可以跟踪数据，通过看它是否有益来决定是否继续合作
2. 不要针对所有人 - 针对合适的人
   1. 例如，优步为奥斯汀的西南偏南会议提供了多年的免费乘车服务，这一举措吸引了成千上万的年轻且有高收入的技术爱好者
   2. 小技巧
      • 说服媒体网站写关于自己的内容
      • 在Hacker News, Quora 和 Reddit上发表帖子
      • 写博客
      • 使用Kickstarter众筹
      • 通过 www.helpareporter.com 来联系记者
      • 免费或通过一些奖励来邀请用户
   3. ==大技巧==
      • 用“仅限邀请”创造排他性的饥饿营销
      • 创建虚假用户以使其更加活跃。 （Reddit采用了这种方法）
      • 专注于单一平台（PayPal和eBay）
      • 逐个用户群组扩散到另一个用户群组（Facebook和大学）
      • 吸引有影响力的人，因为他们有广大的受众和良好的声誉
      • 在电子商务网站的子域上做慈善捐赠（Amazon）
3. 专注于新用户注册（获取）而非品牌意识
4. 增长技术 = 市场营销 + 工程
   1. 例如，爱彼迎（Airbnb）制作工具同时向 Craigslist 交叉发布帖子
   2. 肖恩·埃利斯曾经说过:“坚持专注于获取客户而不是'创造品牌意识'往往需要克制... 诚然，如果公司到了一定规模，品牌意识/品牌建设是有意义的。但是，在最初的一两年内这就完全是在浪费钱”
   3. 无效的行为
      1. 盛大的发布
      2. 一厢情愿地认为，桃李不言，下自成蹊 （而亚伦·斯沃茨认为，用户必须被吸引才会来）

增长黑客的四个步骤​

1. 从产品市场契合（PMF）开始
2. 找到你的增长黑客
3. 实现病毒式传播
4. 完成闭环

如何开始产品市场契合（PMF）？​

1. ==产品/市场契合== 是指产品满足强烈市场需求的程度。

2. 从最小可行产品（MVP）开始，并通过反馈不断演进

3. 利用数据和信息来支持PMF。

4. 尽早了解客户的需求

   1. 例如，亚马逊员工在开发项目之前会发布内部新闻稿以收集反馈。
   2. 例如，维尔纳·沃格尔建议为你正在开发的产品编写常见问题解答/关键用户体验/用户手册 = 概念 + 使用方法 + 参考

5. 运用苏格拉底的方法来发展答案

   1. 这个产品是给谁的？他们为什么会使用它？我为什么使用它？
   2. 是什么让你选择这个产品？是什么阻止你推荐给其他人？缺少什么？最重要的是什么？

设计一个系统，可以将用户给的网址变成短网址，用户使用这些短网址可以访问他们原来给的网址（下面简称长网址）。描述这个系统是怎么运作的，需包括但不限于下面的问题：怎么分配短网址？怎么存储短网址和长网址的映射关系？怎么实现跳转服务？怎么存储访问数据？

假设：在一开始的问题描述中不包含这些假设。一个优秀的面试者在得到一个具体设计的时候会问关于系统规模的问题。

• 长网址的域名大概有上万个
• 新的长网址流量大概是 10,000,000/天 （100/秒）
• 使用短网址访问长网址的跳转服务的流量大概是 10B/天 （100,000/秒）
• 提醒面试者这些是平均数字 - 在一些高峰期的时候这些数字会大很多（一种时间导致的高峰期，比如用户刚工作完回家的时候， 另一种是事件导致的高峰期，比如春节联欢晚会的时候）
• 最近的数据（比如今天的数据）应该被提前收集好，并且在用户想要看的时候可以在五分钟内得到。
• 每天计算历史数据

假设​

每天有1B新网址，100B的短网址访问 短网址越短越好 数据的展示（实时/每天/每个月/每年）

网址编码​

http://blog.codinghorror.com/url-shortening-hashes-in-practice/

方法1. md5(128位，16个16进制数字，冲突，生日悖论，2^(n/2) = 2^64) 再短一些？（64位，8个16进制数字，冲突 2^32）, 64进制。

• 优点：哈希比较简单 而且 易于横向拓展。
• 缺点：太长，怎么去处理过期的网址？

方法2. 分布式的序号生成器。(62进制: az, AZ, 0~9, 62种字符, 62^7), 分区：每个节点包含一些序号。

• 优点：容易淘汰过期的网址，网址更短
• 缺点：不同分区之间的协调（zookeeper)

键值（KV）存储​

MySQL(10k 每秒访问量，慢，没有关系不需要关系型数据库)，键值（100k 每秒访问量，Redis, Memcached）

一个优秀的面试者会问关于短网址的预期使用期限，设计一套系统可以自动清理已经过期的短网址。

跟进​

问题：怎么生成短网址？

• 一个差的面试者 会提议用一个id生成器（单点故障）或者要在每个id生成的时候需要id生成器之间协同合作。 举例，使用自动增值的主键（auto-increment primary key）的数据库。
• 一个可以接受的面试者 会提议用md5，或者一些UUID生成器可以在一些结点上自己生成id的。这些方法可以在分布式系统上生成不冲突的ID，所以可以生产大量的短网址。
• 一个优秀的面试者 会设计一个方法利用一些id生成器，每个生成器先从中央协调器（例如ZooKeeper）保留一块id序列，这些id生成器可以单独从他们的id序列中分配id，有必要的时候在自己的id序列中做一些清理。

问题：怎么存储长网址和短网址之间的映射关系？

• 一个差的面试者 会建议使用一个单一的，非分布式，非关系型的数据库。它只是一个单纯的键值数据库。
• 一个优秀的面试者 会建议用简便的分布式系存储，例如 MongoDB/HBase/Voldemort 等。
• 一个更优秀的面试者 会问关于短网址的预期使用周期，然后设计一套系统==可以清理过期的短网址==。

问题：怎么实现跳转服务？

• 一个差的面试者 会从头开始设计这套系统来解决已经被解决的问题
• 一个优秀的面试者 会建议使用一个现成的HTTP服务器加上一个插件，用这个插件来翻译这个短网址的id，在数据库中找这个id，更新访问数据，返回303，跳转到长网址。 现成HTTP服务器比如 Apache/Jetty/Netty/tomcat 等。

问题：怎么存储访问数据？

• 一个差的面试者 会建议每次访问都写到数据库。
• 一个优秀的面试者 会建议由几个不同部分去做这件事情==生成访问流数据，收集整理，每过一段时间写到永久数据库中==。

问题：怎么分上一个问题优秀面试者提出的存储访问数据的不同部分？

• 一个优秀的面试者 会建议用一个延迟较低的信息系统去暂时存储访问数据，然后将数据交给收集整理部分
• 面试者可能会问访问数据多久需要被更新一次。如果每天更新，一个比较合理的方法是存储在HDFS，用map/reduce去计算数据。 如果是要近乎实时的数据，收集整理的部分就要计算出所需的数据

问题：怎么阻止访问受限的网站？

• 一个优秀的面试者 会要求在键值数据库里维护一个域名的黑名单。
• 一个好的面试者 可能会提出一些先进的技术， 可以用在系统规模变得很大的情况下， 比如bloom filter。

失效转移：失效转移（failover）是一种备份操作模式，用于提高系统稳定性和可用性。当主要组件由于失效或预定关机时间的原因而无法工作时，这种模式中的系统组件（如处理机、服务器、网络或数据库）的功能被转嫁到二级系统组件。

冷备份:冷备份是将关键性文件拷贝到另外的位置的一种说法，使用特征或指标/警报来跟踪故障。系统在发生故障时提供新的备用节点，当然，冷备份仅适用于无状态服务。对于备份Oracle数据库而言，冷备份是最快和最安全的方法。

热备份:保持两个活动系统承担相同的任务角色，也就是系统处于正常运转状态下的备份。两个系统中数据几乎是实时镜像的，且拥有相同的数据。

温备份:保持两个活动系统，除非发生故障，否则次要系统不占用流量。

检查点(或类似于Redis快照):系统在处理任务之前使用预先写入（write-ahead）日志(WAL)记录请求。备用节点在故障转移期间从日志中恢复。

• 缺点
  • 大量的日志恢复起来很耗时
  • 自上次检查点以来丢失数据
• 用户案例:Storm, WhillWheel, Samza

双主机(或全部主机)模式:将两个活动系统保留在负载平衡器之后。主机之间是平行的，且数据复制是双向的。