Repository: parcel-bundler/parcel
Pull request #6000 (2021-03-15 21:32:47)

Changing graph identifiers from content keys to numbers
# ↪️ Pull Request

Changing the content key aware identifiers (strings) to auto incrementing numbers. This will unlock further changes as replacing the adjacency lists. 

* created an opaque node id type
* instead of passing nodes around, passing node ids
* updated where certain add actions took place 

Results:

**Before**
| Graph Type   | Nodes |  Edges |  Serialize w/ Write | Deserialize w/ Read | Serialized Memory | Total Cold Build
| ------------- | ------------- |  ------------- |  ------------- | ------------- | ------------- |  ------------- |
| BundleGraph  | 48348  | 127683 | 1861 ms | 2509 ms | 68.96 mb | 741.96s
| RequestGraph  | 92336  | 715971 | 11133 ms | 5102 ms | 188.32 mb

**With Numeric Ids**
| Graph Type   | Nodes |  Edges |  Serialize w/ Write | Deserialize w/ Read | Serialized Memory | Total Cold Build
| ------------- | ------------- |  ------------- |  ------------- | ------------- | ------------- |  ------------- |
| BundleGraph  | 48348  | 127683 | 1361 ms (-26%)  | 1758 ms (-30%) | 59.24 mb (-14%) | 588.86s (-20%)
| RequestGraph  | 92344  | 716001 | 7713 ms (-31%)  | 2996 ms (-41%) | 102.43 mb (-45%)

## 🚨 Test instructions
* Running the current suite of unit and integration tests
* [x] add unit tests for the content graph
 
## ✔️ PR Todo

