5 ms·
> Is there a real fundamental difference between the two approaches? Yes. With true directories, you can implement directory rename() with O(a+b) time complex
by jude- 12y ago
> Is there a real fundamental difference between the two approaches?
Yes. With true directories, you can implement directory rename() with O(a+b) time complexity, where a and b are the depths of the paths to the directories. With a flat key/value store, directory rename() requires at least O(n) time complexity for n directory children, since each child must be renamed.
- alayne 12y agoIs directory rename an operation that needs to be efficient though? Probably not.
- sysk 12y agoEfficiency is important if the operation needs to be atomic though. POSIX for example requires rename to be an atomic operation. http://en.wikipedia.org/wiki/Rename_(computing) http://en.wikipedia.org/wiki/Rename_(computing)
- alayne 12y agoThere"s no efficiency requirement on atomicity. Who said we need POSIX filesystem semantics anyway? Is it so important we should trade scalability? Obviously that wasn"t the s3 design choice.
- mateuszf 12y agoFilesystems users (developers) already assume that renames are fast. Changing the mode now would mean that some of the applications would seem like blocked or could behave strangely. S3 users already know and should handle that.
- deleted 12y ago[deleted]
- TheCoelacanth 12y agoIt would require rethinking the data structure used to store it to make it work efficiently. A trie-like structure would probably work.
- jude- 12y agoI'd be curious to know how to make it more efficient. Either the descendants of a directory include the directory's name in their identifier, or they don't. If they do, then to implement rename() you need to do something such that all descendants of the directory can be queried by a different identifier than the one they were given upon creation (where the difference is exactly the name change of an ancestor directory). You can: * rename all descendants on directory rename (expensive--takes O(n) time for n descendants). * log each rename() and translate a key with a new directory name into a key with the original directory name (requires O(k) space for k renames and O(d) time in the worst case for translating a path of depth d whose directories have all been renamed; introduces the need to garbage-collect log records when all descendants of a renamed directory get deleted). Granted, this is a more nuanced than what I said before about rename() requiring O(n) time complexity when implemented on top of a key/value store, but the second option is still more costly than rename() with true directories. I'm not sure (but cannot prove at this time) that we can do better than the second option above, but would love to hear your thoughts.
- TheCoelacanth 12y agoI'm not debating that it's inefficient if you use the same data structure that is used now. That's why I suggested using a different one. Instead of a flat list of file names for each directory, you store the file names in a trie, so that files with a shared prefix in their name have a shared ancestor node in the trie. To do a directory rename, you just have to find the node in the trie that corresponds to the directory, move that node to a different location in the trie and change the portion of the name that is stored in that node.
- JadeNB 12y ago> Instead of a flat list of file names for each directory, you store the file names in a trie, so that files with a shared prefix in their name have a shared ancestor node in the trie. But then, if they behave like directories, and the software treats them like directories, aren't you effectively implementing directories in everything but name? (I mean, of course current software doesn't actually treat directory names this way; but it seems like changing the data structure is going a long way to maintain a directory-less fiction.)