16 ms·

CDC File Transfer

917 points by cglong 4y ago

yread 4y ago
It would be cool to use this instead of blobfuse
sigmonsays 4y ago
can we gut rsync and implement this? rsync doesn't even have a great protocol specification... maybe it's a new tool...
- progbits 4y ago
  > Overall, cdc_rsync syncs files about 3 times faster than Cygwin rsync. Sounds promising.
- mjevans 4y ago
  I'd like additional info about the Content Defined Chunking part of the specification. How is the content defined? Where I'd try to begin is with a single pass that looks for runs of 'null' ('\0') bytes, even one long, as potential boundary ends. During that pass also look for 'magic signatures' for known stream types like already compressed content streams (all the more so to just not try compressing anyway). The CDC might also be aware of some file structures, zip, 7z, tar, etc; and have a dedicated segment creation algorithm for them. At a low level, the two ends should exchange a list of segment offsets, lengths, checksum (partial?) and maybe some short fragment of bytes to check. (E.G. 4 byte chunks at various powers of 2 offsets or major chunk starts.) Where the two ends have differences in chunks existing they might also expend some minor additional effort to investigate if the chunks that were identified on the other side exist locally; in case the two versions are using different filters or happened to reach different conclusions.
  - ljusten 4y ago
    In a nutshell, the algorithm computes uint64_t hash = 0; uint64_t magic_pattern = 0b001000010000100001000...; for (size_t n = 0; n < data.size(); ++n) { hash = (hash << 1) + random_table[data[n]]; if ((hash & magic_pattern) == 0) { SetChunkBoundaryAt(n); } } In practice, there's more bells and whistles, but that's the gist of it. By tweaking the numbers of 1's in magic_pattern you can influence the average chunk size (distance between two boundaries). With every additional 1, your chunk size halves. There's no special handling of compressed file types. You'd probably want to do that at a much higher level, e.g. just check for extensions.
