File Fragmentation

Files are considered fragmented when they aren’t laid out in a continuous chunk on disk. This causes extra seeks even if the file is being read sequentially.

I was discussing startup over dinner, someone asked about how much of an issue fragmentation is in Firefox.

Early on I decided to pretend that fragmentation does not exist as we had bigger fish to fry. We were opening too many files on startup, effectively causing our own high-level fragmentation. Luckily, that problem should be mostly solved in Firefox 4 once omnijar and fat xul bugs land (unfortunately, extensions can cause similar issues until we stick em into a single file).

To measure fragmentation I used my SystemTap script to get a list of files opened (one could also use strace or any similar tool) and piped the results to filefrag. Filefrag is a Linux fragmentation-measuring utility. On Windows one can use contig and Mac OS X features hfsdebug. I’m using ext4 on Linux.

My top offenders were:
places.sqlite: 34 extents
cookies.sqlite: 18 extents
XPC.mfasl: 11 extents
Cache/_CACHE_003_: 11 extents
urlclassifier3.sqlite: 6 extents
Cache/_CACHE_002_: 6 extents
Cache/_CACHE_001_: 6 extents
XUL.mfasl: 5 extents
formhistory.sqlite: 5 extents
content-prefs.sqlite: 4 extents
libxul.so: 4 extents
signons.sqlite: 3 extents
icon-theme.cache: 2 extents
libatk-1.0.so.0.2809.1: 2 extents
libflashplayer.so: 2 extents
Cache/_CACHE_MAP_: 2 extents

I did an informal poll of my friends and it seems that the order of fragmentation is similar among them, only the magnitude differs. For example, XFS tends to be 10-20 times more fragmented than ext4 :). I don’t have any numbers for HFS+, but I suspect XFS takes the crown as most fragmentation-prone filesystem to run Firefox.

Interestingly, my friend running NTFS reported similar fragmentation to ext4. That was disappointing as Windows Prefetch supposedly defragments files used with the first 10 seconds of startup. Clearly, isn’t keeping up in this case.

Preliminary Conclusions

places.sqlite is the largest and most performance-critical file in Firefox. It contains browser history and bookmarks. It is the brains behind the AwesomeBar.The fact that it is severely affected by fragmentation significantly impacts Firefox responsiveness. There are no easy fixes for fragmentation there. mak suggested moving history to a separate file to mitigate this, but that isn’t an easy change.

In contrast, cookies.sqlite is tiny(<1mb for me) and probably so fragmented due to cookie expiration. I am guessing that easiest workaround here is to write a new sqlite file every time there is a mass update to the file.

urlclassifier.sqlite is a large file that may be mitigated similarly to cookies.

SQLite 3.7.0 came out today which features WAL logging, which may reduce fragmentation (or make battling it easier). In general, sqlite’s VACUUM (used to clean and compact the database) command does not help with fragmentation, we really need to be doing something like hot backup which would create a new database file every VACUUM.

Our cache code is ancient and sucks. The cache files get fragmented immediately and severely. They are accessed in insane patterns and they get laid out insanely on disk. There are some efforts to improve the code, but I suspect that’s equivalent to putting lipstick on a pig.

*.mfasl files are due to be obsoleted by a startup cache jar. It may get less fragmented. Should be a straight-forward fix it if it does get fragmented.

I’m disappointed to see the .so files get fragmented. This might be an ext4 bug or has something to do with how the updater works (both ours and yum on Fedora).

Further Work

I would like to see more data on fragmentation on Windows/OSX. Feel free to leave a comment with fragmentation numbers for cache, mfasl, sqlite and .dll files in your Firefox. We should look into online defragmentation APIs in modern OSes.

Workarounds?

Easiest way to fix fragmented files is to make a copy of the original file, delete the original and then rename the copy. This works on sane filesystems, apparently it doesn’t work too well on OS X.