- [x ] Added/updated unit tests for this change
- [x] Filled out test instructions (In case there aren't any unit tests)
- [x] Included links to related issues/PRs


height[bot]: > Link [Height](https://parcel.height.app) tasks by mentioning a task ID in the pull request title or description, commit messages, or comments.
>
> 💡Tip: You can also use "Close T-X" to automatically close a task when the pull request is merged.
<!-- Sent by Height -->
parcel-benchmark: ## Benchmark Results
<details><summary>Kitchen Sink ✅</summary><p>

#### Timings

| Description | Time | Difference |
| --- | --- | --- |
| Cold | 8.13s | +110.00ms |
| Cached | 513.00ms | +36.00ms ⚠️ |

#### Cold Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/legacy/parcel.d5807e82.webp | 102.94kb | +0.00b | 557.00ms | +63.00ms ⚠️ |
| dist/modern/parcel.d5807e82.webp | 102.94kb | +0.00b | 473.00ms | -49.00ms 🚀 |
| dist/legacy/index.76ce4b0c.js | 1.12kb | +0.00b | 597.00ms | +41.00ms ⚠️ |
| dist/modern/index.b43fcc94.js | 1.12kb | +0.00b | 533.00ms | -438.00ms 🚀 |
| dist/legacy/index.html | 701.00b | +0.00b | 587.00ms | +46.00ms ⚠️ |

#### Cached Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/legacy/parcel.d5807e82.webp | 102.94kb | +0.00b | 75.00ms | +19.00ms ⚠️ |
| dist/modern/parcel.d5807e82.webp | 102.94kb | +0.00b | 54.00ms | -23.00ms 🚀 |
| dist/modern/index.b43fcc94.js | 1.12kb | +0.00b | 75.00ms | -4.00ms 🚀 |

</p></details>

<details><summary>React HackerNews ✅</summary><p>

#### Timings

| Description | Time | Difference |
| --- | --- | --- |
| Cold | 23.63s | -549.00ms |
| Cached | 810.00ms | +31.00ms |

#### Cold Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/logo.24c8bf9e.png | 274.00b | +0.00b | 136.00ms | -15.00ms 🚀 |

#### Cached Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/index.js | 477.78kb | +0.00b | 148.00ms | -14.00ms 🚀 |
| dist/PermalinkedComment.0a19c7e4.js | 4.24kb | +0.00b | 148.00ms | -14.00ms 🚀 |
| dist/UserProfile.b2960402.js | 1.78kb | +0.00b | 148.00ms | -14.00ms 🚀 |
| dist/NotFound.f3269ae7.js | 542.00b | +0.00b | 115.00ms | -32.00ms 🚀 |
| dist/logo.24c8bf9e.png | 274.00b | +0.00b | 115.00ms | -10.00ms 🚀 |

</p></details>

<details><summary>AtlasKit Editor ✅</summary><p>

#### Timings

| Description | Time | Difference |
| --- | --- | --- |
| Cold | 2.50m | -2.11s |
| Cached | 3.31s | +100.00ms |

#### Cold Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/popup.119ff481.js | 171.12kb | +0.00b | 16.89s | +1.38s ⚠️ |
| dist/EmojiPickerComponent.c4358f76.js | 139.84kb | +0.00b | 12.10s | +1.58s ⚠️ |
| dist/Toolbar.0c83bb49.js | 100.68kb | +0.00b | 16.96s | +1.08s ⚠️ |
| dist/media-viewer.ebcb5e1e.js | 73.43kb | +0.00b | 12.74s | +1.29s ⚠️ |
| dist/card.1d931b4c.js | 52.43kb | +0.00b | 13.75s | +1.09s ⚠️ |
| dist/esm.e3419f0a.js | 27.83kb | +0.00b | 9.41s | +508.00ms ⚠️ |
| dist/component.f25dcadb.js | 22.80kb | +0.00b | 4.38s | +588.00ms ⚠️ |
| dist/DatePicker.faca45d0.js | 21.38kb | +0.00b | 7.26s | -1.63s 🚀 |
| dist/js.8167e2d5.js | 16.55kb | +0.00b | 4.38s | +588.00ms ⚠️ |
| dist/dropzone.3ae9a030.js | 16.15kb | +0.00b | 13.71s | -1.57s 🚀 |
| dist/workerHasher.bc6346e1.js | 11.90kb | +0.00b | 9.40s | +2.63s ⚠️ |
| dist/component.677fad45.js | 6.23kb | +0.00b | 3.59s | -205.00ms 🚀 |
| dist/card.3a4028bd.js | 5.74kb | +0.00b | 12.41s | +1.33s ⚠️ |
| dist/media-viewer.f15e56f4.js | 4.01kb | +0.00b | 11.70s | +2.15s ⚠️ |
| dist/EmojiPickerComponent.4991ddd4.js | 3.68kb | +0.00b | 7.87s | +1.12s ⚠️ |
| dist/png-chunks-extract.608f438d.js | 3.56kb | +0.00b | 4.38s | +588.00ms ⚠️ |
| dist/dropzone.d1e8004d.js | 3.46kb | +0.00b | 16.55s | +5.49s ⚠️ |
| dist/index.ece3a13e.css | 3.46kb | +0.00b | 17.56s | +1.01s ⚠️ |
| dist/Modal.08282ab6.js | 3.23kb | +0.00b | 3.28s | -935.00ms 🚀 |
| dist/clipboard.6a6e5fbd.js | 3.00kb | +0.00b | 16.66s | +4.07s ⚠️ |
| dist/card.2888338b.js | 2.15kb | +0.00b | 12.10s | +2.00s ⚠️ |
| dist/date.a69000aa.js | 1.97kb | +0.00b | 5.34s | +876.00ms ⚠️ |
| dist/images.ece03ae5.js | 1.91kb | +0.00b | 4.92s | +439.00ms ⚠️ |
| dist/feedback.facaac2e.js | 1.87kb | +0.00b | 7.19s | -1.69s 🚀 |
| dist/16.a9ea9b41.js | 1.86kb | +0.00b | 4.58s | +467.00ms ⚠️ |
| dist/browser.8883c452.js | 1.85kb | +0.00b | 13.75s | -1.73s 🚀 |
| dist/workerHasher.31326e89.js | 1.77kb | +0.00b | 9.39s | +3.09s ⚠️ |
| dist/workerHasher.d607e0b8.js | 1.77kb | +0.00b | 14.18s | +1.51s ⚠️ |
| dist/list-number.d4568b49.js | 1.69kb | +0.00b | 4.92s | +306.00ms ⚠️ |
| dist/status.6595d133.js | 1.69kb | +0.00b | 5.24s | +378.00ms ⚠️ |
| dist/link.5be155be.js | 1.54kb | +0.00b | 4.92s | +306.00ms ⚠️ |
| dist/heading3.1c92891c.js | 1.52kb | +0.00b | 5.35s | +488.00ms ⚠️ |
| dist/16.07ccad90.js | 1.51kb | +0.00b | 4.66s | +547.00ms ⚠️ |
| dist/16.02056ae6.js | 1.47kb | +0.00b | 4.66s | +750.00ms ⚠️ |
| dist/emoji.b5624cf5.js | 1.46kb | +0.00b | 4.92s | +439.00ms ⚠️ |
| dist/16.00100306.js | 1.44kb | +0.00b | 4.80s | +522.00ms ⚠️ |
| dist/16.bdd61d2d.js | 1.41kb | +0.00b | 4.80s | +522.00ms ⚠️ |
| dist/expand.4a483eb0.js | 1.39kb | +0.00b | 7.19s | -1.69s 🚀 |
| dist/16.fa5f411c.js | 1.36kb | +0.00b | 4.58s | +307.00ms ⚠️ |
| dist/heading2.22de70fe.js | 1.34kb | +0.00b | 5.35s | +488.00ms ⚠️ |
| dist/16.d10db5a3.js | 1.32kb | +0.00b | 4.59s | +314.00ms ⚠️ |
| dist/mention.c44b48ed.js | 1.30kb | +0.00b | 5.10s | +479.00ms ⚠️ |
| dist/Modal.44e980e0.js | 1.29kb | +0.00b | 4.38s | +588.00ms ⚠️ |
| dist/layout.81f2196c.js | 1.28kb | +0.00b | 4.92s | +305.00ms ⚠️ |
| dist/16.acff901d.js | 1.27kb | +0.00b | 4.57s | +455.00ms ⚠️ |
| dist/component.233c7a65.js | 1.26kb | +0.00b | 3.28s | -934.00ms 🚀 |
| dist/16.015dfb9d.js | 1.26kb | +0.00b | 4.30s | +384.00ms ⚠️ |
| dist/16.828b958e.js | 1.26kb | +0.00b | 4.66s | +547.00ms ⚠️ |
| dist/16.b9b1643b.js | 1.26kb | +0.00b | 4.92s | +807.00ms ⚠️ |
| dist/divider.ed7ccd2e.js | 1.26kb | +0.00b | 5.35s | +880.00ms ⚠️ |
| dist/quote.b6d8bffb.js | 1.25kb | +0.00b | 5.24s | +487.00ms ⚠️ |
| dist/media-card-analytics-error-boundary.ff0177b3.js | 1.25kb | +0.00b | 12.41s | +1.33s ⚠️ |
| dist/16.458399e0.js | 1.23kb | +0.00b | 3.28s | -935.00ms 🚀 |
| dist/decision.c48f9f1e.js | 1.22kb | +0.00b | 5.34s | +876.00ms ⚠️ |
| dist/panel-warning.b5f3360d.js | 1.22kb | +0.00b | 5.10s | +351.00ms ⚠️ |
| dist/list.2dfe3f18.js | 1.19kb | +0.00b | 6.38s | +1.76s ⚠️ |
| dist/heading1.cc82b077.js | 1.19kb | +0.00b | 5.24s | +378.00ms ⚠️ |
| dist/16.90358f40.js | 1.18kb | +0.00b | 4.59s | +316.00ms ⚠️ |
| dist/panel.fc70749c.js | 1.11kb | +0.00b | 5.24s | +487.00ms ⚠️ |
| dist/table.77df779b.js | 1.10kb | +0.00b | 5.24s | +378.00ms ⚠️ |
| dist/panel-success.d5752da0.js | 1.06kb | +0.00b | 5.10s | +351.00ms ⚠️ |
| dist/panel-note.6a71a1f2.js | 1.05kb | +0.00b | 5.10s | +351.00ms ⚠️ |
| dist/media-picker-analytics-error-boundary.49b32f4d.js | 1023.00b | +0.00b | 16.57s | +1.29s ⚠️ |
| dist/media-card-analytics-error-boundary.9a500f44.js | 1019.00b | +0.00b | 9.86s | +578.00ms ⚠️ |
| dist/media-card-analytics-error-boundary.b884d580.js | 1019.00b | +0.00b | 13.78s | +1.15s ⚠️ |
| dist/media-viewer-analytics-error-boundary.83da5db2.js | 1015.00b | +0.00b | 11.74s | +1.65s ⚠️ |
| dist/simpleHasher.79137cb4.js | 767.00b | +0.00b | 9.39s | +2.64s ⚠️ |
| dist/simpleHasher.2c5206fd.js | 767.00b | +0.00b | 15.07s | +1.90s ⚠️ |

#### Cached Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/index.59a13c6f.js | 2.46mb | +3.00b ⚠️ | 591.00ms | -89.00ms 🚀 |
| dist/pdfRenderer.f5a3f4a7.js | 1.11mb | +0.00b | 628.00ms | -62.00ms 🚀 |
| dist/editorView.ea13a2b7.js | 588.08kb | +0.00b | 652.00ms | -62.00ms 🚀 |
| dist/popup.119ff481.js | 171.12kb | +0.00b | 637.00ms | -90.00ms 🚀 |
| dist/EmojiPickerComponent.c4358f76.js | 139.84kb | +0.00b | 641.00ms | -38.00ms 🚀 |
| dist/Toolbar.0c83bb49.js | 100.68kb | +0.00b | 645.00ms | -69.00ms 🚀 |
| dist/media-viewer.ebcb5e1e.js | 73.43kb | +0.00b | 628.00ms | -62.00ms 🚀 |
| dist/card.df70c9b7.js | 54.67kb | +0.00b | 610.00ms | -75.00ms 🚀 |
| dist/card.1d931b4c.js | 52.43kb | +0.00b | 642.00ms | -58.00ms 🚀 |
| dist/Modal.558fb5db.js | 39.59kb | +0.00b | 503.00ms | -59.00ms 🚀 |
| dist/component.ad27194c.js | 31.05kb | +0.00b | 492.00ms | -55.00ms 🚀 |
| dist/esm.e3419f0a.js | 27.83kb | +0.00b | 641.00ms | -38.00ms 🚀 |
| dist/component.f25dcadb.js | 22.80kb | +0.00b | 503.00ms | -66.00ms 🚀 |
| dist/smartMediaEditor.21f91ed8.js | 16.96kb | +0.00b | 652.00ms | -62.00ms 🚀 |
| dist/js.8167e2d5.js | 16.55kb | +0.00b | 503.00ms | -59.00ms 🚀 |
| dist/dropzone.3ae9a030.js | 16.15kb | +0.00b | 642.00ms | -58.00ms 🚀 |
| dist/ui.15dd7acd.js | 14.30kb | +0.00b | 610.00ms | -75.00ms 🚀 |
| dist/workerHasher.bc6346e1.js | 11.90kb | +0.00b | 641.00ms | -38.00ms 🚀 |
| dist/component.677fad45.js | 6.23kb | +0.00b | 512.00ms | -59.00ms 🚀 |
| dist/card.3a4028bd.js | 5.74kb | +0.00b | 628.00ms | -62.00ms 🚀 |
| dist/media-viewer.f15e56f4.js | 4.01kb | +0.00b | 637.00ms | -53.00ms 🚀 |
| dist/EmojiPickerComponent.4991ddd4.js | 3.68kb | +0.00b | 610.00ms | -75.00ms 🚀 |
| dist/png-chunks-extract.608f438d.js | 3.56kb | +0.00b | 503.00ms | -59.00ms 🚀 |
| dist/dropzone.d1e8004d.js | 3.46kb | +0.00b | 637.00ms | -90.00ms 🚀 |
| dist/index.ece3a13e.css | 3.46kb | +0.00b | 650.00ms | -71.00ms 🚀 |
| dist/Modal.08282ab6.js | 3.23kb | +0.00b | 590.00ms | -90.00ms 🚀 |
| dist/clipboard.6a6e5fbd.js | 3.00kb | +0.00b | 642.00ms | -58.00ms 🚀 |
| dist/16.b6ca7fd0.js | 2.50kb | +0.00b | 491.00ms | -54.00ms 🚀 |
| dist/ResourcedEmojiComponent.5046c0ff.js | 2.19kb | +0.00b | 610.00ms | -75.00ms 🚀 |
| dist/card.2888338b.js | 2.15kb | +0.00b | 637.00ms | -90.00ms 🚀 |
| dist/date.a69000aa.js | 1.97kb | +0.00b | 558.00ms | -46.00ms 🚀 |
| dist/images.ece03ae5.js | 1.91kb | +0.00b | 582.00ms | -35.00ms 🚀 |
| dist/feedback.facaac2e.js | 1.87kb | +0.00b | 604.00ms | -43.00ms 🚀 |
| dist/16.a9ea9b41.js | 1.86kb | +0.00b | 536.00ms | -144.00ms 🚀 |
| dist/browser.8883c452.js | 1.85kb | +0.00b | 642.00ms | -58.00ms 🚀 |
| dist/16.89d45d15.js | 1.80kb | +0.00b | 512.00ms | -59.00ms 🚀 |
| dist/workerHasher.31326e89.js | 1.77kb | +0.00b | 641.00ms | -38.00ms 🚀 |
| dist/workerHasher.d607e0b8.js | 1.77kb | +0.00b | 652.00ms | -62.00ms 🚀 |
| dist/list-number.d4568b49.js | 1.69kb | +0.00b | 589.00ms | -35.00ms 🚀 |
| dist/code.efde0f48.js | 1.61kb | +0.00b | 558.00ms | -46.00ms 🚀 |
| dist/link.5be155be.js | 1.54kb | +0.00b | 582.00ms | -35.00ms 🚀 |
| dist/heading6.5a6082c8.js | 1.53kb | +0.00b | 604.00ms | -43.00ms 🚀 |
| dist/heading3.1c92891c.js | 1.52kb | +0.00b | 604.00ms | -34.00ms 🚀 |
| dist/16.07ccad90.js | 1.51kb | +0.00b | 524.00ms | -56.00ms 🚀 |
| dist/16.00f25203.js | 1.47kb | +0.00b | 512.00ms | -59.00ms 🚀 |
| dist/16.02056ae6.js | 1.47kb | +0.00b | 523.00ms | -57.00ms 🚀 |
| dist/emoji.b5624cf5.js | 1.46kb | +0.00b | 582.00ms | -35.00ms 🚀 |
| dist/16.b7da7bde.js | 1.45kb | +0.00b | 491.00ms | -56.00ms 🚀 |
| dist/16.bdd61d2d.js | 1.41kb | +0.00b | 538.00ms | -60.00ms 🚀 |
| dist/heading5.88bc6249.js | 1.41kb | +0.00b | 603.00ms | -44.00ms 🚀 |
| dist/expand.4a483eb0.js | 1.39kb | +0.00b | 604.00ms | -43.00ms 🚀 |
| dist/16.fa5f411c.js | 1.36kb | +0.00b | 537.00ms | -56.00ms 🚀 |
| dist/16.2a21d3f4.js | 1.34kb | +0.00b | 491.00ms | -67.00ms 🚀 |
| dist/heading2.22de70fe.js | 1.34kb | +0.00b | 604.00ms | -34.00ms 🚀 |
| dist/16.d10db5a3.js | 1.32kb | +0.00b | 538.00ms | -55.00ms 🚀 |
| dist/16.c9db7e6b.js | 1.32kb | +0.00b | 558.00ms | -46.00ms 🚀 |
| dist/mention.c44b48ed.js | 1.30kb | +0.00b | 590.00ms | -34.00ms 🚀 |
| dist/heading4.a2524c70.js | 1.29kb | +0.00b | 604.00ms | -37.00ms 🚀 |
| dist/Modal.44e980e0.js | 1.29kb | +0.00b | 503.00ms | -59.00ms 🚀 |
| dist/layout.81f2196c.js | 1.28kb | +0.00b | 582.00ms | -35.00ms 🚀 |
| dist/16.9e97e787.js | 1.28kb | +0.00b | 494.00ms | -51.00ms 🚀 |
| dist/16.acff901d.js | 1.27kb | +0.00b | 524.00ms | -62.00ms 🚀 |
| dist/component.233c7a65.js | 1.26kb | +0.00b | 591.00ms | -89.00ms 🚀 |
| dist/16.015dfb9d.js | 1.26kb | +0.00b | 512.00ms | -66.00ms 🚀 |
| dist/16.828b958e.js | 1.26kb | +0.00b | 523.00ms | -57.00ms 🚀 |
| dist/16.b9b1643b.js | 1.26kb | +0.00b | 524.00ms | -61.00ms 🚀 |
| dist/16.ec84a250.js | 1.26kb | +0.00b | 512.00ms | -59.00ms 🚀 |
| dist/divider.ed7ccd2e.js | 1.26kb | +0.00b | 582.00ms | -35.00ms 🚀 |
| dist/quote.b6d8bffb.js | 1.25kb | +0.00b | 596.00ms | -35.00ms 🚀 |
| dist/media-card-analytics-error-boundary.ff0177b3.js | 1.25kb | +0.00b | 627.00ms | -63.00ms 🚀 |
| dist/action.01ec8983.js | 1.24kb | +0.00b | 558.00ms | -46.00ms 🚀 |
| dist/16.458399e0.js | 1.23kb | +0.00b | 590.00ms | -90.00ms 🚀 |
| dist/decision.c48f9f1e.js | 1.22kb | +0.00b | 558.00ms | -52.00ms 🚀 |
| dist/panel-warning.b5f3360d.js | 1.22kb | +0.00b | 595.00ms | -36.00ms 🚀 |
| dist/list.2dfe3f18.js | 1.19kb | +0.00b | 589.00ms | -35.00ms 🚀 |
| dist/heading1.cc82b077.js | 1.19kb | +0.00b | 604.00ms | -34.00ms 🚀 |
| dist/16.90358f40.js | 1.18kb | +0.00b | 538.00ms | -55.00ms 🚀 |
| dist/panel-error.7454ebc0.js | 1.12kb | +0.00b | 590.00ms | -34.00ms 🚀 |
| dist/panel.fc70749c.js | 1.11kb | +0.00b | 595.00ms | -36.00ms 🚀 |
| dist/table.77df779b.js | 1.10kb | +0.00b | 604.00ms | -34.00ms 🚀 |
| dist/panel-success.d5752da0.js | 1.06kb | +0.00b | 595.00ms | -36.00ms 🚀 |
| dist/panel-note.6a71a1f2.js | 1.05kb | +0.00b | 590.00ms | -34.00ms 🚀 |
| dist/media-picker-analytics-error-boundary.49b32f4d.js | 1023.00b | +0.00b | 642.00ms | -85.00ms 🚀 |
| dist/media-card-analytics-error-boundary.9a500f44.js | 1019.00b | +0.00b | 627.00ms | -58.00ms 🚀 |
| dist/media-card-analytics-error-boundary.b884d580.js | 1019.00b | +0.00b | 652.00ms | -48.00ms 🚀 |
| dist/media-viewer-analytics-error-boundary.83da5db2.js | 1015.00b | +0.00b | 637.00ms | -90.00ms 🚀 |
| dist/simpleHasher.79137cb4.js | 767.00b | +0.00b | 610.00ms | -69.00ms 🚀 |
| dist/simpleHasher.2c5206fd.js | 767.00b | +0.00b | 652.00ms | -62.00ms 🚀 |
| dist/index.html | 119.00b | +0.00b | 525.00ms | -53.00ms 🚀 |

</p></details>

<details><summary>Three.js ✅</summary><p>

#### Timings

| Description | Time | Difference |
| --- | --- | --- |
| Cold | 19.87s | +85.00ms |
| Cached | 644.00ms | -28.00ms |

#### Cold Bundles

*No bundle changes detected.*

#### Cached Bundles

| Bundle | Size | Difference | Time | Difference |
| --- | --- | --- | --- | --- |
| dist/Three.js | 580.60kb | +0.00b | 106.00ms | -11.00ms 🚀 |

</p></details>

**[Click here to view a detailed benchmark overview.](https://benchmark.parceljs.org/benchmark/293229299156124170)**
joeyslater: @mischnic @wbinnssmith - could I get some 👀 on this? I'd like some review before merging in v2 / resolving conflicts. 
mischnic: The two changes to `AssetGraphRequest.js` I commented on would be great, the other comments are just thoughts I had (e.g. what should happen when `addNode` is called twice with the same object/same content id).
joeyslater: > The two changes to `AssetGraphRequest.js` I commented on would be great, the other comments are just thoughts I had (e.g. what should happen when `addNode` is called twice with the same object/same content id).

AssetGraphRequest changes have been made and updated the addNode in RequestGraph. Everything was passing. Merged in v2, so hopefully the pipeline will be green and ready to go

Patch:
diff --git a/packages/core/core/src/AssetGraph.js b/packages/core/core/src/AssetGraph.js
index a861a3fd5..83c3be11d 100644
--- a/packages/core/core/src/AssetGraph.js
+++ b/packages/core/core/src/AssetGraph.js
@@ -7,12 +7,14 @@ import type {
   AssetGroup,
   AssetGroupNode,
   AssetNode,
+  ContentKey,
   Dependency,
   DependencyNode,
   Entry,
   EntryFileNode,
   EntrySpecifierNode,
   Environment,
+  NodeId,
   Target,
 } from './types';
 
@@ -24,7 +26,7 @@ import {
   objectSortedEntries,
 } from '@parcel/utils';
 import nullthrows from 'nullthrows';
-import Graph, {type GraphOpts} from './Graph';
+import ContentGraph, {type SerializedContentGraph} from './ContentGraph';
 import {createDependency} from './Dependency';
 
 type InitOpts = {|
@@ -34,7 +36,7 @@ type InitOpts = {|
 |};
 
 type SerializedAssetGraph = {|
-  ...GraphOpts<AssetGraphNode>,
+  ...SerializedContentGraph<AssetGraphNode>,
   hash?: ?string,
 |};
 
@@ -97,8 +99,8 @@ export function nodeFromEntryFile(entry: Entry): EntryFileNode {
   };
 }
 
-export default class AssetGraph extends Graph<AssetGraphNode> {
-  onNodeRemoved: ?(node: AssetGraphNode) => mixed;
+export default class AssetGraph extends ContentGraph<AssetGraphNode> {
+  onNodeRemoved: ?(nodeId: NodeId) => mixed;
   hash: ?string;
   envCache: Map<string, Environment>;
 
@@ -109,20 +111,24 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
       this.hash = hash;
     } else {
       super();
-      let rootNode = {id: '@@root', type: 'root', value: null};
-      this.setRootNode(rootNode);
+      this.setRootNodeId(
+        this.addNode({
+          id: '@@root',
+          type: 'root',
+          value: null,
+        }),
+      );
     }
     this.envCache = new Map();
   }
 
-  // $FlowFixMe
+  // $FlowFixMe[prop-missing]
   static deserialize(opts: SerializedAssetGraph): AssetGraph {
     return new AssetGraph(opts);
   }
 
-  // $FlowFixMe
+  // $FlowFixMe[prop-missing]
   serialize(): SerializedAssetGraph {
-    // $FlowFixMe Added in Flow 0.121.0 upgrade in #4381
     return {
       ...super.serialize(),
       hash: this.hash,
@@ -154,42 +160,52 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
         ...assetGroups.map(assetGroup => nodeFromAssetGroup(assetGroup)),
       );
     }
-    this.replaceNodesConnectedTo(nullthrows(this.getRootNode()), nodes);
+    this.replaceNodeIdsConnectedTo(
+      nullthrows(this.rootNodeId),
+      nodes.map(node => this.addNode(node)),
+    );
   }
 
-  addNode(node: AssetGraphNode): AssetGraphNode {
+  addNode(node: AssetGraphNode): NodeId {
     this.hash = null;
-    return super.addNode(node);
+    return super.addNodeByContentKey(node.id, node);
   }
 
-  removeNode(node: AssetGraphNode): void {
+  removeNode(nodeId: NodeId): void {
     this.hash = null;
-    this.onNodeRemoved && this.onNodeRemoved(node);
+    this.onNodeRemoved && this.onNodeRemoved(nodeId);
     // This needs to mark all connected nodes that doesn't become orphaned
     // due to replaceNodesConnectedTo to make sure that the symbols of
     // nodes from which at least one parent was removed are updated.
-    if (this.isOrphanedNode(node) && node.type === 'dependency') {
-      let children = this.getNodesConnectedFrom(node);
+    let node = nullthrows(this.getNode(nodeId));
+    if (this.isOrphanedNode(nodeId) && node.type === 'dependency') {
+      let children = this.getNodeIdsConnectedFrom(nodeId).map(id =>
+        nullthrows(this.getNode(id)),
+      );
       for (let n of children) {
         invariant(n.type === 'asset_group' || n.type === 'asset');
         n.usedSymbolsDownDirty = true;
       }
     }
-    return super.removeNode(node);
+    return super.removeNode(nodeId);
   }
 
   resolveEntry(
     entry: string,
     resolved: Array<Entry>,
-    correspondingRequest: string,
+    correspondingRequest: ContentKey,
   ) {
-    let entrySpecifierNode = nullthrows(
-      this.getNode(nodeFromEntrySpecifier(entry).id),
+    let entrySpecifierNodeId = this.getNodeIdByContentKey(
+      nodeFromEntrySpecifier(entry).id,
     );
+    let entrySpecifierNode = nullthrows(this.getNode(entrySpecifierNodeId));
     invariant(entrySpecifierNode.type === 'entry_specifier');
     entrySpecifierNode.correspondingRequest = correspondingRequest;
-    let entryFileNodes = resolved.map(file => nodeFromEntryFile(file));
-    this.replaceNodesConnectedTo(entrySpecifierNode, entryFileNodes);
+
+    this.replaceNodeIdsConnectedTo(
+      entrySpecifierNodeId,
+      resolved.map(file => this.addNode(nodeFromEntryFile(file))),
+    );
   }
 
   resolveTargets(
@@ -218,12 +234,15 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
       return node;
     });
 
-    let entryNode = nullthrows(this.getNode(nodeFromEntryFile(entry).id));
+    let entryNodeId = this.getNodeIdByContentKey(nodeFromEntryFile(entry).id);
+    let entryNode = nullthrows(this.getNode(entryNodeId));
     invariant(entryNode.type === 'entry_file');
     entryNode.correspondingRequest = correspondingRequest;
-    if (this.hasNode(entryNode.id)) {
-      this.replaceNodesConnectedTo(entryNode, depNodes);
-    }
+
+    this.replaceNodeIdsConnectedTo(
+      entryNodeId,
+      depNodes.map(node => this.addNode(node)),
+    );
   }
 
   resolveDependency(
@@ -231,9 +250,9 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
     assetGroup: ?AssetGroup,
     correspondingRequest: string,
   ) {
-    let depNode = nullthrows(this.nodes.get(dependency.id));
+    let depNodeId = this.getNodeIdByContentKey(dependency.id);
+    let depNode = nullthrows(this.getNode(depNodeId));
     invariant(depNode.type === 'dependency');
-    if (!depNode) return;
     depNode.correspondingRequest = correspondingRequest;
 
     if (!assetGroup) {
@@ -241,17 +260,24 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
     }
 
     let assetGroupNode = nodeFromAssetGroup(assetGroup);
-    let existing = this.getNode(assetGroupNode.id);
-    if (existing) {
+    let existing = this.getNodeByContentKey(assetGroupNode.id);
+    if (existing != null) {
       invariant(existing.type === 'asset_group');
       assetGroupNode.value.canDefer =
         assetGroupNode.value.canDefer && existing.value.canDefer;
     }
 
-    this.replaceNodesConnectedTo(depNode, [assetGroupNode]);
+    let assetGroupNodeId = this.addNode(assetGroupNode);
+    this.replaceNodeIdsConnectedTo(this.getNodeIdByContentKey(dependency.id), [
+      assetGroupNodeId,
+    ]);
+
+    this.replaceNodeIdsConnectedTo(depNodeId, [assetGroupNodeId]);
   }
 
-  shouldVisitChild(node: AssetGraphNode, childNode: AssetGraphNode): boolean {
+  shouldVisitChild(nodeId: NodeId, childNodeId: NodeId): boolean {
+    let node = nullthrows(this.getNode(nodeId));
+    let childNode = nullthrows(this.getNode(childNodeId));
     if (
       node.type !== 'dependency' ||
       childNode.type !== 'asset_group' ||
@@ -268,47 +294,57 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
     childNode.deferred = defer;
 
     if (!previouslyDeferred && defer) {
-      this.markParentsWithHasDeferred(node);
+      this.markParentsWithHasDeferred(nodeId);
     } else if (previouslyDeferred && !defer) {
-      this.unmarkParentsWithHasDeferred(childNode);
+      this.unmarkParentsWithHasDeferred(childNodeId);
     }
 
     return !defer;
   }
 
   // Dependency: mark parent Asset <- AssetGroup with hasDeferred true
-  markParentsWithHasDeferred(node: AssetGraphNode) {
-    this.traverseAncestors(node, (_node, _, actions) => {
-      if (_node.type === 'asset') {
-        _node.hasDeferred = true;
-      } else if (_node.type === 'asset_group') {
-        _node.hasDeferred = true;
+  markParentsWithHasDeferred(nodeId: NodeId) {
+    this.traverseAncestors(nodeId, (traversedNodeId, _, actions) => {
+      let traversedNode = nullthrows(this.getNode(traversedNodeId));
+      if (traversedNode.type === 'asset') {
+        traversedNode.hasDeferred = true;
+      } else if (traversedNode.type === 'asset_group') {
+        traversedNode.hasDeferred = true;
         actions.skipChildren();
-      } else if (node !== _node) {
+      } else if (nodeId !== traversedNodeId) {
         actions.skipChildren();
       }
     });
   }
 
   // AssetGroup: update hasDeferred of all parent Dependency <- Asset <- AssetGroup
-  unmarkParentsWithHasDeferred(node: AssetGraphNode) {
-    this.traverseAncestors(node, (_node, ctx, actions) => {
-      if (_node.type === 'asset') {
-        let hasDeferred = this.getNodesConnectedFrom(_node).some(_childNode =>
-          _childNode.hasDeferred == null ? false : _childNode.hasDeferred,
+  unmarkParentsWithHasDeferred(nodeId: NodeId) {
+    this.traverseAncestors(nodeId, (traversedNodeId, ctx, actions) => {
+      let traversedNode = nullthrows(this.getNode(traversedNodeId));
+      if (traversedNode.type === 'asset') {
+        let hasDeferred = this.getNodeIdsConnectedFrom(traversedNodeId).some(
+          childNodeId => {
+            let childNode = nullthrows(this.getNode(childNodeId));
+            return childNode.hasDeferred == null
+              ? false
+              : childNode.hasDeferred;
+          },
         );
         if (!hasDeferred) {
-          delete _node.hasDeferred;
+          delete traversedNode.hasDeferred;
         }
         return {hasDeferred};
-      } else if (_node.type === 'asset_group' && node !== _node) {
+      } else if (
+        traversedNode.type === 'asset_group' &&
+        nodeId !== traversedNodeId
+      ) {
         if (!ctx?.hasDeferred) {
-          delete _node.hasDeferred;
+          delete traversedNode.hasDeferred;
         }
         actions.skipChildren();
-      } else if (_node.type === 'dependency') {
-        _node.hasDeferred = false;
-      } else if (node !== _node) {
+      } else if (traversedNode.type === 'dependency') {
+        traversedNode.hasDeferred = false;
+      } else if (nodeId !== traversedNodeId) {
         actions.skipChildren();
       }
     });
@@ -333,15 +369,16 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
       canDefer &&
       !dependencySymbols.has('*')
     ) {
-      let depNode = this.getNode(dependency.id);
+      let depNodeId = this.getNodeIdByContentKey(dependency.id);
+      let depNode = this.getNode(depNodeId);
       invariant(depNode);
 
-      let assets = this.getNodesConnectedTo(depNode);
+      let assets = this.getNodeIdsConnectedTo(depNodeId);
       let symbols = new Map(
         [...dependencySymbols].map(([key, val]) => [val.local, key]),
       );
       invariant(assets.length === 1);
-      let firstAsset = assets[0];
+      let firstAsset = nullthrows(this.getNode(assets[0]));
       invariant(firstAsset.type === 'asset');
       let resolvedAsset = firstAsset.value;
       let deps = this.getIncomingDependencies(resolvedAsset);
@@ -363,11 +400,11 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
   resolveAssetGroup(
     assetGroup: AssetGroup,
     assets: Array<Asset>,
-    correspondingRequest: string,
+    correspondingRequest: ContentKey,
   ) {
     this.normalizeEnvironment(assetGroup);
     let assetGroupNode = nodeFromAssetGroup(assetGroup);
-    assetGroupNode = this.getNode(assetGroupNode.id);
+    assetGroupNode = this.getNodeByContentKey(assetGroupNode.id);
     if (!assetGroupNode) {
       return;
     }
@@ -401,26 +438,33 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
       });
     }
 
-    this.replaceNodesConnectedTo(
-      assetGroupNode,
-      assetObjects.filter(a => a.isDirect).map(a => a.assetNode),
+    const assetNodeIds = [];
+    for (let {assetNode, isDirect} of assetObjects) {
+      if (isDirect) {
+        assetNodeIds.push(this.addNode(assetNode));
+      }
+    }
+
+    this.replaceNodeIdsConnectedTo(
+      this.getNodeIdByContentKey(assetGroupNode.id),
+      assetNodeIds,
     );
     for (let {assetNode, dependentAssets} of assetObjects) {
       // replaceNodesConnectedTo has merged the value into the existing node, retrieve
       // the actual current node.
-      assetNode = nullthrows(this.getNode(assetNode.id));
+      assetNode = nullthrows(this.getNodeByContentKey(assetNode.id));
       invariant(assetNode.type === 'asset');
       this.resolveAsset(assetNode, dependentAssets);
     }
   }
 
   resolveAsset(assetNode: AssetNode, dependentAssets: Array<Asset>) {
-    let depNodes = [];
+    let depNodeIds: Array<NodeId> = [];
     let depNodesWithAssets = [];
     for (let dep of assetNode.value.dependencies.values()) {
       this.normalizeEnvironment(dep);
       let depNode = nodeFromDep(dep);
-      let existing = this.getNode(depNode.id);
+      let existing = this.getNodeByContentKey(depNode.id);
       if (existing) {
         invariant(existing.type === 'dependency');
         depNode.value.meta = existing.value.meta;
@@ -432,44 +476,58 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
         depNode.complete = true;
         depNodesWithAssets.push([depNode, nodeFromAsset(dependentAsset)]);
       }
-      depNodes.push(depNode);
+      depNodeIds.push(this.addNode(depNode));
     }
+
     assetNode.usedSymbolsDownDirty = true;
-    this.replaceNodesConnectedTo(assetNode, depNodes);
+    this.replaceNodeIdsConnectedTo(
+      this.getNodeIdByContentKey(assetNode.id),
+      depNodeIds,
+    );
 
     for (let [depNode, dependentAssetNode] of depNodesWithAssets) {
-      this.replaceNodesConnectedTo(depNode, [dependentAssetNode]);
+      let depAssetNodeId = this.addNode(dependentAssetNode);
+
+      this.replaceNodeIdsConnectedTo(this.getNodeIdByContentKey(depNode.id), [
+        depAssetNodeId,
+      ]);
     }
   }
 
   getIncomingDependencies(asset: Asset): Array<Dependency> {
-    let node = this.getNode(asset.id);
-    if (!node) {
+    if (!this.hasContentKey(asset.id)) {
       return [];
     }
 
-    return this.findAncestors(node, node => node.type === 'dependency').map(
-      node => {
-        invariant(node.type === 'dependency');
-        return node.value;
-      },
-    );
+    let nodeId = this.getNodeIdByContentKey(asset.id);
+    return this.findAncestors(nodeId, nodeId => {
+      let node = this.getNode(nodeId);
+      return node?.type === 'dependency';
+    }).map(nodeId => {
+      let node = this.getNode(nodeId);
+      invariant(node?.type === 'dependency');
+      return node.value;
+    });
   }
 
   traverseAssets<TContext>(
     visit: GraphVisitor<Asset, TContext>,
-    startNode: ?AssetGraphNode,
+    startNodeId: ?NodeId,
   ): ?TContext {
     return this.filteredTraverse(
-      node => (node.type === 'asset' ? node.value : null),
+      nodeId => {
+        let node = nullthrows(this.getNode(nodeId));
+        return node.type === 'asset' ? node.value : null;
+      },
       visit,
-      startNode,
+      startNodeId,
     );
   }
 
   getEntryAssetGroupNodes(): Array<AssetGroupNode> {
     let entryNodes = [];
-    this.traverse((node, _, actions) => {
+    this.traverse((nodeId, _, actions) => {
+      let node = nullthrows(this.getNode(nodeId));
       if (node.type === 'asset_group') {
         entryNodes.push(node);
         actions.skipChildren();
@@ -495,7 +553,8 @@ export default class AssetGraph extends Graph<AssetGraphNode> {
 
     let hash = crypto.createHash('md5');
     // TODO: sort??
-    this.traverse(node => {
+    this.traverse(nodeId => {
+      let node = nullthrows(this.getNode(nodeId));
       if (node.type === 'asset') {
         hash.update(nullthrows(node.value.outputHash));
       } else if (node.type === 'dependency' && node.value.target) {
diff --git a/packages/core/core/src/BundleGraph.js b/packages/core/core/src/BundleGraph.js
index 26619c55b..b2914420b 100644
--- a/packages/core/core/src/BundleGraph.js
+++ b/packages/core/core/src/BundleGraph.js
@@ -16,6 +16,7 @@ import type {
   BundleGraphNode,
   Dependency,
   DependencyNode,
+  NodeId,
 } from './types';
 import type AssetGraph from './AssetGraph';
 
@@ -26,7 +27,8 @@ import nullthrows from 'nullthrows';
 import {objectSortedEntriesDeep} from '@parcel/utils';
 
 import {getBundleGroupId, getPublicId} from './utils';
-import Graph, {ALL_EDGE_TYPES, mapVisitor, type GraphOpts} from './Graph';
+import {ALL_EDGE_TYPES, mapVisitor} from './Graph';
+import ContentGraph, {type SerializedContentGraph} from './ContentGraph';
 import Environment from './public/Environment';
 
 type BundleGraphEdgeTypes =
@@ -67,7 +69,7 @@ type InternalExportSymbolResolution = {|
 
 type SerializedBundleGraph = {|
   $$raw: true,
-  graph: GraphOpts<BundleGraphNode, BundleGraphEdgeTypes>,
+  graph: SerializedContentGraph<BundleGraphNode, BundleGraphEdgeTypes>,
   bundleContentHashes: Map<string, string>,
   assetPublicIds: Set<string>,
   publicIdByAssetId: Map<string, string>,
@@ -79,7 +81,7 @@ function makeReadOnlySet<T>(set: Set<T>): $ReadOnlySet<T> {
       if (property === 'delete' || property === 'add' || property === 'clear') {
         return undefined;
       } else {
-        // $FlowFixMe
+        // $FlowFixMe[incompatible-type]
         let value = target[property];
         return typeof value === 'function' ? value.bind(target) : value;
       }
@@ -95,7 +97,7 @@ export default class BundleGraph {
   // It needs to be exposed in BundlerRunner for now based on how applying runtimes works and the
   // BundlerRunner takes care of invalidating hashes when runtimes are applied, but this is not ideal.
   _bundleContentHashes: Map<string, string>;
-  _graph: Graph<BundleGraphNode, BundleGraphEdgeTypes>;
+  _graph: ContentGraph<BundleGraphNode, BundleGraphEdgeTypes>;
 
   constructor({
     graph,
@@ -103,7 +105,7 @@ export default class BundleGraph {
     assetPublicIds,
     bundleContentHashes,
   }: {|
-    graph: Graph<BundleGraphNode, BundleGraphEdgeTypes>,
+    graph: ContentGraph<BundleGraphNode, BundleGraphEdgeTypes>,
     publicIdByAssetId: Map<string, string>,
     assetPublicIds: Set<string>,
     bundleContentHashes: Map<string, string>,
@@ -119,14 +121,17 @@ export default class BundleGraph {
     publicIdByAssetId: Map<string, string> = new Map(),
     assetPublicIds: Set<string> = new Set(),
   ): BundleGraph {
-    let graph = new Graph<BundleGraphNode, BundleGraphEdgeTypes>();
+    let graph = new ContentGraph<BundleGraphNode, BundleGraphEdgeTypes>();
+    let assetGroupIds = new Set();
+    let assetGraphNodeIdToBundleGraphNodeId = new Map<NodeId, NodeId>();
 
-    let rootNode = assetGraph.getRootNode();
-    invariant(rootNode != null && rootNode.type === 'root');
-    graph.setRootNode(rootNode);
+    let assetGraphRootNode =
+      assetGraph.rootNodeId != null
+        ? assetGraph.getNode(assetGraph.rootNodeId)
+        : null;
+    invariant(assetGraphRootNode != null && assetGraphRootNode.type === 'root');
 
-    let assetGroupIds = new Set();
-    for (let [, node] of assetGraph.nodes) {
+    for (let [nodeId, node] of assetGraph.nodes) {
       if (node.type === 'asset') {
         let {id: assetId} = node.value;
         // Generate a new, short public id for this asset to use.
@@ -143,9 +148,13 @@ export default class BundleGraph {
 
       // Don't copy over asset groups into the bundle graph.
       if (node.type === 'asset_group') {
-        assetGroupIds.add(node.id);
+        assetGroupIds.add(nodeId);
       } else {
-        graph.addNode(node);
+        let bundleGraphNodeId = graph.addNodeByContentKey(node.id, node);
+        if (node.id === assetGraphRootNode?.id) {
+          graph.setRootNodeId(bundleGraphNodeId);
+        }
+        assetGraphNodeIdToBundleGraphNodeId.set(nodeId, bundleGraphNodeId);
       }
     }
 
@@ -160,10 +169,16 @@ export default class BundleGraph {
       for (let from of fromIds) {
         if (assetGroupIds.has(edge.to)) {
           for (let to of assetGraph.outboundEdges.getEdges(edge.to, null)) {
-            graph.addEdge(from, to);
+            graph.addEdge(
+              nullthrows(assetGraphNodeIdToBundleGraphNodeId.get(from)),
+              nullthrows(assetGraphNodeIdToBundleGraphNodeId.get(to)),
+            );
           }
         } else {
-          graph.addEdge(from, edge.to);
+          graph.addEdge(
+            nullthrows(assetGraphNodeIdToBundleGraphNodeId.get(from)),
+            nullthrows(assetGraphNodeIdToBundleGraphNodeId.get(edge.to)),
+          );
         }
       }
     }
@@ -188,7 +203,7 @@ export default class BundleGraph {
 
   static deserialize(serialized: SerializedBundleGraph): BundleGraph {
     return new BundleGraph({
-      graph: Graph.deserialize(serialized.graph),
+      graph: ContentGraph.deserialize(serialized.graph),
       assetPublicIds: serialized.assetPublicIds,
       bundleContentHashes: serialized.bundleContentHashes,
       publicIdByAssetId: serialized.publicIdByAssetId,
@@ -201,10 +216,14 @@ export default class BundleGraph {
     shouldSkipDependency: Dependency => boolean = d =>
       this.isDependencySkipped(d),
   ) {
+    let assetNodeId = this._graph.getNodeIdByContentKey(asset.id);
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
+
     // The root asset should be reached directly from the bundle in traversal.
     // Its children will be traversed from there.
-    this._graph.addEdge(bundle.id, asset.id);
-    this._graph.traverse((node, _, actions) => {
+    this._graph.addEdge(bundleNodeId, assetNodeId);
+    this._graph.traverse((nodeId, _, actions) => {
+      let node = nullthrows(this._graph.getNode(nodeId));
       if (node.type === 'bundle_group') {
         actions.skipChildren();
         return;
@@ -220,28 +239,30 @@ export default class BundleGraph {
       }
 
       if (node.type === 'asset' || node.type === 'dependency') {
-        this._graph.addEdge(bundle.id, node.id, 'contains');
+        this._graph.addEdge(bundleNodeId, nodeId, 'contains');
       }
 
       if (node.type === 'dependency') {
-        for (let bundleGroupNode of this._graph
-          .getNodesConnectedFrom(node)
-          .filter(node => node.type === 'bundle_group')) {
+        for (let [bundleGroupNodeId, bundleGroupNode] of this._graph
+          .getNodeIdsConnectedFrom(nodeId)
+          .map(id => [id, nullthrows(this._graph.getNode(id))])
+          .filter(([, node]) => node.type === 'bundle_group')) {
           invariant(bundleGroupNode.type === 'bundle_group');
-          this._graph.addEdge(bundle.id, bundleGroupNode.id, 'bundle');
+          this._graph.addEdge(bundleNodeId, bundleGroupNodeId, 'bundle');
         }
 
         // If the dependency references a target bundle, add a reference edge from
         // the source bundle to the dependency for easy traversal.
         if (
           this._graph
-            .getNodesConnectedFrom(node, 'references')
+            .getNodeIdsConnectedFrom(nodeId, 'references')
+            .map(id => nullthrows(this._graph.getNode(id)))
             .some(node => node.type === 'bundle')
         ) {
-          this._graph.addEdge(bundle.id, node.id, 'references');
+          this._graph.addEdge(bundleNodeId, nodeId, 'references');
         }
       }
-    }, nullthrows(this._graph.getNode(asset.id)));
+    }, assetNodeId);
     this._bundleContentHashes.delete(bundle.id);
   }
 
@@ -261,22 +282,27 @@ export default class BundleGraph {
       throw new Error('Expected an async dependency');
     }
 
-    this._graph.addEdge(bundle.id, dependency.id, 'internal_async');
+    this._graph.addEdge(
+      this._graph.getNodeIdByContentKey(bundle.id),
+      this._graph.getNodeIdByContentKey(dependency.id),
+      'internal_async',
+    );
     this.removeExternalDependency(bundle, dependency);
   }
 
   isDependencySkipped(dependency: Dependency): boolean {
-    let node = this._graph.getNode(dependency.id);
+    let node = this._graph.getNodeByContentKey(dependency.id);
     invariant(node && node.type === 'dependency');
     return !!node.hasDeferred || node.excluded;
   }
 
   getParentBundlesOfBundleGroup(bundleGroup: BundleGroup): Array<Bundle> {
     return this._graph
-      .getNodesConnectedTo(
-        nullthrows(this._graph.getNode(getBundleGroupId(bundleGroup))),
+      .getNodeIdsConnectedTo(
+        this._graph.getNodeIdByContentKey(getBundleGroupId(bundleGroup)),
         'bundle',
       )
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'bundle')
       .map(node => {
         invariant(node.type === 'bundle');
@@ -291,24 +317,31 @@ export default class BundleGraph {
     | {|type: 'bundle_group', value: BundleGroup|}
     | {|type: 'asset', value: Asset|}
   ) {
-    let depNode = nullthrows(this._graph.getNode(dependency.id));
+    let depNodeId = this._graph.getNodeIdByContentKey(dependency.id);
+    let bundleNodeId =
+      bundle != null ? this._graph.getNodeIdByContentKey(bundle.id) : null;
 
     if (
-      bundle != null &&
-      this._graph.hasEdge(bundle.id, depNode.id, 'internal_async')
+      bundleNodeId != null &&
+      this._graph.hasEdge(bundleNodeId, depNodeId, 'internal_async')
     ) {
-      let referencedAssetNode = this._graph.getNodesConnectedFrom(
-        depNode,
+      let referencedAssetNodeIds = this._graph.getNodeIdsConnectedFrom(
+        depNodeId,
         'references',
-      )[0];
+      );
 
       let resolved;
-      if (referencedAssetNode == null) {
+      if (referencedAssetNodeIds.length === 0) {
         resolved = this.getDependencyResolution(dependency, bundle);
-      } else {
+      } else if (referencedAssetNodeIds.length === 1) {
+        let referencedAssetNode = this._graph.getNode(
+          referencedAssetNodeIds[0],
+        );
         // If a referenced asset already exists, resolve this dependency to it.
-        invariant(referencedAssetNode.type === 'asset');
+        invariant(referencedAssetNode?.type === 'asset');
         resolved = referencedAssetNode.value;
+      } else {
+        throw new Error('Dependencies can only reference one asset');
       }
 
       if (resolved == null) {
@@ -322,7 +355,8 @@ export default class BundleGraph {
     }
 
     let node = this._graph
-      .getNodesConnectedFrom(nullthrows(this._graph.getNode(dependency.id)))
+      .getNodeIdsConnectedFrom(this._graph.getNodeIdByContentKey(dependency.id))
+      .map(id => nullthrows(this._graph.getNode(id)))
       .find(node => node.type === 'bundle_group');
 
     if (node == null) {
@@ -337,9 +371,12 @@ export default class BundleGraph {
   }
 
   getReferencedBundle(dependency: Dependency, fromBundle: Bundle): ?Bundle {
+    let dependencyNodeId = this._graph.getNodeIdByContentKey(dependency.id);
+
     // If this dependency is async, there will be a bundle group attached to it.
     let node = this._graph
-      .getNodesConnectedFrom(nullthrows(this._graph.getNode(dependency.id)))
+      .getNodeIdsConnectedFrom(dependencyNodeId)
+      .map(id => nullthrows(this._graph.getNode(id)))
       .find(node => node.type === 'bundle_group');
 
     if (node != null) {
@@ -354,10 +391,8 @@ export default class BundleGraph {
     // Resolve the dependency to an asset, and look for it in one of the referenced bundles.
     let referencedBundles = this.getReferencedBundles(fromBundle);
     let referenced = this._graph
-      .getNodesConnectedFrom(
-        nullthrows(this._graph.getNode(dependency.id)),
-        'references',
-      )
+      .getNodeIdsConnectedFrom(dependencyNodeId, 'references')
+      .map(id => nullthrows(this._graph.getNode(id)))
       .find(node => node.type === 'asset');
 
     if (referenced != null) {
@@ -369,9 +404,14 @@ export default class BundleGraph {
   }
 
   removeAssetGraphFromBundle(asset: Asset, bundle: Bundle) {
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
+    let assetNodeId = this._graph.getNodeIdByContentKey(asset.id);
+
     // Remove all contains edges from the bundle to the nodes in the asset's
     // subgraph.
-    this._graph.traverse((node, context, actions) => {
+    this._graph.traverse((nodeId, context, actions) => {
+      let node = nullthrows(this._graph.getNode(nodeId));
+
       if (node.type === 'bundle_group') {
         actions.skipChildren();
         return;
@@ -381,10 +421,10 @@ export default class BundleGraph {
         return;
       }
 
-      if (this._graph.hasEdge(bundle.id, node.id, 'contains')) {
+      if (this._graph.hasEdge(bundleNodeId, nodeId, 'contains')) {
         this._graph.removeEdge(
-          bundle.id,
-          node.id,
+          bundleNodeId,
+          nodeId,
           'contains',
           // Removing this contains edge should not orphan the connected node. This
           // is disabled for performance reasons as these edges are removed as part
@@ -400,9 +440,9 @@ export default class BundleGraph {
         actions.skipChildren();
       }
 
-      if (node.type === 'asset' && this._graph.hasEdge(bundle.id, node.id)) {
+      if (node.type === 'asset' && this._graph.hasEdge(bundleNodeId, nodeId)) {
         // Remove the untyped edge from the bundle to the node (it's an entry)
-        this._graph.removeEdge(bundle.id, node.id);
+        this._graph.removeEdge(bundleNodeId, nodeId);
 
         let entryIndex = bundle.entryAssetIds.indexOf(node.value.id);
         if (entryIndex >= 0) {
@@ -414,15 +454,14 @@ export default class BundleGraph {
 
       if (node.type === 'dependency') {
         this.removeExternalDependency(bundle, node.value);
-        if (this._graph.hasEdge(bundle.id, node.id, 'references')) {
-          this._graph.removeEdge(bundle.id, node.id, 'references');
+        if (this._graph.hasEdge(bundleNodeId, nodeId, 'references')) {
+          this._graph.addEdge(bundleNodeId, nodeId, 'references');
         }
       }
-    }, nullthrows(this._graph.getNode(asset.id)));
+    }, assetNodeId);
 
-    // Remove bundle node if it no longer has any asset graphs
-    let bundleNode = nullthrows(this._graph.getNode(bundle.id));
-    if (this._graph.getNodesConnectedFrom(bundleNode).length === 0) {
+    // Remove bundle node if it no longer has any entry assets
+    if (this._graph.getNodeIdsConnectedFrom(bundleNodeId).length === 0) {
       this.removeBundle(bundle);
     }
 
@@ -431,17 +470,18 @@ export default class BundleGraph {
 
   removeBundle(bundle: Bundle): Set<BundleGroup> {
     // Remove bundle node if it no longer has any entry assets
-    let bundleNode = nullthrows(this._graph.getNode(bundle.id));
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
 
-    let bundleGroupNodes = this._graph.getNodesConnectedTo(
-      bundleNode,
+    let bundleGroupNodeIds = this._graph.getNodeIdsConnectedTo(
+      bundleNodeId,
       'bundle',
     );
-    this._graph.removeNode(bundleNode);
+    this._graph.removeNode(bundleNodeId);
 
     let removedBundleGroups: Set<BundleGroup> = new Set();
     // Remove bundle group node if it no longer has any bundles
-    for (let bundleGroupNode of bundleGroupNodes) {
+    for (let bundleGroupNodeId of bundleGroupNodeIds) {
+      let bundleGroupNode = nullthrows(this._graph.getNode(bundleGroupNodeId));
       invariant(bundleGroupNode.type === 'bundle_group');
       let bundleGroup = bundleGroupNode.value;
 
@@ -463,7 +503,7 @@ export default class BundleGraph {
 
   removeBundleGroup(bundleGroup: BundleGroup) {
     let bundleGroupNode = nullthrows(
-      this._graph.getNode(getBundleGroupId(bundleGroup)),
+      this._graph.getNodeByContentKey(getBundleGroupId(bundleGroup)),
     );
     invariant(bundleGroupNode.type === 'bundle_group');
 
@@ -479,7 +519,14 @@ export default class BundleGraph {
       }
     }
 
-    this._graph.removeNode(bundleGroupNode);
+    // This function can be reentered through removeBundle above. In this case,
+    // the node may already been removed.
+    if (this._graph.hasContentKey(bundleGroupNode.id)) {
+      this._graph.removeNode(
+        this._graph.getNodeIdByContentKey(bundleGroupNode.id),
+      );
+    }
+
     assert(
       bundlesInGroup.every(
         bundle => this.getBundleGroupsContainingBundle(bundle).length > 0,
@@ -488,15 +535,22 @@ export default class BundleGraph {
   }
 
   removeExternalDependency(bundle: Bundle, dependency: Dependency) {
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
     for (let bundleGroupNode of this._graph
-      .getNodesConnectedFrom(nullthrows(this._graph.getNode(dependency.id)))
+      .getNodeIdsConnectedFrom(this._graph.getNodeIdByContentKey(dependency.id))
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'bundle_group')) {
-      if (!this._graph.hasEdge(bundle.id, bundleGroupNode.id, 'bundle')) {
+      let bundleGroupNodeId = this._graph.getNodeIdByContentKey(
+        bundleGroupNode.id,
+      );
+
+      if (!this._graph.hasEdge(bundleNodeId, bundleGroupNodeId, 'bundle')) {
         continue;
       }
 
       let inboundDependencies = this._graph
-        .getNodesConnectedTo(bundleGroupNode)
+        .getNodeIdsConnectedTo(bundleGroupNodeId)
+        .map(id => nullthrows(this._graph.getNode(id)))
         .filter(node => node.type === 'dependency')
         .map(node => {
           invariant(node.type === 'dependency');
@@ -510,10 +564,14 @@ export default class BundleGraph {
         inboundDependencies.every(
           dependency =>
             !this.bundleHasDependency(bundle, dependency) ||
-            this._graph.hasEdge(bundle.id, dependency.id, 'internal_async'),
+            this._graph.hasEdge(
+              bundleNodeId,
+              this._graph.getNodeIdByContentKey(dependency.id),
+              'internal_async',
+            ),
         )
       ) {
-        this._graph.removeEdge(bundle.id, bundleGroupNode.id, 'bundle');
+        this._graph.removeEdge(bundleNodeId, bundleGroupNodeId, 'bundle');
       }
     }
   }
@@ -523,23 +581,32 @@ export default class BundleGraph {
     asset: Asset,
     bundle: Bundle,
   ): void {
-    this._graph.addEdge(dependency.id, asset.id, 'references');
-    this._graph.addEdge(dependency.id, bundle.id, 'references');
-    if (this._graph.hasEdge(dependency.id, asset.id)) {
-      this._graph.removeEdge(dependency.id, asset.id);
+    let dependencyId = this._graph.getNodeIdByContentKey(dependency.id);
+    let assetId = this._graph.getNodeIdByContentKey(asset.id);
+    let bundleId = this._graph.getNodeIdByContentKey(bundle.id);
+    this._graph.addEdge(dependencyId, assetId, 'references');
+
+    this._graph.addEdge(dependencyId, bundleId, 'references');
+    if (this._graph.hasEdge(dependencyId, assetId)) {
+      this._graph.removeEdge(dependencyId, assetId);
     }
   }
 
   createBundleReference(from: Bundle, to: Bundle): void {
-    this._graph.addEdge(from.id, to.id, 'references');
+    this._graph.addEdge(
+      this._graph.getNodeIdByContentKey(from.id),
+      this._graph.getNodeIdByContentKey(to.id),
+      'references',
+    );
   }
 
   findBundlesWithAsset(asset: Asset): Array<Bundle> {
     return this._graph
-      .getNodesConnectedTo(
-        nullthrows(this._graph.getNode(asset.id)),
+      .getNodeIdsConnectedTo(
+        this._graph.getNodeIdByContentKey(asset.id),
         'contains',
       )
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'bundle')
       .map(node => {
         invariant(node.type === 'bundle');
@@ -549,10 +616,11 @@ export default class BundleGraph {
 
   findBundlesWithDependency(dependency: Dependency): Array<Bundle> {
     return this._graph
-      .getNodesConnectedTo(
-        nullthrows(this._graph.getNode(dependency.id)),
+      .getNodeIdsConnectedTo(
+        nullthrows(this._graph.getNodeIdByContentKey(dependency.id)),
         'contains',
       )
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'bundle')
       .map(node => {
         invariant(node.type === 'bundle');
@@ -561,9 +629,9 @@ export default class BundleGraph {
   }
 
   getDependencyAssets(dependency: Dependency): Array<Asset> {
-    let dependencyNode = nullthrows(this._graph.getNode(dependency.id));
     return this._graph
-      .getNodesConnectedFrom(dependencyNode)
+      .getNodeIdsConnectedFrom(this._graph.getNodeIdByContentKey(dependency.id))
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'asset')
       .map(node => {
         invariant(node.type === 'asset');
@@ -572,11 +640,6 @@ export default class BundleGraph {
   }
 
   getDependencyResolution(dep: Dependency, bundle: ?Bundle): ?Asset {
-    let depNode = this._graph.getNode(dep.id);
-    if (!depNode) {
-      return null;
-    }
-
     let assets = this.getDependencyAssets(dep);
     let firstAsset = assets[0];
     let resolved =
@@ -590,7 +653,8 @@ export default class BundleGraph {
     // If a resolution still hasn't been found, return the first referenced asset.
     if (resolved == null) {
       this._graph.traverse(
-        (node, _, traversal) => {
+        (nodeId, _, traversal) => {
+          let node = nullthrows(this._graph.getNode(nodeId));
           if (node.type === 'asset') {
             resolved = node.value;
             traversal.stop();
@@ -598,7 +662,7 @@ export default class BundleGraph {
             traversal.skipChildren();
           }
         },
-        depNode,
+        this._graph.getNodeIdByContentKey(dep.id),
         'references',
       );
     }
@@ -607,12 +671,9 @@ export default class BundleGraph {
   }
 
   getDependencies(asset: Asset): Array<Dependency> {
-    let node = this._graph.getNode(asset.id);
-    if (!node) {
-      throw new Error('Asset not found');
-    }
-
-    return this._graph.getNodesConnectedFrom(node).map(node => {
+    let nodeId = this._graph.getNodeIdByContentKey(asset.id);
+    return this._graph.getNodeIdsConnectedFrom(nodeId).map(id => {
+      let node = nullthrows(this._graph.getNode(id));
       invariant(node.type === 'dependency');
       return node.value;
     });
@@ -629,9 +690,10 @@ export default class BundleGraph {
   }
 
   isAssetReferencedByDependant(bundle: Bundle, asset: Asset): boolean {
-    let assetNode = nullthrows(this._graph.getNode(asset.id));
+    let assetNodeId = nullthrows(this._graph.getNodeIdByContentKey(asset.id));
     let dependencies = this._graph
-      .getNodesConnectedTo(assetNode)
+      .getNodeIdsConnectedTo(assetNodeId)
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'dependency')
       .map(node => {
         invariant(node.type === 'dependency');
@@ -639,11 +701,12 @@ export default class BundleGraph {
       });
 
     // Collect bundles that depend on this asset being available to reference
-    // asynchonously. If any of them appear in our traversal, this asset is
+    // asynchronously. If any of them appear in our traversal, this asset is
     // referenced.
     let asyncInternalReferencingBundles = new Set(
       this._graph
-        .getNodesConnectedTo(assetNode, 'references')
+        .getNodeIdsConnectedTo(assetNodeId, 'references')
+        .map(id => nullthrows(this._graph.getNode(id)))
         .filter(node => node.type === 'dependency')
         .map(node => {
           invariant(node.type === 'dependency');
@@ -651,8 +714,12 @@ export default class BundleGraph {
         })
         .flatMap(dependencyNode =>
           this._graph
-            .getNodesConnectedTo(dependencyNode, 'internal_async')
-            .map(node => {
+            .getNodeIdsConnectedTo(
+              this._graph.getNodeIdByContentKey(dependencyNode.id),
+              'internal_async',
+            )
+            .map(id => {
+              let node = nullthrows(this._graph.getNode(id));
               invariant(node.type === 'bundle');
               return node.value;
             }),
@@ -671,7 +738,7 @@ export default class BundleGraph {
 
     let visitedBundles: Set<Bundle> = new Set();
     // Check if any of this bundle's descendants, referencers, bundles referenced
-    // by referencers, or descedants of its referencers reference the asset.
+    // by referencers, or descendants of its referencers reference the asset.
     let siblingBundles = new Set(
       this.getBundleGroupsContainingBundle(bundle).flatMap(bundleGroup =>
         this.getBundlesInBundleGroup(bundleGroup),
@@ -752,21 +819,23 @@ export default class BundleGraph {
       }
 
       // Get a list of parent bundle nodes pointing to the bundle group
-      let parentBundleNodes = this._graph.getNodesConnectedTo(
-        nullthrows(this._graph.getNode(getBundleGroupId(bundleGroup))),
+      let parentBundleNodes = this._graph.getNodeIdsConnectedTo(
+        this._graph.getNodeIdByContentKey(getBundleGroupId(bundleGroup)),
         'bundle',
       );
 
       // Check that every parent bundle has a bundle group in its ancestry that contains the asset.
-      return parentBundleNodes.every(bundleNode => {
+      return parentBundleNodes.every(bundleNodeId => {
+        let bundleNode = nullthrows(this._graph.getNode(bundleNodeId));
         if (bundleNode.type === 'root') {
           return false;
         }
 
         let isReachable = true;
         this._graph.traverseAncestors(
-          bundleNode,
-          (node, ctx, actions) => {
+          bundleNodeId,
+          (nodeId, ctx, actions) => {
+            let node = nullthrows(this._graph.getNode(nodeId));
             // If we've reached the root or a context change without
             // finding this asset in the ancestry, it is not reachable.
             if (
@@ -814,14 +883,15 @@ export default class BundleGraph {
 
       let parentBundleNodes = this.getParentBundlesOfBundleGroup(
         bundleGroup,
-      ).map(bundle => nullthrows(this._graph.getNode(bundle.id)));
+      ).map(bundle => nullthrows(this._graph.getNodeByContentKey(bundle.id)));
 
       // Find the nearest ancestor bundle that includes the asset.
       for (let bundleNode of parentBundleNodes) {
         invariant(bundleNode.type === 'bundle');
         this._graph.traverseAncestors(
-          bundleNode,
-          (node, ctx, actions) => {
+          this._graph.getNodeIdByContentKey(bundleNode.id),
+          (nodeId, ctx, actions) => {
+            let node = nullthrows(this._graph.getNode(nodeId));
             if (node.type === 'bundle_group') {
               let childBundles = this.getBundlesInBundleGroup(
                 node.value,
@@ -858,29 +928,35 @@ export default class BundleGraph {
     visit: GraphVisitor<AssetNode | DependencyNode, TContext>,
   ): ?TContext {
     let entries = true;
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
 
     // A modified DFS traversal which traverses entry assets in the same order
     // as their ids appear in `bundle.entryAssetIds`.
     return this._graph.dfs({
-      visit: mapVisitor((node, actions) => {
-        if (node.id === bundle.id) {
+      visit: mapVisitor((nodeId, actions) => {
+        let node = nullthrows(this._graph.getNode(nodeId));
+
+        if (nodeId === bundleNodeId) {
           return;
         }
 
         if (node.type === 'dependency' || node.type === 'asset') {
-          if (this._graph.hasEdge(bundle.id, node.id, 'contains')) {
+          if (this._graph.hasEdge(bundleNodeId, nodeId, 'contains')) {
             return node;
           }
         }
 
         actions.skipChildren();
       }, visit),
-      startNode: nullthrows(this._graph.getNode(bundle.id)),
-      getChildren: node => {
-        let children = this._graph.getNodesConnectedFrom(nullthrows(node));
+      startNodeId: bundleNodeId,
+      getChildren: nodeId => {
+        let children = this._graph
+          .getNodeIdsConnectedFrom(nodeId)
+          .map(id => [id, nullthrows(this._graph.getNode(id))]);
+
         let sorted =
           entries && bundle.entryAssetIds.length > 0
-            ? children.sort((a, b) => {
+            ? children.sort(([, a], [, b]) => {
                 let aIndex = bundle.entryAssetIds.indexOf(a.id);
                 let bIndex = bundle.entryAssetIds.indexOf(b.id);
 
@@ -899,7 +975,7 @@ export default class BundleGraph {
             : children;
 
         entries = false;
-        return sorted;
+        return sorted.map(([id]) => id);
       },
     });
   }
@@ -907,11 +983,10 @@ export default class BundleGraph {
   traverseContents<TContext>(
     visit: GraphVisitor<AssetNode | DependencyNode, TContext>,
   ): ?TContext {
-    return this._graph.filteredTraverse(
-      node =>
-        node.type === 'asset' || node.type === 'dependency' ? node : null,
-      visit,
-    );
+    return this._graph.filteredTraverse(nodeId => {
+      let node = nullthrows(this._graph.getNode(nodeId));
+      return node.type === 'asset' || node.type === 'dependency' ? node : null;
+    }, visit);
   }
 
   getChildBundles(bundle: Bundle): Array<Bundle> {
@@ -936,9 +1011,12 @@ export default class BundleGraph {
     startBundle: ?Bundle,
   ): ?TContext {
     return this._graph.filteredTraverse(
-      node => (node.type === 'bundle' ? node.value : null),
+      nodeId => {
+        let node = nullthrows(this._graph.getNode(nodeId));
+        return node.type === 'bundle' ? node.value : null;
+      },
       visit,
-      startBundle ? nullthrows(this._graph.getNode(startBundle.id)) : null,
+      startBundle ? this._graph.getNodeIdByContentKey(startBundle.id) : null,
       ['bundle', 'references'],
     );
   }
@@ -954,7 +1032,8 @@ export default class BundleGraph {
 
   getTotalSize(asset: Asset): number {
     let size = 0;
-    this._graph.traverse((node, _, actions) => {
+    this._graph.traverse((nodeId, _, actions) => {
+      let node = nullthrows(this._graph.getNode(nodeId));
       if (node.type === 'bundle_group') {
         actions.skipChildren();
         return;
@@ -963,17 +1042,17 @@ export default class BundleGraph {
       if (node.type === 'asset') {
         size += node.value.stats.size;
       }
-    }, nullthrows(this._graph.getNode(asset.id)));
+    }, this._graph.getNodeIdByContentKey(asset.id));
     return size;
   }
 
   getReferencingBundles(bundle: Bundle): Array<Bundle> {
     let referencingBundles: Set<Bundle> = new Set();
 
-    let bundleNode = nullthrows(this._graph.getNode(bundle.id));
     this._graph.traverseAncestors(
-      bundleNode,
-      node => {
+      this._graph.getNodeIdByContentKey(bundle.id),
+      nodeId => {
+        let node = nullthrows(this._graph.getNode(nodeId));
         if (node.type === 'bundle' && node.value.id !== bundle.id) {
           referencingBundles.add(node.value);
         }
@@ -998,7 +1077,11 @@ export default class BundleGraph {
 
   getDirectParentBundleGroups(bundle: Bundle): Array<BundleGroup> {
     return this._graph
-      .getNodesConnectedTo(nullthrows(this._graph.getNode(bundle.id)), 'bundle')
+      .getNodeIdsConnectedTo(
+        nullthrows(this._graph.getNodeIdByContentKey(bundle.id)),
+        'bundle',
+      )
+      .map(id => nullthrows(this._graph.getNode(id)))
       .filter(node => node.type === 'bundle_group')
       .map(node => {
         invariant(node.type === 'bundle_group');
@@ -1008,13 +1091,11 @@ export default class BundleGraph {
 
   getBundlesInBundleGroup(bundleGroup: BundleGroup): Array<Bundle> {
     let bundles: Set<Bundle> = new Set();
-    let bundleGroupNode = nullthrows(
-      this._graph.getNode(getBundleGroupId(bundleGroup)),
-    );
-    for (let bundleNode of this._graph.getNodesConnectedFrom(
-      bundleGroupNode,
+    for (let bundleNodeId of this._graph.getNodeIdsConnectedFrom(
+      this._graph.getNodeIdByContentKey(getBundleGroupId(bundleGroup)),
       'bundle',
     )) {
+      let bundleNode = nullthrows(this._graph.getNode(bundleNodeId));
       invariant(bundleNode.type === 'bundle');
       let bundle = bundleNode.value;
       bundles.add(bundle);
@@ -1033,9 +1114,9 @@ export default class BundleGraph {
   ): Array<Bundle> {
     let recursive = opts?.recursive ?? true;
     let referencedBundles = new Set();
-    let bundleNode = nullthrows(this._graph.getNode(bundle.id));
     this._graph.dfs({
-      visit: (node, _, actions) => {
+      visit: (nodeId, _, actions) => {
+        let node = nullthrows(this._graph.getNode(nodeId));
         if (node.type !== 'bundle') {
           return;
         }
@@ -1049,71 +1130,73 @@ export default class BundleGraph {
           actions.skipChildren();
         }
       },
-      startNode: bundleNode,
-      getChildren: node =>
+      startNodeId: this._graph.getNodeIdByContentKey(bundle.id),
+      getChildren: nodeId =>
         // Shared bundles seem to depend on being used in the opposite order
         // they were added.
         // TODO: Should this be the case?
-        this._graph.getNodesConnectedFrom(node, 'references').reverse(),
+        this._graph.getNodeIdsConnectedFrom(nodeId, 'references').reverse(),
     });
 
     return [...referencedBundles];
   }
 
   getIncomingDependencies(asset: Asset): Array<Dependency> {
-    let node = this._graph.getNode(asset.id);
-    if (!node) {
+    if (!this._graph.hasContentKey(asset.id)) {
       return [];
     }
-
     // Dependencies can be a a parent node via an untyped edge (like in the AssetGraph but without AssetGroups)
     // or they can be parent nodes via a 'references' edge
-    return (
-      this._graph
+    return this._graph
+      .getNodeIdsConnectedTo(
+        this._graph.getNodeIdByContentKey(asset.id),
         // $FlowFixMe
-        .getNodesConnectedTo(node, ALL_EDGE_TYPES)
-        .filter(n => n.type === 'dependency')
-        .map(n => {
-          invariant(n.type === 'dependency');
-          return n.value;
-        })
-    );
+        ALL_EDGE_TYPES,
+      )
+      .map(id => nullthrows(this._graph.getNode(id)))
+      .filter(n => n.type === 'dependency')
+      .map(n => {
+        invariant(n.type === 'dependency');
+        return n.value;
+      });
   }
 
   getAssetWithDependency(dep: Dependency): ?Asset {
-    let node = this._graph.getNode(dep.id);
-    if (!node) {
+    if (!this._graph.hasContentKey(dep.id)) {
       return null;
     }
 
-    let res = this._graph.getNodesConnectedTo(node);
+    let res = this._graph.getNodeIdsConnectedTo(
+      this._graph.getNodeIdByContentKey(dep.id),
+    );
     invariant(
       res.length <= 1,
       'Expected a single asset to be connected to a dependency',
     );
-    if (res[0]?.type === 'asset') {
-      return res[0].value;
+    let resNode = this._graph.getNode(res[0]);
+    if (resNode?.type === 'asset') {
+      return resNode.value;
     }
   }
 
   bundleHasAsset(bundle: Bundle, asset: Asset): boolean {
-    return this._graph.hasEdge(bundle.id, asset.id, 'contains');
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
+    let assetNodeId = this._graph.getNodeIdByContentKey(asset.id);
+    return this._graph.hasEdge(bundleNodeId, assetNodeId, 'contains');
   }
 
   bundleHasDependency(bundle: Bundle, dependency: Dependency): boolean {
-    return this._graph.hasEdge(bundle.id, dependency.id, 'contains');
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
+    let dependencyNodeId = this._graph.getNodeIdByContentKey(dependency.id);
+    return this._graph.hasEdge(bundleNodeId, dependencyNodeId, 'contains');
   }
 
   filteredTraverse<TValue, TContext>(
-    bundle: Bundle,
-    filter: (BundleGraphNode, TraversalActions) => ?TValue,
+    bundleNodeId: NodeId,
+    filter: (NodeId, TraversalActions) => ?TValue,
     visit: GraphVisitor<TValue, TContext>,
   ): ?TContext {
-    return this._graph.filteredTraverse(
-      filter,
-      visit,
-      nullthrows(this._graph.getNode(bundle.id)),
-    );
+    return this._graph.filteredTraverse(filter, visit, bundleNodeId);
   }
 
   resolveSymbol(
@@ -1191,7 +1274,6 @@ export default class BundleGraph {
           loc,
         };
       }
-
       // If this module exports wildcards, resolve the original module.
       // Default exports are excluded from wildcard exports.
       // Wildcard reexports are never listed in the reexporting asset's symbols.
@@ -1255,7 +1337,6 @@ export default class BundleGraph {
         }
       }
     }
-
     // We didn't find the exact symbol...
     if (potentialResults.length == 1) {
       // ..., but if it does exist, it has to be behind this one reexport.
@@ -1274,8 +1355,8 @@ export default class BundleGraph {
       };
     }
   }
-  getAssetById(id: string): Asset {
-    let node = this._graph.getNode(id);
+  getAssetById(contentKey: string): Asset {
+    let node = this._graph.getNodeByContentKey(contentKey);
     if (node == null) {
       throw new Error('Node not found');
     } else if (node.type !== 'asset') {
@@ -1408,76 +1489,95 @@ export default class BundleGraph {
   }
 
   addBundleToBundleGroup(bundle: Bundle, bundleGroup: BundleGroup) {
-    let bundleGroupId = getBundleGroupId(bundleGroup);
-    if (this._graph.hasEdge(bundleGroupId, bundle.id, 'bundle')) {
+    let bundleGroupNodeId = this._graph.getNodeIdByContentKey(
+      getBundleGroupId(bundleGroup),
+    );
+    let bundleNodeId = this._graph.getNodeIdByContentKey(bundle.id);
+    if (this._graph.hasEdge(bundleGroupNodeId, bundleNodeId, 'bundle')) {
       // Bundle group already has bundle
       return;
     }
 
-    this._graph.addEdge(bundleGroupId, bundle.id);
-    this._graph.addEdge(bundleGroupId, bundle.id, 'bundle');
+    this._graph.addEdge(bundleGroupNodeId, bundleNodeId);
+    this._graph.addEdge(bundleGroupNodeId, bundleNodeId, 'bundle');
 
     for (let entryAssetId of bundle.entryAssetIds) {
-      if (this._graph.hasEdge(bundleGroupId, entryAssetId)) {
-        this._graph.removeEdge(bundleGroupId, entryAssetId);
+      let entryAssetNodeId = this._graph.getNodeIdByContentKey(entryAssetId);
+      if (this._graph.hasEdge(bundleGroupNodeId, entryAssetNodeId)) {
+        this._graph.removeEdge(bundleGroupNodeId, entryAssetNodeId);
       }
     }
   }
 
   getUsedSymbolsAsset(asset: Asset): $ReadOnlySet<Symbol> {
-    let node = this._graph.getNode(asset.id);
+    let node = this._graph.getNodeByContentKey(asset.id);
     invariant(node && node.type === 'asset');
     return makeReadOnlySet(node.usedSymbols);
   }
 
   getUsedSymbolsDependency(dep: Dependency): $ReadOnlySet<Symbol> {
-    let node = this._graph.getNode(dep.id);
+    let node = this._graph.getNodeByContentKey(dep.id);
     invariant(node && node.type === 'dependency');
     return makeReadOnlySet(node.usedSymbolsUp);
   }
 
   merge(other: BundleGraph) {
-    for (let [, node] of other._graph.nodes) {
-      let existingNode = this._graph.getNode(node.id);
-      if (existingNode != null) {
+    let otherGraphIdToThisNodeId = new Map<NodeId, NodeId>();
+    for (let [otherNodeId, otherNode] of other._graph.nodes) {
+      if (this._graph.hasContentKey(otherNode.id)) {
+        let existingNodeId = this._graph.getNodeIdByContentKey(otherNode.id);
+        otherGraphIdToThisNodeId.set(otherNodeId, existingNodeId);
+
+        let existingNode = nullthrows(this._graph.getNode(existingNodeId));
         // Merge symbols, recompute dep.exluded based on that
         if (existingNode.type === 'asset') {
-          invariant(node.type === 'asset');
+          invariant(otherNode.type === 'asset');
           existingNode.usedSymbols = new Set([
             ...existingNode.usedSymbols,
-            ...node.usedSymbols,
+            ...otherNode.usedSymbols,
           ]);
         } else if (existingNode.type === 'dependency') {
-          invariant(node.type === 'dependency');
+          invariant(otherNode.type === 'dependency');
           existingNode.usedSymbolsDown = new Set([
             ...existingNode.usedSymbolsDown,
-            ...node.usedSymbolsDown,
+            ...otherNode.usedSymbolsDown,
           ]);
           existingNode.usedSymbolsUp = new Set([
             ...existingNode.usedSymbolsUp,
-            ...node.usedSymbolsUp,
+            ...otherNode.usedSymbolsUp,
           ]);
 
           existingNode.excluded =
             (existingNode.excluded || Boolean(existingNode.hasDeferred)) &&
-            (node.excluded || Boolean(node.hasDeferred));
+            (otherNode.excluded || Boolean(otherNode.hasDeferred));
         }
       } else {
-        this._graph.addNode(node);
+        let updateNodeId = this._graph.addNodeByContentKey(
+          otherNode.id,
+          otherNode,
+        );
+        otherGraphIdToThisNodeId.set(otherNodeId, updateNodeId);
       }
     }
 
     for (let edge of other._graph.getAllEdges()) {
-      this._graph.addEdge(edge.from, edge.to, edge.type);
+      this._graph.addEdge(
+        nullthrows(otherGraphIdToThisNodeId.get(edge.from)),
+        nullthrows(otherGraphIdToThisNodeId.get(edge.to)),
+        edge.type,
+      );
     }
   }
 
   isEntryBundleGroup(bundleGroup: BundleGroup): boolean {
     return this._graph
-      .getNodesConnectedTo(
-        nullthrows(this._graph.getNode(getBundleGroupId(bundleGroup))),
+      .getNodeIdsConnectedTo(
+        nullthrows(
+          this._graph.getNodeIdByContentKey(getBundleGroupId(bundleGroup)),
+        ),
         'bundle',
       )
+      .map(id => nullthrows(this._graph.getNode(id)))
       .some(n => n.type === 'root');
   }
 }
diff --git a/packages/core/core/src/ContentGraph.js b/packages/core/core/src/ContentGraph.js
new file mode 100644
index 000000000..57e9cc87b
--- /dev/null
+++ b/packages/core/core/src/ContentGraph.js
@@ -0,0 +1,84 @@
+// @flow strict-local
+
+import Graph, {type GraphOpts} from './Graph';
+import type {ContentKey, Node, NodeId} from './types';
+import nullthrows from 'nullthrows';
+
+export type SerializedContentGraph<
+  TNode: Node,
+  TEdgeType: string | null = null,
+> = {|
+  ...GraphOpts<TNode, TEdgeType>,
+  _contentKeyToNodeId: Map<ContentKey, NodeId>,
+|};
+
+export default class ContentGraph<
+  TNode: Node,
+  TEdgeType: string | null = null,
+> extends Graph<TNode, TEdgeType> {
+  _contentKeyToNodeId: Map<ContentKey, NodeId>;
+
+  constructor(opts: ?SerializedContentGraph<TNode, TEdgeType>) {
+    if (opts) {
+      let {_contentKeyToNodeId, ...rest} = opts;
+      super(rest);
+      this._contentKeyToNodeId = _contentKeyToNodeId;
+    } else {
+      super();
+      this._contentKeyToNodeId = new Map();
+    }
+  }
+
+  // $FlowFixMe[prop-missing]
+  static deserialize(
+    opts: SerializedContentGraph<TNode, TEdgeType>,
+  ): ContentGraph<TNode, TEdgeType> {
+    return new ContentGraph(opts);
+  }
+
+  // $FlowFixMe[prop-missing]
+  serialize(): SerializedContentGraph<TNode, TEdgeType> {
+    return {
+      ...super.serialize(),
+      _contentKeyToNodeId: this._contentKeyToNodeId,
+    };
+  }
+
+  addNodeByContentKey(contentKey: ContentKey, node: TNode): NodeId {
+    if (!this.hasContentKey(contentKey)) {
+      let nodeId = super.addNode(node);
+      this._contentKeyToNodeId.set(contentKey, nodeId);
+      return nodeId;
+    } else {
+      let existingNodeId = this.getNodeIdByContentKey(contentKey);
+      let existingNode = nullthrows(this.getNodeByContentKey(contentKey));
+      existingNode.value = node.value;
+      this.updateNode(existingNodeId, existingNode);
+      return existingNodeId;
+    }
+  }
+
+  getNodeByContentKey(contentKey: ContentKey): ?TNode {
+    let nodeId = this._contentKeyToNodeId.get(contentKey);
+    if (nodeId != null) {
+      return super.getNode(nodeId);
+    }
+  }
+
+  getNodeIdByContentKey(contentKey: ContentKey): NodeId {
+    return nullthrows(
+      this._contentKeyToNodeId.get(contentKey),
+      'Expected content key to exist',
+    );
+  }
+
+  hasContentKey(contentKey: ContentKey): boolean {
+    return this._contentKeyToNodeId.has(contentKey);
+  }
+
+  removeNode(nodeId: NodeId) {
+    this._assertHasNodeId(nodeId);
+    this._contentKeyToNodeId.delete(nullthrows(this.getNode(nodeId)).id);
+    super.removeNode(nodeId);
+  }
+}
diff --git a/packages/core/core/src/Graph.js b/packages/core/core/src/Graph.js
index 754d6fed1..3a55ba40a 100644
--- a/packages/core/core/src/Graph.js
+++ b/packages/core/core/src/Graph.js
@@ -1,5 +1,6 @@
-// @flow
+// @flow strict-local
 
+import {toNodeId, fromNodeId} from './types';
 import type {Edge, Node, NodeId} from './types';
 import type {TraversalActions, GraphVisitor} from '@parcel/types';
 
@@ -10,6 +11,7 @@ export type GraphOpts<TNode, TEdgeType: string | null = null> = {|
   nodes?: Map<NodeId, TNode>,
   edges?: AdjacencyListMap<TEdgeType | null>,
   rootNodeId?: ?NodeId,
+  nextNodeId?: ?number,
 |};
 
 export const ALL_EDGE_TYPES = '@@all_edge_types';
@@ -19,11 +21,14 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
   inboundEdges: AdjacencyList<TEdgeType | null>;
   outboundEdges: AdjacencyList<TEdgeType | null>;
   rootNodeId: ?NodeId;
+  nextNodeId: number = 0;
 
-  constructor(opts: GraphOpts<TNode, TEdgeType> = ({}: any)) {
-    this.nodes = opts.nodes || new Map();
-    this.rootNodeId = opts.rootNodeId;
-    let edges = opts.edges;
+  constructor(opts: ?GraphOpts<TNode, TEdgeType>) {
+    this.nodes = opts?.nodes || new Map();
+    this.setRootNodeId(opts?.rootNodeId);
+    this.nextNodeId = opts?.nextNodeId ?? 0;
+
+    let edges = opts?.edges;
     if (edges != null) {
       this.inboundEdges = new AdjacencyList();
       this.outboundEdges = new AdjacencyList(edges);
@@ -40,6 +45,10 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     }
   }
 
+  setRootNodeId(id: ?NodeId) {
+    this.rootNodeId = id;
+  }
+
   static deserialize(
     opts: GraphOpts<TNode, TEdgeType>,
   ): Graph<TNode, TEdgeType> {
@@ -47,6 +56,7 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       nodes: opts.nodes,
       edges: opts.edges,
       rootNodeId: opts.rootNodeId,
+      nextNodeId: opts.nextNodeId,
     });
   }
 
@@ -55,6 +65,7 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       nodes: this.nodes,
       edges: this.outboundEdges.getListMap(),
       rootNodeId: this.rootNodeId,
+      nextNodeId: this.nextNodeId,
     };
   }
 
@@ -72,39 +83,27 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     return edges;
   }
 
-  addNode(node: TNode): TNode {
-    let existingNode = this.nodes.get(node.id);
-    if (existingNode) {
-      existingNode.value = node.value;
-    }
-    this.nodes.set(node.id, existingNode ?? node);
-    return node;
+  addNode(node: TNode): NodeId {
+    let id = toNodeId(this.nextNodeId++);
+    this.nodes.set(id, node);
+    return id;
   }
 
-  hasNode(id: string): boolean {
+  hasNode(id: NodeId): boolean {
     return this.nodes.has(id);
   }
 
-  getNode(id: string): ?TNode {
+  getNode(id: NodeId): ?TNode {
     return this.nodes.get(id);
   }
 
-  setRootNode(node: TNode): void {
-    this.addNode(node);
-    this.rootNodeId = node.id;
-  }
-
-  getRootNode(): ?TNode {
-    return this.rootNodeId ? this.getNode(this.rootNodeId) : null;
-  }
-
   addEdge(from: NodeId, to: NodeId, type: TEdgeType | null = null): void {
     if (!this.getNode(from)) {
-      throw new Error(`"from" node '${from}' not found`);
+      throw new Error(`"from" node '${fromNodeId(from)}' not found`);
     }
 
     if (!this.getNode(to)) {
-      throw new Error(`"to" node '${to}' not found`);
+      throw new Error(`"to" node '${fromNodeId(to)}' not found`);
     }
 
     this.outboundEdges.addEdge(from, to, type);
@@ -115,13 +114,13 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     return this.outboundEdges.hasEdge(from, to, type);
   }
 
-  getNodesConnectedTo(
-    node: TNode,
+  getNodeIdsConnectedTo(
+    nodeId: NodeId,
     type: TEdgeType | null | Array<TEdgeType | null> = null,
-  ): Array<TNode> {
-    assertHasNode(this, node);
+  ): Array<NodeId> {
+    this._assertHasNodeId(nodeId);
 
-    let inboundByType = this.inboundEdges.getEdgesByType(node.id);
+    let inboundByType = this.inboundEdges.getEdgesByType(nodeId);
     if (inboundByType == null) {
       return [];
     }
@@ -145,16 +144,15 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       nodes = new Set(inboundByType.get(type)?.values() ?? []);
     }
 
-    return [...nodes].map(to => nullthrows(this.nodes.get(to)));
+    return [...nodes];
   }
 
-  getNodesConnectedFrom(
-    node: TNode,
+  getNodeIdsConnectedFrom(
+    nodeId: NodeId,
     type: TEdgeType | null | Array<TEdgeType | null> = null,
-  ): Array<TNode> {
-    assertHasNode(this, node);
-
-    let outboundByType = this.outboundEdges.getEdgesByType(node.id);
+  ): Array<NodeId> {
+    this._assertHasNodeId(nodeId);
+    let outboundByType = this.outboundEdges.getEdgesByType(nodeId);
     if (outboundByType == null) {
       return [];
     }
@@ -178,20 +176,18 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       nodes = new Set(outboundByType.get(type)?.values() ?? []);
     }
 
-    return [...nodes].map(to => nullthrows(this.nodes.get(to)));
+    return [...nodes];
   }
 
   // Removes node and any edges coming from or to that node
-  removeNode(node: TNode) {
-    assertHasNode(this, node);
+  removeNode(nodeId: NodeId) {
+    this._assertHasNodeId(nodeId);
 
-    for (let [type, nodesForType] of this.inboundEdges.getEdgesByType(
-      node.id,
-    )) {
+    for (let [type, nodesForType] of this.inboundEdges.getEdgesByType(nodeId)) {
       for (let from of nodesForType) {
         this.removeEdge(
           from,
-          node.id,
+          nodeId,
           type,
           // Do not allow orphans to be removed as this node could be one
           // and is already being removed.
@@ -200,26 +196,21 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       }
     }
 
-    for (let [type, toNodes] of this.outboundEdges.getEdgesByType(node.id)) {
+    for (let [type, toNodes] of this.outboundEdges.getEdgesByType(nodeId)) {
       for (let to of toNodes) {
-        this.removeEdge(node.id, to, type);
+        this.removeEdge(nodeId, to, type);
       }
     }
 
-    let wasRemoved = this.nodes.delete(node.id);
+    let wasRemoved = this.nodes.delete(nodeId);
     assert(wasRemoved);
   }
 
-  removeById(id: NodeId) {
-    let node = nullthrows(this.getNode(id));
-    this.removeNode(node);
-  }
-
-  removeEdges(node: TNode, type: TEdgeType | null = null) {
-    assertHasNode(this, node);
+  removeEdges(nodeId: NodeId, type: TEdgeType | null = null) {
+    this._assertHasNodeId(nodeId);
 
-    for (let to of this.outboundEdges.getEdges(node.id, type)) {
-      this.removeEdge(node.id, to, type);
+    for (let to of this.outboundEdges.getEdges(nodeId, type)) {
+      this.removeEdge(nodeId, to, type);
     }
   }
 
@@ -231,33 +222,35 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     removeOrphans: boolean = true,
   ) {
     if (!this.outboundEdges.hasEdge(from, to, type)) {
-      throw new Error(`Outbound edge from ${from} to ${to} not found!`);
+      throw new Error(
+        `Outbound edge from ${fromNodeId(from)} to ${fromNodeId(
+          to,
+        )} not found!`,
+      );
     }
 
     if (!this.inboundEdges.hasEdge(to, from, type)) {
-      throw new Error(`Inbound edge from ${to} to ${from} not found!`);
+      throw new Error(
+        `Inbound edge from ${fromNodeId(to)} to ${fromNodeId(from)} not found!`,
+      );
     }
 
     this.outboundEdges.removeEdge(from, to, type);
     this.inboundEdges.removeEdge(to, from, type);
 
-    let connectedNode = nullthrows(this.nodes.get(to));
-    if (removeOrphans && this.isOrphanedNode(connectedNode)) {
-      this.removeNode(connectedNode);
+    if (removeOrphans && this.isOrphanedNode(to)) {
+      this.removeNode(to);
     }
   }
 
-  isOrphanedNode(node: TNode): boolean {
-    assertHasNode(this, node);
+  isOrphanedNode(nodeId: NodeId): boolean {
+    this._assertHasNodeId(nodeId);
 
-    let rootNode = this.getRootNode();
-    if (rootNode == null) {
+    if (this.rootNodeId == null) {
       // If the graph does not have a root, and there are inbound edges,
       // this node should not be considered orphaned.
       // return false;
-      for (let [, inboundNodeIds] of this.inboundEdges.getEdgesByType(
-        node.id,
-      )) {
+      for (let [, inboundNodeIds] of this.inboundEdges.getEdgesByType(nodeId)) {
         if (inboundNodeIds.size > 0) {
           return false;
         }
@@ -269,10 +262,11 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     // Otherwise, attempt to traverse backwards to the root. If there is a path,
     // then this is not an orphaned node.
     let hasPathToRoot = false;
+    // go back to traverseAncestors
     this.traverseAncestors(
-      node,
-      (ancestor, _, actions) => {
-        if (ancestor.id === rootNode.id) {
+      nodeId,
+      (ancestorId, _, actions) => {
+        if (ancestorId === this.rootNodeId) {
           hasPathToRoot = true;
           actions.stop();
         }
@@ -288,103 +282,101 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     return true;
   }
 
+  updateNode(nodeId: NodeId, node: TNode): void {
+    this._assertHasNodeId(nodeId);
+    this.nodes.set(nodeId, node);
+  }
+
   replaceNode(
-    fromNode: TNode,
-    toNode: TNode,
+    fromNodeId: NodeId,
+    toNodeId: NodeId,
     type: TEdgeType | null = null,
   ): void {
-    assertHasNode(this, fromNode);
-
-    this.addNode(toNode);
-
-    for (let parent of this.inboundEdges.getEdges(fromNode.id, type)) {
-      this.addEdge(parent, toNode.id, type);
-      this.removeEdge(parent, fromNode.id, type);
+    this._assertHasNodeId(fromNodeId);
+    for (let parent of this.inboundEdges.getEdges(fromNodeId, type)) {
+      this.addEdge(parent, toNodeId, type);
+      this.removeEdge(parent, fromNodeId, type);
     }
-
-    this.removeNode(fromNode);
+    this.removeNode(fromNodeId);
   }
 
   // Update a node's downstream nodes making sure to prune any orphaned branches
-  replaceNodesConnectedTo(
-    fromNode: TNode,
-    toNodes: $ReadOnlyArray<TNode>,
-    replaceFilter?: null | (TNode => boolean),
+  replaceNodeIdsConnectedTo(
+    fromNodeId: NodeId,
+    toNodeIds: $ReadOnlyArray<NodeId>,
+    replaceFilter?: null | (NodeId => boolean),
     type?: TEdgeType | null = null,
   ): void {
-    assertHasNode(this, fromNode);
+    this._assertHasNodeId(fromNodeId);
 
-    let outboundEdges = this.outboundEdges.getEdges(fromNode.id, type);
+    let outboundEdges = this.outboundEdges.getEdges(fromNodeId, type);
     let childrenToRemove = new Set(
       replaceFilter
-        ? [...outboundEdges].filter(toNodeId =>
-            replaceFilter(nullthrows(this.nodes.get(toNodeId))),
-          )
+        ? [...outboundEdges].filter(toNodeId => replaceFilter(toNodeId))
         : outboundEdges,
     );
-    for (let toNode of toNodes) {
-      this.addNode(toNode);
-      childrenToRemove.delete(toNode.id);
+    for (let toNodeId of toNodeIds) {
+      childrenToRemove.delete(toNodeId);
 
-      if (!this.hasEdge(fromNode.id, toNode.id, type)) {
-        this.addEdge(fromNode.id, toNode.id, type);
+      if (!this.hasEdge(fromNodeId, toNodeId, type)) {
+        this.addEdge(fromNodeId, toNodeId, type);
       }
     }
 
     for (let child of childrenToRemove) {
-      this.removeEdge(fromNode.id, child, type);
+      this.removeEdge(fromNodeId, child, type);
     }
   }
 
   traverse<TContext>(
-    visit: GraphVisitor<TNode, TContext>,
-    startNode: ?TNode,
+    visit: GraphVisitor<NodeId, TContext>,
+    startNodeId: ?NodeId,
     type: TEdgeType | null | Array<TEdgeType | null> = null,
   ): ?TContext {
     return this.dfs({
       visit,
-      startNode,
-      getChildren: node => this.getNodesConnectedFrom(node, type),
+      startNodeId,
+      getChildren: nodeId => this.getNodeIdsConnectedFrom(nodeId, type),
     });
   }
 
   filteredTraverse<TValue, TContext>(
-    filter: (TNode, TraversalActions) => ?TValue,
+    filter: (NodeId, TraversalActions) => ?TValue,
     visit: GraphVisitor<TValue, TContext>,
-    startNode: ?TNode,
+    startNodeId: ?NodeId,
     type?: TEdgeType | null | Array<TEdgeType | null>,
   ): ?TContext {
-    return this.traverse(mapVisitor(filter, visit), startNode, type);
+    return this.traverse(mapVisitor(filter, visit), startNodeId, type);
   }
 
   traverseAncestors<TContext>(
-    startNode: TNode,
-    visit: GraphVisitor<TNode, TContext>,
+    startNodeId: ?NodeId,
+    visit: GraphVisitor<NodeId, TContext>,
     type: TEdgeType | null | Array<TEdgeType | null> = null,
   ): ?TContext {
     return this.dfs({
       visit,
-      startNode,
-      getChildren: node => this.getNodesConnectedTo(node, type),
+      startNodeId,
+      getChildren: nodeId => this.getNodeIdsConnectedTo(nodeId, type),
     });
   }
 
   dfs<TContext>({
     visit,
-    startNode,
+    startNodeId,
     getChildren,
   }: {|
-    visit: GraphVisitor<TNode, TContext>,
-    getChildren(node: TNode): Array<TNode>,
-    startNode?: ?TNode,
+    visit: GraphVisitor<NodeId, TContext>,
+    getChildren(nodeId: NodeId): Array<NodeId>,
+    startNodeId?: ?NodeId,
   |}): ?TContext {
-    let root = startNode ?? this.getRootNode();
-    if (root == null) {
-      throw new Error('A start node is required to traverse');
-    }
-    assertHasNode(this, root);
+    let traversalStartNode = nullthrows(
+      startNodeId ?? this.rootNodeId,
+      'A start node is required to traverse',
+    );
+    this._assertHasNodeId(traversalStartNode);
 
-    let visited = new Set<TNode>();
+    let visited = new Set<NodeId>();
     let stopped = false;
     let skipped = false;
     let actions: TraversalActions = {
@@ -396,15 +388,16 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       },
     };
 
-    let walk = (node, context) => {
-      if (!this.hasNode(node.id)) return;
-      visited.add(node);
+    let walk = (nodeId, context: ?TContext) => {
+      if (!this.hasNode(nodeId)) return;
+      visited.add(nodeId);
 
       skipped = false;
       let enter = typeof visit === 'function' ? visit : visit.enter;
       if (enter) {
-        let newContext = enter(node, context, actions);
+        let newContext = enter(nodeId, context, actions);
         if (typeof newContext !== 'undefined') {
+          // $FlowFixMe[reassign-const]
           context = newContext;
         }
       }
@@ -417,7 +410,7 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
         return context;
       }
 
-      for (let child of getChildren(node)) {
+      for (let child of getChildren(nodeId)) {
         if (visited.has(child)) {
           continue;
         }
@@ -430,8 +423,9 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       }
 
       if (typeof visit !== 'function' && visit.exit) {
-        let newContext = visit.exit(node, context, actions);
+        let newContext = visit.exit(nodeId, context, actions);
         if (typeof newContext !== 'undefined') {
+          // $FlowFixMe[reassign-const]
           context = newContext;
         }
       }
@@ -445,26 +439,26 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
       }
     };
 
-    return walk(root);
+    return walk(traversalStartNode);
   }
 
-  bfs(visit: (node: TNode) => ?boolean): ?TNode {
-    let root = this.getRootNode();
-    if (!root) {
-      throw new Error('A root node is required to traverse');
-    }
+  bfs(visit: (nodeId: NodeId) => ?boolean): ?NodeId {
+    let rootNodeId = nullthrows(
+      this.rootNodeId,
+      'A root node is required to traverse',
+    );
 
-    let queue: Array<TNode> = [root];
-    let visited = new Set<TNode>([root]);
+    let queue: Array<NodeId> = [rootNodeId];
+    let visited = new Set<NodeId>([rootNodeId]);
 
     while (queue.length > 0) {
       let node = queue.shift();
-      let stop = visit(node);
+      let stop = visit(rootNodeId);
       if (stop === true) {
         return node;
       }
 
-      for (let child of this.getNodesConnectedFrom(node)) {
+      for (let child of this.getNodeIdsConnectedFrom(node)) {
         if (!visited.has(child)) {
           visited.add(child);
           queue.push(child);
@@ -475,97 +469,80 @@ export default class Graph<TNode: Node, TEdgeType: string | null = null> {
     return null;
   }
 
-  getSubGraph(node: TNode): this {
-    let graph = new this.constructor();
-    graph.setRootNode(node);
-
-    let nodes = [];
-    this.traverse(node => {
-      nodes.push(node);
-      graph.addNode(node);
-    }, node);
-
-    for (let node of nodes) {
-      for (let [type, toNodes] of this.outboundEdges.getEdgesByType(node.id)) {
-        for (let to of toNodes) {
-          graph.addEdge(node.id, to, type);
-        }
-      }
-    }
-
-    return graph;
-  }
-
-  findAncestor(node: TNode, fn: (node: TNode) => boolean): ?TNode {
+  findAncestor(nodeId: NodeId, fn: (nodeId: NodeId) => boolean): ?NodeId {
     let res = null;
-    this.traverseAncestors(node, (node, ctx, traversal) => {
-      if (fn(node)) {
-        res = node;
+    this.traverseAncestors(nodeId, (nodeId, ctx, traversal) => {
+      if (fn(nodeId)) {
+        res = nodeId;
         traversal.stop();
       }
     });
     return res;
   }
 
-  findAncestors(node: TNode, fn: (node: TNode) => boolean): Array<TNode> {
+  findAncestors(
+    nodeId: NodeId,
+    fn: (nodeId: NodeId) => boolean,
+  ): Array<NodeId> {
     let res = [];
-    this.traverseAncestors(node, (node, ctx, traversal) => {
-      if (fn(node)) {
-        res.push(node);
+    this.traverseAncestors(nodeId, (nodeId, ctx, traversal) => {
+      if (fn(nodeId)) {
+        res.push(nodeId);
         traversal.skipChildren();
       }
     });
     return res;
   }
 
-  findDescendant(node: TNode, fn: (node: TNode) => boolean): ?TNode {
+  findDescendant(nodeId: NodeId, fn: (nodeId: NodeId) => boolean): ?NodeId {
     let res = null;
-    this.traverse((node, ctx, traversal) => {
-      if (fn(node)) {
-        res = node;
+    this.traverse((nodeId, ctx, traversal) => {
+      if (fn(nodeId)) {
+        res = nodeId;
         traversal.stop();
       }
-    }, node);
+    }, nodeId);
     return res;
   }
 
-  findDescendants(node: TNode, fn: (node: TNode) => boolean): Array<TNode> {
+  findDescendants(
+    nodeId: NodeId,
+    fn: (nodeId: NodeId) => boolean,
+  ): Array<NodeId> {
     let res = [];
-    this.traverse((node, ctx, traversal) => {
-      if (fn(node)) {
-        res.push(node);
+    this.traverse((nodeId, ctx, traversal) => {
+      if (fn(nodeId)) {
+        res.push(nodeId);
         traversal.skipChildren();
       }
-    }, node);
+    }, nodeId);
     return res;
   }
 
-  findNode(predicate: TNode => boolean): ?TNode {
-    return Array.from(this.nodes.values()).find(predicate);
-  }
-
-  findNodes(predicate: TNode => boolean): Array<TNode> {
-    return Array.from(this.nodes.values()).filter(predicate);
+  _assertHasNodeId(nodeId: NodeId) {
+    if (!this.hasNode(nodeId)) {
+      throw new Error('Does not have node ' + fromNodeId(nodeId));
+    }
   }
 }
 
-export function mapVisitor<TNode, TValue, TContext>(
-  filter: (TNode, TraversalActions) => ?TValue,
+export function mapVisitor<NodeId, TValue, TContext>(
+  filter: (NodeId, TraversalActions) => ?TValue,
   visit: GraphVisitor<TValue, TContext>,
-): GraphVisitor<TNode, TContext> {
+): GraphVisitor<NodeId, TContext> {
   return {
-    enter: (node, context, actions) => {
+    enter: (nodeId, context, actions) => {
       let enter = typeof visit === 'function' ? visit : visit.enter;
       if (!enter) {
         return;
       }
 
-      let value = filter(node, actions);
+      let value = filter(nodeId, actions);
       if (value != null) {
         return enter(value, context, actions);
       }
     },
-    exit: (node, context, actions) => {
+    exit: (nodeId, context, actions) => {
       if (typeof visit === 'function') {
         return;
       }
@@ -575,7 +552,7 @@ export function mapVisitor<TNode, TValue, TContext>(
         return;
       }
 
-      let value = filter(node, actions);
+      let value = filter(nodeId, actions);
       if (value != null) {
         return exit(value, context, actions);
       }
@@ -583,12 +560,6 @@ export function mapVisitor<TNode, TValue, TContext>(
   };
 }
 
-function assertHasNode<TNode: Node>(graph: Graph<TNode, *>, node: TNode) {
-  if (!graph.hasNode(node.id)) {
-    throw new Error('Does not have node ' + node.id);
-  }
-}
-
 type AdjacencyListMap<TEdgeType> = Map<NodeId, Map<TEdgeType, Set<NodeId>>>;
 class AdjacencyList<TEdgeType> {
   _listMap: AdjacencyListMap<TEdgeType>;
diff --git a/packages/core/core/src/Parcel.js b/packages/core/core/src/Parcel.js
index 793025e7c..ef4f959a7 100644
--- a/packages/core/core/src/Parcel.js
+++ b/packages/core/core/src/Parcel.js
@@ -319,7 +319,7 @@ export default class Parcel {
         ),
         buildTime: Date.now() - startTime,
         requestBundle: async bundle => {
-          let bundleNode = bundleGraph._graph.getNode(bundle.id);
+          let bundleNode = bundleGraph._graph.getNodeByContentKey(bundle.id);
           invariant(bundleNode?.type === 'bundle', 'Bundle does not exist');
 
           if (!bundleNode.value.isPlaceholder) {
diff --git a/packages/core/core/src/RequestTracker.js b/packages/core/core/src/RequestTracker.js
index 7c124aa0d..73368d1bb 100644
--- a/packages/core/core/src/RequestTracker.js
+++ b/packages/core/core/src/RequestTracker.js
@@ -11,7 +11,12 @@ import type {
 } from '@parcel/types';
 import type {Event, Options as WatcherOptions} from '@parcel/watcher';
 import type WorkerFarm from '@parcel/workers';
-import type {NodeId, ParcelOptions, RequestInvalidation} from './types';
+import type {
+  ContentKey,
+  NodeId,
+  ParcelOptions,
+  RequestInvalidation,
+} from './types';
 
 import invariant from 'assert';
 import nullthrows from 'nullthrows';
@@ -22,7 +27,7 @@ import {
   md5FromObject,
   md5FromString,
 } from '@parcel/utils';
-import Graph, {type GraphOpts} from './Graph';
+import ContentGraph, {type SerializedContentGraph} from './ContentGraph';
 import {assertSignalNotAborted, hashFromOption} from './utils';
 import {
   PARCEL_VERSION,
@@ -38,7 +43,7 @@ import {
 } from './constants';
 
 type SerializedRequestGraph = {|
-  ...GraphOpts<RequestGraphNode, RequestGraphEdgeType>,
+  ...SerializedContentGraph<RequestGraphNode, RequestGraphEdgeType>,
   invalidNodeIds: Set<NodeId>,
   incompleteNodeIds: Set<NodeId>,
   globNodeIds: Set<NodeId>,
@@ -47,21 +52,21 @@ type SerializedRequestGraph = {|
   unpredicatableNodeIds: Set<NodeId>,
 |};
 
-type FileNode = {|id: string, +type: 'file', value: File|};
-type GlobNode = {|id: string, +type: 'glob', value: Glob|};
+type FileNode = {|id: ContentKey, +type: 'file', value: File|};
+type GlobNode = {|id: ContentKey, +type: 'glob', value: Glob|};
 type FileNameNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'file_name',
   value: string,
 |};
 type EnvNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'env',
   value: {|key: string, value: string | void|},
 |};
 
 type OptionNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'option',
   value: {|key: string, hash: string|},
 |};
@@ -82,7 +87,7 @@ type StoredRequest = {|
 
 type InvalidateReason = number;
 type RequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'request',
   value: StoredRequest,
   invalidateReason: InvalidateReason,
@@ -112,10 +117,10 @@ export type RunAPI = {|
   invalidateOnOptionChange: string => void,
   getInvalidations(): Array<RequestInvalidation>,
   storeResult: (result: mixed, cacheKey?: string) => void,
+  getRequestResult<T>(contentKey: ContentKey): Async<?T>,
   getPreviousResult<T>(ifMatch?: string): Async<?T>,
-  getRequestResult<T>(id: string): Async<?T>,
   getSubRequests(): Array<StoredRequest>,
-  canSkipSubrequest(string): boolean,
+  canSkipSubrequest(ContentKey): boolean,
   runRequest: <TInput, TResult>(
     subRequest: Request<TInput, TResult>,
     opts?: RunRequestOpts,
@@ -176,7 +181,7 @@ const nodeFromOption = (option: string, value: mixed) => ({
   },
 });
 
-export class RequestGraph extends Graph<
+export class RequestGraph extends ContentGraph<
   RequestGraphNode,
   RequestGraphEdgeType,
 > {
@@ -189,9 +194,9 @@ export class RequestGraph extends Graph<
   // filesystem changes alone. They should rerun on each startup of Parcel.
   unpredicatableNodeIds: Set<NodeId> = new Set();
 
-  // $FlowFixMe
+  // $FlowFixMe[prop-missing]
   static deserialize(opts: SerializedRequestGraph): RequestGraph {
-    // $FlowFixMe Added in Flow 0.121.0 upgrade in #4381
+    // $FlowFixMe[prop-missing]
     let deserialized = new RequestGraph(opts);
     deserialized.invalidNodeIds = opts.invalidNodeIds;
     deserialized.incompleteNodeIds = opts.incompleteNodeIds;
@@ -199,11 +204,10 @@ export class RequestGraph extends Graph<
     deserialized.envNodeIds = opts.envNodeIds;
     deserialized.optionNodeIds = opts.optionNodeIds;
     deserialized.unpredicatableNodeIds = opts.unpredicatableNodeIds;
-    // $FlowFixMe Added in Flow 0.121.0 upgrade in #4381 (Windows only)
     return deserialized;
   }
 
-  // $FlowFixMe
+  // $FlowFixMe[prop-missing]
   serialize(): SerializedRequestGraph {
     return {
       ...super.serialize(),
@@ -216,77 +220,84 @@ export class RequestGraph extends Graph<
     };
   }
 
-  addNode(node: RequestGraphNode): RequestGraphNode {
-    if (!this.hasNode(node.id)) {
+  // addNode for RequestGraph should not override the value if added multiple times
+  addNode(node: RequestGraphNode): NodeId {
+    let didNodeExist = this.hasContentKey(node.id);
+
+    if (!didNodeExist) {
+      let nodeId = super.addNodeByContentKey(node.id, node);
       if (node.type === 'glob') {
-        this.globNodeIds.add(node.id);
+        this.globNodeIds.add(nodeId);
       }
 
       if (node.type === 'env') {
-        this.envNodeIds.add(node.id);
+        this.envNodeIds.add(nodeId);
       }
 
       if (node.type === 'option') {
-        this.optionNodeIds.add(node.id);
+        this.optionNodeIds.add(nodeId);
       }
     }
 
-    return super.addNode(node);
+    return this.getNodeIdByContentKey(node.id);
   }
 
-  removeNode(node: RequestGraphNode): void {
-    this.invalidNodeIds.delete(node.id);
-    this.incompleteNodeIds.delete(node.id);
+  removeNode(nodeId: NodeId): void {
+    this.invalidNodeIds.delete(nodeId);
+    this.incompleteNodeIds.delete(nodeId);
+    let node = nullthrows(this.getNode(nodeId));
     if (node.type === 'glob') {
-      this.globNodeIds.delete(node.id);
+      this.globNodeIds.delete(nodeId);
     }
     if (node.type === 'env') {
-      this.envNodeIds.delete(node.id);
+      this.envNodeIds.delete(nodeId);
     }
     if (node.type === 'option') {
-      this.optionNodeIds.delete(node.id);
+      this.optionNodeIds.delete(nodeId);
     }
-    return super.removeNode(node);
+    return super.removeNode(nodeId);
   }
 
-  getRequestNode(id: string): RequestNode {
-    let node = nullthrows(this.getNode(id));
+  getRequestNode(nodeId: NodeId): RequestNode {
+    let node = nullthrows(this.getNode(nodeId));
     invariant(node.type === 'request');
     return node;
   }
 
   completeRequest(request: StoredRequest) {
-    this.invalidNodeIds.delete(request.id);
-    this.incompleteNodeIds.delete(request.id);
+    let nodeId = this.getNodeIdByContentKey(request.id);
+    this.invalidNodeIds.delete(nodeId);
+    this.incompleteNodeIds.delete(nodeId);
   }
 
   replaceSubrequests(
-    requestId: string,
-    subrequestNodes: Array<RequestGraphNode>,
+    requestNodeId: NodeId,
+    subrequestContentKeys: Array<ContentKey>,
   ) {
-    let requestNode = this.getRequestNode(requestId);
-    if (!this.hasNode(requestId)) {
-      this.addNode(requestNode);
+    let subrequestNodeIds = [];
+    for (let key of subrequestContentKeys) {
+      if (this.hasContentKey(key)) {
+        subrequestNodeIds.push(this.getNodeIdByContentKey(key));
+      }
     }
 
-    this.replaceNodesConnectedTo(
-      requestNode,
-      subrequestNodes,
+    this.replaceNodeIdsConnectedTo(
+      requestNodeId,
+      subrequestNodeIds,
       null,
       'subrequest',
     );
   }
 
-  invalidateNode(node: RequestGraphNode, reason: InvalidateReason) {
+  invalidateNode(nodeId: NodeId, reason: InvalidateReason) {
+    let node = nullthrows(this.getNode(nodeId));
     invariant(node.type === 'request');
-    if (this.hasNode(node.id)) {
-      node.invalidateReason |= reason;
-      this.invalidNodeIds.add(node.id);
+    node.invalidateReason |= reason;
+    this.invalidNodeIds.add(nodeId);
 
-      let parentNodes = this.getNodesConnectedTo(node, 'subrequest');
-      for (let parentNode of parentNodes) {
-        this.invalidateNode(parentNode, reason);
-      }
+    let parentNodes = this.getNodeIdsConnectedTo(nodeId, 'subrequest');
+    for (let parentNode of parentNodes) {
+      this.invalidateNode(parentNode, reason);
     }
   }
 
@@ -294,7 +305,7 @@ export class RequestGraph extends Graph<
     for (let nodeId of this.unpredicatableNodeIds) {
       let node = nullthrows(this.getNode(nodeId));
       invariant(node.type !== 'file' && node.type !== 'glob');
-      this.invalidateNode(node, STARTUP);
+      this.invalidateNode(nodeId, STARTUP);
     }
   }
 
@@ -303,8 +314,8 @@ export class RequestGraph extends Graph<
       let node = nullthrows(this.getNode(nodeId));
       invariant(node.type === 'env');
       if (env[node.value.key] !== node.value.value) {
-        let parentNodes = this.getNodesConnectedTo(
-          node,
+        let parentNodes = this.getNodeIdsConnectedTo(
+          nodeId,
           'invalidated_by_update',
         );
         for (let parentNode of parentNodes) {
@@ -319,8 +330,8 @@ export class RequestGraph extends Graph<
       let node = nullthrows(this.getNode(nodeId));
       invariant(node.type === 'option');
       if (hashFromOption(options[node.value.key]) !== node.value.hash) {
-        let parentNodes = this.getNodesConnectedTo(
-          node,
+        let parentNodes = this.getNodeIdsConnectedTo(
+          nodeId,
           'invalidated_by_update',
         );
         for (let parentNode of parentNodes) {
@@ -330,32 +341,23 @@ export class RequestGraph extends Graph<
     }
   }
 
-  invalidateOnFileUpdate(requestId: string, filePath: FilePath) {
-    let requestNode = this.getRequestNode(requestId);
-    let fileNode = nodeFromFilePath(filePath);
-    if (!this.hasNode(fileNode.id)) {
-      this.addNode(fileNode);
-    }
+  invalidateOnFileUpdate(requestNodeId: NodeId, filePath: FilePath) {
+    let fileNodeId = this.addNode(nodeFromFilePath(filePath));
 
-    if (!this.hasEdge(requestNode.id, fileNode.id, 'invalidated_by_update')) {
-      this.addEdge(requestNode.id, fileNode.id, 'invalidated_by_update');
+    if (!this.hasEdge(requestNodeId, fileNodeId, 'invalidated_by_update')) {
+      this.addEdge(requestNodeId, fileNodeId, 'invalidated_by_update');
     }
   }
 
-  invalidateOnFileDelete(requestId: string, filePath: FilePath) {
-    let requestNode = this.getRequestNode(requestId);
-    let fileNode = nodeFromFilePath(filePath);
-    if (!this.hasNode(fileNode.id)) {
-      this.addNode(fileNode);
-    }
+  invalidateOnFileDelete(requestNodeId: NodeId, filePath: FilePath) {
+    let fileNodeId = this.addNode(nodeFromFilePath(filePath));
 
-    if (!this.hasEdge(requestNode.id, fileNode.id, 'invalidated_by_delete')) {
-      this.addEdge(requestNode.id, fileNode.id, 'invalidated_by_delete');
+    if (!this.hasEdge(requestNodeId, fileNodeId, 'invalidated_by_delete')) {
+      this.addEdge(requestNodeId, fileNodeId, 'invalidated_by_delete');
     }
   }
 
-  invalidateOnFileCreate(requestId: string, input: FileCreateInvalidation) {
-    let requestNode = this.getRequestNode(requestId);
+  invalidateOnFileCreate(requestNodeId: NodeId, input: FileCreateInvalidation) {
     let node;
     if (input.glob != null) {
       node = nodeFromGlob(input.glob);
@@ -368,21 +370,19 @@ export class RequestGraph extends Graph<
       // quickly matched by following the edges. This is also memory efficient
       // since common sub-paths (e.g. 'node_modules') are deduplicated.
       let parts = input.fileName.split('/').reverse();
-      let last;
+      let lastNodeId;
       for (let part of parts) {
         let fileNameNode = nodeFromFileName(part);
-        if (!this.hasNode(fileNameNode.id)) {
-          this.addNode(fileNameNode);
-        }
 
+        let fileNameNodeId = this.addNode(fileNameNode);
         if (
-          last != null &&
-          !this.hasEdge(last.id, fileNameNode.id, 'dirname')
+          lastNodeId != null &&
+          !this.hasEdge(lastNodeId, fileNameNodeId, 'dirname')
         ) {
-          this.addEdge(last.id, fileNameNode.id, 'dirname');
+          this.addEdge(lastNodeId, fileNameNodeId, 'dirname');
         }
 
-        last = fileNameNode;
+        lastNodeId = fileNameNodeId;
       }
 
       // The `aboveFilePath` condition asserts that requests are only invalidated
@@ -390,9 +390,7 @@ export class RequestGraph extends Graph<
       // is created in a parent directory). There is likely to already be a node
       // for this file in the graph (e.g. the source file) that we can reuse for this.
       node = nodeFromFilePath(aboveFilePath);
-      if (!this.hasNode(node.id)) {
-        this.addNode(node);
-      }
+      let nodeId = this.addNode(node);
 
       // Now create an edge from the `aboveFilePath` node to the first file_name node
       // in the chain created above, and an edge from the last node in the chain back to
@@ -402,13 +400,14 @@ export class RequestGraph extends Graph<
       // This indicates a complete match, and any requests attached to the `aboveFilePath`
       // node will be invalidated.
       let firstId = 'file_name:' + parts[0];
-      if (!this.hasEdge(node.id, firstId, 'invalidated_by_create_above')) {
-        this.addEdge(node.id, firstId, 'invalidated_by_create_above');
+      let firstNodeId = this.getNodeIdByContentKey(firstId);
+      if (!this.hasEdge(nodeId, firstNodeId, 'invalidated_by_create_above')) {
+        this.addEdge(nodeId, firstNodeId, 'invalidated_by_create_above');
       }
 
-      invariant(last != null);
-      if (!this.hasEdge(last.id, node.id, 'invalidated_by_create_above')) {
-        this.addEdge(last.id, node.id, 'invalidated_by_create_above');
+      invariant(lastNodeId != null);
+      if (!this.hasEdge(lastNodeId, nodeId, 'invalidated_by_create_above')) {
+        this.addEdge(lastNodeId, nodeId, 'invalidated_by_create_above');
       }
     } else if (input.filePath != null) {
       node = nodeFromFilePath(input.filePath);
@@ -416,64 +415,63 @@ export class RequestGraph extends Graph<
       throw new Error('Invalid invalidation');
     }
 
-    if (!this.hasNode(node.id)) {
-      this.addNode(node);
-    }
-
-    if (!this.hasEdge(requestNode.id, node.id, 'invalidated_by_create')) {
-      this.addEdge(requestNode.id, node.id, 'invalidated_by_create');
+    let nodeId = this.addNode(node);
+    if (!this.hasEdge(requestNodeId, nodeId, 'invalidated_by_create')) {
+      this.addEdge(requestNodeId, nodeId, 'invalidated_by_create');
     }
   }
 
-  invalidateOnStartup(requestId: string) {
-    let requestNode = this.getRequestNode(requestId);
-    this.unpredicatableNodeIds.add(requestNode.id);
+  invalidateOnStartup(requestNodeId: NodeId) {
+    this.getRequestNode(requestNodeId);
+    this.unpredicatableNodeIds.add(requestNodeId);
   }
 
-  invalidateOnEnvChange(requestId: string, env: string, value: string | void) {
-    let requestNode = this.getRequestNode(requestId);
+  invalidateOnEnvChange(
+    requestNodeId: NodeId,
+    env: string,
+    value: string | void,
+  ) {
     let envNode = nodeFromEnv(env, value);
-    if (!this.hasNode(envNode.id)) {
-      this.addNode(envNode);
-    }
+    let envNodeId = this.addNode(envNode);
 
-    if (!this.hasEdge(requestNode.id, envNode.id, 'invalidated_by_update')) {
-      this.addEdge(requestNode.id, envNode.id, 'invalidated_by_update');
+    if (!this.hasEdge(requestNodeId, envNodeId, 'invalidated_by_update')) {
+      this.addEdge(requestNodeId, envNodeId, 'invalidated_by_update');
     }
   }
 
-  invalidateOnOptionChange(requestId: string, option: string, value: mixed) {
-    let requestNode = this.getRequestNode(requestId);
+  invalidateOnOptionChange(
+    requestNodeId: NodeId,
+    option: string,
+    value: mixed,
+  ) {
     let optionNode = nodeFromOption(option, value);
-    if (!this.hasNode(optionNode.id)) {
-      this.addNode(optionNode);
-    }
+    let optionNodeId = this.addNode(optionNode);
 
-    if (!this.hasEdge(requestNode.id, optionNode.id, 'invalidated_by_update')) {
-      this.addEdge(requestNode.id, optionNode.id, 'invalidated_by_update');
+    if (!this.hasEdge(requestNodeId, optionNodeId, 'invalidated_by_update')) {
+      this.addEdge(requestNodeId, optionNodeId, 'invalidated_by_update');
     }
   }
 
-  clearInvalidations(node: RequestNode) {
-    this.unpredicatableNodeIds.delete(node.id);
-    this.replaceNodesConnectedTo(node, [], null, 'invalidated_by_update');
-    this.replaceNodesConnectedTo(node, [], null, 'invalidated_by_delete');
-    this.replaceNodesConnectedTo(node, [], null, 'invalidated_by_create');
+  clearInvalidations(nodeId: NodeId) {
+    this.unpredicatableNodeIds.delete(nodeId);
+    this.replaceNodeIdsConnectedTo(nodeId, [], null, 'invalidated_by_update');
+    this.replaceNodeIdsConnectedTo(nodeId, [], null, 'invalidated_by_delete');
+    this.replaceNodeIdsConnectedTo(nodeId, [], null, 'invalidated_by_create');
   }
 
-  getInvalidations(requestId: string): Array<RequestInvalidation> {
-    if (!this.hasNode(requestId)) {
+  getInvalidations(requestNodeId: NodeId): Array<RequestInvalidation> {
+    if (!this.hasNode(requestNodeId)) {
       return [];
     }
 
     // For now just handling updates. Could add creates/deletes later if needed.
-    let requestNode = this.getRequestNode(requestId);
-    let invalidations = this.getNodesConnectedFrom(
-      requestNode,
+    let invalidations = this.getNodeIdsConnectedFrom(
+      requestNodeId,
       'invalidated_by_update',
     );
     return invalidations
-      .map(node => {
+      .map(nodeId => {
+        let node = nullthrows(this.getNode(nodeId));
         switch (node.type) {
           case 'file':
             return {type: 'file', filePath: node.value.filePath};
@@ -486,15 +484,15 @@ export class RequestGraph extends Graph<
       .filter(Boolean);
   }
 
-  getSubRequests(requestId: string): Array<StoredRequest> {
-    if (!this.hasNode(requestId)) {
+  getSubRequests(requestNodeId: NodeId): Array<StoredRequest> {
+    if (!this.hasNode(requestNodeId)) {
       return [];
     }
 
-    let requestNode = this.getRequestNode(requestId);
-    let subRequests = this.getNodesConnectedFrom(requestNode, 'subrequest');
+    let subRequests = this.getNodeIdsConnectedFrom(requestNodeId, 'subrequest');
 
-    return subRequests.map(node => {
+    return subRequests.map(nodeId => {
+      let node = nullthrows(this.getNode(nodeId));
       invariant(node.type === 'request');
       return node.value;
     });
@@ -509,13 +507,16 @@ export class RequestGraph extends Graph<
     // by the original file_name node, and the matched node is inside the current directory, invalidate
     // all connected requests pointed to by the file node.
     let dirname = path.dirname(filePath);
+
+    let nodeId = this.getNodeIdByContentKey(node.id);
     for (let matchNode of matchNodes) {
+      let matchNodeId = this.getNodeIdByContentKey(matchNode.id);
       if (
-        this.hasEdge(node.id, matchNode.id, 'invalidated_by_create_above') &&
+        this.hasEdge(nodeId, matchNodeId, 'invalidated_by_create_above') &&
         isDirectoryInside(path.dirname(matchNode.value.filePath), dirname)
       ) {
-        let connectedNodes = this.getNodesConnectedTo(
-          matchNode,
+        let connectedNodes = this.getNodeIdsConnectedTo(
+          matchNodeId,
           'invalidated_by_create',
         );
         for (let connectedNode of connectedNodes) {
@@ -527,30 +528,40 @@ export class RequestGraph extends Graph<
     // Find the `file_name` node for the parent directory and
     // recursively invalidate connected requests as described above.
     let basename = path.basename(dirname);
-    let parent = this.getNode('file_name:' + basename);
-    if (parent != null && this.hasEdge(node.id, parent.id, 'dirname')) {
-      invariant(parent.type === 'file_name');
-      this.invalidateFileNameNode(parent, dirname, matchNodes);
+    let contentKey = 'file_name:' + basename;
+    if (this.hasContentKey(contentKey)) {
+      if (
+        this.hasEdge(nodeId, this.getNodeIdByContentKey(contentKey), 'dirname')
+      ) {
+        let parent = nullthrows(this.getNodeByContentKey(contentKey));
+        invariant(parent.type === 'file_name');
+        this.invalidateFileNameNode(parent, dirname, matchNodes);
+      }
     }
   }
 
   respondToFSEvents(events: Array<Event>): boolean {
     let didInvalidate = false;
     for (let {path: filePath, type} of events) {
-      let node = this.getNode(filePath);
+      let hasFileRequest = this.hasContentKey(filePath);
 
       // sometimes mac os reports update events as create events.
       // if it was a create event, but the file already exists in the graph,
       // then also invalidate nodes connected by invalidated_by_update edges.
-      if (node && (type === 'create' || type === 'update')) {
-        let nodes = this.getNodesConnectedTo(node, 'invalidated_by_update');
+      if (hasFileRequest && (type === 'create' || type === 'update')) {
+        let nodeId = this.getNodeIdByContentKey(filePath);
+        let nodes = this.getNodeIdsConnectedTo(nodeId, 'invalidated_by_update');
+
         for (let connectedNode of nodes) {
           didInvalidate = true;
           this.invalidateNode(connectedNode, FILE_UPDATE);
         }
 
         if (type === 'create') {
-          let nodes = this.getNodesConnectedTo(node, 'invalidated_by_create');
+          let nodes = this.getNodeIdsConnectedTo(
+            nodeId,
+            'invalidated_by_create',
+          );
           for (let connectedNode of nodes) {
             didInvalidate = true;
             this.invalidateNode(connectedNode, FILE_CREATE);
@@ -558,13 +569,17 @@ export class RequestGraph extends Graph<
         }
       } else if (type === 'create') {
         let basename = path.basename(filePath);
-        let fileNameNode = this.getNode('file_name:' + basename);
-        if (fileNameNode?.type === 'file_name') {
+        let fileNameNode = this.getNodeByContentKey('file_name:' + basename);
+        if (fileNameNode != null && fileNameNode?.type === 'file_name') {
+          let fileNameNodeId = this.getNodeIdByContentKey(
+            'file_name:' + basename,
+          );
           // Find potential file nodes to be invalidated if this file name pattern matches
-          let above = this.getNodesConnectedTo(
-            fileNameNode,
+          let above = this.getNodeIdsConnectedTo(
+            fileNameNodeId,
             'invalidated_by_create_above',
-          ).map(node => {
+          ).map(nodeId => {
+            let node = nullthrows(this.getNode(nodeId));
             invariant(node.type === 'file');
             return node;
           });
@@ -575,13 +590,13 @@ export class RequestGraph extends Graph<
           }
         }
 
-        for (let id of this.globNodeIds) {
-          let globNode = this.getNode(id);
+        for (let globeNodeId of this.globNodeIds) {
+          let globNode = this.getNode(globeNodeId);
           invariant(globNode && globNode.type === 'glob');
 
           if (isGlobMatch(filePath, globNode.value)) {
-            let connectedNodes = this.getNodesConnectedTo(
-              globNode,
+            let connectedNodes = this.getNodeIdsConnectedTo(
+              globeNodeId,
               'invalidated_by_create',
             );
             for (let connectedNode of connectedNodes) {
@@ -590,9 +605,10 @@ export class RequestGraph extends Graph<
             }
           }
         }
-      } else if (node && type === 'delete') {
-        for (let connectedNode of this.getNodesConnectedTo(
-          node,
+      } else if (hasFileRequest && type === 'delete') {
+        let nodeId = this.getNodeIdByContentKey(filePath);
+        for (let connectedNode of this.getNodeIdsConnectedTo(
+          nodeId,
           'invalidated_by_delete',
         )) {
           didInvalidate = true;
@@ -630,43 +646,45 @@ export default class RequestTracker {
     this.signal = signal;
   }
 
-  startRequest(request: StoredRequest) {
-    if (!this.graph.hasNode(request.id)) {
-      let node = nodeFromRequest(request);
-      this.graph.addNode(node);
-    } else {
+  startRequest(request: StoredRequest): NodeId {
+    let didPreviouslyExist = this.graph.hasContentKey(request.id);
+    let requestNodeId;
+    if (didPreviouslyExist) {
+      requestNodeId = this.graph.getNodeIdByContentKey(request.id);
       // Clear existing invalidations for the request so that the new
       // invalidations created during the request replace the existing ones.
-      this.graph.clearInvalidations(this.graph.getRequestNode(request.id));
+      this.graph.clearInvalidations(requestNodeId);
+    } else {
+      requestNodeId = this.graph.addNode(nodeFromRequest(request));
     }
 
-    this.graph.incompleteNodeIds.add(request.id);
-    this.graph.invalidNodeIds.delete(request.id);
-  }
-
-  removeRequest(id: string) {
-    this.graph.removeById(id);
+    this.graph.incompleteNodeIds.add(requestNodeId);
+    this.graph.invalidNodeIds.delete(requestNodeId);
+    return requestNodeId;
   }
 
   // If a cache key is provided, the result will be removed from the node and stored in a separate cache entry
-  storeResult(id: string, result: mixed, cacheKey: ?string) {
-    let node = this.graph.getNode(id);
+  storeResult(nodeId: NodeId, result: mixed, cacheKey: ?string) {
+    let node = this.graph.getNode(nodeId);
     if (node && node.type === 'request') {
       node.value.result = result;
       node.value.resultCacheKey = cacheKey;
     }
   }
 
-  hasValidResult(id: string): boolean {
+  hasValidResult(nodeId: NodeId): boolean {
     return (
-      this.graph.nodes.has(id) &&
-      !this.graph.invalidNodeIds.has(id) &&
-      !this.graph.incompleteNodeIds.has(id)
+      this.graph.hasNode(nodeId) &&
+      !this.graph.invalidNodeIds.has(nodeId) &&
+      !this.graph.incompleteNodeIds.has(nodeId)
     );
   }
 
-  async getRequestResult<T>(id: string, ifMatch?: string): Async<?T> {
-    let node = nullthrows(this.graph.getNode(id));
+  async getRequestResult<T>(
+    contentKey: ContentKey,
+    ifMatch?: string,
+  ): Async<?T> {
+    let node = nullthrows(this.graph.getNodeByContentKey(contentKey));
     invariant(node.type === 'request');
 
     if (ifMatch != null && node.value.resultCacheKey !== ifMatch) {
@@ -687,21 +705,21 @@ export default class RequestTracker {
     }
   }
 
-  completeRequest(id: string) {
-    this.graph.invalidNodeIds.delete(id);
-    this.graph.incompleteNodeIds.delete(id);
-    let node = this.graph.getNode(id);
+  completeRequest(nodeId: NodeId) {
+    this.graph.invalidNodeIds.delete(nodeId);
+    this.graph.incompleteNodeIds.delete(nodeId);
+    let node = this.graph.getNode(nodeId);
     if (node?.type === 'request') {
       node.invalidateReason = VALID;
     }
   }
 
-  rejectRequest(id: string) {
-    this.graph.incompleteNodeIds.delete(id);
+  rejectRequest(nodeId: NodeId) {
+    this.graph.incompleteNodeIds.delete(nodeId);
 
-    let node = this.graph.getNode(id);
+    let node = this.graph.getNode(nodeId);
     if (node?.type === 'request') {
-      this.graph.invalidateNode(node, ERROR);
+      this.graph.invalidateNode(nodeId, ERROR);
     }
   }
 
@@ -724,28 +742,36 @@ export default class RequestTracker {
   }
 
   replaceSubrequests(
-    requestId: string,
-    subrequestNodes: Array<RequestGraphNode>,
+    requestNodeId: NodeId,
+    subrequestContextKeys: Array<ContentKey>,
   ) {
-    this.graph.replaceSubrequests(requestId, subrequestNodes);
+    this.graph.replaceSubrequests(requestNodeId, subrequestContextKeys);
   }
 
   async runRequest<TInput, TResult>(
     request: Request<TInput, TResult>,
     opts?: ?RunRequestOpts,
   ): Async<TResult> {
-    let id = request.id;
+    let requestId = this.graph.hasContentKey(request.id)
+      ? this.graph.getNodeIdByContentKey(request.id)
+      : undefined;
+    let hasValidResult = requestId != null && this.hasValidResult(requestId);
 
-    let hasValidResult = this.hasValidResult(id);
     if (!opts?.force && hasValidResult) {
-      // $FlowFixMe
-      return this.getRequestResult<TResult>(id);
+      // $FlowFixMe[incompatible-type]
+      return this.getRequestResult<TResult>(request.id);
     }
 
-    let {api, subRequests} = this.createAPI(id);
+    let requestNodeId = this.startRequest({
+      id: request.id,
+      type: request.type,
+    });
+
+    let {api, subRequestContentKeys} = this.createAPI(requestNodeId);
+
     try {
-      this.startRequest({id, type: request.type});
-      let node = this.graph.getRequestNode(id);
+      let node = this.graph.getRequestNode(requestNodeId);
+
       let result = await request.run({
         input: request.input,
         api,
@@ -755,24 +781,21 @@ export default class RequestTracker {
       });
 
       assertSignalNotAborted(this.signal);
-      this.completeRequest(id);
+      this.completeRequest(requestNodeId);
 
       return result;
     } catch (err) {
-      this.rejectRequest(id);
+      this.rejectRequest(requestNodeId);
       throw err;
     } finally {
-      this.graph.replaceSubrequests(
-        id,
-        [...subRequests].map(subRequestId =>
-          nullthrows(this.graph.getNode(subRequestId)),
-        ),
-      );
+      this.graph.replaceSubrequests(requestNodeId, [...subRequestContentKeys]);
     }
   }
 
-  createAPI(requestId: string): {|api: RunAPI, subRequests: Set<NodeId>|} {
-    let subRequests = new Set();
+  createAPI(
+    requestId: NodeId,
+  ): {|api: RunAPI, subRequestContentKeys: Set<ContentKey>|} {
+    let subRequestContentKeys = new Set<ContentKey>();
     let invalidations = this.graph.getInvalidations(requestId);
     let api: RunAPI = {
       invalidateOnFileCreate: input =>
@@ -795,12 +818,17 @@ export default class RequestTracker {
         this.storeResult(requestId, result, cacheKey);
       },
       getSubRequests: () => this.graph.getSubRequests(requestId),
-      getPreviousResult: <T>(ifMatch?: string): Async<?T> =>
-        this.getRequestResult<T>(requestId, ifMatch),
+      getPreviousResult: <T>(ifMatch?: string): Async<?T> => {
+        let contentKey = nullthrows(this.graph.getNode(requestId)?.id);
+        return this.getRequestResult<T>(contentKey, ifMatch);
+      },
       getRequestResult: <T>(id): Async<?T> => this.getRequestResult<T>(id),
-      canSkipSubrequest: id => {
-        if (this.hasValidResult(id)) {
-          subRequests.add(id);
+      canSkipSubrequest: contentKey => {
+        if (
+          this.graph.hasContentKey(contentKey) &&
+          this.hasValidResult(this.graph.getNodeIdByContentKey(contentKey))
+        ) {
+          subRequestContentKeys.add(contentKey);
           return true;
         }
 
@@ -810,12 +838,12 @@ export default class RequestTracker {
         subRequest: Request<TInput, TResult>,
         opts?: RunRequestOpts,
       ): Async<TResult> => {
-        subRequests.add(subRequest.id);
+        subRequestContentKeys.add(subRequest.id);
         return this.runRequest<TInput, TResult>(subRequest, opts);
       },
     };
 
-    return {api, subRequests};
+    return {api, subRequestContentKeys};
   }
 
   async writeToCache() {
diff --git a/packages/core/core/src/applyRuntimes.js b/packages/core/core/src/applyRuntimes.js
index ff7045eee..5f5046d4b 100644
--- a/packages/core/core/src/applyRuntimes.js
+++ b/packages/core/core/src/applyRuntimes.js
@@ -5,9 +5,9 @@ import type {SharedReference} from '@parcel/workers';
 import type {
   AssetGroup,
   Bundle as InternalBundle,
+  ContentKey,
   Config,
   DevDepRequest,
-  NodeId,
   ParcelOptions,
 } from './types';
 import type ParcelConfig from './ParcelConfig';
@@ -143,11 +143,12 @@ export default async function applyRuntimes({
 
   for (let {bundle, assetGroup, dependency, isEntry} of connections) {
     let assetGroupNode = nodeFromAssetGroup(assetGroup);
-    let assetGroupAssets = runtimesAssetGraph.getNodesConnectedFrom(
-      assetGroupNode,
+    let assetGroupAssetNodeIds = runtimesAssetGraph.getNodeIdsConnectedFrom(
+      runtimesAssetGraph.getNodeIdByContentKey(assetGroupNode.id),
     );
-    invariant(assetGroupAssets.length === 1);
-    let runtimeNode = assetGroupAssets[0];
+    invariant(assetGroupAssetNodeIds.length === 1);
+    let runtimeNodeId = assetGroupAssetNodeIds[0];
+    let runtimeNode = nullthrows(runtimesAssetGraph.getNode(runtimeNodeId));
     invariant(runtimeNode.type === 'asset');
 
     let resolution =
@@ -156,15 +157,21 @@ export default async function applyRuntimes({
         dependencyToInternalDependency(dependency),
         bundle,
       );
-    let duplicatedAssetIds: Set<NodeId> = new Set();
-    runtimesGraph._graph.traverse((node, _, actions) => {
+
+    let runtimesGraphRuntimeNodeId = runtimesGraph._graph.getNodeIdByContentKey(
+      runtimeNode.id,
+    );
+    let duplicatedContentKeys: Set<ContentKey> = new Set();
+    runtimesGraph._graph.traverse((nodeId, _, actions) => {
+      let node = nullthrows(runtimesGraph._graph.getNode(nodeId));
       if (node.type !== 'dependency') {
         return;
       }
 
       let assets = runtimesGraph._graph
-        .getNodesConnectedFrom(node)
-        .map(assetNode => {
+        .getNodeIdsConnectedFrom(nodeId)
+        .map(assetNodeId => {
+          let assetNode = nullthrows(runtimesGraph._graph.getNode(assetNodeId));
           invariant(assetNode.type === 'asset');
           return assetNode.value;
         });
@@ -174,39 +181,49 @@ export default async function applyRuntimes({
           bundleGraph.isAssetReachableFromBundle(asset, bundle) ||
           resolution?.id === asset.id
         ) {
-          duplicatedAssetIds.add(asset.id);
+          duplicatedContentKeys.add(asset.id);
           actions.skipChildren();
         }
       }
-    }, runtimeNode);
+    }, runtimesGraphRuntimeNodeId);
+
+    let bundleNodeId = bundleGraph._graph.getNodeIdByContentKey(bundle.id);
+    let bundleGraphRuntimeNodeId = bundleGraph._graph.getNodeIdByContentKey(
+      runtimeNode.id,
+    ); // the node id is not constant between graphs
 
-    runtimesGraph._graph.traverse((node, _, actions) => {
+    runtimesGraph._graph.traverse((nodeId, _, actions) => {
+      let node = nullthrows(runtimesGraph._graph.getNode(nodeId));
       if (node.type === 'asset' || node.type === 'dependency') {
-        if (duplicatedAssetIds.has(node.id)) {
+        if (duplicatedContentKeys.has(node.id)) {
           actions.skipChildren();
           return;
         }
 
-        bundleGraph._graph.addEdge(bundle.id, node.id, 'contains');
+        const bundleGraphNodeId = bundleGraph._graph.getNodeIdByContentKey(
+          node.id,
+        ); // the node id is not constant between graphs
+        bundleGraph._graph.addEdge(bundleNodeId, bundleGraphNodeId, 'contains');
       }
-    }, runtimeNode);
+    }, runtimesGraphRuntimeNodeId);
 
     if (isEntry) {
-      bundleGraph._graph.addEdge(
-        nullthrows(bundleGraph._graph.getNode(bundle.id)).id,
-        runtimeNode.id,
-      );
+      bundleGraph._graph.addEdge(bundleNodeId, bundleGraphRuntimeNodeId);
       bundle.entryAssetIds.unshift(runtimeNode.id);
     }
 
     if (dependency == null) {
       // Verify this asset won't become an island
       assert(
-        bundleGraph._graph.getNodesConnectedTo(runtimeNode).length > 0,
+        bundleGraph._graph.getNodeIdsConnectedTo(bundleGraphRuntimeNodeId)
+          .length > 0,
         'Runtime must have an inbound dependency or be an entry',
       );
     } else {
-      bundleGraph._graph.addEdge(dependency.id, runtimeNode.id);
+      let dependencyNodeId = bundleGraph._graph.getNodeIdByContentKey(
+        dependency.id,
+      );
+      bundleGraph._graph.addEdge(dependencyNodeId, bundleGraphRuntimeNodeId);
     }
   }
 }
diff --git a/packages/core/core/src/public/Bundle.js b/packages/core/core/src/public/Bundle.js
index 69680d804..924939cb4 100644
--- a/packages/core/core/src/public/Bundle.js
+++ b/packages/core/core/src/public/Bundle.js
@@ -147,7 +147,7 @@ export class Bundle implements IBundle {
 
   getEntryAssets(): Array<IAsset> {
     return this.#bundle.entryAssetIds.map(id => {
-      let assetNode = this.#bundleGraph._graph.getNode(id);
+      let assetNode = this.#bundleGraph._graph.getNodeByContentKey(id);
       invariant(assetNode != null && assetNode.type === 'asset');
       return assetFromValue(assetNode.value, this.#options);
     });
@@ -155,7 +155,7 @@ export class Bundle implements IBundle {
 
   getMainEntry(): ?IAsset {
     if (this.#bundle.mainEntryId != null) {
-      let assetNode = this.#bundleGraph._graph.getNode(
+      let assetNode = this.#bundleGraph._graph.getNodeByContentKey(
         this.#bundle.mainEntryId,
       );
       invariant(assetNode != null && assetNode.type === 'asset');
diff --git a/packages/core/core/src/public/MutableBundleGraph.js b/packages/core/core/src/public/MutableBundleGraph.js
index 7942c574c..e9337207e 100644
--- a/packages/core/core/src/public/MutableBundleGraph.js
+++ b/packages/core/core/src/public/MutableBundleGraph.js
@@ -69,7 +69,7 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
   }
 
   createBundleGroup(dependency: IDependency, target: Target): BundleGroup {
-    let dependencyNode = this.#graph._graph.getNode(dependency.id);
+    let dependencyNode = this.#graph._graph.getNodeByContentKey(dependency.id);
     if (!dependencyNode) {
       throw new Error('Dependency not found');
     }
@@ -94,29 +94,40 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
       value: bundleGroup,
     };
 
-    this.#graph._graph.addNode(bundleGroupNode);
-    let assetNodes = this.#graph._graph.getNodesConnectedFrom(dependencyNode);
-    this.#graph._graph.addEdge(dependencyNode.id, bundleGroupNode.id);
-    this.#graph._graph.replaceNodesConnectedTo(bundleGroupNode, assetNodes);
-    this.#graph._graph.addEdge(dependencyNode.id, resolved.id, 'references');
-    this.#graph._graph.removeEdge(dependencyNode.id, resolved.id);
+    let bundleGroupNodeId = this.#graph._graph.addNodeByContentKey(
+      bundleGroupNode.id,
+      bundleGroupNode,
+    );
+    let dependencyNodeId = this.#graph._graph.getNodeIdByContentKey(
+      dependencyNode.id,
+    );
+    let resolvedNodeId = this.#graph._graph.getNodeIdByContentKey(resolved.id);
+    let assetNodes = this.#graph._graph.getNodeIdsConnectedFrom(
+      dependencyNodeId,
+    );
+    this.#graph._graph.addEdge(dependencyNodeId, bundleGroupNodeId);
+    this.#graph._graph.replaceNodeIdsConnectedTo(bundleGroupNodeId, assetNodes);
+    this.#graph._graph.addEdge(dependencyNodeId, resolvedNodeId, 'references');
+    this.#graph._graph.removeEdge(dependencyNodeId, resolvedNodeId);
 
     if (dependency.isEntry) {
       this.#graph._graph.addEdge(
-        nullthrows(this.#graph._graph.getRootNode()).id,
-        bundleGroupNode.id,
+        nullthrows(this.#graph._graph.rootNodeId),
+        bundleGroupNodeId,
         'bundle',
       );
     } else {
-      let inboundBundleNodes = this.#graph._graph.getNodesConnectedTo(
-        dependencyNode,
+      let inboundBundleNodeIds = this.#graph._graph.getNodeIdsConnectedTo(
+        dependencyNodeId,
         'contains',
       );
-      for (let inboundBundleNode of inboundBundleNodes) {
-        invariant(inboundBundleNode.type === 'bundle');
+      for (let inboundBundleNodeId of inboundBundleNodeIds) {
+        invariant(
+          this.#graph._graph.getNode(inboundBundleNodeId)?.type === 'bundle',
+        );
         this.#graph._graph.addEdge(
-          inboundBundleNode.id,
-          bundleGroupNode.id,
+          inboundBundleNodeId,
+          bundleGroupNodeId,
           'bundle',
         );
       }
@@ -148,7 +159,7 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
         path.relative(this.#options.projectRoot, target.distDir),
     );
 
-    let existing = this.#graph._graph.getNode(bundleId);
+    let existing = this.#graph._graph.getNodeByContentKey(bundleId);
     if (existing != null) {
       invariant(existing.type === 'bundle');
       return Bundle.get(existing.value, this.#graph, this.#options);
@@ -161,7 +172,9 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
 
     let isPlaceholder = false;
     if (entryAsset) {
-      let entryAssetNode = this.#graph._graph.getNode(entryAsset.id);
+      let entryAssetNode = this.#graph._graph.getNodeByContentKey(
+        entryAsset.id,
+      );
       invariant(entryAssetNode?.type === 'asset', 'Entry asset does not exist');
       isPlaceholder = entryAssetNode.requested === false;
     }
@@ -192,10 +205,16 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
       },
     };
 
-    this.#graph._graph.addNode(bundleNode);
+    let bundleNodeId = this.#graph._graph.addNodeByContentKey(
+      bundleId,
+      bundleNode,
+    );
 
     if (opts.entryAsset) {
-      this.#graph._graph.addEdge(bundleNode.id, opts.entryAsset.id);
+      this.#graph._graph.addEdge(
+        bundleNodeId,
+        this.#graph._graph.getNodeIdByContentKey(opts.entryAsset.id),
+      );
     }
     return Bundle.get(bundleNode.value, this.#graph, this.#options);
   }
@@ -236,7 +255,8 @@ export default class MutableBundleGraph extends BundleGraph<IBundle>
     visit: GraphVisitor<BundlerBundleGraphTraversable, TContext>,
   ): ?TContext {
     return this.#graph._graph.filteredTraverse(
-      node => {
+      nodeId => {
+        let node = nullthrows(this.#graph._graph.getNode(nodeId));
         if (node.type === 'asset') {
           return {
             type: 'asset',
diff --git a/packages/core/core/src/requests/AssetGraphRequest.js b/packages/core/core/src/requests/AssetGraphRequest.js
index efb917eaa..a47688ff4 100644
--- a/packages/core/core/src/requests/AssetGraphRequest.js
+++ b/packages/core/core/src/requests/AssetGraphRequest.js
@@ -12,20 +12,19 @@ import type {SharedReference} from '@parcel/workers';
 import type {Diagnostic} from '@parcel/diagnostic';
 import type {
   Asset,
-  AssetGraphNode,
   AssetGroup,
   AssetNode,
   AssetRequestInput,
   Dependency,
   DependencyNode,
   Entry,
+  NodeId,
   ParcelOptions,
   Target,
 } from '../types';
 import type {StaticRunOpts, RunAPI} from '../RequestTracker';
 import type {EntryResult} from './EntryRequest';
 import type {PathRequestInput} from './PathRequest';
-
 import invariant from 'assert';
 import nullthrows from 'nullthrows';
 import path from 'path';
@@ -143,40 +142,41 @@ export class AssetGraphBuilder {
 
   async build(): Promise<AssetGraphRequestResult> {
     let errors = [];
+    let rootNodeId = nullthrows(
+      this.assetGraph.rootNodeId,
+      'A root node is required to traverse',
+    );
 
-    let root = this.assetGraph.getRootNode();
-    if (!root) {
-      throw new Error('A root node is required to traverse');
-    }
-
-    let visited = new Set([root.id]);
-    const visit = (node: AssetGraphNode) => {
+    let visited = new Set([rootNodeId]);
+    const visit = (nodeId: NodeId) => {
       if (errors.length > 0) {
         return;
       }
 
-      if (this.shouldSkipRequest(node)) {
-        visitChildren(node);
+      if (this.shouldSkipRequest(nodeId)) {
+        visitChildren(nodeId);
       } else {
         // ? do we need to visit children inside of the promise that is queued?
-        this.queueCorrespondingRequest(node, errors).then(() =>
-          visitChildren(node),
+        this.queueCorrespondingRequest(nodeId, errors).then(() =>
+          visitChildren(nodeId),
         );
       }
     };
-    const visitChildren = (node: AssetGraphNode) => {
-      for (let child of this.assetGraph.getNodesConnectedFrom(node)) {
+
+    const visitChildren = (nodeId: NodeId) => {
+      for (let childNodeId of this.assetGraph.getNodeIdsConnectedFrom(nodeId)) {
+        let child = nullthrows(this.assetGraph.getNode(childNodeId));
         if (
-          (!visited.has(child.id) || child.hasDeferred) &&
-          this.shouldVisitChild(node, child)
+          (!visited.has(childNodeId) || child.hasDeferred) &&
+          this.shouldVisitChild(nodeId, childNodeId)
         ) {
-          visited.add(child.id);
-          visit(child);
+          visited.add(childNodeId);
+          visit(childNodeId);
         }
       }
     };
 
-    visit(root);
+    visit(rootNodeId);
     await this.queue.run();
 
     this.api.storeResult(
@@ -194,12 +194,13 @@ export class AssetGraphBuilder {
     // Skip symbol propagation if no target is using scope hoisting
     // (mainly for faster development builds)
     let entryDependencies = this.assetGraph
-      .getNodesConnectedFrom(root)
+      .getNodeIdsConnectedFrom(rootNodeId)
       .flatMap(entrySpecifier =>
-        this.assetGraph.getNodesConnectedFrom(entrySpecifier),
+        this.assetGraph.getNodeIdsConnectedFrom(entrySpecifier),
       )
       .flatMap(entryFile =>
-        this.assetGraph.getNodesConnectedFrom(entryFile).map(dep => {
+        this.assetGraph.getNodeIdsConnectedFrom(entryFile).map(depNodeId => {
+          let dep = nullthrows(this.assetGraph.getNode(depNodeId));
           invariant(dep.type === 'dependency');
           return dep;
         }),
@@ -221,9 +222,11 @@ export class AssetGraphBuilder {
     };
   }
 
-  shouldVisitChild(node: AssetGraphNode, child: AssetGraphNode): boolean {
+  shouldVisitChild(nodeId: NodeId, childNodeId: NodeId): boolean {
     if (this.shouldBuildLazily) {
-      if (node.type === 'asset' && child.type === 'dependency') {
+      let node = nullthrows(this.assetGraph.getNode(nodeId));
+      let childNode = nullthrows(this.assetGraph.getNode(childNodeId));
+      if (node.type === 'asset' && childNode.type === 'dependency') {
         if (this.requestedAssetIds.has(node.value.id)) {
           node.requested = true;
         } else if (!node.requested) {
@@ -237,20 +240,20 @@ export class AssetGraphBuilder {
           }
         }
 
-        let previouslyDeferred = child.deferred;
-        child.deferred = node.requested === false;
+        let previouslyDeferred = childNode.deferred;
+        childNode.deferred = node.requested === false;
 
-        if (!previouslyDeferred && child.deferred) {
-          this.assetGraph.markParentsWithHasDeferred(child);
-        } else if (previouslyDeferred && !child.deferred) {
-          this.assetGraph.unmarkParentsWithHasDeferred(child);
+        if (!previouslyDeferred && childNode.deferred) {
+          this.assetGraph.markParentsWithHasDeferred(childNodeId);
+        } else if (previouslyDeferred && !childNode.deferred) {
+          this.assetGraph.unmarkParentsWithHasDeferred(childNodeId);
         }
 
-        return !child.deferred;
+        return !childNode.deferred;
       }
     }
 
-    return this.assetGraph.shouldVisitChild(node, child);
+    return this.assetGraph.shouldVisitChild(nodeId, childNodeId);
   }
 
   propagateSymbols() {
@@ -399,6 +402,8 @@ export class AssetGraphBuilder {
     // Because namespace reexports introduce ambiguity, go up the graph from the leaves to the
     // root and remove requested symbols that aren't actually exported
     this.propagateSymbolsUp((assetNode, incomingDeps, outgoingDeps) => {
+      invariant(assetNode.type === 'asset');
+
       let assetSymbols: ?$ReadOnlyMap<
         Symbol,
         {|local: Symbol, loc: ?SourceLocation, meta?: ?Meta|},
@@ -423,7 +428,11 @@ export class AssetGraphBuilder {
         if (!outgoingDepSymbols) continue;
 
         // excluded, assume everything that is requested exists
-        if (this.assetGraph.getNodesConnectedFrom(outgoingDep).length === 0) {
+        if (
+          this.assetGraph.getNodeIdsConnectedFrom(
+            this.assetGraph.getNodeIdByContentKey(outgoingDep.id),
+          ).length === 0
+        ) {
           outgoingDep.usedSymbolsDown.forEach(s =>
             outgoingDep.usedSymbolsUp.add(s),
           );
@@ -471,8 +480,11 @@ export class AssetGraphBuilder {
             incomingDep.usedSymbolsUp.add(s);
           } else if (!hasNamespaceReexport) {
             let loc = incomingDep.value.symbols?.get(s)?.loc;
-            let [resolution] = this.assetGraph.getNodesConnectedFrom(
-              incomingDep,
+            let [resolutionNodeId] = this.assetGraph.getNodeIdsConnectedFrom(
+              this.assetGraph.getNodeIdByContentKey(incomingDep.id),
+            );
+            let resolution = nullthrows(
+              this.assetGraph.getNode(resolutionNodeId),
             );
             invariant(resolution && resolution.type === 'asset_group');
 
@@ -507,9 +519,12 @@ export class AssetGraphBuilder {
           incomingDep.value.symbols != null &&
           incomingDep.usedSymbolsUp.size === 0
         ) {
-          let assetGroups = this.assetGraph.getNodesConnectedFrom(incomingDep);
+          let assetGroups = this.assetGraph.getNodeIdsConnectedFrom(
+            this.assetGraph.getNodeIdByContentKey(incomingDep.id),
+          );
           if (assetGroups.length === 1) {
-            let [assetGroup] = assetGroups;
+            let [assetGroupId] = assetGroups;
+            let assetGroup = nullthrows(this.assetGraph.getNode(assetGroupId));
             invariant(assetGroup.type === 'asset_group');
             if (assetGroup.value.sideEffects === false) {
               incomingDep.excluded = true;
@@ -525,23 +540,24 @@ export class AssetGraphBuilder {
 
   propagateSymbolsDown(
     visit: (
-      node: AssetNode,
+      assetNode: AssetNode,
       incoming: $ReadOnlyArray<DependencyNode>,
       outgoing: $ReadOnlyArray<DependencyNode>,
     ) => void,
   ) {
-    let root = this.assetGraph.getRootNode();
-    if (!root) {
-      throw new Error('A root node is required to traverse');
-    }
-
-    let queue: Set<AssetGraphNode> = new Set([root]);
-    let visited = new Set<AssetGraphNode>();
+    let rootNodeId = nullthrows(
+      this.assetGraph.rootNodeId,
+      'A root node is required to traverse',
+    );
+    let queue: Set<NodeId> = new Set([rootNodeId]);
+    let visited = new Set<NodeId>();
 
     while (queue.size > 0) {
-      let node = nullthrows(queue.values().next().value);
-      queue.delete(node);
-      let outgoing = this.assetGraph.getNodesConnectedFrom(node);
+      let queuedNodeId = nullthrows(queue.values().next().value);
+      queue.delete(queuedNodeId);
+
+      let outgoing = this.assetGraph.getNodeIdsConnectedFrom(queuedNodeId);
+      let node = nullthrows(this.assetGraph.getNode(queuedNodeId));
 
       let wasNodeDirty = false;
       if (node.type === 'dependency' || node.type === 'asset_group') {
@@ -551,29 +567,31 @@ export class AssetGraphBuilder {
         visit(
           node,
           this.assetGraph.getIncomingDependencies(node.value).map(d => {
-            let dep = this.assetGraph.getNode(d.id);
+            let dep = this.assetGraph.getNodeByContentKey(d.id);
             invariant(dep && dep.type === 'dependency');
             return dep;
           }),
           outgoing.map(dep => {
-            invariant(dep.type === 'dependency');
-            return dep;
+            let depNode = nullthrows(this.assetGraph.getNode(dep));
+            invariant(depNode.type === 'dependency');
+            return depNode;
           }),
         );
         node.usedSymbolsDownDirty = false;
       }
 
-      visited.add(node);
+      visited.add(queuedNodeId);
       for (let child of outgoing) {
+        let childNode = nullthrows(this.assetGraph.getNode(child));
         let childDirty = false;
         if (
-          (child.type === 'asset' || child.type === 'asset_group') &&
+          (childNode.type === 'asset' || childNode.type === 'asset_group') &&
           wasNodeDirty
         ) {
-          child.usedSymbolsDownDirty = true;
+          childNode.usedSymbolsDownDirty = true;
           childDirty = true;
-        } else if (child.type === 'dependency') {
-          childDirty = child.usedSymbolsDownDirty;
+        } else if (childNode.type === 'dependency') {
+          childDirty = childNode.usedSymbolsDownDirty;
         }
         if (!visited.has(child) || childDirty) {
           queue.add(child);
@@ -584,27 +602,29 @@ export class AssetGraphBuilder {
 
   propagateSymbolsUp(
     visit: (
-      node: AssetNode,
+      assetNode: AssetNode,
       incoming: $ReadOnlyArray<DependencyNode>,
       outgoing: $ReadOnlyArray<DependencyNode>,
     ) => Array<Diagnostic>,
   ): void {
-    let root = this.assetGraph.getRootNode();
-    if (!root) {
-      throw new Error('A root node is required to traverse');
-    }
+    let rootNodeId = nullthrows(
+      this.assetGraph.rootNodeId,
+      'A root node is required to traverse',
+    );
 
-    let errors = new Map<AssetNode, Array<Diagnostic>>();
+    let errors = new Map<NodeId, Array<Diagnostic>>();
 
-    let dirtyDeps = new Set<DependencyNode>();
-    let visited = new Set([root.id]);
+    let dirtyDeps = new Set<NodeId>();
+    let visited = new Set([rootNodeId]);
     // post-order dfs
-    const walk = (node: AssetGraphNode) => {
-      let outgoing = this.assetGraph.getNodesConnectedFrom(node);
-      for (let child of outgoing) {
-        if (!visited.has(child.id)) {
-          visited.add(child.id);
-          walk(child);
+    const walk = (nodeId: NodeId) => {
+      let node = nullthrows(this.assetGraph.getNode(nodeId));
+      let outgoing = this.assetGraph.getNodeIdsConnectedFrom(nodeId);
+      for (let childId of outgoing) {
+        if (!visited.has(childId)) {
+          visited.add(childId);
+          walk(childId);
+          let child = nullthrows(this.assetGraph.getNode(childId));
           if (node.type === 'asset') {
             invariant(child.type === 'dependency');
             if (child.usedSymbolsUpDirtyUp) {
@@ -619,7 +639,7 @@ export class AssetGraphBuilder {
         let incoming = this.assetGraph
           .getIncomingDependencies(node.value)
           .map(d => {
-            let n = this.assetGraph.getNode(d.id);
+            let n = this.assetGraph.getNodeByContentKey(d.id);
             invariant(n && n.type === 'dependency');
             return n;
           });
@@ -634,46 +654,51 @@ export class AssetGraphBuilder {
           let e = visit(
             node,
             incoming,
-            outgoing.map(dep => {
-              invariant(dep.type === 'dependency');
-              return dep;
+            outgoing.map(depNodeId => {
+              let depNode = nullthrows(this.assetGraph.getNode(depNodeId));
+              invariant(depNode.type === 'dependency');
+              return depNode;
             }),
           );
           if (e.length > 0) {
-            errors.set(node, e);
+            errors.set(nodeId, e);
           } else {
-            errors.delete(node);
+            errors.delete(nodeId);
           }
         }
       } else if (node.type === 'dependency') {
         if (node.usedSymbolsUpDirtyUp) {
-          dirtyDeps.add(node);
+          dirtyDeps.add(nodeId);
         } else {
-          dirtyDeps.delete(node);
+          dirtyDeps.delete(nodeId);
         }
       }
     };
-    walk(root);
-    // traverse circular dependencies if neccessary (anchestors of `dirtyDeps`)
+    walk(rootNodeId);
+    // traverse circular dependencies if necessary (ancestors of `dirtyDeps`)
     visited = new Set();
     let queue = new Set(dirtyDeps);
     while (queue.size > 0) {
-      let node = nullthrows(queue.values().next().value);
-      queue.delete(node);
-
-      visited.add(node);
+      let queuedNodeId = nullthrows(queue.values().next().value);
+      queue.delete(queuedNodeId);
+      visited.add(queuedNodeId);
+      let node = nullthrows(this.assetGraph.getNode(queuedNodeId));
       if (node.type === 'asset') {
         let incoming = this.assetGraph
           .getIncomingDependencies(node.value)
-          .map(d => {
-            let n = this.assetGraph.getNode(d.id);
-            invariant(n && n.type === 'dependency');
-            return n;
+          .map(dep => {
+            let depNode = this.assetGraph.getNodeByContentKey(dep.id);
+            invariant(depNode && depNode.type === 'dependency');
+            return depNode;
+          });
+        let outgoing = this.assetGraph
+          .getNodeIdsConnectedFrom(queuedNodeId)
+          .map(depNodeId => {
+            let depNode = nullthrows(this.assetGraph.getNode(depNodeId));
+
+            invariant(depNode.type === 'dependency');
+            return depNode;
           });
-        let outgoing = this.assetGraph.getNodesConnectedFrom(node).map(dep => {
-          invariant(dep.type === 'dependency');
-          return dep;
-        });
         for (let dep of outgoing) {
           if (dep.usedSymbolsUpDirtyUp) {
             node.usedSymbolsUpDirty = true;
@@ -683,19 +708,22 @@ export class AssetGraphBuilder {
         if (node.usedSymbolsUpDirty) {
           let e = visit(node, incoming, outgoing);
           if (e.length > 0) {
-            errors.set(node, e);
+            errors.set(queuedNodeId, e);
           } else {
-            errors.delete(node);
+            errors.delete(queuedNodeId);
           }
         }
         for (let i of incoming) {
           if (i.usedSymbolsUpDirtyUp) {
-            queue.add(i);
+            queue.add(this.assetGraph.getNodeIdByContentKey(i.id));
           }
         }
       } else {
-        for (let connectedNode of this.assetGraph.getNodesConnectedTo(node)) {
-          queue.add(connectedNode);
+        let connectedNodes = this.assetGraph.getNodeIdsConnectedTo(
+          queuedNodeId,
+        );
+        if (connectedNodes.length > 0) {
+          queue.add(...connectedNodes);
         }
       }
     }
@@ -708,7 +736,8 @@ export class AssetGraphBuilder {
     }
   }
 
-  shouldSkipRequest(node: AssetGraphNode): boolean {
+  shouldSkipRequest(nodeId: NodeId): boolean {
+    let node = nullthrows(this.assetGraph.getNode(nodeId));
     return (
       node.complete === true ||
       !typesWithRequests.has(node.type) ||
@@ -718,10 +747,11 @@ export class AssetGraphBuilder {
   }
 
   queueCorrespondingRequest(
-    node: AssetGraphNode,
+    nodeId: NodeId,
     errors: Array<Error>,
   ): Promise<mixed> {
     let promise;
+    let node = nullthrows(this.assetGraph.getNode(nodeId));
     switch (node.type) {
       case 'entry_specifier':
         promise = this.runEntryRequest(node.value);
diff --git a/packages/core/core/src/requests/AssetRequest.js b/packages/core/core/src/requests/AssetRequest.js
index f93b2c34e..bff3e8d41 100644
--- a/packages/core/core/src/requests/AssetRequest.js
+++ b/packages/core/core/src/requests/AssetRequest.js
@@ -5,6 +5,7 @@ import type {StaticRunOpts} from '../RequestTracker';
 import type {
   AssetRequestInput,
   AssetRequestResult,
+  ContentKey,
   DevDepRequest,
   TransformationRequest,
 } from '../types';
@@ -23,7 +24,7 @@ type RunInput = {|
 |};
 
 export type AssetRequest = {|
-  id: string,
+  id: ContentKey,
   +type: 'asset_request',
   run: RunInput => Async<AssetRequestResult>,
   input: AssetRequestInput,
diff --git a/packages/core/core/src/types.js b/packages/core/core/src/types.js
index 2856f7609..37f5b6d5f 100644
--- a/packages/core/core/src/types.js
+++ b/packages/core/core/src/types.js
@@ -109,7 +109,7 @@ export type Dependency = {|
 |};
 
 export type Asset = {|
-  id: string,
+  id: ContentKey,
   committed: boolean,
   hash: ?string,
   filePath: FilePath,
@@ -213,7 +213,16 @@ export type ParcelOptions = {|
   |},
 |};
 
-export type NodeId = string;
+// forcing NodeId to be opaque as it should only be created once
+export opaque type NodeId = number;
+export function toNodeId(x: number): NodeId {
+  return x;
+}
+export function fromNodeId(x: NodeId): number {
+  return x;
+}
+
+export type ContentKey = string;
 
 export type Edge<TEdgeType: string | null> = {|
   from: NodeId,
@@ -222,14 +231,14 @@ export type Edge<TEdgeType: string | null> = {|
 |};
 
 export interface Node {
-  id: string;
+  id: ContentKey;
   +type: string;
   // $FlowFixMe
   value: any;
 }
 
 export type AssetNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'asset',
   value: Asset,
   usedSymbols: Set<Symbol>,
@@ -240,7 +249,7 @@ export type AssetNode = {|
 |};
 
 export type DependencyNode = {|
-  id: string,
+  id: ContentKey,
   type: 'dependency',
   value: Dependency,
   complete?: boolean,
@@ -259,7 +268,7 @@ export type DependencyNode = {|
   excluded: boolean,
 |};
 
-export type RootNode = {|id: string, +type: 'root', value: string | null|};
+export type RootNode = {|id: ContentKey, +type: 'root', value: string | null|};
 
 export type AssetRequestInput = {|
   name?: string, // AssetGraph name, needed so that different graphs can isolated requests since the results are not stored
@@ -282,7 +291,7 @@ export type AssetGroup = $Rest<
   {|optionsRef: SharedReference|},
 >;
 export type AssetGroupNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'asset_group',
   value: AssetGroup,
   correspondingRequest?: string,
@@ -304,19 +313,19 @@ export type TransformationRequest = {|
 |};
 
 export type DepPathRequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'dep_path_request',
   value: Dependency,
 |};
 
 export type AssetRequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'asset_request',
   value: AssetRequestInput,
 |};
 
 export type EntrySpecifierNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'entry_specifier',
   value: ModuleSpecifier,
   correspondingRequest?: string,
@@ -329,7 +338,7 @@ export type Entry = {|
 |};
 
 export type EntryFileNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'entry_file',
   value: Entry,
   correspondingRequest?: string,
@@ -367,7 +376,7 @@ export type Config = {|
 |};
 
 export type DepVersionRequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'dep_version_request',
   value: DepVersionRequestDesc,
 |};
@@ -384,13 +393,13 @@ export type EntryRequest = {|
 |};
 
 export type EntryRequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'entry_request',
   value: string,
 |};
 
 export type TargetRequestNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'target_request',
   value: FilePath,
 |};
@@ -405,13 +414,13 @@ export type CacheEntry = {|
 |};
 
 export type Bundle = {|
-  id: string,
+  id: ContentKey,
   publicId: ?string,
   hashReference: string,
   type: string,
   env: Environment,
-  entryAssetIds: Array<string>,
-  mainEntryId: ?string,
+  entryAssetIds: Array<ContentKey>,
+  mainEntryId: ?ContentKey,
   isEntry: ?boolean,
   isInline: ?boolean,
   isSplittable: ?boolean,
@@ -425,13 +434,13 @@ export type Bundle = {|
 |};
 
 export type BundleNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'bundle',
   value: Bundle,
 |};
 
 export type BundleGroupNode = {|
-  id: string,
+  id: ContentKey,
   +type: 'bundle_group',
   value: BundleGroup,
 |};
diff --git a/packages/core/workers/src/Worker.js b/packages/core/workers/src/Worker.js
index 4ac4eb0cb..7ea0cdae1 100644
--- a/packages/core/workers/src/Worker.js
+++ b/packages/core/workers/src/Worker.js
@@ -121,8 +121,8 @@ export default class Worker extends EventEmitter {
     this.emit('ready');
   }
 
-  sendSharedReference(ref: SharedReference, value: mixed) {
-    new Promise((resolve, reject) => {
+  sendSharedReference(ref: SharedReference, value: mixed): Promise<any> {
+    return new Promise((resolve, reject) => {
       this.call({
         method: 'createSharedReference',
         args: [ref, value],
diff --git a/yarn.lock b/yarn.lock
index ec2eae137..2a12fd904 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -1859,8 +1859,8 @@
 
 "@napi-rs/cli@1.0.0-alpha.10":
   version "1.0.0-alpha.10"
-  resolved "https://registry.yarnpkg.com/@napi-rs/cli/-/cli-1.0.0-alpha.10.tgz#7d6d3f77a5728fb62c9bca28128451e1b58be810"
-  integrity sha512-T9uxMZOdo/3rotlz6d3ECbVbBIXPpHHC+Ta3N87EvA93ZPWIQIUvskc28WBit/bWAX4xDtfBZRLA9gtWX0b8kw==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@napi-rs/cli/-/cli-1.0.0-alpha.10.tgz#7d6d3f77a5728fb62c9bca28128451e1b58be810"
+  integrity sha1-fW0/d6Vyj7Ysm8ooEoRR4bWL6BA=
   dependencies:
     "@octokit/rest" "^18.0.12"
     chalk "^4.1.0"
@@ -1908,15 +1908,15 @@
 
 "@octokit/auth-token@^2.4.4":
   version "2.4.5"
-  resolved "https://registry.yarnpkg.com/@octokit/auth-token/-/auth-token-2.4.5.tgz#568ccfb8cb46f36441fac094ce34f7a875b197f3"
-  integrity sha512-BpGYsPgJt05M7/L/5FoE1PiAbdxXFZkX/3kDYcsvd1v6UhlnE5e96dTDr0ezX/EFwciQxf3cNV0loipsURU+WA==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/auth-token/-/auth-token-2.4.5.tgz#568ccfb8cb46f36441fac094ce34f7a875b197f3"
+  integrity sha1-VozPuMtG82RB+sCUzjT3qHWxl/M=
   dependencies:
     "@octokit/types" "^6.0.3"
 
 "@octokit/core@^2.4.3":
   version "2.5.4"
-  resolved "https://registry.yarnpkg.com/@octokit/core/-/core-2.5.4.tgz#f7fbf8e4f86c5cc2497a8887ba2561ec8d358054"
-  integrity sha512-HCp8yKQfTITYK+Nd09MHzAlP1v3Ii/oCohv0/TW9rhSLvzb98BOVs2QmVYuloE6a3l6LsfyGIwb6Pc4ycgWlIQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/core/-/core-2.5.4.tgz#f7fbf8e4f86c5cc2497a8887ba2561ec8d358054"
+  integrity sha1-9/v45PhsXMJJeoiHuiVh7I01gFQ=
   dependencies:
     "@octokit/auth-token" "^2.4.0"
     "@octokit/graphql" "^4.3.1"
@@ -1985,13 +1985,13 @@
 
 "@octokit/plugin-request-log@^1.0.0", "@octokit/plugin-request-log@^1.0.2":
   version "1.0.3"
-  resolved "https://registry.yarnpkg.com/@octokit/plugin-request-log/-/plugin-request-log-1.0.3.tgz#70a62be213e1edc04bb8897ee48c311482f9700d"
-  integrity sha512-4RFU4li238jMJAzLgAwkBAw+4Loile5haQMQr+uhFq27BmyJXcXSKvoQKqh0agsZEiUlW6iSv3FAgvmGkur7OQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/plugin-request-log/-/plugin-request-log-1.0.3.tgz#70a62be213e1edc04bb8897ee48c311482f9700d"
+  integrity sha1-cKYr4hPh7cBLuIl+5IwxFIL5cA0=
 
 "@octokit/plugin-rest-endpoint-methods@3.17.0":
   version "3.17.0"
-  resolved "https://registry.yarnpkg.com/@octokit/plugin-rest-endpoint-methods/-/plugin-rest-endpoint-methods-3.17.0.tgz#d8ba04eb883849dd98666c55bf49d8c9fe7be055"
-  integrity sha512-NFV3vq7GgoO2TrkyBRUOwflkfTYkFKS0tLAPym7RNpkwLCttqShaEGjthOsPEEL+7LFcYv3mU24+F2yVd3npmg==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/plugin-rest-endpoint-methods/-/plugin-rest-endpoint-methods-3.17.0.tgz#d8ba04eb883849dd98666c55bf49d8c9fe7be055"
+  integrity sha1-2LoE64g4Sd2YZmxVv0nYyf574FU=
   dependencies:
     "@octokit/types" "^4.1.6"
     deprecation "^2.3.1"
@@ -2069,8 +2069,8 @@
 
 "@octokit/rest@^17.1.3":
   version "17.11.2"
-  resolved "https://registry.yarnpkg.com/@octokit/rest/-/rest-17.11.2.tgz#f3dbd46f9f06361c646230fd0ef8598e59183ead"
-  integrity sha512-4jTmn8WossTUaLfNDfXk4fVJgbz5JgZE8eCs4BvIb52lvIH8rpVMD1fgRCrHbSd6LRPE5JFZSfAEtszrOq3ZFQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/rest/-/rest-17.11.2.tgz#f3dbd46f9f06361c646230fd0ef8598e59183ead"
+  integrity sha1-89vUb58GNhxkYjD9DvhZjlkYPq0=
   dependencies:
     "@octokit/core" "^2.4.3"
     "@octokit/plugin-paginate-rest" "^2.2.0"
@@ -2096,15 +2096,15 @@
 
 "@octokit/types@^4.1.6":
   version "4.1.10"
-  resolved "https://registry.yarnpkg.com/@octokit/types/-/types-4.1.10.tgz#e4029c11e2cc1335051775bc1600e7e740e4aca4"
-  integrity sha512-/wbFy1cUIE5eICcg0wTKGXMlKSbaAxEr00qaBXzscLXpqhcwgXeS6P8O0pkysBhRfyjkKjJaYrvR1ExMO5eOXQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/types/-/types-4.1.10.tgz#e4029c11e2cc1335051775bc1600e7e740e4aca4"
+  integrity sha1-5AKcEeLMEzUFF3W8FgDn50DkrKQ=
   dependencies:
     "@types/node" ">= 8"
 
 "@octokit/types@^5.0.0":
   version "5.5.0"
-  resolved "https://registry.yarnpkg.com/@octokit/types/-/types-5.5.0.tgz#e5f06e8db21246ca102aa28444cdb13ae17a139b"
-  integrity sha512-UZ1pErDue6bZNjYOotCNveTXArOMZQFG6hKJfOnGnulVCMcVVi7YIIuuR4WfBhjo7zgpmzn/BkPDnUXtNx+PcQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/@octokit/types/-/types-5.5.0.tgz#e5f06e8db21246ca102aa28444cdb13ae17a139b"
+  integrity sha1-5fBujbISRsoQKqKERM2xOuF6E5s=
   dependencies:
     "@types/node" ">= 8"
 
@@ -3609,7 +3609,7 @@ charenc@~0.0.1:
 
 checkup@^1.3.0:
   version "1.3.0"
-  resolved "https://registry.yarnpkg.com/checkup/-/checkup-1.3.0.tgz#d3800276fea5d0f247ffc951be78c8b02f8e0d76"
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/checkup/-/checkup-1.3.0.tgz#d3800276fea5d0f247ffc951be78c8b02f8e0d76"
   integrity sha1-04ACdv6l0PJH/8lRvnjIsC+ODXY=
 
 chokidar@3.5.1:
@@ -3740,8 +3740,8 @@ cli-width@^3.0.0:
 
 clipanion@^2.6.2:
   version "2.6.2"
-  resolved "https://registry.yarnpkg.com/clipanion/-/clipanion-2.6.2.tgz#820e7440812052442455b248f927b187ed732f71"
-  integrity sha512-0tOHJNMF9+4R3qcbBL+4IxLErpaYSYvzs10aXuECDbZdJOuJHdagJMAqvLdeaUQTI/o2uSCDRpet6ywDiKOAYw==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/clipanion/-/clipanion-2.6.2.tgz#820e7440812052442455b248f927b187ed732f71"
+  integrity sha1-gg50QIEgUkQkVbJI+Sexh+1zL3E=
 
 cliui@^3.2.0:
   version "3.2.0"
@@ -5852,8 +5852,8 @@ fclone@^1.0.11:
 
 fdir@^4.1.0:
   version "4.1.0"
-  resolved "https://registry.yarnpkg.com/fdir/-/fdir-4.1.0.tgz#f739ec79f61f69779a6430a622e5f54c57caf921"
-  integrity sha512-oOkohnPg4nUIkd6w22iGbFD7c7UvVnXB3a7/GHcPSsXDUGm6Jxp12bGI5O0gr0YuhDh5l/vDExdHOnrW/j9EqQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/fdir/-/fdir-4.1.0.tgz#f739ec79f61f69779a6430a622e5f54c57caf921"
+  integrity sha1-9znsefYfaXeaZDCmIuX1TFfK+SE=
 
 figgy-pudding@^3.4.1, figgy-pudding@^3.5.1:
   version "3.5.1"
@@ -7812,7 +7812,7 @@ isstream@~0.1.2:
 
 jju@^1.4.0:
   version "1.4.0"
-  resolved "https://registry.yarnpkg.com/jju/-/jju-1.4.0.tgz#a3abe2718af241a2b2904f84a625970f389ae32a"
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/jju/-/jju-1.4.0.tgz#a3abe2718af241a2b2904f84a625970f389ae32a"
   integrity sha1-o6vicYryQaKykE+EpiWXDzia4yo=
 
 js-stringify@^1.0.2:
@@ -10843,8 +10843,8 @@ purgecss@^1.4.0:
 
 putasset@^5.0.3:
   version "5.0.3"
-  resolved "https://registry.yarnpkg.com/putasset/-/putasset-5.0.3.tgz#2fa82a8fc5e2333869df8ffb0e1f8618b1c87b9b"
-  integrity sha512-LGRp0SLOC4PDP/BawMaG3/hw6iKgQPRXcBF7WIzx2XTYwHVk2sS3gpvZqz6bf9GhKMal2phs+DF7J6eIAXEL4w==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/putasset/-/putasset-5.0.3.tgz#2fa82a8fc5e2333869df8ffb0e1f8618b1c87b9b"
+  integrity sha1-L6gqj8XiMzhp34/7Dh+GGLHIe5s=
   dependencies:
     "@octokit/rest" "^17.1.3"
     checkup "^1.3.0"
@@ -11139,8 +11139,8 @@ readdirp@~3.5.0:
 
 readjson@^2.0.1:
   version "2.2.2"
-  resolved "https://registry.yarnpkg.com/readjson/-/readjson-2.2.2.tgz#ed940ebdd72b88b383e02db7117402f980158959"
-  integrity sha512-PdeC9tsmLWBiL8vMhJvocq+OezQ3HhsH2HrN7YkhfYcTjQSa/iraB15A7Qvt7Xpr0Yd2rDNt6GbFwVQDg3HcAw==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/readjson/-/readjson-2.2.2.tgz#ed940ebdd72b88b383e02db7117402f980158959"
+  integrity sha1-7ZQOvdcriLOD4C23EXQC+YAViVk=
   dependencies:
     jju "^1.4.0"
     try-catch "^3.0.0"
@@ -12809,8 +12809,8 @@ token-stream@1.0.0:
 
 toml@^3.0.0:
   version "3.0.0"
-  resolved "https://registry.yarnpkg.com/toml/-/toml-3.0.0.tgz#342160f1af1904ec9d204d03a5d61222d762c5ee"
-  integrity sha512-y/mWCZinnvxjTKYhJ+pYxwD0mRLVvOtdS2Awbgxln6iEnt4rk0yBxeSBHkGJcPucRiG0e55mwWp+g/05rsrd6w==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/toml/-/toml-3.0.0.tgz#342160f1af1904ec9d204d03a5d61222d762c5ee"
+  integrity sha1-NCFg8a8ZBOydIE0DpdYSItdixe4=
 
 tough-cookie@^2.3.3, tough-cookie@^2.5.0:
   version "2.5.0"
@@ -12881,13 +12881,13 @@ trough@^1.0.0:
 
 try-catch@^3.0.0:
   version "3.0.0"
-  resolved "https://registry.yarnpkg.com/try-catch/-/try-catch-3.0.0.tgz#7996d8b89895e2e8ae62cbdbeb4fe17470f8131b"
-  integrity sha512-3uAqUnoemzca1ENvZ72EVimR+E8lqBbzwZ9v4CEbLjkaV3Q+FtdmPUt7jRtoSoTiYjyIMxEkf6YgUpe/voJ1ng==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/try-catch/-/try-catch-3.0.0.tgz#7996d8b89895e2e8ae62cbdbeb4fe17470f8131b"
+  integrity sha1-eZbYuJiV4uiuYsvb60/hdHD4Exs=
 
 try-to-catch@^3.0.0:
   version "3.0.0"
-  resolved "https://registry.yarnpkg.com/try-to-catch/-/try-to-catch-3.0.0.tgz#a1903b44d13d5124c54d14a461d22ec1f52ea14b"
-  integrity sha512-eIm6ZXwR35jVF8By/HdbbkcaCDTBI5PpCPkejRKrYp0jyf/DbCCcRhHD7/O9jtFI3ewsqo9WctFEiJTS6i+CQA==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/try-to-catch/-/try-to-catch-3.0.0.tgz#a1903b44d13d5124c54d14a461d22ec1f52ea14b"
+  integrity sha1-oZA7RNE9USTFTRSkYdIuwfUuoUs=
 
 tsconfig-paths@^3.9.0:
   version "3.9.0"
@@ -13255,8 +13255,8 @@ universal-user-agent@^4.0.0:
 
 universal-user-agent@^5.0.0:
   version "5.0.0"
-  resolved "https://registry.yarnpkg.com/universal-user-agent/-/universal-user-agent-5.0.0.tgz#a3182aa758069bf0e79952570ca757de3579c1d9"
-  integrity sha512-B5TPtzZleXyPrUMKCpEHFmVhMN6EhmJYjG5PQna9s7mXeSqGTLap4OpqLl5FCEFUI3UBmllkETwKf/db66Y54Q==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/universal-user-agent/-/universal-user-agent-5.0.0.tgz#a3182aa758069bf0e79952570ca757de3579c1d9"
+  integrity sha1-oxgqp1gGm/DnmVJXDKdX3jV5wdk=
   dependencies:
     os-name "^3.1.0"
 
@@ -14139,8 +14139,8 @@ yargs-parser@^15.0.0:
 
 yargs-parser@^18.1.1:
   version "18.1.3"
-  resolved "https://registry.yarnpkg.com/yargs-parser/-/yargs-parser-18.1.3.tgz#be68c4975c6b2abf469236b0c870362fab09a7b0"
-  integrity sha512-o50j0JeToy/4K6OZcaQmW6lyXXKhq7csREXcDwk2omFPJEwUNOVtJKvmDr9EI1fAJZUyZcRF7kxGBWmRXudrCQ==
+  resolved "https://packages.atlassian.com/api/npm/npm-remote/yargs-parser/-/yargs-parser-18.1.3.tgz#be68c4975c6b2abf469236b0c870362fab09a7b0"
+  integrity sha1-vmjEl1xrKr9GkjawyHA2L6sJp7A=
   dependencies:
     camelcase "^5.0.0"
     decamelize "^1.2.0"


Test patch:
diff --git a/packages/core/core/test/AssetGraph.test.js b/packages/core/core/test/AssetGraph.test.js
index cfe36fc26..0c62fe6b0 100644
--- a/packages/core/core/test/AssetGraph.test.js
+++ b/packages/core/core/test/AssetGraph.test.js
@@ -1,5 +1,4 @@
-// @flow
-
+// @flow strict-local
 import assert from 'assert';
 import invariant from 'assert';
 import nullthrows from 'nullthrows';
@@ -22,9 +21,9 @@ describe('AssetGraph', () => {
       entries: ['/path/to/index1', '/path/to/index2'],
     });
 
-    assert(graph.nodes.has('@@root'));
-    assert(graph.nodes.has('entry_specifier:/path/to/index1'));
-    assert(graph.nodes.has('entry_specifier:/path/to/index2'));
+    assert(graph.hasNode(nullthrows(graph.rootNodeId)));
+    assert(graph.hasContentKey('entry_specifier:/path/to/index1'));
+    assert(graph.hasContentKey('entry_specifier:/path/to/index2'));
   });
 
   it('resolveEntry should connect an entry_specifier node to entry_file nodes', () => {
@@ -45,7 +44,7 @@ describe('AssetGraph', () => {
     );
 
     assert(
-      graph.nodes.has(
+      graph.hasContentKey(
         nodeFromEntryFile({
           filePath: '/path/to/index1/src/main.js',
           packagePath: '/path/to/index1',
@@ -54,11 +53,13 @@ describe('AssetGraph', () => {
     );
     assert(
       graph.hasEdge(
-        'entry_specifier:/path/to/index1',
-        nodeFromEntryFile({
-          filePath: '/path/to/index1/src/main.js',
-          packagePath: '/path/to/index1',
-        }).id,
+        graph.getNodeIdByContentKey('entry_specifier:/path/to/index1'),
+        graph.getNodeIdByContentKey(
+          nodeFromEntryFile({
+            filePath: '/path/to/index1/src/main.js',
+            packagePath: '/path/to/index1',
+          }).id,
+        ),
       ),
     );
   });
@@ -102,7 +103,7 @@ describe('AssetGraph', () => {
     );
 
     assert(
-      graph.nodes.has(
+      graph.hasContentKey(
         createDependency({
           moduleSpecifier: '/path/to/index1/src/main.js',
           target: DEFAULT_TARGETS[0],
@@ -111,7 +112,7 @@ describe('AssetGraph', () => {
       ),
     );
     assert(
-      graph.nodes.has(
+      graph.hasContentKey(
         createDependency({
           moduleSpecifier: '/path/to/index2/src/main.js',
           target: DEFAULT_TARGETS[0],
@@ -121,53 +122,65 @@ describe('AssetGraph', () => {
     );
     assert.deepEqual(graph.getAllEdges(), [
       {
-        from: '@@root',
-        to: 'entry_specifier:/path/to/index1',
+        from: graph.rootNodeId,
+        to: graph.getNodeIdByContentKey('entry_specifier:/path/to/index1'),
         type: null,
       },
       {
-        from: '@@root',
-        to: 'entry_specifier:/path/to/index2',
+        from: graph.rootNodeId,
+        to: graph.getNodeIdByContentKey('entry_specifier:/path/to/index2'),
         type: null,
       },
       {
-        from: 'entry_specifier:/path/to/index1',
-        to: nodeFromEntryFile({
-          filePath: '/path/to/index1/src/main.js',
-          packagePath: '/path/to/index1',
-        }).id,
+        from: graph.getNodeIdByContentKey('entry_specifier:/path/to/index1'),
+        to: graph.getNodeIdByContentKey(
+          nodeFromEntryFile({
+            filePath: '/path/to/index1/src/main.js',
+            packagePath: '/path/to/index1',
+          }).id,
+        ),
         type: null,
       },
       {
-        from: 'entry_specifier:/path/to/index2',
-        to: nodeFromEntryFile({
-          filePath: '/path/to/index2/src/main.js',
-          packagePath: '/path/to/index2',
-        }).id,
+        from: graph.getNodeIdByContentKey('entry_specifier:/path/to/index2'),
+        to: graph.getNodeIdByContentKey(
+          nodeFromEntryFile({
+            filePath: '/path/to/index2/src/main.js',
+            packagePath: '/path/to/index2',
+          }).id,
+        ),
         type: null,
       },
       {
-        from: nodeFromEntryFile({
-          filePath: '/path/to/index1/src/main.js',
-          packagePath: '/path/to/index1',
-        }).id,
-        to: createDependency({
-          moduleSpecifier: '/path/to/index1/src/main.js',
-          target: DEFAULT_TARGETS[0],
-          env: DEFAULT_ENV,
-        }).id,
+        from: graph.getNodeIdByContentKey(
+          nodeFromEntryFile({
+            filePath: '/path/to/index1/src/main.js',
+            packagePath: '/path/to/index1',
+          }).id,
+        ),
+        to: graph.getNodeIdByContentKey(
+          createDependency({
+            moduleSpecifier: '/path/to/index1/src/main.js',
+            target: DEFAULT_TARGETS[0],
+            env: DEFAULT_ENV,
+          }).id,
+        ),
         type: null,
       },
       {
-        from: nodeFromEntryFile({
-          filePath: '/path/to/index2/src/main.js',
-          packagePath: '/path/to/index2',
-        }).id,
-        to: createDependency({
-          moduleSpecifier: '/path/to/index2/src/main.js',
-          target: DEFAULT_TARGETS[0],
-          env: DEFAULT_ENV,
-        }).id,
+        from: graph.getNodeIdByContentKey(
+          nodeFromEntryFile({
+            filePath: '/path/to/index2/src/main.js',
+            packagePath: '/path/to/index2',
+          }).id,
+        ),
+        to: graph.getNodeIdByContentKey(
+          createDependency({
+            moduleSpecifier: '/path/to/index2/src/main.js',
+            target: DEFAULT_TARGETS[0],
+            env: DEFAULT_ENV,
+          }).id,
+        ),
         type: null,
       },
     ]);
@@ -199,19 +212,27 @@ describe('AssetGraph', () => {
     let req = {filePath: '/index.js', env: DEFAULT_ENV, query: {}};
 
     graph.resolveDependency(dep, req, '3');
-    assert(graph.nodes.has(nodeFromAssetGroup(req).id));
-    assert(graph.hasEdge(dep.id, nodeFromAssetGroup(req).id));
+    let assetGroupNodeId = graph.getNodeIdByContentKey(
+      nodeFromAssetGroup(req).id,
+    );
+    let dependencyNodeId = graph.getNodeIdByContentKey(dep.id);
+    assert(graph.nodes.has(assetGroupNodeId));
+    assert(graph.hasEdge(dependencyNodeId, assetGroupNodeId));
 
     let req2 = {filePath: '/index.jsx', env: DEFAULT_ENV, query: {}};
     graph.resolveDependency(dep, req2, '4');
-    assert(!graph.nodes.has(nodeFromAssetGroup(req).id));
-    assert(graph.nodes.has(nodeFromAssetGroup(req2).id));
-    assert(graph.hasEdge(dep.id, nodeFromAssetGroup(req2).id));
-    assert(!graph.hasEdge(dep.id, nodeFromAssetGroup(req).id));
+
+    let assetGroupNodeId2 = graph.getNodeIdByContentKey(
+      nodeFromAssetGroup(req2).id,
+    );
+    assert(!graph.nodes.has(assetGroupNodeId));
+    assert(graph.nodes.has(assetGroupNodeId2));
+    assert(graph.hasEdge(dependencyNodeId, assetGroupNodeId2));
+    assert(!graph.hasEdge(dependencyNodeId, assetGroupNodeId));
 
     graph.resolveDependency(dep, req2, '5');
-    assert(graph.nodes.has(nodeFromAssetGroup(req2).id));
-    assert(graph.hasEdge(dep.id, nodeFromAssetGroup(req2).id));
+    assert(graph.nodes.has(assetGroupNodeId2));
+    assert(graph.hasEdge(dependencyNodeId, assetGroupNodeId2));
   });
 
   it('resolveAssetGroup should update the asset and dep nodes a file is connected to', () => {
@@ -294,16 +315,32 @@ describe('AssetGraph', () => {
     ];
 
     graph.resolveAssetGroup(req, assets, '4');
-    assert(graph.nodes.has('1'));
-    assert(graph.nodes.has('2'));
-    assert(graph.nodes.has('3'));
-    assert(graph.nodes.has([...assets[0].dependencies.values()][0].id));
-    assert(graph.nodes.has([...assets[1].dependencies.values()][0].id));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '1'));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '2'));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '3'));
-    assert(graph.hasEdge('1', [...assets[0].dependencies.values()][0].id));
-    assert(graph.hasEdge('2', [...assets[1].dependencies.values()][0].id));
+
+    let nodeId1 = graph.getNodeIdByContentKey('1');
+    let nodeId2 = graph.getNodeIdByContentKey('2');
+    let nodeId3 = graph.getNodeIdByContentKey('3');
+
+    let assetGroupNode = graph.getNodeIdByContentKey(
+      nodeFromAssetGroup(req).id,
+    );
+
+    let dependencyNodeId1 = graph.getNodeIdByContentKey(
+      [...assets[0].dependencies.values()][0].id,
+    );
+    let dependencyNodeId2 = graph.getNodeIdByContentKey(
+      [...assets[1].dependencies.values()][0].id,
+    );
+
+    assert(graph.nodes.has(nodeId1));
+    assert(graph.nodes.has(nodeId2));
+    assert(graph.nodes.has(nodeId3));
+    assert(graph.nodes.has(dependencyNodeId1));
+    assert(graph.nodes.has(dependencyNodeId2));
+    assert(graph.hasEdge(assetGroupNode, nodeId1));
+    assert(graph.hasEdge(assetGroupNode, nodeId2));
+    assert(graph.hasEdge(assetGroupNode, nodeId3));
+    assert(graph.hasEdge(nodeId1, dependencyNodeId1));
+    assert(graph.hasEdge(nodeId2, dependencyNodeId2));
 
     let assets2 = [
       createAsset({
@@ -338,20 +375,21 @@ describe('AssetGraph', () => {
     ];
 
     graph.resolveAssetGroup(req, assets2, '5');
-    assert(graph.nodes.has('1'));
-    assert(graph.nodes.has('2'));
-    assert(!graph.nodes.has('3'));
-    assert(graph.nodes.has([...assets[0].dependencies.values()][0].id));
-    assert(!graph.nodes.has([...assets[1].dependencies.values()][0].id));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '1'));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '2'));
-    assert(!graph.hasEdge(nodeFromAssetGroup(req).id, '3'));
-    assert(graph.hasEdge('1', [...assets[0].dependencies.values()][0].id));
-    assert(!graph.hasEdge('2', [...assets[1].dependencies.values()][0].id));
+
+    assert(graph.nodes.has(nodeId1));
+    assert(graph.nodes.has(nodeId2));
+    assert(!graph.nodes.has(nodeId3));
+    assert(graph.nodes.has(dependencyNodeId1));
+    assert(!graph.nodes.has(dependencyNodeId2));
+    assert(graph.hasEdge(assetGroupNode, nodeId1));
+    assert(graph.hasEdge(assetGroupNode, nodeId2));
+    assert(!graph.hasEdge(assetGroupNode, nodeId3));
+    assert(graph.hasEdge(nodeId1, dependencyNodeId1));
+    assert(!graph.hasEdge(nodeId2, dependencyNodeId2));
   });
 
   // Assets can define dependent assets in the same asset group by declaring a dependency with a module
-  // specifer that matches the dependent asset's unique key. These dependent assets are then connected
+  // specifier that matches the dependent asset's unique key. These dependent assets are then connected
   // to the asset's dependency instead of the asset group.
   it('resolveAssetGroup should handle dependent assets in asset groups', () => {
     let graph = new AssetGraph();
@@ -422,16 +460,28 @@ describe('AssetGraph', () => {
     ];
 
     graph.resolveAssetGroup(req, assets, '3');
-    assert(graph.nodes.has('1'));
-    assert(graph.nodes.has('2'));
-    assert(graph.nodes.has('3'));
-    assert(graph.hasEdge(nodeFromAssetGroup(req).id, '1'));
-    assert(!graph.hasEdge(nodeFromAssetGroup(req).id, '2'));
-    assert(!graph.hasEdge(nodeFromAssetGroup(req).id, '3'));
-    assert(graph.hasEdge('1', nodeFromDep(dep1).id));
-    assert(graph.hasEdge(nodeFromDep(dep1).id, '2'));
-    assert(graph.hasEdge('2', nodeFromDep(dep2).id));
-    assert(graph.hasEdge(nodeFromDep(dep2).id, '3'));
+
+    let nodeId1 = graph.getNodeIdByContentKey('1');
+    let nodeId2 = graph.getNodeIdByContentKey('2');
+    let nodeId3 = graph.getNodeIdByContentKey('3');
+
+    let assetGroupNodeId = graph.getNodeIdByContentKey(
+      nodeFromAssetGroup(req).id,
+    );
+
+    let depNodeId1 = graph.getNodeIdByContentKey(nodeFromDep(dep1).id);
+    let depNodeId2 = graph.getNodeIdByContentKey(nodeFromDep(dep2).id);
+
+    assert(nodeId1);
+    assert(nodeId2);
+    assert(nodeId3);
+    assert(graph.hasEdge(assetGroupNodeId, nodeId1));
+    assert(!graph.hasEdge(assetGroupNodeId, nodeId2));
+    assert(!graph.hasEdge(assetGroupNodeId, nodeId3));
+    assert(graph.hasEdge(nodeId1, depNodeId1));
+    assert(graph.hasEdge(depNodeId1, nodeId2));
+    assert(graph.hasEdge(nodeId2, depNodeId2));
+    assert(graph.hasEdge(depNodeId2, nodeId3));
   });
 
   it('should support marking and unmarking all parents with hasDeferred', () => {
@@ -492,11 +542,13 @@ describe('AssetGraph', () => {
     graph.resolveDependency(fooUtilsDep, utilsAssetGroup, '0');
 
     // foo's dependency is deferred
-    graph.markParentsWithHasDeferred(fooUtilsDepNode);
-    let node = nullthrows(graph.getNode(fooAssetNode.id));
+    graph.markParentsWithHasDeferred(
+      graph.getNodeIdByContentKey(fooUtilsDepNode.id),
+    );
+    let node = nullthrows(graph.getNodeByContentKey(fooAssetNode.id));
     invariant(node.type === 'asset');
     assert(node.hasDeferred);
-    node = nullthrows(graph.getNode(fooAssetGroupNode.id));
+    node = nullthrows(graph.getNodeByContentKey(fooAssetGroupNode.id));
     invariant(node.type === 'asset_group');
     assert(node.hasDeferred);
 
@@ -524,23 +576,25 @@ describe('AssetGraph', () => {
     graph.resolveDependency(barUtilsDep, utilsAssetGroup, '4');
 
     // bar undeferres utils
-    graph.unmarkParentsWithHasDeferred(utilsAssetGroupNode);
-    node = nullthrows(graph.getNode(fooUtilsDep.id));
+    graph.unmarkParentsWithHasDeferred(
+      graph.getNodeIdByContentKey(utilsAssetGroupNode.id),
+    );
+    node = nullthrows(graph.getNodeByContentKey(fooUtilsDep.id));
     invariant(node.type === 'dependency');
     assert(!node.hasDeferred);
-    node = nullthrows(graph.getNode(fooAssetNode.id));
+    node = nullthrows(graph.getNodeByContentKey(fooAssetNode.id));
     invariant(node.type === 'asset');
     assert(!node.hasDeferred);
-    node = nullthrows(graph.getNode(fooAssetGroupNode.id));
+    node = nullthrows(graph.getNodeByContentKey(fooAssetGroupNode.id));
     invariant(node.type === 'asset_group');
     assert(!node.hasDeferred);
-    node = nullthrows(graph.getNode(barUtilsDep.id));
+    node = nullthrows(graph.getNodeByContentKey(barUtilsDep.id));
     invariant(node.type === 'dependency');
     assert(!node.hasDeferred);
-    node = nullthrows(graph.getNode(barAssetNode.id));
+    node = nullthrows(graph.getNodeByContentKey(barAssetNode.id));
     invariant(node.type === 'asset');
     assert(!node.hasDeferred);
-    node = nullthrows(graph.getNode(barAssetGroupNode.id));
+    node = nullthrows(graph.getNodeByContentKey(barAssetGroupNode.id));
     invariant(node.type === 'asset_group');
     assert(!node.hasDeferred);
   });
diff --git a/packages/core/core/test/ContentGraph.test.js b/packages/core/core/test/ContentGraph.test.js
new file mode 100644
index 000000000..046500c48
--- /dev/null
+++ b/packages/core/core/test/ContentGraph.test.js
@@ -0,0 +1,48 @@
+// @flow strict-local
+
+import assert from 'assert';
+import ContentGraph from '../src/ContentGraph';
+
+describe('ContentGraph', () => {
+  it('should addNodeByContentKey if no node exists with the content key', () => {
+    let graph = new ContentGraph();
+
+    const node = {id: 'contentKey', type: 'mynode', value: ' 1'};
+
+    const nodeId1 = graph.addNodeByContentKey('contentKey', node);
+
+    assert.deepEqual(graph.getNode(nodeId1), node);
+    assert(graph.hasContentKey('contentKey'));
+    assert.deepEqual(graph.getNodeByContentKey('contentKey'), node);
+  });
+
+  it('should update the node through addNodeByContentKey if a node with the content key exists', () => {
+    let graph = new ContentGraph();
+
+    const node1 = {id: 'contentKey', value: '1', type: 'mynode'};
+    const node2 = {id: 'contentKey', value: '2', type: 'mynode'};
+
+    const nodeId1 = graph.addNodeByContentKey('contentKey', node1);
+    const nodeId2 = graph.addNodeByContentKey('contentKey', node2);
+
+    assert.deepEqual(graph.getNode(nodeId1), node1);
+    assert(graph.hasContentKey('contentKey'));
+
+    assert.equal(nodeId1, nodeId2);
+    assert.deepEqual(graph.getNode(nodeId2), node2);
+  });
+
+  it('should remove the content key from graph when node is removed', () => {
+    let graph = new ContentGraph();
+
+    const node1 = {id: 'contentKey', value: '1', type: 'mynode'};
+    const nodeId1 = graph.addNodeByContentKey('contentKey', node1);
+
+    assert.deepEqual(graph.getNode(nodeId1), node1);
+    assert(graph.hasContentKey('contentKey'));
+
+    graph.removeNode(nodeId1);
+
+    assert(!graph.hasContentKey('contentKey'));
+  });
+});
diff --git a/packages/core/core/test/Graph.test.js b/packages/core/core/test/Graph.test.js
index d149e1d11..179d5baed 100644
--- a/packages/core/core/test/Graph.test.js
+++ b/packages/core/core/test/Graph.test.js
@@ -3,8 +3,8 @@
 import assert from 'assert';
 import sinon from 'sinon';
 
-// flowlint-next-line untyped-import:off
 import Graph from '../src/Graph';
+import {toNodeId} from '../src/types';
 
 describe('Graph', () => {
   it('constructor should initialize an empty graph', () => {
@@ -15,15 +15,15 @@ describe('Graph', () => {
 
   it('addNode should add a node to the graph', () => {
     let graph = new Graph();
-    let node = {id: 'a', type: 'mynode', value: 'a'};
-    graph.addNode(node);
-    assert.equal(graph.nodes.get(node.id), node);
+    let node = {id: 'do not use', type: 'mynode', value: 'a'};
+    let id = graph.addNode(node);
+    assert.equal(graph.nodes.get(id), node);
   });
 
   it("errors when removeNode is called with a node that doesn't belong", () => {
     let graph = new Graph();
     assert.throws(() => {
-      graph.removeNode({id: 'dne', type: 'mynode', value: null});
+      graph.removeNode(toNodeId(-1));
     }, /Does not have node/);
   });
 
@@ -39,62 +39,55 @@ describe('Graph', () => {
     let graph = new Graph();
 
     assert.throws(() => {
-      graph.traverse(() => {}, {id: 'dne', type: 'mynode', value: null});
+      graph.traverse(() => {}, toNodeId(-1));
     }, /Does not have node/);
   });
 
-  it("errors if replaceNodesConnectedTo is called with a node that doesn't belong", () => {
+  it("errors if replaceNodeIdsConnectedTo is called with a node that doesn't belong", () => {
     let graph = new Graph();
     assert.throws(() => {
-      graph.replaceNodesConnectedTo(
-        {id: 'dne', type: 'mynode', value: null},
-        [],
-      );
+      graph.replaceNodeIdsConnectedTo(toNodeId(-1), []);
     }, /Does not have node/);
   });
 
   it("errors when adding an edge to a node that doesn't exist", () => {
     let graph = new Graph();
-    graph.addNode({id: 'foo', type: 'mynode', value: null});
+    let node = graph.addNode({id: 'foo', type: 'mynode', value: null});
     assert.throws(() => {
-      graph.addEdge('foo', 'dne');
-    }, /"to" node 'dne' not found/);
+      graph.addEdge(node, toNodeId(-1));
+    }, /"to" node '-1' not found/);
   });
 
   it("errors when adding an edge from a node that doesn't exist", () => {
     let graph = new Graph();
-    graph.addNode({id: 'foo', type: 'mynode', value: null});
+    let node = graph.addNode({id: 'foo', type: 'mynode', value: null});
     assert.throws(() => {
-      graph.addEdge('dne', 'foo');
-    }, /"from" node 'dne' not found/);
+      graph.addEdge(toNodeId(-1), node);
+    }, /"from" node '-1' not found/);
   });
 
   it('hasNode should return a boolean based on whether the node exists in the graph', () => {
     let graph = new Graph();
-    let node = {id: 'a', type: 'mynode', value: 'a'};
-    graph.addNode(node);
-    assert(graph.hasNode(node.id));
-    assert(!graph.hasNode('b'));
+    let node = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    assert(graph.hasNode(node));
+    assert(!graph.hasNode(toNodeId(-1)));
   });
 
   it('addEdge should add an edge to the graph', () => {
     let graph = new Graph();
-    graph.addNode({id: 'a', type: 'mynode', value: null});
-    graph.addNode({id: 'b', type: 'mynode', value: null});
-    graph.addEdge('a', 'b');
-    assert(graph.hasEdge('a', 'b'));
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: null});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: null});
+    graph.addEdge(nodeA, nodeB);
+    assert(graph.hasEdge(nodeA, nodeB));
   });
 
   it('isOrphanedNode should return true or false if the node is orphaned or not', () => {
     let graph = new Graph();
-    let nodeA = {id: 'a', type: 'mynode', value: 'a'};
-    let nodeB = {id: 'b', type: 'mynode', value: 'b'};
-    let nodeC = {id: 'c', type: 'mynode', value: 'c'};
-    graph.addNode(nodeA);
-    graph.addNode(nodeB);
-    graph.addNode(nodeC);
-    graph.addEdge('a', 'b');
-    graph.addEdge('a', 'c', 'edgetype');
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeA, nodeC, 'edgetype');
     assert(graph.isOrphanedNode(nodeA));
     assert(!graph.isOrphanedNode(nodeB));
     assert(!graph.isOrphanedNode(nodeC));
@@ -107,21 +100,23 @@ describe('Graph', () => {
     //      /
     //     c
     let graph = new Graph();
-    graph.addNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addNode({id: 'd', type: 'mynode', value: 'd'});
-    graph.addEdge('a', 'b');
-    graph.addEdge('a', 'd');
-    graph.addEdge('b', 'c');
-    graph.addEdge('b', 'd');
-
-    graph.removeEdge('a', 'b');
-    assert(graph.nodes.has('a'));
-    assert(graph.nodes.has('d'));
-    assert(!graph.nodes.has('b'));
-    assert(!graph.nodes.has('c'));
-    assert.deepEqual(graph.getAllEdges(), [{from: 'a', to: 'd', type: null}]);
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeA, nodeD);
+    graph.addEdge(nodeB, nodeC);
+    graph.addEdge(nodeB, nodeD);
+
+    graph.removeEdge(nodeA, nodeB);
+    assert(graph.nodes.has(nodeA));
+    assert(graph.nodes.has(nodeD));
+    assert(!graph.nodes.has(nodeB));
+    assert(!graph.nodes.has(nodeC));
+    assert.deepEqual(graph.getAllEdges(), [
+      {from: nodeA, to: nodeD, type: null},
+    ]);
   });
 
   it('removing a node recursively deletes orphaned nodes', () => {
@@ -143,30 +138,27 @@ describe('Graph', () => {
     //          f
 
     let graph = new Graph();
-    graph.addNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addNode({id: 'd', type: 'mynode', value: 'd'});
-    graph.addNode({id: 'e', type: 'mynode', value: 'e'});
-    graph.addNode({id: 'f', type: 'mynode', value: 'f'});
-    graph.addNode({id: 'g', type: 'mynode', value: 'g'});
-
-    graph.addEdge('a', 'b');
-    graph.addEdge('a', 'c');
-    graph.addEdge('b', 'd');
-    graph.addEdge('b', 'e');
-    graph.addEdge('c', 'f');
-    graph.addEdge('d', 'g');
-
-    graph.removeById('b');
-
-    assert.deepEqual(
-      [...graph.nodes.values()].map(node => node.id),
-      ['a', 'c', 'f'],
-    );
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    let nodeE = graph.addNode({id: 'e', type: 'mynode', value: 'e'});
+    let nodeF = graph.addNode({id: 'f', type: 'mynode', value: 'f'});
+    let nodeG = graph.addNode({id: 'g', type: 'mynode', value: 'g'});
+
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeA, nodeC);
+    graph.addEdge(nodeB, nodeD);
+    graph.addEdge(nodeB, nodeE);
+    graph.addEdge(nodeC, nodeF);
+    graph.addEdge(nodeD, nodeG);
+
+    graph.removeNode(nodeB);
+
+    assert.deepEqual([...graph.nodes.keys()], [nodeA, nodeC, nodeF]);
     assert.deepEqual(graph.getAllEdges(), [
-      {from: 'a', to: 'c', type: null},
-      {from: 'c', to: 'f', type: null},
+      {from: nodeA, to: nodeC, type: null},
+      {from: nodeC, to: nodeF, type: null},
     ]);
   });
 
@@ -189,31 +181,29 @@ describe('Graph', () => {
     //          f
 
     let graph = new Graph();
-    graph.setRootNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addNode({id: 'd', type: 'mynode', value: 'd'});
-    graph.addNode({id: 'e', type: 'mynode', value: 'e'});
-    graph.addNode({id: 'f', type: 'mynode', value: 'f'});
-    graph.addNode({id: 'g', type: 'mynode', value: 'g'});
-
-    graph.addEdge('a', 'b');
-    graph.addEdge('a', 'c');
-    graph.addEdge('b', 'd');
-    graph.addEdge('g', 'd');
-    graph.addEdge('b', 'e');
-    graph.addEdge('c', 'f');
-    graph.addEdge('d', 'g');
-
-    graph.removeById('b');
-
-    assert.deepEqual(
-      [...graph.nodes.values()].map(node => node.id),
-      ['a', 'c', 'f'],
-    );
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    let nodeE = graph.addNode({id: 'e', type: 'mynode', value: 'e'});
+    let nodeF = graph.addNode({id: 'f', type: 'mynode', value: 'f'});
+    let nodeG = graph.addNode({id: 'g', type: 'mynode', value: 'g'});
+    graph.setRootNodeId(nodeA);
+
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeA, nodeC);
+    graph.addEdge(nodeB, nodeD);
+    graph.addEdge(nodeG, nodeD);
+    graph.addEdge(nodeB, nodeE);
+    graph.addEdge(nodeC, nodeF);
+    graph.addEdge(nodeD, nodeG);
+
+    graph.removeNode(nodeB);
+
+    assert.deepEqual([...graph.nodes.keys()], [nodeA, nodeC, nodeF]);
     assert.deepEqual(graph.getAllEdges(), [
-      {from: 'a', to: 'c', type: null},
-      {from: 'c', to: 'f', type: null},
+      {from: nodeA, to: nodeC, type: null},
+      {from: nodeC, to: nodeF, type: null},
     ]);
   });
 
@@ -226,94 +216,98 @@ describe('Graph', () => {
     //       \ /    |
     //        e -----
     let graph = new Graph();
-    graph.setRootNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addNode({id: 'd', type: 'mynode', value: 'd'});
-    graph.addNode({id: 'e', type: 'mynode', value: 'e'});
-
-    graph.addEdge('a', 'b');
-    graph.addEdge('b', 'c');
-    graph.addEdge('b', 'd');
-    graph.addEdge('c', 'e');
-    graph.addEdge('d', 'e');
-    graph.addEdge('e', 'b');
-
-    const getNodeIds = () => [...graph.nodes.values()].map(node => node.id);
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    let nodeE = graph.addNode({id: 'e', type: 'mynode', value: 'e'});
+    graph.setRootNodeId(nodeA);
+
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeB, nodeC);
+    graph.addEdge(nodeB, nodeD);
+    graph.addEdge(nodeC, nodeE);
+    graph.addEdge(nodeD, nodeE);
+    graph.addEdge(nodeE, nodeB);
+
+    const getNodeIds = () => [...graph.nodes.keys()];
     let nodesBefore = getNodeIds();
 
-    graph.removeEdge('c', 'e');
+    graph.removeEdge(nodeC, nodeE);
 
     assert.deepEqual(nodesBefore, getNodeIds());
     assert.deepEqual(graph.getAllEdges(), [
-      {from: 'a', to: 'b', type: null},
-      {from: 'b', to: 'c', type: null},
-      {from: 'b', to: 'd', type: null},
-      {from: 'd', to: 'e', type: null},
-      {from: 'e', to: 'b', type: null},
+      {from: nodeA, to: nodeB, type: null},
+      {from: nodeB, to: nodeC, type: null},
+      {from: nodeB, to: nodeD, type: null},
+      {from: nodeD, to: nodeE, type: null},
+      {from: nodeE, to: nodeB, type: null},
     ]);
   });
 
   it('removing a node with only one inbound edge does not cause it to be removed as an orphan', () => {
     let graph = new Graph();
 
-    graph.setRootNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addEdge('a', 'b');
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    graph.setRootNodeId(nodeA);
+
+    graph.addEdge(nodeA, nodeB);
 
     let spy = sinon.spy(graph, 'removeNode');
     try {
-      graph.removeById('b');
+      graph.removeNode(nodeB);
 
-      assert(spy.calledOnceWithExactly({id: 'b', type: 'mynode', value: 'b'}));
+      assert(spy.calledOnceWithExactly(nodeB));
     } finally {
       spy.restore();
     }
   });
 
-  it("replaceNodesConnectedTo should update a node's downstream nodes", () => {
+  it("replaceNodeIdsConnectedTo should update a node's downstream nodes", () => {
     let graph = new Graph();
     let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
     let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addEdge('a', 'b');
-    graph.addEdge('a', 'c');
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    graph.addEdge(nodeA, nodeB);
+    graph.addEdge(nodeA, nodeC);
 
-    let nodeD = {id: 'd', type: 'mynode', value: 'd'};
-    graph.replaceNodesConnectedTo(nodeA, [nodeB, nodeD]);
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    graph.replaceNodeIdsConnectedTo(nodeA, [nodeB, nodeD]);
 
-    assert(graph.nodes.has('a'));
-    assert(graph.nodes.has('b'));
-    assert(!graph.nodes.has('c'));
-    assert(graph.nodes.has('d'));
+    assert(graph.hasNode(nodeA));
+    assert(graph.hasNode(nodeB));
+    assert(!graph.hasNode(nodeC));
+    assert(graph.hasNode(nodeD));
     assert.deepEqual(graph.getAllEdges(), [
-      {from: 'a', to: 'b', type: null},
-      {from: 'a', to: 'd', type: null},
+      {from: nodeA, to: nodeB, type: null},
+      {from: nodeA, to: nodeD, type: null},
     ]);
   });
 
   it('traverses along edge types if a filter is given', () => {
     let graph = new Graph();
-    graph.addNode({id: 'a', type: 'mynode', value: 'a'});
-    graph.addNode({id: 'b', type: 'mynode', value: 'b'});
-    graph.addNode({id: 'c', type: 'mynode', value: 'c'});
-    graph.addNode({id: 'd', type: 'mynode', value: 'd'});
+    let nodeA = graph.addNode({id: 'a', type: 'mynode', value: 'a'});
+    let nodeB = graph.addNode({id: 'b', type: 'mynode', value: 'b'});
+    let nodeC = graph.addNode({id: 'c', type: 'mynode', value: 'c'});
+    let nodeD = graph.addNode({id: 'd', type: 'mynode', value: 'd'});
 
-    graph.addEdge('a', 'b', 'edgetype');
-    graph.addEdge('a', 'd');
-    graph.addEdge('b', 'c');
-    graph.addEdge('b', 'd', 'edgetype');
+    graph.addEdge(nodeA, nodeB, 'edgetype');
+    graph.addEdge(nodeA, nodeD);
+    graph.addEdge(nodeB, nodeC);
+    graph.addEdge(nodeB, nodeD, 'edgetype');
 
-    graph.rootNodeId = 'a';
+    graph.setRootNodeId(nodeA);
 
     let visited = [];
     graph.traverse(
-      node => {
-        visited.push(node.id);
+      nodeId => {
+        visited.push(nodeId);
       },
       null, // use root as startNode
       'edgetype',
     );
-    assert.deepEqual(visited, ['a', 'b', 'd']);
+
+    assert.deepEqual(visited, [nodeA, nodeB, nodeD]);
   });
 });
diff --git a/packages/core/core/test/Parcel.test.js b/packages/core/core/test/Parcel.test.js
index 69ed2fe12..60f1be5b7 100644
--- a/packages/core/core/test/Parcel.test.js
+++ b/packages/core/core/test/Parcel.test.js
@@ -9,7 +9,7 @@ import path from 'path';
 import Parcel, {createWorkerFarm} from '../src/Parcel';
 
 describe('Parcel', function() {
-  this.timeout(60000);
+  this.timeout(75000);
 
   let workerFarm;
   before(() => {
diff --git a/packages/core/core/test/PublicBundle.test.js b/packages/core/core/test/PublicBundle.test.js
index 9b153edc0..15d9fbc42 100644
--- a/packages/core/core/test/PublicBundle.test.js
+++ b/packages/core/core/test/PublicBundle.test.js
@@ -5,7 +5,7 @@ import {Bundle, NamedBundle, PackagedBundle} from '../src/public/Bundle';
 import BundleGraph from '../src/BundleGraph';
 import {createEnvironment} from '../src/Environment';
 import {DEFAULT_OPTIONS} from './test-utils';
-import Graph from '../src/Graph';
+import ContentGraph from '../src/ContentGraph';
 
 describe('Public Bundle', () => {
   let internalBundle;
@@ -37,7 +37,7 @@ describe('Public Bundle', () => {
     };
 
     bundleGraph = new BundleGraph({
-      graph: new Graph(),
+      graph: new ContentGraph(),
       assetPublicIds: new Set(),
       publicIdByAssetId: new Map(),
       bundleContentHashes: new Map(),
diff --git a/packages/core/core/test/RequestTracker.test.js b/packages/core/core/test/RequestTracker.test.js
index ee55b18a3..9ae15d494 100644
--- a/packages/core/core/test/RequestTracker.test.js
+++ b/packages/core/core/test/RequestTracker.test.js
@@ -39,8 +39,10 @@ describe('RequestTracker', () => {
       run: () => {},
       input: null,
     });
-    let node = nullthrows(tracker.graph.getNode('abc'));
-    tracker.graph.invalidateNode(node, INITIAL_BUILD);
+    tracker.graph.invalidateNode(
+      tracker.graph.getNodeIdByContentKey('abc'),
+      INITIAL_BUILD,
+    );
     let called = false;
     await tracker.runRequest({
       id: 'abc',
@@ -68,8 +70,10 @@ describe('RequestTracker', () => {
       },
       input: null,
     });
-    let node = nullthrows(tracker.graph.getNode('xyz'));
-    tracker.graph.invalidateNode(node, INITIAL_BUILD);
+    tracker.graph.invalidateNode(
+      tracker.graph.getNodeIdByContentKey('xyz'),
+      INITIAL_BUILD,
+    );
     assert(
       tracker
         .getInvalidRequests()
@@ -116,8 +120,8 @@ describe('RequestTracker', () => {
       },
       input: null,
     });
-    let node = nullthrows(tracker.graph.getNode('abc'));
-    tracker.graph.invalidateNode(node, INITIAL_BUILD);
+    let nodeId = nullthrows(tracker.graph.getNodeIdByContentKey('abc'));
+    tracker.graph.invalidateNode(nodeId, INITIAL_BUILD);
     await tracker.runRequest({
       id: 'abc',
       type: 'mock_request',
@@ -131,7 +135,7 @@ describe('RequestTracker', () => {
       },
       input: null,
     });
-    assert(!tracker.graph.hasNode('xyz'));
+    assert(!tracker.graph.hasContentKey('xyz'));
   });
 
   it('should return a cached result if it was stored', async () => {