脑洞大开：如何手动实现共享文件夹里的文件锁

October 10, 2014 - 1 minute read -
中文博客 interview

最近在找实习，参加了不少面试，对各类神坑的面试问题也见识了不少。最近脑洞大开，想到了下面这样一个情景，目测可以作为一道让人脑洞大开的面试题。

从前，有一个由 N 个人组成的团队，需要一起做一份幻灯片。请假设他们只愿意用 Microsoft PowerPoint，并且忽略 Office365 的存在。他们打算用一种类似 Dropbox 的服务同步一个文件夹，并把幻灯片的 .pptx 文件放在那个文件夹中。

这样就出现了一个问题，当有多个人同时编辑这个文件时，可能会产生冲突，让一些人的编辑结果丢失，或者出现不同的版本。假设这些情况都是他们不愿意看到的，请设计一种方案，让小组的每一个成员遵守，使得最多在每一个时刻，只有一个人编辑那个 .pptx 文件。

这篇日志将会就这个问题提出一种可行的解决方案。以下是对该方案的描述与分析。

文件夹同步服务的特点

假设我们使用的文件夹同步服务具有一下的特点。在我看来，这些假设，是符合逻辑的。

  1. 在理想情况下，每个团队成员拥有的文件夹是完全相同的。

  2. 当某个团队成员对自己拥有的文件夹副本进行了修改（添加，删除，编辑文件），这个修改需要一定的的时间在所以成员的文件夹中体现。

  3. 当某个团队成员按照一定的顺序对同步文件夹中的两个文件进行了修改，这些修改会按照发生顺序在剩余团队成员的文件夹中体现。即假如成员一先修改了文件A，然后修改了文件B，那么成员二的文件夹里文件A的修改必须发生在文件B的修改之前。

信号量 (Semephore)

多线程系统中，控制共享资源访问最常见的做法，就是使用 Semephore。

在我们的例子中，我们把大家需要编辑的文件叫做slides.pptx。假如我们需要引入 Semephore，很自然会想到使用一个额外文件，作为标记，我们暂且把这个文件叫做slides.lock。

我们可以创建下面这 3 条规则：

  1. 任何团队成员在编辑文件前，需要检查slides.lock文件是否存在，只有当此文件不存在时才可以进行第2步。

  2. 在编辑文件之前，需要创建slides.lock，以通知团队其他成员此文件被锁定。

  3. 在结束完文件编辑后，需要删除slides.lock，释放对文件的锁定。

很快，我们会发现这个设计还会存在一定的问题：假如两个成员同时请求编辑这个文件，他们可能会同时创建slides.lock而不产生冲突，这样就不可以保证文件只被一个人同时修改了。

而解决这个问题的想法也很自然，就是在 lock 文件中加入自己的名字或者 ID。例如1号小明创建的 lock 应该叫做slides.lock.1。这样，假如继续依照上面的规则，假如两人同时创造了 lock 文件，他们应该可以发现这个现象并及时阻止这件事情的发生(惊悚)。

已读回执 (Acknowledgement)

仔细思考前一步提出的解决方案，其实仍然存在一些可能，使得冲突发生：假如两人同时创造了自己的 lock 文件，但是由于系统同步延迟，这个文件没有及时反馈到其他人的文件夹中，仍然有可能使人误以为自己是唯一的修改权限获得者。

在之前的假设中，我并没有找到有效的冲突检查方法，所以我在试图进一步的避免冲突发生。

冲突发生的根源，在于我们在修改文件前，无法确认其他所以成员已经认可自己的 lock。仿照数据链路层 Data Link Layer 中 Acknowledgement 的设计，我们要求团队成员对于每一个 lock 请求进行认可。

我们把这种文件成为 ack 文件。命名原则是slides.ack.1.2：这代表 ID 为 2 的成员认可了 ID 为 1 的成员的 lock 请求，而请求 lock 的成员需要得到其余所以成员的认可后，才可以进行下一步。每个成员只可以同时 ack 一个人的 lock 请求。

这个方案看起来终于没有任何问题了，但是他指是理论上保证了文件只被一人修改，并没有具体指出，当有多人请求了 lock 之后，具体需要如何解决这个冲突。

冲突检查 (Collision Detection)

在古老的以太网中，有一种名叫 CSMA/CD (Carrier sense multiple access with collision detection) 的技术。启发我们的其实只是最后两个单词——冲突检查。

仿照 CSMA/CD 的设计，我们要求发生冲突后的双方同时放弃这次 lock 的请求，随机休息一段时间后，再次请求。

最终修改后的方案如下：

  1. 锁定文件

    1.1 检查slides.lock.*和slides.ack.*.*文件是否存在，只有当共享文件夹中不存在这类文件时才可以继续。

    1.2 创建slides.lock.<my-id>的文件。

    1.3 循环检查，假如：

    • 得到所有成员的slides.ack.<my-id>.*：开始修改文件。

    • 检测到另外的slides.lock.*：随机休息若干时间，返回 1.1 步。

  2. 释放文件

    2.1 删除slides.lock.<my-id>

  3. 日常操作

    3.1 遇到 slides.lock.*

    • 假如只有一个 lock 文件，则创建 slides.ack.*.<my-id>。

    • 假如文件不止一个，则不做反应。

    3.2 已 ack 的 lock 文件消失后，删除相应的 ack 文件。

最后

脑洞打开了之后真关不起来，不知道会不会忽略了什么，欢迎在下面的评论区讨论这个问题。

这道题考查了应试者操作系统和计算机网络的一些知识，应该是一道非常不wu错liao的面试题。