什么样的好友系统

    大体上常见网站的好友系统分这么两种：一类是如 facebook，严格的好友验证，一方发出请求，另一方核准，接受请求的话两人相互为对方的好友；另一种如豆瓣，从 twitter 上改进而来，你可以任意 follow（关注）他人，如果两人都 follow 对方，就算做好友，好友在这里是“followers”和“following”的交集。其实 QQ 是人们最熟悉的使用第二种方法的软件，只不过多了个对 follow 的验证，而且你只能看到你自己的 following 而无法一目了然的看到哪些是 friends。

    采用哪种方式纯属个人喜好的问题，曾经跟老陈争论了很久。我是支持用第二种方法的，我的理由是，一些明星人物可以被非常多的人 follow，而他自己可能只 follow 了十几个人。而老陈更纠结于这些词用中文怎么叫、怎么能让用户很快理解设计者的意图。叫“好友”不太恰当（因为这个列表是公开的，不像 QQ 只有自己能看见，而你未必是你 following 的 friend），叫“跟随”又有些生硬。当时好像还没想到“关注”这个词。

    原始想法

    这是我想当然的设计，数据库里只有两个 int 字段：user 和 following，再都放到主键里。

    CREATE TABLE IF NOT EXISTS friend (

      user int(10) unsigned NOT NULL,

      follow int(10) unsigned NOT NULL,

      PRIMARY KEY (user, follow)

    ) ENGINE=MyISAM DEFAULT CHARSET=ucs2;

    可能用 QQ 时间久了，思维都很 QQ 了。这个方式如果用于 QQ，那是正确的。这个方式主要的优点有两个：原子操作保证了不会在大的访问压力下出错，以及便于 hash 分割到多个数据库，如果你的用户们都很活跃，添加了大量的好友（10M user * 100 follow 的话），那么负载是很可观的，这时你可以从容的把好友数据放到 n 个数据库里（主要是因为 MyISAM 的表级锁，我试图通过多个机器分担表锁、CPU 和 内存 IO 的同时又避免 InnoDB 的诸多缺点，这个表的全部操作都在内存中的索引缓存里）。

    下面再细数缺点：

    太耗内存，数据跟索引的比接近 1:2（准确的说是 9:17，在 MySQL 5.1 下），标准的 key_buffer_size 杀手。更让人头疼的，我这个表还没加查 followers 的索引呢！加了的话索引又得翻番，这个时候问题真的就有点大了。

    这就引申了下一个问题：查 followers 的话需要扫描所有的库，显然会造成瓶颈。

    最后，也是最严重的问题：最容易得到的仅仅是 following 列表，而无从确认哪些是 friend，这需要一一去确认，哪怕仅仅是查 memcache，如果 following 很多的话，这也是不小的开销。

    在我想到改进方法的时候，总结了一下之前的错误，最根本的问题在于这种一对多的关系，比方说一个人加了 100 个好友，对应记录是 100 行，200 个用户 id，可实际不重复的 id 只有 101 个，即 100 个相同的 user 字段是问题所在。而在添加第二个索引的时候这个问题又被放大了。

    同时绝对的原子操作又没什么意义了，因为你总之是对两个数据库（总考虑的是最糟糕的情况，分多个库后在不同库的两个用户之前的操作，下同）分别提交 query，就算存储的结果是对的，也可能在读取并保存到 memcache 时产生误差。由于太多的读取操作更提高了这种错误的几率。

    改进版

    昨晚想到的解决方案是这样，三个字段，user 字段不用说，list 字段是 blob 类型，存一个序列化后的数组，包含 friend / followers / following 的 id，还有一个叫 ver 的辅助字段保证原子操作（这应该是一个古老的小技巧）。

    CREATE TABLE IF NOT EXISTS friend (

      user int(10) unsigned NOT NULL,

      ver int(10) unsigned NOT NULL,

      list blob NOT NULL,

      PRIMARY KEY (user),

      KEY user (user,ver)

    ) ENGINE=MyISAM DEFAULT CHARSET=ucs2;

    具体的用法是，每次操作（其实基本操作就两个，follow 和 unfollow，而 friend、followers 和 following 是操作的结果）都是两条 query，分别针对主体客体两行记录，过程都是一样，读出用户的整个 follow 数组，根据具体情况，可能是 following 部分要增加一个用户 id，或者这个 id 已经是你的 follower，那就挪到 firend 里，再把结果保存。关键是靠 ver 字段来保证操作不会出现错误，即 UPDATE friend SET list = xxx, ver = ver + 1 WHERE user = xxx AND ver = xxx，如果没有更新行，说明之前读到的 list 是过期的，在读写的间隔里已经有别的 UPDATE 了，那再重新 SELECT / UPDATE

    虽然行不定宽可能会影响速度，但总的速度应该差不多，之前虽然是完全从内存中读，但是要读很多行，而且要想缓存 friend 关系或者查 followers 的话需要更多的空间。

    此外还有个额外的好处，就是对列表按时间的排序。如果你的 followers 过多，像 奥尼尔的 twitter 那样（我现在看是有 2.5M followers），你需要做个取舍了，至少你肯定没法真的把所有 followers 都列出来，例如 30 人一页，让人按顺序翻上 83K+ 页，那也没什么意义。很显然，超过一定数量后就只有数字了。所以你可以额外增加一个计数，按 follow 的时间顺序倒序保留最近 followers，比方说保留一万个，超过的话就踢掉列表里最后的那位，同时计数 += 1。

    对于超出部分的这番处理，在我看来是有必要的。一个有数量限制的列表可以保证功能在绝大多数情况下的正常使用。比方说奥尼尔现实中认识的一个人跟他说“嘿，我昨天在 twitter 上 follow 你了”，那奥尼尔晚上回家后还可以正常的加上他，可能是从 followers 里翻了五页以后找到了，或者直接搜那人的名字找到了，但总之会两人都正常的成为对方的 friend。除非奥尼尔过了 5 个月再理会那人，可能那人已经从奥尼尔的 followers 列表里移除了，于是那人在奥尼尔的 following 里，而奥尼尔在那人的 friend 里（甚至这里也可以做个修正判断，如果两个人中有一个人的列表没超出限制，则意味着更为权威，但是，这个操作就要同时对两个人的列表都要负责了，如果再出现 ver 号不同的冲突，处理起来太麻烦，可能会产生其他问题，我觉得没必要，上述情况已经很罕见了，就算真的发生了，多大点事啊）。

    用户 follow 了一个人之后，最有可能的举动是刷新一下那人的页面，看自己是否出现在 followers 的第一个位置里，而且按道理来讲如果 follow 的是个很火的人，你过一分钟再刷新列表可能你已经到了第五或者第六的位置上去了。新方案可以正确的展示这种效果

    我曾经跟老陈说，你需要限制好友数量，QQ 和 MSN 都有限制的。这是个冠冕堂皇的理由，但不是一个正确的理由，直到我想到有限列表和无限计数可以分开处理的时候我才承认这点。

    必须承认，这个世界总是存在无厘头的妖孽，就像眼镜片上的灰一样永远也擦不完的。如果真的有像 奥巴马 这种 749,616 Following、2,686,225 Followers 的妖孽帐号存在，比拒绝他 follow 那么多人更好的方法是用之前的这种欺骗（说好听点，障眼法），跟我对论坛的处理是一个意思。

    问题

    因为这是个新想法，我躺在床上验证了几个小时后睡着，自以为问题不大，但毕竟没有在生产环境下试过，可能还要有些修补，也有可能根本就是错的我却没意识到。

    能想到的两个问题，一是每次操作时更新的主客体的操作顺序可能要琢磨下，应该问题不大，但另一个不得不说是隐患：短时间的高压可能会抗不住，但这种情况存在么？比方说某名人在电视上报道后的三个小时里增加了十万 followers，折合该 user 每秒不到 10 次 follow，貌似问题也不大。但我上面说了，如果 ver 编号不对会重读重写，如果每个页面至少尝试 20 次再退出的话，说不定会积累不少 web 进程在哪里。但是 web 服务器是最好堆的，比增加 MySQL 或 Memcache 要轻松愉快得多，只要提前做好准备就不是大问题。我提倡尽量把数据库要做的事情挪到 web 服务器上，数据库的升级扩充成本远大于 web 服务器。

    补充

    有个重要辅助功能是记录用户之间的“联系度”，即用户之间交互的时候都会产生一个分值，如果想复杂点可以不同的动作（发站内消息、相互访问空间、评论、论坛回贴等等）会有不同的分，凭借这个联系度排名，你可以轻松给出默认的好友列表顺序，或者更准确的推荐“好友的好友”之类的。这必须是一个隐藏属性，否则会有人注意到这个值然后去刷它，这也带来的好处是实时要求不高，算的有偏差也影响不大。这是我在上个公司离职前做的最后一个功能，虽然效果很不错但不是很有成就感，这不是那种需要琢磨才能做出来的挑战。

    对于用户列表，有个简单的优化方式，如果你的 user id 跟我一样是普通的整数的话，存的时候不要直接把数组序列化，最有效的压缩是把用 10 个字节表示的 32 位整数转成 4 字节字符串，在 PHP 里是

    不仅仅是 4 字节本身就很短了，同时定长的字符串也免去了分隔符所占的字节。在 MySQL 和 Memcache 里少存点总不是坏处，在 PHP 里再展开。

    任何一个现代的高负载的系统没有 Memcache（或类似的分布式内存缓存）的存在就实在是可笑的，我提倡的方法是尽可能多的使用 Memcache，而避免使用 MySQL Slave 之类的方案。用户对操作的及时反馈非常在意，slave 可能出现的若干秒延迟是很致命的。在我眼里 slave 通常只适合备份用。

    最后，我得跟老陈和小张说很抱歉，当初当你们试图让我寻找更好的方案我给不出来，而现在的新方案看起来解决了很多老问题却没带来多少新问题（或者真正的新问题又如以往被我选择性的无视了），而且这个新方案看起来真的很简单，可我却一直没想出来。这不是态度问题，这真的需要时间。