brendoncarroll 4y ago
FastCDC is the same chunking algorithm used in Got. https://github.com/gotvc/got https://github.com/gotvc/got
- jws 4y ago
  To elaborate, rsync chunks in fixed sizes, so inserting or deleting a few bytes makes all different chunks from that point onward. If instead you chunk based off of local content (conceptually like chunking text into sentences at periods, but its a binary thing on has an upper size limit and lower size limit and I couldn't find the algorithm specification) so that after an insertion or deletion in a small number of bytes you start getting the same chunks as before. This drastically reduces the cost of identifying unmodified chunks.
  - brendoncarroll 4y ago
    I̶ ̶d̶o̶n̶'̶t̶ ̶t̶h̶i̶n̶k̶ ̶r̶s̶y̶n̶c̶ ̶u̶s̶e̶s̶ ̶f̶i̶x̶e̶d̶ ̶s̶i̶z̶e̶d̶ ̶c̶h̶u̶n̶k̶s̶.̶ The algorithm is described here; it's a rolling hash. https://rsync.samba.org/tech_report/node3.html https://rsync.samba.org/tech_report/node3.html Your description of content defined chunking is exactly right though. There are a number of techniques for doing it. FastCDC is one of them, although not the one used in rsync. https://en.wikipedia.org/wiki/Rolling_hash https://en.wikipedia.org/wiki/Rolling_hash EDIT: Corrected in the comments below. Fixed sized chunks searched for at any offset with a rolling hash. The rsync algorithm description is here. https://rsync.samba.org/tech_report/node2.html https://rsync.samba.org/tech_report/node2.html
    - teraflop 4y ago
      rsync does use fixed-size chunks, but the rolling hash allows them to be identified even at non-integer chunk offsets. So a change partway through the file doesn't force rsync to actually re-transfer all of the subsequent unmodified chunks, but it does incur a computational cost to find them since it has to search through all possible offsets.
  - eps 4y ago
Waterluvian 4y ago
Maybe I’m projecting (probably) but I detect some subtext in the README’s language. Like a “developers who are irate that Stadia was shut down, wanting to free anything they can for the community” type feeling.
- elromulous 4y ago
  Google / abc has a solid track record of open sourcing shutdown projects. See Makani[1] and iirc also Loon. [1] https://news.ycombinator.com/item?id=24456613 https://news.ycombinator.com/item?id=24456613
  - Waterluvian 4y ago
    Aha! I wasn’t at all aware of that. Okay, this reads more like that to me second time around. Just excitement to open source a cool piece of tech that came from Stadia.
  - codetrotter 4y ago
    Another example is Google Wave, which was also open sourced after it was shut down. https://en.wikipedia.org/wiki/Google_Wave https://en.wikipedia.org/wiki/Google_Wave https://incubator.apache.org/projects/wave.html https://incubator.apache.org/projects/wave.html Apache Wave was retired in 2018, but the source remains at least.
    - ocdtrekkie 4y ago
      Apache Wave is still one-click installable on Sandstorm and occasionally hilarious to share instances of with people. Won't do it here though, would kill my poor Intel NUC, Wave is not exactly performance-friendly.
    - josephg 4y ago
      Always nice to see my old work pop up! I'm really proud to have worked on the team that opensourced wave!
- deleted 4y ago
  [deleted]
deleted 4y ago
[deleted]
teraflop 4y ago
TL;DR they rediscovered the context-dependent variable block size technique that Tarsnap uses: https://www.tarsnap.com/download/EuroBSDCon13.pdf https://www.tarsnap.com/download/EuroBSDCon13.pdf
- crazygringo 4y ago
  They don't claim to have invented CDC, or FastCDC, they just made and are sharing a useful implementation of it. And if that Tarsnap presentation is from 2013, and FastCDC was published in 2016 [1] according to Wikipedia [2], then presumably Tarsnap didn't invent FastCDC either. [1] https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf https://www.usenix.org/system/files/conference/atc16/atc16-p... [2] https://en.wikipedia.org/wiki/Rolling_hash#Gear_fingerprint_and_content-based_chunking_algorithm_FastCDC https://en.wikipedia.org/wiki/Rolling_hash#Gear_fingerprint_...
  - jyxent 4y ago
    Another well-cited predecessor is "A low-bandwidth network file system." (https://dl.acm.org/doi/abs/10.1145/502034.502052 https://dl.acm.org/doi/abs/10.1145/502034.502052), which was published in 2001. It uses Rabin fingerprinting to define chunk boundaries.
- kccqzy 4y ago
  The Tarsnap technique is interesting but that presentation is a bit hard to follow. What are the examples for values alpha and p?
elromulous 4y ago
I took a quick glance at the repo, it wasn't totally clear to me if the client is windows only. Anyone know more?
- Moissanite 4y ago
  I thought the same; seems to be perfectly fine as a Linux-to-Linux tool.
  - skanga 4y ago
    Thanks! Does it work Windows to Windows also?
    - ljusten 4y ago
      Windows to Windows is being worked on, see https://github.com/google/cdc-file-transfer/compare/main...sync_windows https://github.com/google/cdc-file-transfer/compare/main...s.... Linux to Linux is also an option if there is demand, but currently it's Windows to Linux only.
      - skanga 4y ago
        That's great. Thanks!
- megak1d 4y ago
  Can I use this to replace some rsync cronjobs I have? I'd love to convert them to 'streaming' rather than updating every few minutes when the cron fires.
- ocdtrekkie 4y ago
  I imagine that one could develop this further into both ends being cross-platform but the readme seems to really strongly define it is solely built to transfer files from Windows to Linux. If that's all you need for internal tool, that's all you build (and test).
zX41ZdbW 4y ago
Content Defined Chunking is one of my favorite algorithms because it has some "magic" similar to HyperLogLogs, Bloom filters, etc... This algorithm is good to explain to people, to get them inspired by computer science. I usually explain the simplest variant with rolling hashes. It is interesting what the result will be (average saving on deduplication) if it is applied globally to a large-scale blob storage, such as Amazon S3 or Google Drive (we need metadata storage about chunks, and the chunks can be deduplicated). PS. I don't use this algorithm in ClickHouse, but it always remains tempting.
- piceas 4y ago
  Implementing fastCDC is fun (2016). Do you have a suggestion on what to read on the topic since then? I don't keep up with these things. A quick search came up with the following but I haven't read it yet. Fan Ni and Song Jiang, "RapidCDC: Leveraging Duplicate Locality to Accelerate Chunking in CDC-based Deduplication Systems", in Proceedings of 2019 ACM Symposium on Cloud Computing (ACM SoCC'19), Santa Cruz, CA, November, 2019. https://ranger.uta.edu/~sjiang/index.html https://ranger.uta.edu/~sjiang/index.html
  - windowsworkstoo 4y ago
    Microsoft have this for DFS-R and the spec is open https://learn.microsoft.com/en-us/openspecs/windows_protocols/ms-rdc/5b027295-0b63-45b9-8f62-0e49448350d9 https://learn.microsoft.com/en-us/openspecs/windows_protocol... - its pretty straight forward to implement.
- deleted 4y ago
  [deleted]
- klabb3 4y ago
  > It is interesting what the result will be (average saving on deduplication) if it is applied globally to a large-scale blob storage, such as Amazon S3 or Google Drive (we need metadata storage about chunks, and the chunks can be deduplicated). Yes this is truly promising but beware of dragons. Under current legal doctrine, blobs need some form of chain of custody. You can’t just deliver chunks to whomever has a hash (unless you’re decentralized, and you can move this problem to your users). Why? Because this is how bittorrent works, and we all know the legal dangers there. Encryption helps against eavesdropping, but not against an adversary who already has the hash and simply wants to prove you are distributing pirated material or even CSAM. You may be able to circumvent this to shift blame back on the user, in some cases. For instance, say you are re-syncing dangerous goods that you initially uploaded over Dropbox, then Dropbox can probably blame you, even though they are technically distributing. But that requires Dropbox to be reasonably confident that “you” (ie the same legal entity) had those chunks in the first place.
m000 4y ago
It would be interesting to also try this on more underpowered systems. E.g. aging armv5-based NAS boxes. Would we have similar performance improvements, or any improvements would be hampered by poor I/O performance and architectural inefficiencies?
- oll3 4y ago
  Built this cdc tool for software update of embedded (Linux) systems and have deployed it with good enough performance on a couple of arm CPUs; https://github.com/oll3/bita https://github.com/oll3/bita Though main goal has been keeping data usage low rather than speed up.
5440 4y ago
I'm currently working on a required CDC (Center for Disease Control) reporting function for a COVID test. For a second I thought this article was going to be extremely helpful.
- dn3500 4y ago
  The first computer I used professionaly was a Control Data Corporation (CDC) 6600. For a second I thought I could use this to transfer some of my old files.
- lucb1e 4y ago
  I have nothing to do with the CDC and am from another continent but had the same confusion. Not be enough TLAs are available it seems!
- dvasdekis 4y ago
  A new CDC (Change Data Capture) approach open-sourced by Google? Quickly I, a subsequently disappointed data engineer, started reading
  - pjot 4y ago
    I similarly assumed something was coming out from BigQuery
- gtirloni 4y ago
  I thought Cult of the Dead Cow was back.
- stefan_ 4y ago
  > USB communications device class (or USB CDC class) is a composite Universal Serial Bus device class. I may add this (and it fits somewhat nicely with file transfer..)
  - userbinator 4y ago
    That's what my mind also went to first upon seeing the title.
encryptluks2 4y ago
This is great for syncing, but what about separating courgette from Chromium so that we can finally have a descent delta diff program? I am tired of Windows community relying on SmartVersion to create ISO diff files just because you need to be a master at compiling Chromium just to use courgette.
punnerud 4y ago
With a small bit of tweaking this could be used for syncing live SQLite databases (probably)
- linsomniac 4y ago
  Shouldn't require any tweaking, the sliding window should be able to work on sqlite files just as well as the game content files used in this article. If you want something smarter and very much more sqlite optimized, you probably want to look at litefs. https://github.com/superfly/litefs https://github.com/superfly/litefs
- josephg 4y ago
  The problem is conflicts. If two remote peers both edit data concurrently, its not obvious what the resulting sqlite state should be. Better to embed a CRDT inside sqlite that can understand the semantics of sqlite's data, like cr-sqlite is doing: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite
- manigandham 4y ago
  You can use Litestream which is purpose built for streaming SQLite database replicas: https://litestream.io/ https://litestream.io/
dmarlow 4y ago
The write up was super clear and easy to follow. Thanks for the insights, context, and explanations! Oh, and the technology is cool too.
ohjeez 4y ago
I'm so old that I assumed this post was about interfacing with Control Data mainframes.
- Tor3 4y ago
  You were not the only one..
paravz 4y ago
sounds like cdc_rsync should be a good replacement for rsync in a generic backup
- linsomniac 4y ago
  Imagine an rsync that was A LOT smarter for backup use cases. Detecting files that have been renamed, files that have been compressed, similar files, files that have only been appended to, files that are the same across multiple systems (Oh, yeah, I probably already have a copy of this kernel file from this other host). Basically, deduplication as part of rsync.
  - RandomBK 4y ago
    BorgBackup has most of what you're looking for, though it doesn't implement CDC and doesn't replicate the files as-is in the backup location (instead using a compressed/deduped/chunked storage format)
    - linsomniac 4y ago
      For single system backups I've switched to using restic and it's been pretty great. I don't trust Borg, a couple years ago I tried doing a recovery using it and ran into some unicode issue in, I believe, a filename, and I couldn't track down exactly what file it was or get any files backed up after that file in the archive. I ended up using another backup I had. For my multiple backups to a backup host where I'm using rsync, restic really doesn't work (having 100+ systems backed up to the same destination).
  - paravz 4y ago
    Exactly what I'm looking for recently.. I dismissed ZFS (not mature on Linux) and btrfs (seems to be too complex and buggy as seen in a few horror stories) So far I started using --link-dest for rsync, as explained in https://lincolnloop.com/insights/detecting-file-moves-renames-rsync/ https://lincolnloop.com/insights/detecting-file-moves-rename... and used in https://github.com/dparoli/hrsync/blob/master/hrsync#L52 https://github.com/dparoli/hrsync/blob/master/hrsync#L52
Mortiffer 4y ago
Lame move google, CDC = Change Data Capture .
- Thorrez 4y ago
  The acronym CDC meaning Content-Defined Chunking wasn't invented by Google I don't think. Here's the 2016 paper introducing the FastCDC algorithm[1]. Disclosure: I work at Google, but not on anything related to this. [1] https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf https://www.usenix.org/system/files/conference/atc16/atc16-p...
teleforce 4y ago
This is an excellent candidate to be used with local-first software [1]. Thanks for sharing, never knew that this algorithm existed. [1]Local-first software: You own your data, in spite of the cloud: https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/
- glacials 4y ago
  Interesting! I recently wrote about this in the context of Google and Apple ecosystems and did not know it had a name. [1] I called in offline-first vs. online-first design. [1]: https://twos.dev/apple.html#offline https://twos.dev/apple.html#offline
dleslie 4y ago
> However, this was impractical, especially with the shift to working from home during the pandemic with sub-par internet connections. scp always copies full files, there is no "delta mode" to copy only the things that changed, it is slow for many small files, and there is no fast compression. I didn't appreciate the scope of this problem until a friend of mine visited from the valley. I live in semirural Canada, and they were floored by the speed and low latency of the fibre connection I have. I sort of took it for granted that people would spend the extra twenty bucks or so to make work from home a painless experience, or at least ask their employer to fund a better connection. It caused me to reach out, and I found many wfh peers with terrible connections, low powered laptops, and few second monitors. And proper desks? The exception. My family is mostly in trades, and so spending a little cash to improve my tools felt like common sense. Apparently it isn't.
- adastra22 4y ago
  > I sort of took it for granted that people would spend the extra twenty bucks or so to make work from home a painless experience I think you took for granted the mere availability of fiber as an option. 30Mbps DSL is the best option I have, other than Starlink. And I live in San Jose!
  - dleslie 4y ago
    You're not wrong. It's amazing how poor access can be. I live in a tiny town on Vancouver Island and I have gigabit symmetric, for a very reasonable price. When I lived in Vancouver that simply wasn't an option.
    - Topgamer7 4y ago
      The Canadian government gives grants to telecoms to install fibre. And I think there is some relation to signing up end users too but I can't recall.
      - dan-robertson 4y ago
dark-star 4y ago
Comparing it with rsync running on Cygwin is a bit unfair, as Cygwin is known to be terribly inefficient. I don't doubt that their CDC based algorithm is faster, but probably not by the margin they claim if Cygwin is taken out of the equation
- lathiat 4y ago
  They addressed that specifically in the README. They tested on Linux and it was worse but had a worse CPU so assumed it was comparable.
- ljusten 4y ago
  IIUC, rsync computes a relatively expensive Rabin-Karp rolling hash (https://librsync.github.io/rabinkarp_8c_source.html https://librsync.github.io/rabinkarp_8c_source.html) and performs a hash map lookup for every byte. Hash map lookups might not be very cache friendly for larger data sets. In comparison, cdc_rsync only computes hash = (hash << 1) + random_table[data[n]]; bool chunk_boundary = (hash & magic_pattern) == 0; per byte. That's only a few ops and very cache friendly. The random table only has 256 entries, 8 bytes each, so it easily fits into L1.
- ljusten 4y ago
  I should also note that we used a fairly fast 100 MB/sec connection to upload the data, so the rsync diffing algorithm running at 50 MB/sec is actually a bottleneck. The difference would be smaller on a slower connection, where the network overhead would dominate the results.
josephg 4y ago
I'm really impressed with the readme file in this repository. Its a master class in effective documentation. Just look at the structure: - 1-2 sentence summary of the project - History (why we built this and didn't just use existing tools) - What we've built, including what it does and how it compares to other tools (rsync in this case). - How to install and use it And the whole thing is full of images and animations showing the tool in action, and explaining enough of its internals. I consider myself good at documentation, but I'm taking notes. This is excellent.
- SV_BubbleTime 4y ago
  It’s always amazing to me how little emphasis people give to INTENT on their repo.
- deleted 4y ago
  [deleted]
- hot_gril 4y ago
  This is how I strive to document things. Focus primarily on what the tool is used for and why, not trying to define what it is.
  - aembleton 4y ago
    Also for commit messages - why the change is made, not what it is.
- zmmmmm 4y ago
  The documentation in the code itself is pretty great as well: https://github.com/google/cdc-file-transfer/blob/main/fastcdc/fastcdc.h#L59 https://github.com/google/cdc-file-transfer/blob/main/fastcd...
ithkuil 4y ago
I did a similar thing a few years ago https://github.com/mkmik/imsy https://github.com/mkmik/imsy It's less sophisticated but it uses the same core idea and the implementation is super simple
chaxor 4y ago
Any idea how it compares to aspera? I may give benchmarking a shot later when I get to my computer, but if anyone has any intuition that could be helpful.
RyanShook 4y ago
This looks like a very useful tool with a wide range of applications. Is it Windows to Linux only? It would be so nice if it was system agnostic.
- ljusten 4y ago
  We're currently adding support for Windows to Windows to cdc_rsync. If there is demand, Linux to Linux would also be possible.
deleted 4y ago
[deleted]
hot_gril 4y ago
> Born from the ashes of Stadia Love it. Those were some very expensive ashes. I hope more comes from them too.
- haarts 4y ago
  I take heart when reading about recovered parts of expensive ashes. But I firmly believe that no project is wasted especially one that pushed the boundaries of what is commonly done. All the people working there learnt something. They might apply their new found knowledge to other fields or future carriers. The money invested is not lost but converted into bigger brains. I look at VC money in much the same way. It's not great when a startup fails. But a lot is learnt.
- ssth 4y ago
  We can feel developer's bitterness from that sentence alone.
  - hot_gril 4y ago
    Stadia did impact my work a little, but not enough to matter to me. I'd be upset if I worked on it directly.
- nayuki 4y ago
  It's like how Google Docs' concurrent editing was born from the ashes of Google Wave.
  - collinmanderson 4y ago
    I don’t believe that Google docs concurrent editing came from wave. I thought they were separate though I might be wrong.
  - kragen 4y ago
    i thought it came from etherpad
- archon810 4y ago
xuhu 4y ago
How does cdc_rsync compare to Courgette for sending a 500MB rebuilt ELF binary where .text and .data now have slightly different offsets ?
- hcs 4y ago
  I haven't tested but I would guess it's a whole lot faster to compute but will end up sending much more data, given that it only works via exact chunks. A big part of binary patching is finding the largest possible chunks, even if they mismatch slightly. Speaking of Courgette, though, I suggest looking into Zucchini which is faster and often produces smaller patches: https://news.ycombinator.com/item?id=29028534 https://news.ycombinator.com/item?id=29028534 (sorry for linking to my own comment but I haven't found any good explanation or benchmarks from Google)
_ea1k 4y ago
Looks interesting, but when did we start saying "synching" instead of "syncing"? I mean, its literally based on the idea behind rsync. Why the sudden need to add an "h"?
- deleted 4y ago
  [deleted]
- capableweb 4y ago
  If by "we" you mean the internet, it seems most people still use "syncing" rather than "synching": https://trends.google.com/trends/explore?date=all&q=syncing,synching https://trends.google.com/trends/explore?date=all&q=syncing,... Still, "syncing" is supposed to be shorthand for "synchronizing", which has the "h" you feel comes out of nowhere. So I guess both makes sense, but I don't use that form myself nor have seen anyone else use it in the wild.
  - _ea1k 4y ago
    Repo description: "Tools for synching and streaming files from Windows to Linux" It then goes on to talk about how much like rsync their new "cdc_rsync" tool is. I get that the long version uses an h, but why include the silent h when making a shorthand? It sort of defeats the purpose of making a shorthand.
raverbashing 4y ago
The real question is, why is this not part of the base internet protocols already? Only goes to show how TCP is not as reliable as it should
- kccqzy 4y ago
  There are many older and more venerable file transfer protocols, like FTP or TFTP. Add encryption and then you have SCP and SFTP. SFTP is the default protocol used by the scp command, and TFTP is still often used to communicate with routers and access points and similar equipment. And I'm not sure what that has anything to do with TCP not as reliable. TCP has real problems on the modern Internet but the first part does not imply the second part.
  - raverbashing 4y ago
    And none of those protocols keeps the connection alive if you unplug your network cable and plug it back on really quickly Might I say, even if you get the same IP back from the router
    - kccqzy 4y ago
      That's not a problem with TCP, that's more of a problem with IP itself. Connections are currently identified by the source/destination IP and port numbers, but that should not have been the case. Imagine we use a UUID for the connection and keep an updatable cache between UUID and IP. Still nothing to do with TCP. Also, this kind of partial file transfer protocol is still needed because what if a host crashes? Even if we completely solve the mobile IP problem we would still rely on both ends of the connection tracking state. That state is lost due to a crash or power failure.
- manigandham 4y ago
  What does this have to do with TCP being reliable?
  - raverbashing 4y ago
AnonC 4y ago
I skimmed through the readme, which explains the concepts quite well, but am unclear on what needs to be installed on each machine (assuming Windows as the source and Linux as the destination). There’s a mention of copying the Linux build output, cdc_rsync_server, to the Windows machine. Why is this needed? And is there something on the Linux machine that needs to be (newly) added in the PATH?
- ljusten 4y ago
  Just uncompress the binaries on the Windows machine and run cdc_rsync. The Linux component, cdc_rsync_server, is deployed automatically on first run. It is scp'ed to ~/.cache/cdc-file-transfer/bin. So nothing has to be installed on the Linux machine.
  - AnonC 4y ago
    Thank you so much for responding here, OP! Really appreciate it. Perhaps you could add this explanation in the readme?
greatgib 4y ago
I don't understand, you can have rsync use a ssh tunnel directly. Easily. Isn't that enough?
- ljusten 4y ago
  Note that cdc_rsync runs on Windows and syncs to Linux. rsync is a Linux-only tool where you'd have to jump through some hoops to make it work on Windows.
omeid2 4y ago
How does it compare with Syncthing?
- Avamander 4y ago
  I was just wondering that, is the approach free, could Syncthing utilize it?
cwaffles 4y ago
CDC slides explaining the algorithm: https://www.usenix.org/sites/default/files/conference/protected-files/atc16_slides_xia.pdf https://www.usenix.org/sites/default/files/conference/protec...
- ddalex 4y ago
  What I don't get is how are the Gear CDC constants (the lookup table for gears) generated. Any insight ?
  - piceas 4y ago
    The fastCDC paper says they used random values. "It employs an array of 256 random 64-bit integers to map the values of the byte contents in the sliding window" I presume using something else would skew the distribution of selected chunks. I don't know if that would help or hinder. In my very limited experience, a picture of Rick Astley as the constants gave a similar distribution™ of chunks over a mixture of documentation files and Linux ISOs.
wankle 4y ago
If it's for Linux then will we finally have a Google Drive Linux Client?
winrid 4y ago
So game devs had to port their games to Linux to run on Stadia servers? That seems like a huge bottleneck...
- disqard 4y ago
  Yes, this was a core architectural requirement of Stadia (running the games on Linux), as opposed to hosting virtualized Windows machines (which would've allowed serving up Windows-based games). Whether this specific design choice alone killed Stadia, no one can say -- but it was probably one of the most important factors in its demise.
  - verdverm 4y ago
    Input lag and pixelated graphics is why I quit, I had gigabit fiber at the time
    - dijit 4y ago
      Likely it was caused by your computer and browser not playing nice with x265 hardware decoding, I used to run the gamelet on the same network as my desktop and would get the same on some configurations. Frustratingly, it was not easy to know at a glance that this was what was happening, but there were times (many times, actually) where my chromecast ultra at home was performing much better with Stadia than my gaming PC
    - ljusten 4y ago
      I got the same when I was running Stadia on a 2.4 GHz wifi network. Once I switched to a wired connection, it worked like a charm. 5 GHz supposedly works as well, but my robot vacuum cleaner needs a 2.4 GHz network facepalm.
      - baq 4y ago
        I have a PV inverter which doesn't work if there's more than one AP with the same SSID and is 2.4GHz only... ended up buying an el-cheapo AP and giving it a unique name. PITA
geokon 4y ago
This might be a dumb question.. but when I read this "scp always copies full files, there is no "delta mode" to copy only the things that changed, it is slow for many small files, and there is no fast compression." my thinking was: If you want to send diffs.. why not just use git? It does compression and chunks and all that. Maybe the defaults perform poorly for binary files? But couldn't you fix that with a custom diff algo? (if it's somehow not appropriate, it'd still be nice to port whatever secret sauce they use here to git..)
- deathanatos 4y ago
  I'm sort of in the same boat, but with the sentence, > To help this situation, we developed two tools, cdc_rsync Why not use rsync? (It does seem they ended up faster than rsync, so perhaps that's "why", but that seems more like a post-hoc justification.) The "we use variable chunk windows" bit is intriguing, but the example GIF sort of just pre-supposes that the local & remote chunks match up. That could have happened in the rsync case/GIF, but that wasn't the case considered, so it's an oranges/apples comparison. (Or, how is it that the local manages to be clairvoyant enough to choose the same windows?)
  - mindwok 4y ago
    I was wondering the same thing. It isn't explicit in the write-up but it's because rsync does not have a native Windows implementation, only rsync under Cygwin, so they developed this to achieve the same thing except it turned out faster than rsync.
    - int_19h 4y ago
      MSYS2 has rsync. Unlike Cygwin, I would consider that native.
  - ljusten 4y ago
    >> Or, how is it that the local manages to be clairvoyant enough to choose the same windows? Yes! In content defined chunking, the chunk boundaries depend on the content, in our case a 64 byte window. If the local and the remote files have the same 64 byte sequence anywhere, and that 64 byte sequence has some magic pattern of 0s and 1s, they will both have chunk boundaries there. A chunk is the range of data between two chunk boundaries, so if N consecutive chunk boundaries match, then N-1 consecutive chunks match.
up2isomorphism 4y ago
This also has been discovered long time ago by many people including myself for a backup system.
LarryMullins 4y ago
Always interesting to see the sort of tangential projects that get rolled into the budget of larger projects at companies like Google. Funding the development of yet another file transfer utility, interesting as this one is, definitely wasn't necessary.
- remus 4y ago
  > Funding the development of yet another file transfer utility, interesting as this one is, definitely wasn't necessary. Interesting you say that as I thought they explained their motivation pretty clearly. Is there a tool they missed that already does the job?
  - LarryMullins 4y ago
    I think most companies would have used an off the shelf solution and expected devs to simply deal with the inefficiency.
    - Tor3 4y ago
      For devs it's only inconvenient and annoying, but for the devs' company the inefficiency means money. At our company we were almost all of us working remotely during the pandemic (and many still do), and anything which slowed down or made a developer inefficient was looked at and improved on where possible. Because it's about (though not only about) money.
deanCommie 4y ago
> At Stadia, game developers had access to Linux cloud instances to run games. Most developers wrote their games on Windows, though. Therefore, they needed a way to make them available on the remote Linux instance. Am I reading this right that onboarding your game to Stadia as a developer involved essentially rsyncing data directly to a Linux cloud instance? That's.....
- ljusten 4y ago
  Just the compiled and baked game, not your sources. You still developed on Windows or wherever, the cloud instance was just used for running the game.
c7b 4y ago
Slightly OT, but I like the schematic gifs used in the Readme.md (pretty amazing doc overall!) like this one [0]. Does anyone have suggestions what tools they might have used (or might be used in general) to create those? [0] https://github.com/google/cdc-file-transfer/blob/main/docs/linux_rsync_animation.gif https://github.com/google/cdc-file-transfer/blob/main/docs/l...
- yellow_lead 4y ago
  Maybe just draw.io plus Photoshop or some gif generator. The gifs don't look very complicated
- ljusten 4y ago
  We used an internal Chrome extension to capture the gifs. There also seem to be some externally available GIF capturing tools, like https://chrome.google.com/webstore/detail/chrome-capture-screenshot/ggaabchcecdbomdcnbahdfddfikjmphe?hl=en https://chrome.google.com/webstore/detail/chrome-capture-scr... (disclaimer: I haven't tried those). We then used https://ezgif.com/optimize https://ezgif.com/optimize to remove dupe/unwanted frames, tweak timings and compress the gif. The actual content was done in Google Slides.
  - c7b 4y ago
    Awesome, thanks for replying here! If I may be greedy: I suppose you used something else for capturing the command prompt gif?
    - ljusten 4y ago
      Nope, luckily we still partially work from home and use Chrome Remote Desktop. The command prompt was running on my Windows machine, which I accessed remotely, so I could capture it with the extension. That wouldn't have worked if I had been in the office that day.
- r4kbY44D 4y ago
  ImageMagick does the trick, for example `convert -delay 20 -loop 0 *.png out.gif`
roydivision 4y ago
This would be interesting applied to local file copy, for instance for some backup strategies where large files change slightly.
- ljusten 4y ago
  This is currently being worked on, see https://github.com/google/cdc-file-transfer/compare/main...sync_windows https://github.com/google/cdc-file-transfer/compare/main...s...
worldsavior 4y ago
Why is it only from windows to Linux?
- ljusten 4y ago
  That's because most Stadia devs used Windows, but the cloud instances ran on Linux, so devs had to copy their games from Windows to Linux. We're currently adding support for Windows to Windows as well.
  - jamespo 4y ago
    And linux to linux?
    - aembleton 4y ago
      We also ran the experiment with the native Linux rsync, i.e syncing Linux to Linux, to rule out issues with Cygwin. Linux rsync performed on average 35% worse than Cygwin rsync, which can be attributed to CPU differences. Source: https://github.com/google/cdc-file-transfer https://github.com/google/cdc-file-transfer
      - ssth 4y ago
        I suspect that author made comparison using windows box and linux box with "cpu difference" because those 2 have different spec.
  - worldsavior 4y ago
    But why not make cross platform? If already creating a file transfer program, make it cross platform. What're the complications?
    - aembleton 4y ago
      It does do Linux to Linux as that's covered by the Readme. For anything else, I guess it didn't fill the scope of what was needed for Stadia
tmchow 4y ago
1. I thought this was going to be something about the Center for Disease Control 2. This is a really neat project, and super expensive ashes to rise from Stadia. 3. This is targeted at Windows to Linux, but given the speed advantages that it has over rsync couldn’t this be Linux to Linux? That said, I’d be afraid to use this over rsync just from the body of experience and knowledge that exists about rsync.
- rsync 4y ago
  "I thought this was going to be something about the Center for Disease Control" I thought cultdeadcow. Tool for transferring t-files.
- tga_d 4y ago
  I was thinking something similar to your third point, though more for cdc_stream, since as of last year sshfs is no longer maintained anyway.
xearl 4y ago
Is there any chance to get this faster sync algorithm into rsync itself?
- ljusten 4y ago
  The same question was asked here: https://github.com/google/cdc-file-transfer/issues/56 https://github.com/google/cdc-file-transfer/issues/56
Dowwie 4y ago
Could this serve as a general-purpose protocol that all remote development would benefit by using?
- sirjaz 4y ago
  Only if it could go the other way. Everyone seems to forget about Windows/Windows Server. 80%+ Desktop, and 55%+ Server(Include on-prem 70%+, Cloud 50%) Market Share.
didgetmaster 4y ago
One of the biggest problems with extremely large files is how a simple insert or delete near the front of the file causes all bytes following it to be shifted and re-written to disk. Add 3 bytes to the beginning of a 50 GB file and you are writing 50 GB to disk. I have been implementing a file system replacement project for several years. It is designed to handle hundreds of millions of files within a single container; put contextual meta-data tags on them; and enable lightning fast searches for things based off file type and/or tags. (https://www.youtube.com/watch?v=dWIo6sia_hw https://www.youtube.com/watch?v=dWIo6sia_hw) One of the ideas (not yet fully implemented) was to break up large files at the file system level. You might have a 50 GB file of data that looks exactly like a normal file to any application accessing it, but in reality it might be 10 separate chunks of 5 GB each. If you add or delete any bytes within any individual chunk, it only adjusts that specific chunk. For example, deleting 100 bytes at offset 6 GB causes the second chunk to shrink by 100 bytes. All the chunks following it are unaffected. The file still looks to be 100 bytes smaller to the application, but it doesn't realize that a chunk in the middle was just reduced in size instead of all the bytes after the change being shifted down. This feature would also make it easier to copy large files from one system to another. Data could be transferred one chunk at a time. If the copy was interrupted, only missing chunks would need to be copied when the process was restarted.
- themaninthedark 4y ago
  I know that BitTorrent has to allocate all the space before it downloads but would that be a good base to start with?
  - nicolaslem 4y ago
    This is also how Restic works, changing a few bytes in a 50 GB file won't reupload 50 GB of data unlike most backup solutions that work primarily with files.
    - didgetmaster 4y ago
      This change would not be just be for backups or file transfers. It would fundamentally change how big files are stored by the file system. Much like the way fragmentation is handled solely by the file system and an application accessing the file is completely unaware if the file is stored within a single fragment or multiple fragments; the file system would manage the individual 'chunks'. For example, a 6 GB file might be made up of 3 separate 2 GB chunks. An application might delete 20 bytes from the front of the file. This causes the first chunk to now be 2 GB - 20 bytes. The other 2 chunks are unchanged. Current file systems do not allow this where a file can have a block somewhere in its interior that is just a partial block.
rsync 4y ago
What is required on the server (linux) side ? I see how you put together the two .exe files but what is required on the linux side of things ?
Ciantic 4y ago
I can't find any mention of rclone [1]. It would be intersting to know how this compares to rclone copy or sync, because it uses threading, rsync doesn't. [1]: https://rclone.org/ https://rclone.org/

CDC File Transfer

917 points by cglong 4y ago

yread 4y ago

It would be cool to use this instead of blobfuse

sigmonsays 4y ago

can we gut rsync and implement this? rsync doesn't even have a great protocol specification... maybe it's a new tool...

progbits 4y ago
> Overall, cdc_rsync syncs files about 3 times faster than Cygwin rsync. Sounds promising.
mjevans 4y ago
I'd like additional info about the Content Defined Chunking part of the specification. How is the content defined? Where I'd try to begin is with a single pass that looks for runs of 'null' ('\0') bytes, even one long, as potential boundary ends. During that pass also look for 'magic signatures' for known stream types like already compressed content streams (all the more so to just not try compressing anyway). The CDC might also be aware of some file structures, zip, 7z, tar, etc; and have a dedicated segment creation algorithm for them. At a low level, the two ends should exchange a list of segment offsets, lengths, checksum (partial?) and maybe some short fragment of bytes to check. (E.G. 4 byte chunks at various powers of 2 offsets or major chunk starts.) Where the two ends have differences in chunks existing they might also expend some minor additional effort to investigate if the chunks that were identified on the other side exist locally; in case the two versions are using different filters or happened to reach different conclusions.
- ljusten 4y ago
  In a nutshell, the algorithm computes uint64_t hash = 0; uint64_t magic_pattern = 0b001000010000100001000...; for (size_t n = 0; n < data.size(); ++n) { hash = (hash << 1) + random_table[data[n]]; if ((hash & magic_pattern) == 0) { SetChunkBoundaryAt(n); } } In practice, there's more bells and whistles, but that's the gist of it. By tweaking the numbers of 1's in magic_pattern you can influence the average chunk size (distance between two boundaries). With every additional 1, your chunk size halves. There's no special handling of compressed file types. You'd probably want to do that at a much higher level, e.g. just check for extensions.

brendoncarroll 4y ago

FastCDC is the same chunking algorithm used in Got. https://github.com/gotvc/got https://github.com/gotvc/got

jws 4y ago
To elaborate, rsync chunks in fixed sizes, so inserting or deleting a few bytes makes all different chunks from that point onward. If instead you chunk based off of local content (conceptually like chunking text into sentences at periods, but its a binary thing on has an upper size limit and lower size limit and I couldn't find the algorithm specification) so that after an insertion or deletion in a small number of bytes you start getting the same chunks as before. This drastically reduces the cost of identifying unmodified chunks.
- brendoncarroll 4y ago
  I̶ ̶d̶o̶n̶'̶t̶ ̶t̶h̶i̶n̶k̶ ̶r̶s̶y̶n̶c̶ ̶u̶s̶e̶s̶ ̶f̶i̶x̶e̶d̶ ̶s̶i̶z̶e̶d̶ ̶c̶h̶u̶n̶k̶s̶.̶ The algorithm is described here; it's a rolling hash. https://rsync.samba.org/tech_report/node3.html https://rsync.samba.org/tech_report/node3.html Your description of content defined chunking is exactly right though. There are a number of techniques for doing it. FastCDC is one of them, although not the one used in rsync. https://en.wikipedia.org/wiki/Rolling_hash https://en.wikipedia.org/wiki/Rolling_hash EDIT: Corrected in the comments below. Fixed sized chunks searched for at any offset with a rolling hash. The rsync algorithm description is here. https://rsync.samba.org/tech_report/node2.html https://rsync.samba.org/tech_report/node2.html
  - teraflop 4y ago
    rsync does use fixed-size chunks, but the rolling hash allows them to be identified even at non-integer chunk offsets. So a change partway through the file doesn't force rsync to actually re-transfer all of the subsequent unmodified chunks, but it does incur a computational cost to find them since it has to search through all possible offsets.
- eps 4y ago

Waterluvian 4y ago

Maybe I’m projecting (probably) but I detect some subtext in the README’s language. Like a “developers who are irate that Stadia was shut down, wanting to free anything they can for the community” type feeling.

elromulous 4y ago
Google / abc has a solid track record of open sourcing shutdown projects. See Makani[1] and iirc also Loon. [1] https://news.ycombinator.com/item?id=24456613 https://news.ycombinator.com/item?id=24456613
- Waterluvian 4y ago
  Aha! I wasn’t at all aware of that. Okay, this reads more like that to me second time around. Just excitement to open source a cool piece of tech that came from Stadia.
- codetrotter 4y ago
  Another example is Google Wave, which was also open sourced after it was shut down. https://en.wikipedia.org/wiki/Google_Wave https://en.wikipedia.org/wiki/Google_Wave https://incubator.apache.org/projects/wave.html https://incubator.apache.org/projects/wave.html Apache Wave was retired in 2018, but the source remains at least.
  - ocdtrekkie 4y ago
    Apache Wave is still one-click installable on Sandstorm and occasionally hilarious to share instances of with people. Won't do it here though, would kill my poor Intel NUC, Wave is not exactly performance-friendly.
  - josephg 4y ago
    Always nice to see my old work pop up! I'm really proud to have worked on the team that opensourced wave!
deleted 4y ago
[deleted]

deleted 4y ago

[deleted]

teraflop 4y ago

TL;DR they rediscovered the context-dependent variable block size technique that Tarsnap uses: https://www.tarsnap.com/download/EuroBSDCon13.pdf https://www.tarsnap.com/download/EuroBSDCon13.pdf

crazygringo 4y ago
They don't claim to have invented CDC, or FastCDC, they just made and are sharing a useful implementation of it. And if that Tarsnap presentation is from 2013, and FastCDC was published in 2016 [1] according to Wikipedia [2], then presumably Tarsnap didn't invent FastCDC either. [1] https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf https://www.usenix.org/system/files/conference/atc16/atc16-p... [2] https://en.wikipedia.org/wiki/Rolling_hash#Gear_fingerprint_and_content-based_chunking_algorithm_FastCDC https://en.wikipedia.org/wiki/Rolling_hash#Gear_fingerprint_...
- jyxent 4y ago
  Another well-cited predecessor is "A low-bandwidth network file system." (https://dl.acm.org/doi/abs/10.1145/502034.502052 https://dl.acm.org/doi/abs/10.1145/502034.502052), which was published in 2001. It uses Rabin fingerprinting to define chunk boundaries.
kccqzy 4y ago
The Tarsnap technique is interesting but that presentation is a bit hard to follow. What are the examples for values alpha and p?

elromulous 4y ago

I took a quick glance at the repo, it wasn't totally clear to me if the client is windows only. Anyone know more?

Moissanite 4y ago
I thought the same; seems to be perfectly fine as a Linux-to-Linux tool.
- skanga 4y ago
  Thanks! Does it work Windows to Windows also?
  - ljusten 4y ago
    Windows to Windows is being worked on, see https://github.com/google/cdc-file-transfer/compare/main...sync_windows https://github.com/google/cdc-file-transfer/compare/main...s.... Linux to Linux is also an option if there is demand, but currently it's Windows to Linux only.
    - skanga 4y ago
      That's great. Thanks!
megak1d 4y ago
Can I use this to replace some rsync cronjobs I have? I'd love to convert them to 'streaming' rather than updating every few minutes when the cron fires.
ocdtrekkie 4y ago
I imagine that one could develop this further into both ends being cross-platform but the readme seems to really strongly define it is solely built to transfer files from Windows to Linux. If that's all you need for internal tool, that's all you build (and test).

zX41ZdbW 4y ago

Content Defined Chunking is one of my favorite algorithms because it has some "magic" similar to HyperLogLogs, Bloom filters, etc... This algorithm is good to explain to people, to get them inspired by computer science. I usually explain the simplest variant with rolling hashes. It is interesting what the result will be (average saving on deduplication) if it is applied globally to a large-scale blob storage, such as Amazon S3 or Google Drive (we need metadata storage about chunks, and the chunks can be deduplicated). PS. I don't use this algorithm in ClickHouse, but it always remains tempting.

piceas 4y ago
Implementing fastCDC is fun (2016). Do you have a suggestion on what to read on the topic since then? I don't keep up with these things. A quick search came up with the following but I haven't read it yet. Fan Ni and Song Jiang, "RapidCDC: Leveraging Duplicate Locality to Accelerate Chunking in CDC-based Deduplication Systems", in Proceedings of 2019 ACM Symposium on Cloud Computing (ACM SoCC'19), Santa Cruz, CA, November, 2019. https://ranger.uta.edu/~sjiang/index.html https://ranger.uta.edu/~sjiang/index.html
- windowsworkstoo 4y ago
  Microsoft have this for DFS-R and the spec is open https://learn.microsoft.com/en-us/openspecs/windows_protocols/ms-rdc/5b027295-0b63-45b9-8f62-0e49448350d9 https://learn.microsoft.com/en-us/openspecs/windows_protocol... - its pretty straight forward to implement.
deleted 4y ago
[deleted]
klabb3 4y ago
> It is interesting what the result will be (average saving on deduplication) if it is applied globally to a large-scale blob storage, such as Amazon S3 or Google Drive (we need metadata storage about chunks, and the chunks can be deduplicated). Yes this is truly promising but beware of dragons. Under current legal doctrine, blobs need some form of chain of custody. You can’t just deliver chunks to whomever has a hash (unless you’re decentralized, and you can move this problem to your users). Why? Because this is how bittorrent works, and we all know the legal dangers there. Encryption helps against eavesdropping, but not against an adversary who already has the hash and simply wants to prove you are distributing pirated material or even CSAM. You may be able to circumvent this to shift blame back on the user, in some cases. For instance, say you are re-syncing dangerous goods that you initially uploaded over Dropbox, then Dropbox can probably blame you, even though they are technically distributing. But that requires Dropbox to be reasonably confident that “you” (ie the same legal entity) had those chunks in the first place.

m000 4y ago

It would be interesting to also try this on more underpowered systems. E.g. aging armv5-based NAS boxes. Would we have similar performance improvements, or any improvements would be hampered by poor I/O performance and architectural inefficiencies?

oll3 4y ago
Built this cdc tool for software update of embedded (Linux) systems and have deployed it with good enough performance on a couple of arm CPUs; https://github.com/oll3/bita https://github.com/oll3/bita Though main goal has been keeping data usage low rather than speed up.

5440 4y ago

I'm currently working on a required CDC (Center for Disease Control) reporting function for a COVID test. For a second I thought this article was going to be extremely helpful.

dn3500 4y ago
The first computer I used professionaly was a Control Data Corporation (CDC) 6600. For a second I thought I could use this to transfer some of my old files.
lucb1e 4y ago
I have nothing to do with the CDC and am from another continent but had the same confusion. Not be enough TLAs are available it seems!
dvasdekis 4y ago
A new CDC (Change Data Capture) approach open-sourced by Google? Quickly I, a subsequently disappointed data engineer, started reading
- pjot 4y ago
  I similarly assumed something was coming out from BigQuery
gtirloni 4y ago
I thought Cult of the Dead Cow was back.
stefan_ 4y ago
> USB communications device class (or USB CDC class) is a composite Universal Serial Bus device class. I may add this (and it fits somewhat nicely with file transfer..)
- userbinator 4y ago
  That's what my mind also went to first upon seeing the title.

encryptluks2 4y ago

This is great for syncing, but what about separating courgette from Chromium so that we can finally have a descent delta diff program? I am tired of Windows community relying on SmartVersion to create ISO diff files just because you need to be a master at compiling Chromium just to use courgette.

punnerud 4y ago

With a small bit of tweaking this could be used for syncing live SQLite databases (probably)

linsomniac 4y ago
Shouldn't require any tweaking, the sliding window should be able to work on sqlite files just as well as the game content files used in this article. If you want something smarter and very much more sqlite optimized, you probably want to look at litefs. https://github.com/superfly/litefs https://github.com/superfly/litefs
josephg 4y ago
The problem is conflicts. If two remote peers both edit data concurrently, its not obvious what the resulting sqlite state should be. Better to embed a CRDT inside sqlite that can understand the semantics of sqlite's data, like cr-sqlite is doing: https://github.com/vlcn-io/cr-sqlite https://github.com/vlcn-io/cr-sqlite
manigandham 4y ago
You can use Litestream which is purpose built for streaming SQLite database replicas: https://litestream.io/ https://litestream.io/

dmarlow 4y ago

The write up was super clear and easy to follow. Thanks for the insights, context, and explanations! Oh, and the technology is cool too.

ohjeez 4y ago

I'm so old that I assumed this post was about interfacing with Control Data mainframes.

Tor3 4y ago
You were not the only one..

paravz 4y ago

sounds like cdc_rsync should be a good replacement for rsync in a generic backup

linsomniac 4y ago
Imagine an rsync that was A LOT smarter for backup use cases. Detecting files that have been renamed, files that have been compressed, similar files, files that have only been appended to, files that are the same across multiple systems (Oh, yeah, I probably already have a copy of this kernel file from this other host). Basically, deduplication as part of rsync.
- RandomBK 4y ago
  BorgBackup has most of what you're looking for, though it doesn't implement CDC and doesn't replicate the files as-is in the backup location (instead using a compressed/deduped/chunked storage format)
  - linsomniac 4y ago
    For single system backups I've switched to using restic and it's been pretty great. I don't trust Borg, a couple years ago I tried doing a recovery using it and ran into some unicode issue in, I believe, a filename, and I couldn't track down exactly what file it was or get any files backed up after that file in the archive. I ended up using another backup I had. For my multiple backups to a backup host where I'm using rsync, restic really doesn't work (having 100+ systems backed up to the same destination).
- paravz 4y ago
  Exactly what I'm looking for recently.. I dismissed ZFS (not mature on Linux) and btrfs (seems to be too complex and buggy as seen in a few horror stories) So far I started using --link-dest for rsync, as explained in https://lincolnloop.com/insights/detecting-file-moves-renames-rsync/ https://lincolnloop.com/insights/detecting-file-moves-rename... and used in https://github.com/dparoli/hrsync/blob/master/hrsync#L52 https://github.com/dparoli/hrsync/blob/master/hrsync#L52

Mortiffer 4y ago

Lame move google, CDC = Change Data Capture .

Thorrez 4y ago
The acronym CDC meaning Content-Defined Chunking wasn't invented by Google I don't think. Here's the 2016 paper introducing the FastCDC algorithm[1]. Disclosure: I work at Google, but not on anything related to this. [1] https://www.usenix.org/system/files/conference/atc16/atc16-paper-xia.pdf https://www.usenix.org/system/files/conference/atc16/atc16-p...

teleforce 4y ago

This is an excellent candidate to be used with local-first software [1]. Thanks for sharing, never knew that this algorithm existed. [1]Local-first software: You own your data, in spite of the cloud: https://www.inkandswitch.com/local-first/ https://www.inkandswitch.com/local-first/

glacials 4y ago
Interesting! I recently wrote about this in the context of Google and Apple ecosystems and did not know it had a name. [1] I called in offline-first vs. online-first design. [1]: https://twos.dev/apple.html#offline https://twos.dev/apple.html#offline

dleslie 4y ago

> However, this was impractical, especially with the shift to working from home during the pandemic with sub-par internet connections. scp always copies full files, there is no "delta mode" to copy only the things that changed, it is slow for many small files, and there is no fast compression. I didn't appreciate the scope of this problem until a friend of mine visited from the valley. I live in semirural Canada, and they were floored by the speed and low latency of the fibre connection I have. I sort of took it for granted that people would spend the extra twenty bucks or so to make work from home a painless experience, or at least ask their employer to fund a better connection. It caused me to reach out, and I found many wfh peers with terrible connections, low powered laptops, and few second monitors. And proper desks? The exception. My family is mostly in trades, and so spending a little cash to improve my tools felt like common sense. Apparently it isn't.

adastra22 4y ago
> I sort of took it for granted that people would spend the extra twenty bucks or so to make work from home a painless experience I think you took for granted the mere availability of fiber as an option. 30Mbps DSL is the best option I have, other than Starlink. And I live in San Jose!
- dleslie 4y ago
  You're not wrong. It's amazing how poor access can be. I live in a tiny town on Vancouver Island and I have gigabit symmetric, for a very reasonable price. When I lived in Vancouver that simply wasn't an option.
  - Topgamer7 4y ago
    The Canadian government gives grants to telecoms to install fibre. And I think there is some relation to signing up end users too but I can't recall.
    - dan-robertson 4y ago

dark-star 4y ago

Comparing it with rsync running on Cygwin is a bit unfair, as Cygwin is known to be terribly inefficient. I don't doubt that their CDC based algorithm is faster, but probably not by the margin they claim if Cygwin is taken out of the equation

lathiat 4y ago
They addressed that specifically in the README. They tested on Linux and it was worse but had a worse CPU so assumed it was comparable.
ljusten 4y ago
IIUC, rsync computes a relatively expensive Rabin-Karp rolling hash (https://librsync.github.io/rabinkarp_8c_source.html https://librsync.github.io/rabinkarp_8c_source.html) and performs a hash map lookup for every byte. Hash map lookups might not be very cache friendly for larger data sets. In comparison, cdc_rsync only computes hash = (hash << 1) + random_table[data[n]]; bool chunk_boundary = (hash & magic_pattern) == 0; per byte. That's only a few ops and very cache friendly. The random table only has 256 entries, 8 bytes each, so it easily fits into L1.
ljusten 4y ago
I should also note that we used a fairly fast 100 MB/sec connection to upload the data, so the rsync diffing algorithm running at 50 MB/sec is actually a bottleneck. The difference would be smaller on a slower connection, where the network overhead would dominate the results.

josephg 4y ago

I'm really impressed with the readme file in this repository. Its a master class in effective documentation. Just look at the structure: - 1-2 sentence summary of the project - History (why we built this and didn't just use existing tools) - What we've built, including what it does and how it compares to other tools (rsync in this case). - How to install and use it And the whole thing is full of images and animations showing the tool in action, and explaining enough of its internals. I consider myself good at documentation, but I'm taking notes. This is excellent.

SV_BubbleTime 4y ago
It’s always amazing to me how little emphasis people give to INTENT on their repo.
deleted 4y ago
[deleted]
hot_gril 4y ago
This is how I strive to document things. Focus primarily on what the tool is used for and why, not trying to define what it is.
- aembleton 4y ago
  Also for commit messages - why the change is made, not what it is.
zmmmmm 4y ago
The documentation in the code itself is pretty great as well: https://github.com/google/cdc-file-transfer/blob/main/fastcdc/fastcdc.h#L59 https://github.com/google/cdc-file-transfer/blob/main/fastcd...

ithkuil 4y ago

I did a similar thing a few years ago https://github.com/mkmik/imsy https://github.com/mkmik/imsy It's less sophisticated but it uses the same core idea and the implementation is super simple

chaxor 4y ago

Any idea how it compares to aspera? I may give benchmarking a shot later when I get to my computer, but if anyone has any intuition that could be helpful.

RyanShook 4y ago

This looks like a very useful tool with a wide range of applications. Is it Windows to Linux only? It would be so nice if it was system agnostic.

ljusten 4y ago
We're currently adding support for Windows to Windows to cdc_rsync. If there is demand, Linux to Linux would also be possible.

deleted 4y ago

[deleted]

hot_gril 4y ago

> Born from the ashes of Stadia Love it. Those were some very expensive ashes. I hope more comes from them too.

haarts 4y ago
I take heart when reading about recovered parts of expensive ashes. But I firmly believe that no project is wasted especially one that pushed the boundaries of what is commonly done. All the people working there learnt something. They might apply their new found knowledge to other fields or future carriers. The money invested is not lost but converted into bigger brains. I look at VC money in much the same way. It's not great when a startup fails. But a lot is learnt.
ssth 4y ago
We can feel developer's bitterness from that sentence alone.
- hot_gril 4y ago
  Stadia did impact my work a little, but not enough to matter to me. I'd be upset if I worked on it directly.
nayuki 4y ago
It's like how Google Docs' concurrent editing was born from the ashes of Google Wave.
- collinmanderson 4y ago
  I don’t believe that Google docs concurrent editing came from wave. I thought they were separate though I might be wrong.
- kragen 4y ago
  i thought it came from etherpad
archon810 4y ago

xuhu 4y ago

How does cdc_rsync compare to Courgette for sending a 500MB rebuilt ELF binary where .text and .data now have slightly different offsets ?

hcs 4y ago
I haven't tested but I would guess it's a whole lot faster to compute but will end up sending much more data, given that it only works via exact chunks. A big part of binary patching is finding the largest possible chunks, even if they mismatch slightly. Speaking of Courgette, though, I suggest looking into Zucchini which is faster and often produces smaller patches: https://news.ycombinator.com/item?id=29028534 https://news.ycombinator.com/item?id=29028534 (sorry for linking to my own comment but I haven't found any good explanation or benchmarks from Google)

_ea1k 4y ago

Looks interesting, but when did we start saying "synching" instead of "syncing"? I mean, its literally based on the idea behind rsync. Why the sudden need to add an "h"?

deleted 4y ago
[deleted]
capableweb 4y ago
If by "we" you mean the internet, it seems most people still use "syncing" rather than "synching": https://trends.google.com/trends/explore?date=all&q=syncing,synching https://trends.google.com/trends/explore?date=all&q=syncing,... Still, "syncing" is supposed to be shorthand for "synchronizing", which has the "h" you feel comes out of nowhere. So I guess both makes sense, but I don't use that form myself nor have seen anyone else use it in the wild.
- _ea1k 4y ago
  Repo description: "Tools for synching and streaming files from Windows to Linux" It then goes on to talk about how much like rsync their new "cdc_rsync" tool is. I get that the long version uses an h, but why include the silent h when making a shorthand? It sort of defeats the purpose of making a shorthand.

raverbashing 4y ago

The real question is, why is this not part of the base internet protocols already? Only goes to show how TCP is not as reliable as it should

kccqzy 4y ago
There are many older and more venerable file transfer protocols, like FTP or TFTP. Add encryption and then you have SCP and SFTP. SFTP is the default protocol used by the scp command, and TFTP is still often used to communicate with routers and access points and similar equipment. And I'm not sure what that has anything to do with TCP not as reliable. TCP has real problems on the modern Internet but the first part does not imply the second part.
- raverbashing 4y ago
  And none of those protocols keeps the connection alive if you unplug your network cable and plug it back on really quickly Might I say, even if you get the same IP back from the router
  - kccqzy 4y ago
    That's not a problem with TCP, that's more of a problem with IP itself. Connections are currently identified by the source/destination IP and port numbers, but that should not have been the case. Imagine we use a UUID for the connection and keep an updatable cache between UUID and IP. Still nothing to do with TCP. Also, this kind of partial file transfer protocol is still needed because what if a host crashes? Even if we completely solve the mobile IP problem we would still rely on both ends of the connection tracking state. That state is lost due to a crash or power failure.
manigandham 4y ago
What does this have to do with TCP being reliable?
- raverbashing 4y ago

AnonC 4y ago

I skimmed through the readme, which explains the concepts quite well, but am unclear on what needs to be installed on each machine (assuming Windows as the source and Linux as the destination). There’s a mention of copying the Linux build output, cdc_rsync_server, to the Windows machine. Why is this needed? And is there something on the Linux machine that needs to be (newly) added in the PATH?

ljusten 4y ago
Just uncompress the binaries on the Windows machine and run cdc_rsync. The Linux component, cdc_rsync_server, is deployed automatically on first run. It is scp'ed to ~/.cache/cdc-file-transfer/bin. So nothing has to be installed on the Linux machine.
- AnonC 4y ago
  Thank you so much for responding here, OP! Really appreciate it. Perhaps you could add this explanation in the readme?

greatgib 4y ago

I don't understand, you can have rsync use a ssh tunnel directly. Easily. Isn't that enough?

ljusten 4y ago
Note that cdc_rsync runs on Windows and syncs to Linux. rsync is a Linux-only tool where you'd have to jump through some hoops to make it work on Windows.

omeid2 4y ago

How does it compare with Syncthing?

Avamander 4y ago
I was just wondering that, is the approach free, could Syncthing utilize it?

cwaffles 4y ago

CDC slides explaining the algorithm: https://www.usenix.org/sites/default/files/conference/protected-files/atc16_slides_xia.pdf https://www.usenix.org/sites/default/files/conference/protec...

ddalex 4y ago
What I don't get is how are the Gear CDC constants (the lookup table for gears) generated. Any insight ?
- piceas 4y ago
  The fastCDC paper says they used random values. "It employs an array of 256 random 64-bit integers to map the values of the byte contents in the sliding window" I presume using something else would skew the distribution of selected chunks. I don't know if that would help or hinder. In my very limited experience, a picture of Rick Astley as the constants gave a similar distribution™ of chunks over a mixture of documentation files and Linux ISOs.

wankle 4y ago

If it's for Linux then will we finally have a Google Drive Linux Client?

winrid 4y ago

So game devs had to port their games to Linux to run on Stadia servers? That seems like a huge bottleneck...

disqard 4y ago
Yes, this was a core architectural requirement of Stadia (running the games on Linux), as opposed to hosting virtualized Windows machines (which would've allowed serving up Windows-based games). Whether this specific design choice alone killed Stadia, no one can say -- but it was probably one of the most important factors in its demise.
- verdverm 4y ago
  Input lag and pixelated graphics is why I quit, I had gigabit fiber at the time
  - dijit 4y ago
    Likely it was caused by your computer and browser not playing nice with x265 hardware decoding, I used to run the gamelet on the same network as my desktop and would get the same on some configurations. Frustratingly, it was not easy to know at a glance that this was what was happening, but there were times (many times, actually) where my chromecast ultra at home was performing much better with Stadia than my gaming PC
  - ljusten 4y ago
    I got the same when I was running Stadia on a 2.4 GHz wifi network. Once I switched to a wired connection, it worked like a charm. 5 GHz supposedly works as well, but my robot vacuum cleaner needs a 2.4 GHz network facepalm.
    - baq 4y ago
      I have a PV inverter which doesn't work if there's more than one AP with the same SSID and is 2.4GHz only... ended up buying an el-cheapo AP and giving it a unique name. PITA

geokon 4y ago

This might be a dumb question.. but when I read this "scp always copies full files, there is no "delta mode" to copy only the things that changed, it is slow for many small files, and there is no fast compression." my thinking was: If you want to send diffs.. why not just use git? It does compression and chunks and all that. Maybe the defaults perform poorly for binary files? But couldn't you fix that with a custom diff algo? (if it's somehow not appropriate, it'd still be nice to port whatever secret sauce they use here to git..)

deathanatos 4y ago
I'm sort of in the same boat, but with the sentence, > To help this situation, we developed two tools, cdc_rsync Why not use rsync? (It does seem they ended up faster than rsync, so perhaps that's "why", but that seems more like a post-hoc justification.) The "we use variable chunk windows" bit is intriguing, but the example GIF sort of just pre-supposes that the local & remote chunks match up. That could have happened in the rsync case/GIF, but that wasn't the case considered, so it's an oranges/apples comparison. (Or, how is it that the local manages to be clairvoyant enough to choose the same windows?)
- mindwok 4y ago
  I was wondering the same thing. It isn't explicit in the write-up but it's because rsync does not have a native Windows implementation, only rsync under Cygwin, so they developed this to achieve the same thing except it turned out faster than rsync.
  - int_19h 4y ago
    MSYS2 has rsync. Unlike Cygwin, I would consider that native.
- ljusten 4y ago
  >> Or, how is it that the local manages to be clairvoyant enough to choose the same windows? Yes! In content defined chunking, the chunk boundaries depend on the content, in our case a 64 byte window. If the local and the remote files have the same 64 byte sequence anywhere, and that 64 byte sequence has some magic pattern of 0s and 1s, they will both have chunk boundaries there. A chunk is the range of data between two chunk boundaries, so if N consecutive chunk boundaries match, then N-1 consecutive chunks match.

up2isomorphism 4y ago

This also has been discovered long time ago by many people including myself for a backup system.

LarryMullins 4y ago

Always interesting to see the sort of tangential projects that get rolled into the budget of larger projects at companies like Google. Funding the development of yet another file transfer utility, interesting as this one is, definitely wasn't necessary.

remus 4y ago
> Funding the development of yet another file transfer utility, interesting as this one is, definitely wasn't necessary. Interesting you say that as I thought they explained their motivation pretty clearly. Is there a tool they missed that already does the job?
- LarryMullins 4y ago
  I think most companies would have used an off the shelf solution and expected devs to simply deal with the inefficiency.
  - Tor3 4y ago
    For devs it's only inconvenient and annoying, but for the devs' company the inefficiency means money. At our company we were almost all of us working remotely during the pandemic (and many still do), and anything which slowed down or made a developer inefficient was looked at and improved on where possible. Because it's about (though not only about) money.

deanCommie 4y ago

> At Stadia, game developers had access to Linux cloud instances to run games. Most developers wrote their games on Windows, though. Therefore, they needed a way to make them available on the remote Linux instance. Am I reading this right that onboarding your game to Stadia as a developer involved essentially rsyncing data directly to a Linux cloud instance? That's.....

ljusten 4y ago
Just the compiled and baked game, not your sources. You still developed on Windows or wherever, the cloud instance was just used for running the game.

c7b 4y ago

Slightly OT, but I like the schematic gifs used in the Readme.md (pretty amazing doc overall!) like this one [0]. Does anyone have suggestions what tools they might have used (or might be used in general) to create those? [0] https://github.com/google/cdc-file-transfer/blob/main/docs/linux_rsync_animation.gif https://github.com/google/cdc-file-transfer/blob/main/docs/l...

yellow_lead 4y ago
Maybe just draw.io plus Photoshop or some gif generator. The gifs don't look very complicated
ljusten 4y ago
We used an internal Chrome extension to capture the gifs. There also seem to be some externally available GIF capturing tools, like https://chrome.google.com/webstore/detail/chrome-capture-screenshot/ggaabchcecdbomdcnbahdfddfikjmphe?hl=en https://chrome.google.com/webstore/detail/chrome-capture-scr... (disclaimer: I haven't tried those). We then used https://ezgif.com/optimize https://ezgif.com/optimize to remove dupe/unwanted frames, tweak timings and compress the gif. The actual content was done in Google Slides.
- c7b 4y ago
  Awesome, thanks for replying here! If I may be greedy: I suppose you used something else for capturing the command prompt gif?
  - ljusten 4y ago
    Nope, luckily we still partially work from home and use Chrome Remote Desktop. The command prompt was running on my Windows machine, which I accessed remotely, so I could capture it with the extension. That wouldn't have worked if I had been in the office that day.
r4kbY44D 4y ago
ImageMagick does the trick, for example `convert -delay 20 -loop 0 *.png out.gif`

roydivision 4y ago

This would be interesting applied to local file copy, for instance for some backup strategies where large files change slightly.

ljusten 4y ago
This is currently being worked on, see https://github.com/google/cdc-file-transfer/compare/main...sync_windows https://github.com/google/cdc-file-transfer/compare/main...s...

worldsavior 4y ago

Why is it only from windows to Linux?

ljusten 4y ago
That's because most Stadia devs used Windows, but the cloud instances ran on Linux, so devs had to copy their games from Windows to Linux. We're currently adding support for Windows to Windows as well.
- jamespo 4y ago
  And linux to linux?
  - aembleton 4y ago
    We also ran the experiment with the native Linux rsync, i.e syncing Linux to Linux, to rule out issues with Cygwin. Linux rsync performed on average 35% worse than Cygwin rsync, which can be attributed to CPU differences. Source: https://github.com/google/cdc-file-transfer https://github.com/google/cdc-file-transfer
    - ssth 4y ago
      I suspect that author made comparison using windows box and linux box with "cpu difference" because those 2 have different spec.
- worldsavior 4y ago
  But why not make cross platform? If already creating a file transfer program, make it cross platform. What're the complications?
  - aembleton 4y ago
    It does do Linux to Linux as that's covered by the Readme. For anything else, I guess it didn't fill the scope of what was needed for Stadia

tmchow 4y ago

1. I thought this was going to be something about the Center for Disease Control 2. This is a really neat project, and super expensive ashes to rise from Stadia. 3. This is targeted at Windows to Linux, but given the speed advantages that it has over rsync couldn’t this be Linux to Linux? That said, I’d be afraid to use this over rsync just from the body of experience and knowledge that exists about rsync.

rsync 4y ago
"I thought this was going to be something about the Center for Disease Control" I thought cultdeadcow. Tool for transferring t-files.
tga_d 4y ago
I was thinking something similar to your third point, though more for cdc_stream, since as of last year sshfs is no longer maintained anyway.

xearl 4y ago

Is there any chance to get this faster sync algorithm into rsync itself?

ljusten 4y ago
The same question was asked here: https://github.com/google/cdc-file-transfer/issues/56 https://github.com/google/cdc-file-transfer/issues/56

Dowwie 4y ago

Could this serve as a general-purpose protocol that all remote development would benefit by using?

sirjaz 4y ago
Only if it could go the other way. Everyone seems to forget about Windows/Windows Server. 80%+ Desktop, and 55%+ Server(Include on-prem 70%+, Cloud 50%) Market Share.

didgetmaster 4y ago

One of the biggest problems with extremely large files is how a simple insert or delete near the front of the file causes all bytes following it to be shifted and re-written to disk. Add 3 bytes to the beginning of a 50 GB file and you are writing 50 GB to disk. I have been implementing a file system replacement project for several years. It is designed to handle hundreds of millions of files within a single container; put contextual meta-data tags on them; and enable lightning fast searches for things based off file type and/or tags. (https://www.youtube.com/watch?v=dWIo6sia_hw https://www.youtube.com/watch?v=dWIo6sia_hw) One of the ideas (not yet fully implemented) was to break up large files at the file system level. You might have a 50 GB file of data that looks exactly like a normal file to any application accessing it, but in reality it might be 10 separate chunks of 5 GB each. If you add or delete any bytes within any individual chunk, it only adjusts that specific chunk. For example, deleting 100 bytes at offset 6 GB causes the second chunk to shrink by 100 bytes. All the chunks following it are unaffected. The file still looks to be 100 bytes smaller to the application, but it doesn't realize that a chunk in the middle was just reduced in size instead of all the bytes after the change being shifted down. This feature would also make it easier to copy large files from one system to another. Data could be transferred one chunk at a time. If the copy was interrupted, only missing chunks would need to be copied when the process was restarted.

themaninthedark 4y ago
I know that BitTorrent has to allocate all the space before it downloads but would that be a good base to start with?
- nicolaslem 4y ago
  This is also how Restic works, changing a few bytes in a 50 GB file won't reupload 50 GB of data unlike most backup solutions that work primarily with files.
  - didgetmaster 4y ago
    This change would not be just be for backups or file transfers. It would fundamentally change how big files are stored by the file system. Much like the way fragmentation is handled solely by the file system and an application accessing the file is completely unaware if the file is stored within a single fragment or multiple fragments; the file system would manage the individual 'chunks'. For example, a 6 GB file might be made up of 3 separate 2 GB chunks. An application might delete 20 bytes from the front of the file. This causes the first chunk to now be 2 GB - 20 bytes. The other 2 chunks are unchanged. Current file systems do not allow this where a file can have a block somewhere in its interior that is just a partial block.

rsync 4y ago

What is required on the server (linux) side ? I see how you put together the two .exe files but what is required on the linux side of things ?

Ciantic 4y ago

I can't find any mention of rclone [1]. It would be intersting to know how this compares to rclone copy or sync, because it uses threading, rsync doesn't. [1]: https://rclone.org/ https://rclone.org/