git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 00/32] Split index mode for very large indexes

From
Shawn Pearce <spearce@spearce.org>
Date
Apr 28, 2014, 21:18 UTC
Message-ID
<CAJo=hJtgijOOMPbFjvTUaENw=hr0YixYmy1UkdqEd=CpLZ5L2A@mail.gmail.com>
In-Reply-To
<1398682553-11634-1-git-send-email-pclouds@gmail.com>
On Mon, Apr 28, 2014 at 3:55 AM, Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
Show 10 quoted lines
> I hinted about it earlier [1]. It now passes the test suite and with a
> design that I'm happy with (thanks to Junio for a suggestion about the
> rename problem).
>
> From the user point of view, this reduces the writable size of index
> down to the number of updated files. For example my webkit index v4 is
> 14MB. With a fresh split, I only have to update an index of 200KB.
> Every file I touch will add about 80 bytes to that. As long as I don't
> touch every single tracked file in my worktree, I should not pay
> penalty for writing 14MB index file on every operation.
This is a very welcome type of improvement.

I am however concerned about the complexity of the format employed. Why do we need two EWAH bitmaps in the new index? Why isn't this just a pair of sorted files that are merge-joined at read, with records in $GIT_DIR/index taking priority over same-named records in $GIT_DIR/sharedindex.$SHA1? Deletes could be marked with a bit or an "all zero" metadata record.

Show 9 quoted lines
> The read penalty is not addressed here, so I still pay 14MB hashing
> cost. But that's an easy problem. We could cache the validated index
> in a daemon. Whenever git needs to load an index, it pokes the daemon.
> The daemon verifies that the on-disk index still has the same
> signature, then sends the in-mem index to git. When git updates the
> index, it pokes the daemon again to update in-mem index. Next time git
> reads the index, it does not have to pay I/O cost any more (actually
> it does but the cost is hidden away when you do not have to read it
> yet).

If we are going this far, maybe it is worthwhile building a mmap() region the daemon exports to the git client that holds the "in memory" format of the index. Clients would mmap this PROT_READ, MAP_PRIVATE and can then quickly access the base file information without doing further validation, or copying the large(ish) data over a pipe.

Junio had some other great ideas for improving the index on really large trees. Maybe I should let him comment since they are really his ideas. Something about not even checking out most files, storing most subtrees as just a "tree" entry in the index. E.g. if you are a bad developer and never touch the "t/" subdirectory then that is stored as just "t" and the SHA-1 of the "t" tree, rather than the recursively exploded list of the test directory.