29 comments

  1. Robert O'Callahan

    My MacOS profile:
    places.sqlite: 94 extents
    downloads.sqlite: 5 extents
    cookies.sqlite: 2 extents
    cert8.db: 2 extents
    formhistory.sqlite: 3 extents

  2. Everything over 50 extents, using Chris’s script:
    /home/source/build/trunk/browser/toolkit/library/libxul.so: 417
    urlclassifier3.sqlite: 351
    Cache/_CACHE_003_: 266
    /home/source/build/trunk/browser/js/src/libmozjs.so: 239
    places.sqlite: 218
    /home/source/build/trunk/browser/dist/bin/chrome/toolkit.jar: 176
    Cache/_CACHE_002_: 115
    Cache/_CACHE_001_: 89
    /usr/share/icons/gnome/icon-theme.cache: 80
    /home/source/build/trunk/browser/dist/bin/chrome/browser.jar: 77
    /home/jcranmer/.mozilla/plugins/libflashplayer.so: 72
    cookies.sqlite: 63
    /usr/local/lib/libgcc_s.so.1: 53
    /home/source/build/trunk/browser/nss/nss/libnss3.so: 53

    For the record, the partition that /home is on is pretty close to full (1.2G free).

  3. I remember two items from a “Linux FAQ for Windows users” when I first came in contact with Linux: at that time, ext2 was the “normal” Linux filesystem; journalising filesystems were a novelty, being talked about in various places, but not yet implemented other than as “test versions”. Here are the questions and answers:
    * Where’s the antivirus?
    — You don’t need one, there are no viruses on Linux.
    * Where’s the defragmenter?
    — You don’t need one, files don’t get fragmented on the ext2 filesystem.
    I never believed either answer, I just filed there under “other advice needed”.

    Today I just ran filefrag manually on my Reiser filesystem, in my SeaMonkey “default” profile (for a trunk version, Mozilla/5.0 (X11; U; Linux i686; en-US; rv:2.0b2pre) Gecko/20100701 Lightning/1.1a1pre SeaMonkey/2.1a3pre – Build ID: 20100701101320, supporting the “new” addons manager but “just not” requiring the new XPCOM registering procedure, and using Places for history but not yet bookmarks); then I sorted the results.

    filefrag -sx *.sqlite *.mfasl Cache/_* bookmarks.html

    Cache/_CACHE_003_: 290 extents found
    Cache/_CACHE_002_: 255 extents found
    Cache/_CACHE_001_: 181 extents found
    XUL.mfasl: 138 extents found
    places.sqlite: 107 extents found
    cookies.sqlite: 80 extents found
    XPC.mfasl: 61 extents found
    extensions.sqlite: 11 extents found
    Cache/_CACHE_MAP_: 10 extents found
    signons.sqlite: 9 extents found
    msgFolderCache.sqlite: 7 extents found
    global-messages-db.sqlite: 6 extents found
    formhistory.sqlite: 5 extents found
    permissions.sqlite: 5 extents found
    downloads.sqlite: 3 extents found
    bookmarks.html: 3 extents found
    content-prefs.sqlite: 2 extents found
    webappsstore.sqlite: 2 extents found
    urlbarhistory.sqlite: 1 extent found
    cleanup.sqlite: 0 extents found
    mandelbookmarks.sqlite: 0 extents found

  4. From a Windows XP machine:

    cookies.sqlite is in 30 fragments
    places.sqlite is in 9 fragments
    Cache\_CACHE_001_ is in 39 fragments
    Cache\_CACHE_002_ is in 49 fragments
    urlclassifier3.sqlite is in 34 fragments
    XPC.mfl is in 8 fragments

    Most are not fragmented or very low fragments (<5)

  5. cookies.sqlite: 7 fragments
    downloads.sqlite: 6 fragments
    extensions.sqlite: 4 fragments
    formhistory.sqlite: 18 fragments
    places.sqlite: 128 fragments

    for the roaming parts of my profile, 4.574 fragments/file average

    just about everything in the firefox bin dir is defragmented except for:
    mozjs.dll: 17
    mozsqlite3.dll: 9
    xul.dll: 125

    just about everything under components\ has 2 fragments
    chrome\browser.jar: 7
    chrome\en-US.jar: 3
    chrome\toolkit.jar: 4

    Also, you might find it annoying that Microsoft changed the meaning of fragmentation in Vista+ so that it depends on the size of the fragment. Supposedly this was done to match other file systems’ definitions.

  6. places.sqlite: 0 extents found
    cookies.sqlite: 0 extents found
    downloads.sqlite: 0 extents found
    cert8.db: 0 extents found
    formhistory.sqlite: 0 extents found

    Do I win? This is on a linux ZFS filesystem (on a RAID-Z pool), which apparently doesn’t answer that question correctly/meaningfully.

    You should find that there is correlation with free space as well as file size and filesystem type.

  7. Sounds to me like the easiest fix would be to just make SQLLite a lot more aggressive in allocating file space.

    Disk is cheap today, so
    (1) the first time the SQLLite DB is created, allocate a decent reasonable size
    (2) when the SQLLite DB is extended, make it way more aggressive about taking space i.e. just double up
    (3) Also make it less aggressive about freeing space when it does a VACUUM.

    That will probably dramatically reduce fragments because you aren’t asking the filesystem for another small piece every second day.

  8. The problem with fragmentation is that the more you use a filesystem, the more free blocks will be scattered all over the filesystem in small chunks. You may want to take a look at the e2freefrag output for your filesystem (should work for ext2,3 and 4).

    There might be a problem in ext4 code, though, because copying the 20MB libxul.so in my /usr partition fills 512K, 1M and 2M extents without touching the 4M, 8M and 16M extents that are unused, even if there are only a few. But maybe there isn’t because it may also try to keep all extents for a given file more or less gathered. It may be better to use 12 2M extents close together than 3 8M extents spread over the filesystem.

  9. Frank Ch. Eigler

    Taras, can you elaborate why the possible fragmentation of places.sqlite is a significant problem? What are the actual sqlite access patterns to it? How large is it? Why doesn’t it just fit into RAM? Is it only the write/sync traffic that’s a problem?

  10. @Neil. Yup, that’s what my idea is see http://thread.gmane.org/gmane.comp.db.sqlite.general/58344 and https://bugzilla.mozilla.org/show_bug.cgi?id=581606

    @Frank
    Problem is that once the file is 50mb in size and highly fragmented it takes a while to read it in which is what we do when you type in the addressbar(and thus query your history among other things)

  11. Apologies for my mere macro-level observation, but do you think it’s likely that any work to reduce fragmentation will make it into FF4? Such wins would be awesome to see.

  12. AFAIK there is absolutely no way to prevent file fragmentation on Win32 as far as XP where even newly allocated files aren’t guaranteed to be layed continously. It gets worse when disk space is low and ‘slack space’ defrag can do little about it. Files subject to grow in size will fragment no matter what, even if you use ‘copy-on-write’.

  13. Frank Ch. Eigler

    Taras, what are the access patterns for the file? I assume you’re talking during regular browsing as opposed to initial startup, and apparently RAM is not spacious enough to cache the whole thing (which is a bit of a surprise to me, fwiw). Even in this case though, does sqlite and your db schema do something useful in reducing I/O like use indexes? Or is it like a full scan of the database every time a character is pressed? If the latter, perhaps the SQL widget is not buying you much except in the form of indirection.

  14. When you get an update to Adobe Acrobat Reader, it installs, then at the end it states it is “optimizing installation” or something like that. Is it defragmenting the newly installed files? This wouldn’t help with history-type files, but would help with libraries, etc. and would be a tolerable use of time during the installation process, rather than at startup, etc.

  15. See bug 570058 regarding the updater… we’ll likely copy the updated file for a partial patch to avoid fragmentation since some file systems don’t actually prevent fragmentation and Windows is the only one that has a defragmentation program that runs automatically be default.

  16. Taras, maybe a little different approach to the search, I always liked AwesomeBar, until as you describe it started to take too much time to provide the results, I’m just wondering why it looks like it uses the same thread. Actually I develop a full-text related applications from time to time, one of them used a separated thread to look up into the base, so the primary thread just passes the string to the queue of the other thread. As for the user experience it feels much much better. As for the visual indication, the primary thread can always show a different display string when it’s still working and when nothing is found.

  17. @Max
    Firefox 4 moves awesomebar IO off the main thread. Trouble is that IO can’t be threaded effectively, because if you have a flush going on and you happen to do a read in another thread(the OS could do it while paging in code for the binary) your UI will still freeze. So even if the IO happens on a separate thread, that’s not enough.

    @Frank, it’s mostly the overhead of reading the cache into memory that concerns me. Apparently it can take minutes to certain whole-database queries for the first time.

  18. Throwing in my “me too”:

    % lsof -p 19498 | sudo perl -lane ‘if (-f $F[-1]) { system(“filefrag”, $F[-1]) }’ | sort -u | fgrep -v ’1 extent found’
    /home/sfink/.mozilla/firefox/i5kpvq88.default/Cache/_CACHE_001_: 15 extents found, perfection would be 1 extent
    /home/sfink/.mozilla/firefox/i5kpvq88.default/Cache/_CACHE_002_: 16 extents found, perfection would be 1 extent
    /home/sfink/.mozilla/firefox/i5kpvq88.default/Cache/_CACHE_003_: 32 extents found, perfection would be 1 extent
    /home/sfink/.mozilla/firefox/i5kpvq88.default/Cache/_CACHE_MAP_: 5 extents found, perfection would be 1 extent
    /home/sfink/.mozilla/firefox/i5kpvq88.default/formhistory.sqlite: 2 extents found, perfection would be 1 extent
    /home/sfink/.mozilla/firefox/i5kpvq88.default/urlclassifier3.sqlite: 2 extents found, perfection would be 1 extent
    /usr/lib/locale/locale-archive: 2 extents found, perfection would be 1 extent

  19. That was my home machine (ext3 on Fedora 10), which has seen lots of use and is often near capacity. Here’s my month-old work machine (ext4 on Fedora 13), with only 8% disk utilization:

    /usr/lib/locale/locale-archive: 6 extents found
    /home/sfink/.xsession-errors: 9 extents found
    /home/sfink/.xsession-errors: 9 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/.parentlock: 0 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/places.sqlite: 6 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/cookies.sqlite: 16 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/formhistory.sqlite: 12 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/cookies.sqlite-journal: 2 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/urlclassifier3.sqlite: 55 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/places.sqlite-journal: 0 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/downloads.sqlite: 3 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/Cache/_CACHE_001_: 3 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/Cache/_CACHE_002_: 4 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/Cache/_CACHE_003_: 6 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#extdev.2010-07-29.log: 2 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#build.2010-07-29.log: 5 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#developers.2010-07-29.log: 12 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#devtools.2010-07-29.log: 6 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#jsapi.2010-07-29.log: 9 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/channels/#startup.2010-07-29.log: 2 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/chatzilla/logs/moznet/users/taras.2010-07-29.log: 5 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/XUL.mfasl: 11 extents found
    /home/sfink/.mozilla/firefox/25ipimud.default/signons.sqlite: 2 extents found

  20. DSO fragmentation is probably correlated with prelink. We probably don’t preallocate space for the additional sections prelink creates. Would be a pretty easy thing to fix though.

  21. sorry taras. i did not read this post before writing you about sqlite fragmentation. these are great findings you did.

    i wondered how they did it in chrome and found
    http://code.google.com/p/chromium/issues/detail?id=6626
    maybe contains or points to interesting things.

    i think pre-allocating more space makes sense since firefox has become severely dependent on database performance. grown database weapons may be worth, let’s try them!

    complementary possible approaches i think:

    - don’t load the whole places database on startup. only eg: bookmarks toolbar, bookmarks root level, and the most visited pages. read-only, redundant, eventually much smaller, databases with this info could be kept for this purpose. the rest would be loaded on demand. “on demand” definition is not trivial here but i think it could be kept simple. usage patterns will surely help to decide what is worth to be loaded on startup and what not.

    - for cache: assuming allocating or whatever solution for database is adopted works well, could using sqlite for cache files help? i guess trivial reads would be slower but the overall performance would be better due to less fragmentation.

  22. another

    - instead of load and query the local database, query the firefox sync profile online. this would put the load on the server and impose a minimum lag of 0.5 to 1 seconds before responses, but may result in a better user experience than wait for the whole local database to be loaded.

  23. So i should have added here my recent comment, about 121 fragment for xul.dll, and 71 fragments for startupCache.4.little on Windows XP.

    What I didn’t see too much above is that in my case the bad effect of fragmentation seems to be *concentrated* on the programme file getting fragmented after applying an update.

    Take that into account and try to do something Tara !

  24. Thanks for the info. startupcache should be fine in newest builds, is this a nightly?

    xul.dll fragmentation from the updater should get fixed before firefox4.

  25. @jmdesp actually I was wrong, *.dll fragmentation isn’t yet slated to go away in Firefox4. Updater fragmentation is tracked in bug 570058.

  26. Easiest solution is to create a ramdrive. Then link the files (if the names are consistent) or directories to the ramdisk.

    Fragmentation on a ramdisk for the most part irrelevent.

    If you lose power big deal.. For the most part the files are cookies, temp files or browsing history. All of which won’t be too much of a hassle if lost.

    I run firefox on a Win7 machine that has only SSDs. And I was concerned about the amount of writes firefox was doing. I’ve dumped the Profiles\b17icel5.default dir to ram disk, and firefox runs like lighning.

    The ramdisk software I use takes a snapshot every 4hrs, so if I lose power I just go back 4hrs. Works like a treat.
    – Craig

  27. CraigM, a solution like that is reasonable for a poweruser.

    However neither requiring administrator privileges to create the ramdisk nor loosing hours worth of user data are realistic for a browser vendor.

  28. From my Ubuntu amd64 system, where I’ve used FF extremely heavily, some principle culprits:

    boomtango/data/boomtango.sqlite: 1283 extents found
    places.sqlite: 437 extents found
    lazarus.sqlite: 298 extents found
    urlclassifier3.sqlite: 241 extents found

    Wow. I had to disable boomtango for performance reasons even though I liked it. It would freeze things up for minutes at a time.

    A profile copy made a big difference. Still have 348 fragments for boomtango. It’s a 1300MB file. Maybe it just stores too much.

    places is down to 14 fragments, and so is classifiers. Nice.

    If you need a worst case scenario for sqlite, boomtango with a six month power user history is a good place to start.