V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
gzxu
V2EX  ›  程序员

想造一个 Linux 下 OneDrive 同步客户端的轮子,请问对于网盘同步这样的需求,有没有什么成熟的算法?

  •  1
     
  •   gzxu · 2018-05-10 18:30:33 +08:00 · 3961 次点击
    这是一个创建于 2149 天前的主题,其中的信息可能已经有所发展或是发生改变。

    已有的轮子

    GitHub 上简单搜了下有这些

    但这些轮子都缺少冲突检测的功能,以及依赖于 inotify 来实现对文件移动的检测(检测到文件移动后我们就可以在服务器端同样移动一下而不用重新上传)。我没有下载尝试,但阅读代码后发现以上解决方案执行的操作都是,先把服务器上的内容下载下来,覆盖掉本地内容,然后检测文件系统的改变并实时上传,直到下一次同步的时候再用云端内容覆盖掉本地内容。

    我希望实现 Windows 下官方客户端的功能。

    需求

    1. 首次运行的时候,用云端内容填充本地目录(这个没问题)
    2. 每次同步的时候,将云端增加和修改的文件同步到本地,删除在云端被删除的文件,同时将本地这样的修改同步到云端。对本地文件有哪些修改进行描述的时候,尽量减少上传量,避免重复上传的发生。如果出现冲突,提示用户(也就是我)
    3. 非同步时段,没有网络操作,也没有 daemon 进程。因为如果程序的正常工作依赖一个驻留进程的话,总是担心这个进程有没有运行、没有运行是不是数据就不一致了这样的问题很难受的

    OneDrive 提供了这些接口

    然而微软没有提供“告知客户端,云端文件有修改”这样的接口,导致 daemon 方案的必要性大大降低。同时微软也没有提供批量上传文件的接口

    问题

    1. 对两棵树进行 diff 操作的算法是什么?

      我想要尽量简明地对本地文件有哪些修改进行描述。我们知道,我们执行 git mv 命令之后,查阅提交内容,git 会告诉我们移动了一个文件。这很容易让我们理解为 git mv 命令在 Git 的数据库里面写入了一条“用户移动了文件”的记录。但是,据 Pro Git 所述

      Unlike many other VCS systems, Git doesn ’ t explicitly track file movement. If you rename a file in Git, no metadata is stored in Git that tells it you renamed the file.

      The only real difference is that git mv is one command instead of three  —  it ’ s a convenience function.

      我很好奇这样的操作是用什么算法完成的。

    2. 如何尽量多地自动解决冲突,尽量少地提醒用户解决冲突?

      依前文所述,微软提供了云端文件树的增量描述,如果前一个问题解决了,我们也得到了本地文件树的增量描述。那么问题来了,如何对两个“增量描述”进行比较,并检测冲突?

    3. 更基本的一个问题,如何描述这样的文件树,如何规划数据结构?

    题外话

    正如很多资深苹果用户一样,我是曾经个资深微软用户,许多重要的文件在 OneDrive 上有一份存档,OneDrive 的空间也比较大。但由于 Windows 10 不断地让我失望,它从我的启动分区消失已经有一年多了。由于众所周知的原因,使用 OneDrive 客户端比使用网页版方便且稳定得多(虽然都不咋地)。我不是计算机相关专业的,因此我认为我可能欠缺不少基础知识,希望各位能多多指教,非常感谢~

    第 1 条附言  ·  2018-10-29 21:53:37 +08:00
    看到有朋友收藏了这个主题,更新一下吧,故事的后续在这里 https://www.v2ex.com/t/459891
    16 条回复    2018-05-11 09:18:12 +08:00
    agi
        1
    agi  
       2018-05-10 18:46:50 +08:00   ❤️ 1
    路过帮顶
    beginor
        2
    beginor  
       2018-05-10 18:52:11 +08:00 via Android
    能否用 wine 开运行 Windows 版的 onedrive ?
    smallthing
        3
    smallthing  
       2018-05-10 18:57:51 +08:00
    win10 开始是很失望,现在越来越好了.每天都重度使用
    Alchem
        4
    Alchem  
       2018-05-10 19:03:44 +08:00 via Android
    其实我想说 Win 10 很好啊,不懂楼主失望在哪里呀
    好吧我承认我歪楼了🙄
    geelaw
        5
    geelaw  
       2018-05-10 19:09:33 +08:00
    如果你想获得 Windows 上的 OneDrive 的功能,你需要 extended attributes 这种东西,which 我不知道 Linux 上的常用文件系统有没有这种功能。

    如果你想获得变化的通知,你需要一个 publicly accessible 的 Web API,使用 Webhook 或者 Subscription 的接口。

    我觉得可以这样:放一个文件夹专门存 leaves (不是文件夹的文件),用 userid!itemid 这种格式;对于实体的文件夹,所有的文件都用 soft link 弄上去,每个文件夹放一个 .userid!itemid 的占位符,表示这是云上的哪个文件夹(类似 .gitkeep 的作用,如果不放心,可以生成一个 guid 然后毁灭网卡,用它命名,这样除非是找茬否则就不会有什么问题了)。

    最简单的更新方案是:寻找每个云上的更新,如果自从上次以来原来对应的文件没有修改过,则 apply 云上的修改;否则认定为一个冲突,要求用户解决;然后寻找本机的更新,确认云上自从上次以来没有修改过该文件,并把更新应用到云上。

    如果本地出现了一个文件夹但文件夹里面没有占位符,说明是一个新的文件夹;如果本地出现了一个不是 soft link 的文件,说明是一个新的文件。
    geelaw
        6
    geelaw  
       2018-05-10 19:13:27 +08:00   ❤️ 1
    @geelaw 这里的一个问题是用户 naively 复制一个文件会导致的问题,你会搞不清楚谁是原本谁是副本。
    ftexplore
        7
    ftexplore  
       2018-05-10 19:27:25 +08:00
    直接用 Git 就行啊。一些文档、代码,Git 就可以直接当网盘用
    maomo
        8
    maomo  
       2018-05-10 19:33:19 +08:00   ❤️ 1
    rclone 了解一下
    gzxu
        9
    gzxu  
    OP
       2018-05-10 20:04:41 +08:00
    @geelaw #5 感谢回复

    我觉得我可能把问题想复杂了,我原来的构想是跟 Git 一样,列一份所有文件对应的 SHA256 索引( OneDrive 提供云上所有文件的 SHA256 )这样可以解决重复文件的问题,然后就懵了,跳进了算法的坑

    扩展的属性在 Linux 上是有的,因为我的 Fedora 默认启用 SELinux,这玩意依赖 xattr。我之前没想到还可以用这个

    > 可以生成一个 guid 然后毁灭网卡

    请问这是什么意思 😂😂😂
    gzxu
        10
    gzxu  
    OP
       2018-05-10 20:05:24 +08:00
    #7 @ftexplore 我需要在手机上查看云端的 Word 文档 😂😂😂
    gzxu
        11
    gzxu  
    OP
       2018-05-10 20:06:08 +08:00
    @maomo #8 哇,看了一眼感觉这玩意不错呀,我仔细看看,谢谢提醒
    gzxu
        12
    gzxu  
    OP
       2018-05-10 20:07:45 +08:00
    @beginor #2 Wine AppDB 上说了,不能😂😂😂
    geelaw
        13
    geelaw  
       2018-05-10 20:21:12 +08:00 via iPhone
    @gzxu guid 和网卡地址有关系,毁灭网卡之后就不可能有人产生来自该网卡的 guid,这可以保证之前产生的 guid 绝对不会被别人产生,所以除非一个人找茬儿,几乎不可能产生这样的文件名。

    相关故事: https://blogs.msdn.microsoft.com/oldnewthing/20040211-00/?p=40663/
    gzxu
        14
    gzxu  
    OP
       2018-05-10 20:32:23 +08:00
    @geelaw #13 这样嘛,我还以为和 http://man7.org/linux/man-pages/man1/uuidgen.1.html 一样是随机生成的。原来是个梗😂
    gzxu
        15
    gzxu  
    OP
       2018-05-10 22:12:17 +08:00
    @maomo #8 看了一下,比较失望,一方面只有单向同步功能,另一方面它没有利用到 OneDrive 的云端快照 API,无法保证下载目录结构的过程中云端文件没有变化,不过还是可以参考一下的,谢谢你啦~
    maomo
        16
    maomo  
       2018-05-11 09:18:12 +08:00
    @gzxu #15 如果你需要的是像 git merge 那样的双向同步,那 rclone 的确没有
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3030 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 15:01 · PVG 23:01 · LAX 08:01 · JFK 11:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.