1

I've been asked to design folder-like structure (in java, but I expect this solution to be language agnostic). There is one root, just like / on linux. Then, it can have almost indefinitely nested folders and files inside. Now, here's the catch: I have to be able, to track some of file details, like size, on every level. For example, user may want to know, how many files are in Folder 2, and what is their size. To do that, system needs to take every file in Folder 2 (so in this example that would be File5 and File 6), take every folder in it (Folder 4), and every file in Folder4. Folder 4 can have its own nested folders, and they can have more nested folders and files in them as well. Realistically, max level of nested folders will be around 32.

My question is, how to design a system like that? I know I cannot calculate this on the fly. There are just too much data, and user would have too wait for too long. So, I think, there is a necessity to store additional information in folders. Then, they have to be updated every single time a file is changed, and information would have to be propagated up to the root folder. If that changes anything, I'll be using cassandra as database storage.

raw schema

  • 4
    You're not really asking about a data structure, but about an algorithm: "How do I cache cumulative values stored in a tree?" As it stands, I can't see why the obvious "whenever you change a relevant value in a node, update all its ancestors" strategy wouldn't work. – Kilian Foth Jan 10 at 11:13
  • @KilianFoth You're right, my bad. Thank you very much for formulating a question - it yields better google searches than mine :) – Dargenn Jan 10 at 11:16
6

I know I cannot calculate this on the fly. There are just too much data, and user would have too wait for too long.

How long will the user have to wait for? From what number of nested levels and/or number of files will it become "too long" to wait? What is the expected regular usage of this system, is that going to yield waiting times that are too long?

I think you're doing premature optimisation. First figure out the in-memory data structure, how you'll store it in the DB, what the algorithms are to calculate the necessary metadata and go build that. When you have it working, make some measurements on how long it takes to calculate on the fly and think of optimizing it: maybe you will use caching, maybe you can optimize the algorithm or maybe it will turn out that it's actually not a problem.

Of course, you will make your life easier if you build it in such a way that the logic for grabbing this folder-level metadata can be easily and dynamically swapped out: either querying a cache or straight up running the algorithm or any other yet-to-be discovered future strategy.

Lastly, you should try to not reinvent the wheel. We have been building file systems and tools around them for decades - you should look for some open source tools and see how they approached these issues.

3

This is much more complicated problem that it seems on first sight. I think you should first analyze write and read usages of the requiremens and "quality" of metadata you expect.

If you are writing/updating/deleting files and only check the metadata ocasionally, then calculating the metadata on-demand might be best option. Maybe some caching is possible.

If you are checking the madata more often that changing the files, then changing the metadata when the files change might be best option.

If you are fine with having "stale" metadata, then some kind of asynchronous metadata calculation might be possible. Just mark folder up to the root as "stale" and have periodic recalculation routine that finds stale folders and update's it's metadata. The client also has option to either work for stale metadata or wait for metadata to be fresh. Also, when you start messing with asynchrony, be careful of possible race condtions as one part might want to mark folder as stale, while other is marking it as "done". Maybe have "last change time" flag to tell if the change should be applied.

Another question is locality of changes. Do you expect changes to be concentrated in small area in a timeframe, of are changes distributed equally across all files and folders? If they are local, then some kind of batching of changes might be helpful. This might be best when combined with ability to mark data as stale. If locality is big, then caching is great option.

  • 1
    There are definitely more writes than reads. I expect load in every folder to be more or less equal, so changes should be distributed evenly. – Dargenn Jan 10 at 13:15
0

In your file table, have a folder attribute which is the full path to the folder containing the file.

folder: /path/of/folders/
filename: my_file.txt
size: 2346
modification_date: 1/1/1970

Now you can find the total size of a folder with a query like:

SELECT sum(size) FROM file WHERE startswith(folder, '/path/of/')

This way you avoid having to query for the contents of a folder, then the contents of subfolders, etc. etc. I suspect it will be enough for your purpose.

If not, you can use the same trick to more efficiently update metadata

UPDATE FOLDER SET size = size + delta WHERE startswith(file_folder_path, path)

I don't know Cassandra and how its limitation would work on this. But for a generic database solution, this would make sense as an approach.

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.