Brainstorm: manifest for ~100k files

Can you reliably bundle sets of the files (changesets or versions perhaps)? Even with the hashing lookup, iterating over 100k of them is going to be a hindrance.

Another option depending on your environment/requirements is to generate some change record whenever a new version of a file is added. As the clients update, remove the updates from the queue. Instead of checking 100k each time, the client just gets the un-processed change records (or one merged delta if it's feasible). More data, more updates to some DB, but if your clients check in often but update rarely (and rarely get out of sync with the servers) it might be better.

I dunno, seems like there's a bit of nuance or requirements here that is missing, but hopefully some of the brainstorm helps.

Before I even start, why the heck do you need to synchronize over 100k files? I dont think I even have that many files on my computer?!? I only see a way to ease the pain, because with that many files there will be pain still!!!

The problem with trying to maintain files synchronized like this is how do you delete old files on clients computers. It would be terrible if there were a bunch of dangling files not used sitting in the clients directory where your program is stored. So, you need a way to store the CHANGES that occur from some given point so that the client can follow those changes, i.e. delete oldnotusedfile.txt. The only changes should be deletions, you do not need support for renaming, because renaming should be a delete followed by an insert to make it easy. So, you need to store the inserts / deletes that occur, but you also don't want clients downloading a file only to delete it later on because in version 1.0, the file was created, then in version 2.0 the file was deleted. This wastes your time and theirs. So, the system also needs to be able to correctly remove any place where a file was inserted, then later on deleted, and then delete this file from the server too (keep your server clean!).

There should be two manifest files only on the server, one called: oldmanifest and the other uptodatemanifest.
What I see if that each time a new revision comes out, create a new manifest file (for now, call this newmanifest), but only store the changes that occrured from the uptodatemanifest (at the beginning there will be no changes). Then, take the uptodatemanifest and merge it with the oldmanifest(the result of the merging should be stored in oldmanifest. At the beginning, there will be no changes), cleaning it to prevent any insert and delete of the same files so it is as lean as possible. Then rename newmanifest to uptodatemanifest. So, now oldmanifest contains all of the changes that have occurred, and uptodatemanifest containes only the changes between oldmanifest and the uptodate one.

Now, this will work well if most of your clients keep themselves up-to-date as they will only be downloading the uptodatemanifest; however, if many clients go a few versions behind, then update, they will be downloading the BIG oldmanifest, which is where ALL the changes are stored. You can deal with this by keeping like 5 or 6 of the small change manifest files in between the uptodatemanifest and the oldmanafest as a kind of buffer. So, when a client connects to update, he checks the uptodatemanifest which should have the version, say 3.123, and he compares that will his version 3.100, so the client then gets the previous manafest file until it is .001 greater than his current version or he gets the oldmanfest file in which case, he downloads the big one and gets up-to-date there. Then starts from there until he reaches the uptodatemanifest at which point he is up-to-date.

This way, the oldest files that need to be kept on the server are the ones from the version kept in oldmanifest, and you shouldn't have clients hammering your server with file requests.

Thats about it.

Let the Shoooting bein!

"Old versions of the files need to be available so that outdated clients can patch their way up to current; this is already supported via a delta system but needs to be integrated into a larger architecture. Essentially, I need to generate a manifest of all the files, update this manifest live when files change on an authoritative server, and distribute the manifest (and accompanying files) on demand to clients as they patch up to current."


Use Mercurial or Git?

Can you reliably bundle sets of the files (changesets or versions perhaps)? Even with the hashing lookup, iterating over 100k of them is going to be a hindrance.

Another option depending on your environment/requirements is to generate some change record whenever a new version of a file is added. As the clients update, remove the updates from the queue. Instead of checking 100k each time, the client just gets the un-processed change records (or one merged delta if it's feasible). More data, more updates to some DB, but if your clients check in often but update rarely (and rarely get out of sync with the servers) it might be better.

I dunno, seems like there's a bit of nuance or requirements here that is missing, but hopefully some of the brainstorm helps.

There'll be some bundling steps; notably, major versions will have all the individual files packed into a single bundle file which is delta'd out to patch up to minor versions. Only major version changes would require more than a delta of the bundle, and even then, that's a very unlikely situation (the vast bulk of the time deltas are sufficient).

The manifest deltas help here as well; it's basically what you suggest with the change queue. The authoritative servers generate a delta from any given manifest version to the current, up-to-date version, and then clients can compare and fetch only the files listed in the manifest delta. Of course for each individual file another set of deltas is used to ensure that minimum data actually goes over the wire.

Clients desyncing with an authoritative server will be fairly rare.

And yes, I'm purposefully being vague on some of the details :-)

Before I even start, why the heck do you need to synchronize over 100k files? I dont think I even have that many files on my computer?!? I only see a way to ease the pain, because with that many files there will be pain still!!!

It has to be done. Trust me.

The problem with trying to maintain files synchronized like this is how do you delete old files on clients computers. It would be terrible if there were a bunch of dangling files not used sitting in the clients directory where your program is stored. So, you need a way to store the CHANGES that occur from some given point so that the client can follow those changes, i.e. delete oldnotusedfile.txt. The only changes should be deletions, you do not need support for renaming, because renaming should be a delete followed by an insert to make it easy. So, you need to store the inserts / deletes that occur, but you also don't want clients downloading a file only to delete it later on because in version 1.0, the file was created, then in version 2.0 the file was deleted. This wastes your time and theirs. So, the system also needs to be able to correctly remove any place where a file was inserted, then later on deleted, and then delete this file from the server too (keep your server clean!).[/quote]

That's actually trivially easy and handled by the manifest system and the delta patcher. I wish that just syncing two folders worth of files was the limit of the challenge, because that's an easy problem to solve.

There should be two manifest files only on the server, one called: oldmanifest and the other uptodatemanifest.
What I see if that each time a new revision comes out, create a new manifest file (for now, call this newmanifest), but only store the changes that occrured from the uptodatemanifest (at the beginning there will be no changes). Then, take the uptodatemanifest and merge it with the oldmanifest(the result of the merging should be stored in oldmanifest. At the beginning, there will be no changes), cleaning it to prevent any insert and delete of the same files so it is as lean as possible. Then rename newmanifest to uptodatemanifest. So, now oldmanifest contains all of the changes that have occurred, and uptodatemanifest containes only the changes between oldmanifest and the uptodate one.[/quote]

Doesn't work. I need clients to be able to patch from an arbitrary version of the old data. Assuming that all clients are always up to date is a major no-no.

Now, this will work well if most of your clients keep themselves up-to-date as they will only be downloading the uptodatemanifest; however, if many clients go a few versions behind, then update, they will be downloading the BIG oldmanifest, which is where ALL the changes are stored. You can deal with this by keeping like 5 or 6 of the small change manifest files in between the uptodatemanifest and the oldmanafest as a kind of buffer. So, when a client connects to update, he checks the uptodatemanifest which should have the version, say 3.123, and he compares that will his version 3.100, so the client then gets the previous manafest file until it is .001 greater than his current version or he gets the oldmanfest file in which case, he downloads the big one and gets up-to-date there. Then starts from there until he reaches the uptodatemanifest at which point he is up-to-date.

This way, the oldest files that need to be kept on the server are the ones from the version kept in oldmanifest, and you shouldn't have clients hammering your server with file requests.

Thats about it.

Let the Shoooting bein!
[/quote]

Closer, but still not quite practical. There may be up to 50 old versions (possibly even more) that have to be tracked reliably at any given time, before the oldest version is officially end-of-life.

Use Mercurial or Git?

Demanding that all of our users learn a DVCS is laughably unfeasible.

In your quote of

Doesn't work. I need clients to be able to patch from an arbitrary version of the old data. Assuming that all clients are always up to date is a major no-no.

The method I mentioned allows clients to update from any version because the oldmanafest file would hold all of the changes that they need to make in order to become up-to-date. I never mention assuming the clients are always up to date. There wouldn't be a point in an update system then because everyone would be up to date.... .. . .


And there also wouldnt be a problem keeping 50 old versions on the server before it ended its life cycle. You need to keep 50 delta manafest files which is no problem, instead of only 5 or 6. Then as you update, you move up the oldmanifest file by consuming the oldest manifest delta file.

Imagine storing the delta manifest files in an array. Create your array at a size of 50, then when you want to create a new manifest file because a new version comes out, you take the OLDEST two manifest files, and merge them, then shift down all the other manifests. Then you insert the new manifest at the top of the array. This way you keep a bunch of small manifests for the 50 revisions, but there is the BIG maamma manifest which contains ALL the changes needed to make the client up-to-date at the end of the array.

When clients connect to get up-to-date, they first check the latests manifest and compare their versions. From there they can continue to go back through the array until they hit either then END of the array (which has the oldest manifest and ALL the changes needed to bring it up to date), or they hit their current version, which means this is the clients start point to begin updating from.

The BIG old manifest file should also be keep sorted somehow so when it is merged, the merge operation can happen quickly and it can also clean it up to remove any paired insert/removes

[quote name='Telastyn' timestamp='1308339329' post='4824573']
Can you reliably bundle sets of the files (changesets or versions perhaps)? Even with the hashing lookup, iterating over 100k of them is going to be a hindrance.

Another option depending on your environment/requirements is to generate some change record whenever a new version of a file is added. As the clients update, remove the updates from the queue. Instead of checking 100k each time, the client just gets the un-processed change records (or one merged delta if it's feasible). More data, more updates to some DB, but if your clients check in often but update rarely (and rarely get out of sync with the servers) it might be better.

I dunno, seems like there's a bit of nuance or requirements here that is missing, but hopefully some of the brainstorm helps.

There'll be some bundling steps; notably, major versions will have all the individual files packed into a single bundle file which is delta'd out to patch up to minor versions. Only major version changes would require more than a delta of the bundle, and even then, that's a very unlikely situation (the vast bulk of the time deltas are sufficient).

The manifest deltas help here as well; it's basically what you suggest with the change queue. The authoritative servers generate a delta from any given manifest version to the current, up-to-date version, and then clients can compare and fetch only the files listed in the manifest delta. Of course for each individual file another set of deltas is used to ensure that minimum data actually goes over the wire.

Clients desyncing with an authoritative server will be fairly rare.

And yes, I'm purposefully being vague on some of the details :-)
[/quote]

Indeed, and not altogether unexpected.

If you're forcing the manifest to be sync'd first why the CRCs? The sync process would trigger, then the client would identify what files are out of date and send the direct request to URL, maybe with a querystring or restful request based on the filename, start version and target version; gets a delta (or redirect to whole file if needs be). And really, if you control the filenames, couldn't you provide a perfect hash for them (or simply send along IDs with the manifest)?

*snip*

OK, that's a bit clearer of an explanation... but I don't see how it really fundamentally improves on what I'm suggesting anyways? It seems like you introduce an arbitrary cap on old versions by having your "base" changelist when I can allow any number of old versions and chain between any arbitrary pairing of versions using intelligent delta generation.

If you're forcing the manifest to be sync'd first why the CRCs? The sync process would trigger, then the client would identify what files are out of date and send the direct request to URL, maybe with a querystring or restful request based on the filename, start version and target version; gets a delta (or redirect to whole file if needs be). And really, if you control the filenames, couldn't you provide a perfect hash for them (or simply send along IDs with the manifest)?

The client might have locally modified files which should be permitted, but when a sync to master is triggered, I need to replace them with master versions of the files from the authoritative server. This means that the client has to be in charge of what files it pulls beyond just what's listed in the change manifest, i.e. it has to compare its own local change set with the change set from the authoritative source, and replace any files that can't be delta'd based on the change manifest.

Blergh, that's confusing :-D

Anyways... we could potentially just assign monotonically incremented IDs for every file name, but that requires a lookup to go from filename -> ID. If we use a CRC32 of the filename instead, even with the presence of collisions, we have O(1) computation of a file's "compact" ID plus minor chaining overhead for the rare case when chaining is really needed (at which point we just decay to canonical filenames anyways).

Part of the complication here is we're trying to transition away from using monotonically allocated IDs and towards using canonical filenames as much as possible, but we have to support both approaches in the interim.


Whew. My brain hurts.

I gather that you're going to detect locally modified files by looking at the manifest then (and thereby only dealing with manually patched files)? Generating delta for unknown local changes seems impossible given the system as described.

Why not use a cloud file hosting like DropBox or something and stick all the files on there. DropBox or any other cloud file hosting will do the hashing and updating for you and in addition they will keep usually 10 versions of that file (maybe unlimited for paid accounts).. Essentially your replicating their service, maybe there is a enterprise level service where they have better admin oversight on who gets access.

My guess is use the cloud file hosting with read only access and custom fronted for committing changes, merging and checkouts basically acting like a CVS..


Good Luck!

-ddn

I gather that you're going to detect locally modified files by looking at the manifest then (and thereby only dealing with manually patched files)? Generating delta for unknown local changes seems impossible given the system as described.

Local changes will be monitored by an app that generates a local changelist. This changelist is compared to the master changelist from the authoritative server on sync. Any discrepancies are resolved manually, based on user preferences: either the authoritative version overrides local changes, or not - for all files in the current changeset. Fairly straightforward.

Why not use a cloud file hosting like DropBox or something and stick all the files on there. DropBox or any other cloud file hosting will do the hashing and updating for you and in addition they will keep usually 10 versions of that file (maybe unlimited for paid accounts).. Essentially your replicating their service, maybe there is a enterprise level service where they have better admin oversight on who gets access.

My guess is use the cloud file hosting with read only access and custom fronted for committing changes, merging and checkouts basically acting like a CVS..


Good Luck!

-ddn

Because using someone else's hosting is not an acceptable solution. Same reason we can't be using GitHub for all this.

Believe me, I'm not ignorant. I know about these solutions, and they are not going to cut it. We have very specific requirements that can't be satisfied with off-the-shelf products, including security concerns, which obviously I can't detail.

In the system I'm working with, we simply have multiple manifests.

Each manifest only contains references to the *current* fileset (about 6000 files) and does not include previous versions. The total CDN size is ~250K files.

Each manifest filename is hashed, and then there are also 'named' manifests (such as "latest" or whatever) which get overwritten as we push new builds. The hash-named manifests remain immutable.

For your distribution system, you could have a client update itself by comparing its current manifest to the new manifest if just downloaded, download new files and delete removed files.

Rsync?

I'd just drop the whole manifest approach (thereby eliminating several possible failure modes) and use rsync. Also gets rid of the need to keep old files around, while still keeping bandwidth costs for a client update proportional to the staleness of their version.

Seems like a solved problem to me...

Any suggestions for better options?

Packaging the files in a single versioned auto-installable file?

Based on the responses so far, that doesn't sound like an option.

Based on the responses so far, that doesn't sound like an option.

To be honest I'm having a hard time trying to understand the whole thing. He has a lot of files hosted with manifests and clients download them how? I'm guessing it's through some propietary client application... but I'm not sure O_o

To be honest I'm having a hard time trying to understand the whole thing. He has a lot of files hosted with manifests and clients download them how?
[/quote]

An educated guess based on his new job, I'd presume this involves updating the various nodes in a cluster (or distributed instances) of MMO servers. When someone tweaks a map, model or a AI script or a drop pattern, that needs to be pushed out to all of the machines (or sent to the machines when they check-in). And I suspect the files are fairly large, hence the push for deltas everywhere. The download sounds like a simple web get at a virtual file system.

"Demanding that all of our users learn a DVCS is laughably unfeasible."

That's your value-add -- meaning they don't have to.

Why don't you just tell us what the problem actually is instead of this secrecy act?

Because it's a security issue, and wrapped in several layers of NDAs which I'm probably stretching just by posting the thread.

[quote name='Katie' timestamp='1308344766' post='4824610']
Use Mercurial or Git?

Demanding that all of our users learn a DVCS is laughably unfeasible.
[/quote]

But you can script git or Mercurial and/or embed client libraries in your application very easily; you only need the simplest basic commands (in particular, clients have read-only access).
Expert users might enjoy read-only web interfaces or the like, but the most your users would have to learn is their own user credentials and which TCP/IP ports need to be open.

Suppose a client wants to update from version X to (newer) version Y.

1. The client has a local repository containing version X and all older ones.
2. Pull version Y from your central repository; now you have a repository containing version Y and all older ones. In Git, this is a compact patch, coming in a single file; beware the Subversion approach of several auxiliary files and separate HTTP requests for each file in the working copy.
3. Create a working copy containing files from version Y.
4. With the version Y working copy, update/reinstall the application. Note that what you store in the repository needs not be what ends up in the installed application; you might be able to rebuild or decompress something cleverly to save even more space.
5. Optionally delete the version Y working copy (keeping only the version Y repository).

Obviously, rollback to an old version would be extremely simple: it's already there in the client's repository.
Initial installation can be bootstrapped after cloning from scratch a new repository containing the version to be installed.
If you really dislike the disk space waste of keeping around deltas for all old versions, you can occasionally switch clients to a new repository that doesn't contain them.