Previous: Nguyễn Thái Ngọc DuyNext: Duy Nguyen
Message 41 of 75 in “Split index mode for very large indexes”
  1. 00/32 Split index mode for very large indexesNguyễn Thái Ngọc Duy, Apr 28, 2014
  2. 01/32 ewah: fix constness of ewah_read_mmapNguyễn Thái Ngọc Duy, Apr 28, 2014
  3. 02/32 ewah: delete unused ewah_read_mmap_native declarationNguyễn Thái Ngọc Duy, Apr 28, 2014
  4. 03/32 sequencer: do not update/refresh index if the lock cannot be heldNguyễn Thái Ngọc Duy, Apr 28, 2014
  5. 04/32 read-cache: new API write_locked_index instead of write_index/write_cacheNguyễn Thái Ngọc Duy, Apr 28, 2014
  6. 05/32 read-cache: relocate and unexport commit_locked_index()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  7. 06/32 read-cache: store in-memory flags in the first 12 bits of ce_flagsNguyễn Thái Ngọc Duy, Apr 28, 2014
  8. 07/32 read-cache: be strict about "changed" in remove_marked_cache_entries()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  9. 08/32 read-cache: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  10. 09/32 update-index: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  11. 10/32 resolve-undo: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  12. 11/32 unpack-trees: be specific what part of the index has changedNguyễn Thái Ngọc Duy, Apr 28, 2014
  13. 12/32 cache-tree: mark istate->cache_changed on cache tree invalidationNguyễn Thái Ngọc Duy, Apr 28, 2014
  14. 13/32 cache-tree: mark istate->cache_changed on cache tree updateNguyễn Thái Ngọc Duy, Apr 28, 2014
  15. 14/32 cache-tree: mark istate->cache_changed on prime_cache_tree()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  16. 15/32 entry.c: update cache_changed if refresh_cache is set in checkout_entry()Nguyễn Thái Ngọc Duy, Apr 28, 2014
  17. 16/32 read-cache: save index SHA-1 after readingNguyễn Thái Ngọc Duy, Apr 28, 2014
  18. 17/32 read-cache: split-index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  19. Junio C HamanoApr 28, 2014
  20. Duy NguyenApr 29, 2014
  21. Junio C HamanoApr 29, 2014
  22. Duy NguyenApr 29, 2014
  23. Junio C HamanoApr 30, 2014
  24. 18/32 read-cache: mark new entries for split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  25. Eric SunshineApr 30, 2014
  26. 19/32 read-cache: save deleted entries in split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  27. 20/32 read-cache: mark updated entries for split indexNguyễn Thái Ngọc Duy, Apr 28, 2014
  28. 21/32 split-index: the writing partNguyễn Thái Ngọc Duy, Apr 28, 2014
  29. 22/32 split-index: the reading partNguyễn Thái Ngọc Duy, Apr 28, 2014
  30. 23/32 split-index: do not invalidate cache-tree at read timeNguyễn Thái Ngọc Duy, Apr 28, 2014
  31. 24/32 split-index: strip pathname of on-disk replaced entriesNguyễn Thái Ngọc Duy, Apr 28, 2014
  32. Junio C HamanoApr 29, 2014
  33. 25/32 update-index: new options to enable/disable split index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  34. 26/32 update-index --split-index: do not split if $GIT_DIR is read onlyNguyễn Thái Ngọc Duy, Apr 28, 2014
  35. 27/32 rev-parse: add --shared-index-path to get shared index pathNguyễn Thái Ngọc Duy, Apr 28, 2014
  36. 28/32 read-tree: force split-index mode off on --index-outputNguyễn Thái Ngọc Duy, Apr 28, 2014
  37. 29/32 read-tree: note about dropping split-index mode or index versionNguyễn Thái Ngọc Duy, Apr 28, 2014
  38. 30/32 read-cache: force split index mode with GIT_TEST_SPLIT_INDEXNguyễn Thái Ngọc Duy, Apr 28, 2014
  39. 31/32 t2104: make sure split index mode is off for the version testNguyễn Thái Ngọc Duy, Apr 28, 2014
  40. 32/32 t1700: new tests for split-index modeNguyễn Thái Ngọc Duy, Apr 28, 2014
  41. Shawn PearceApr 28, 2014
  42. Duy NguyenApr 29, 2014
  43. Duy NguyenMay 9, 2014
  44. Junio C HamanoMay 9, 2014
  45. 0/8 Speed up cache loading timeNguyễn Thái Ngọc Duy, May 13, 2014
  46. 1/8 read-cache: allow to keep mmap'd memory after readingNguyễn Thái Ngọc Duy, May 13, 2014
  47. 2/3 Add read-cache--daemonNguyễn Thái Ngọc Duy, May 13, 2014
  48. Erik Faye-LundMay 13, 2014
  49. Duy NguyenMay 13, 2014
  50. Duy NguyenMay 13, 2014
  51. Erik Faye-LundMay 13, 2014
  52. Duy NguyenMay 13, 2014
  53. Erik Faye-LundMay 13, 2014
  54. Duy NguyenMay 13, 2014
  55. Erik Faye-LundMay 13, 2014
  56. 2/8 unix-socket: stub impl. for platforms with no unix socket supportNguyễn Thái Ngọc Duy, May 13, 2014
  57. Erik Faye-LundMay 13, 2014
  58. Erik Faye-LundMay 13, 2014
  59. 3/8 daemonize: set a flag before exiting the main processNguyễn Thái Ngọc Duy, May 13, 2014
  60. 3/3 read-cache: try index data from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  61. 4/8 Add read-cache--daemon for caching index and related stuffNguyễn Thái Ngọc Duy, May 13, 2014
  62. Erik Faye-LundMay 13, 2014
  63. 5/8 read-cache: try index data from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  64. Erik Faye-LundMay 13, 2014
  65. 6/8 read-cache--daemon: do not read index from shared memoryNguyễn Thái Ngọc Duy, May 13, 2014
  66. 7/8 read-cache: skip verifying trailing SHA-1 on cached indexNguyễn Thái Ngọc Duy, May 13, 2014
  67. 8/8 read-cache: inform the daemon that the index has been updatedNguyễn Thái Ngọc Duy, May 13, 2014
  68. Erik Faye-LundMay 13, 2014
  69. David TurnerMay 22, 2014
  70. Stefan BellerMay 13, 2014
  71. Duy NguyenMay 13, 2014
  72. 9/8 even faster loading time with index version 254Nguyễn Thái Ngọc Duy, May 13, 2014
  73. Junio C HamanoApr 28, 2014
  74. Richard HansenApr 30, 2014
  75. Duy NguyenMay 1, 2014

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.