pdf-caching.js 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990
  1. import OError from '@overleaf/o-error'
  2. const PDF_JS_CHUNK_SIZE = 128 * 1024
  3. const MAX_SUB_REQUEST_COUNT = 4
  4. const MAX_SUB_REQUEST_BYTES = 4 * PDF_JS_CHUNK_SIZE
  5. const SAMPLE_NGINX_BOUNDARY = '00000000000000000001'
  6. const HEADER_OVERHEAD_PER_MULTI_PART_CHUNK = composeMultipartHeader({
  7. boundary: SAMPLE_NGINX_BOUNDARY,
  8. // Assume an upper bound of O(9GB) for the pdf size.
  9. start: 9 * 1024 * 1024 * 1024,
  10. end: 9 * 1024 * 1024 * 1024,
  11. size: 9 * 1024 * 1024 * 1024,
  12. })
  13. const MULTI_PART_THRESHOLD = 4
  14. const INCREMENTAL_CACHE_SIZE = 1000
  15. // Download large chunks once the shard bandwidth exceeds 50% of their size.
  16. const CHUNK_USAGE_THRESHOLD_PREFETCH_LARGE = 0.5
  17. // Preferred caching once we downloaded a chunk (in multiple shards) in full.
  18. const CHUNK_USAGE_THRESHOLD_TRIGGER_PREFERRED = 1
  19. const CHUNK_USAGE_THRESHOLD_CACHED = 42
  20. // 42 * 0.7^11 < 1, aka we keep stale entries around for 11 compiles.
  21. const CHUNK_USAGE_STALE_DECAY_RATE = 0.7
  22. /**
  23. * @param {Object} file
  24. */
  25. function backfillEdgeBounds(file) {
  26. const encoder = new TextEncoder()
  27. for (const chunk of file.ranges) {
  28. if (chunk.objectId) {
  29. chunk.objectId = encoder.encode(chunk.objectId)
  30. chunk.start -= chunk.objectId.byteLength
  31. chunk.size = chunk.end - chunk.start
  32. }
  33. }
  34. }
  35. /**
  36. * @param {Map} usageScore
  37. * @param {Map} cachedUrls
  38. */
  39. function trimState({ usageScore, cachedUrls }) {
  40. for (const hash of usageScore) {
  41. if (usageScore.size < INCREMENTAL_CACHE_SIZE) {
  42. break
  43. }
  44. const score = usageScore.get(hash)
  45. if (score >= CHUNK_USAGE_THRESHOLD_TRIGGER_PREFERRED) {
  46. // Keep entries that are worth caching around for longer.
  47. usageScore.set(hash, score * CHUNK_USAGE_STALE_DECAY_RATE)
  48. continue
  49. }
  50. cachedUrls.delete(hash)
  51. usageScore.delete(hash)
  52. }
  53. }
  54. /**
  55. * @param {Object} file
  56. * @param {Map} usageScore
  57. * @param {Map} cachedUrls
  58. */
  59. function preprocessFileOnce({ file, usageScore, cachedUrls }) {
  60. if (file.preprocessed) return
  61. file.preprocessed = true
  62. file.createdAt = new Date(file.createdAt)
  63. file.prefetched = file.prefetched || []
  64. trimState({ usageScore, cachedUrls })
  65. backfillEdgeBounds(file)
  66. }
  67. /**
  68. * @param {Array} chunks
  69. */
  70. function estimateSizeOfMultipartResponse(chunks) {
  71. /*
  72. --boundary
  73. HEADER
  74. BLOB
  75. --boundary
  76. HEADER
  77. BLOB
  78. --boundary--
  79. */
  80. return (
  81. chunks.reduce(
  82. (totalBytes, chunk) =>
  83. totalBytes +
  84. HEADER_OVERHEAD_PER_MULTI_PART_CHUNK +
  85. (chunk.end - chunk.start)
  86. ) + ('\r\n' + SAMPLE_NGINX_BOUNDARY + '--').length
  87. )
  88. }
  89. /**
  90. *
  91. * @param {Object} metrics
  92. * @param {number} size
  93. * @param {number} cachedCount
  94. * @param {number} cachedBytes
  95. * @param {number} fetchedCount
  96. * @param {number} fetchedBytes
  97. */
  98. function trackDownloadStats(
  99. metrics,
  100. { size, cachedCount, cachedBytes, fetchedCount, fetchedBytes }
  101. ) {
  102. metrics.cachedCount += cachedCount
  103. metrics.cachedBytes += cachedBytes
  104. metrics.fetchedCount += fetchedCount
  105. metrics.fetchedBytes += fetchedBytes
  106. metrics.requestedCount++
  107. metrics.requestedBytes += size
  108. }
  109. /**
  110. * @param {Object} metrics
  111. * @param {boolean} sizeDiffers
  112. * @param {boolean} mismatch
  113. * @param {boolean} success
  114. */
  115. function trackChunkVerify(metrics, { sizeDiffers, mismatch, success }) {
  116. if (sizeDiffers) {
  117. metrics.chunkVerifySizeDiffers |= 0
  118. metrics.chunkVerifySizeDiffers += 1
  119. }
  120. if (mismatch) {
  121. metrics.chunkVerifyMismatch |= 0
  122. metrics.chunkVerifyMismatch += 1
  123. }
  124. if (success) {
  125. metrics.chunkVerifySuccess |= 0
  126. metrics.chunkVerifySuccess += 1
  127. }
  128. }
  129. /**
  130. * @param chunk
  131. * @param {ArrayBuffer} arrayBuffer
  132. * @return {Uint8Array}
  133. */
  134. function backFillObjectContext(chunk, arrayBuffer) {
  135. if (!chunk.objectId) {
  136. // This is a dynamic chunk
  137. return new Uint8Array(arrayBuffer)
  138. }
  139. const { size, objectId } = chunk
  140. const fullBuffer = new Uint8Array(size)
  141. const sourceBuffer = new Uint8Array(arrayBuffer)
  142. try {
  143. fullBuffer.set(objectId, 0)
  144. fullBuffer.set(sourceBuffer, objectId.byteLength)
  145. } catch (err) {
  146. throw OError.tag(err, 'broken back-filling of object-id', {
  147. objectIdByteLength: objectId.byteLength,
  148. fullBufferByteLength: fullBuffer.byteLength,
  149. arrayBufferByteLength: arrayBuffer.byteLength,
  150. sourceBufferByteLength: sourceBuffer.byteLength,
  151. })
  152. }
  153. return fullBuffer
  154. }
  155. /**
  156. * @param {Array} chunks
  157. * @param {number} start
  158. * @param {number} end
  159. * @returns {Array}
  160. */
  161. function getMatchingChunks(chunks, start, end) {
  162. const matchingChunks = []
  163. for (const chunk of chunks) {
  164. if (chunk.end <= start) {
  165. // no overlap:
  166. // | REQUESTED_RANGE |
  167. // | CHUNK |
  168. continue
  169. }
  170. if (chunk.start >= end) {
  171. // no overlap:
  172. // | REQUESTED_RANGE |
  173. // | CHUNK |
  174. break
  175. }
  176. matchingChunks.push(chunk)
  177. }
  178. return matchingChunks
  179. }
  180. /**
  181. * @param {Object} a
  182. * @param {Object} b
  183. */
  184. function sortBySizeDESC(a, b) {
  185. return a.size > b.size ? -1 : 1
  186. }
  187. /**
  188. * @param {Object} a
  189. * @param {Object} b
  190. */
  191. function sortByStartASC(a, b) {
  192. return a.start > b.start ? 1 : -1
  193. }
  194. /**
  195. * @param {Object} chunk
  196. */
  197. function usageAboveThreshold(chunk) {
  198. // We fetched enough shards of this chunk. Cache it in full now.
  199. return chunk.totalUsage > CHUNK_USAGE_THRESHOLD_TRIGGER_PREFERRED
  200. }
  201. /**
  202. * @param {Array} potentialChunks
  203. * @param {Map} usageScore
  204. * @param {Map} cachedUrls
  205. * @param {Object} metrics
  206. * @param {number} start
  207. * @param {number} end
  208. * @param {boolean} prefetchLargeEnabled
  209. */
  210. function cutRequestAmplification({
  211. potentialChunks,
  212. usageScore,
  213. cachedUrls,
  214. metrics,
  215. start,
  216. end,
  217. prefetchLargeEnabled,
  218. }) {
  219. // NOTE: Map keys are stored in insertion order.
  220. // We re-insert keys on cache hit and turn 'usageScore' into a cheap LRU.
  221. const chunks = []
  222. const skipAlreadyAdded = chunk => !chunks.includes(chunk)
  223. let tooManyRequests = false
  224. let tooMuchBandwidth = false
  225. let newChunks = 0
  226. let newCacheBandwidth = 0
  227. for (const chunk of potentialChunks) {
  228. const newUsage =
  229. (Math.min(end, chunk.end) - Math.max(start, chunk.start)) / chunk.size
  230. const totalUsage = (usageScore.get(chunk.hash) || 0) + newUsage
  231. usageScore.delete(chunk.hash)
  232. usageScore.set(chunk.hash, totalUsage)
  233. chunk.totalUsage = totalUsage
  234. }
  235. // Always download already cached entries
  236. for (const chunk of potentialChunks) {
  237. if (chunk.totalUsage >= CHUNK_USAGE_THRESHOLD_CACHED) {
  238. chunks.push(chunk)
  239. }
  240. }
  241. // Prefer large blobs over small ones.
  242. potentialChunks.sort(sortBySizeDESC)
  243. // Prefer chunks with high (previous) usage over brand-new chunks.
  244. const firstComeFirstCache = () => true
  245. for (const trigger of [usageAboveThreshold, firstComeFirstCache]) {
  246. for (const chunk of potentialChunks.filter(skipAlreadyAdded)) {
  247. if (newCacheBandwidth + chunk.size > MAX_SUB_REQUEST_BYTES) {
  248. // We would breach the bandwidth amplification limit.
  249. tooMuchBandwidth = true
  250. continue
  251. }
  252. if (newChunks + 1 > MAX_SUB_REQUEST_COUNT) {
  253. // We would breach the request rate amplification limit.
  254. tooManyRequests = true
  255. continue
  256. }
  257. if (trigger(chunk)) {
  258. newCacheBandwidth += chunk.size
  259. newChunks += 1
  260. chunks.push(chunk)
  261. }
  262. }
  263. }
  264. const largeChunk = potentialChunks.filter(skipAlreadyAdded)[0]
  265. if (largeChunk?.size >= PDF_JS_CHUNK_SIZE) {
  266. // This is a large chunk that exceeds the bandwidth amplification limit.
  267. if (largeChunk.start <= start && largeChunk.end >= end) {
  268. // This is a large chunk spanning the entire range. pdf.js will only
  269. // request these in case it needs the underlying stream, so it is OK to
  270. // download as much data as the stream is large in one go.
  271. chunks.push(largeChunk)
  272. } else if (
  273. prefetchLargeEnabled &&
  274. largeChunk.totalUsage > CHUNK_USAGE_THRESHOLD_PREFETCH_LARGE
  275. ) {
  276. // pdf.js actually wants the smaller (dynamic) chunk in the range that
  277. // happens to sit right next to this large chunk.
  278. // pdf.js has requested a lot of the large chunk via shards by now, and it
  279. // is time to download it in full to stop "wasting" more bandwidth and
  280. // more importantly cut down latency as we can prefetch the small chunk.
  281. chunks.push(largeChunk)
  282. }
  283. }
  284. if (tooManyRequests) {
  285. metrics.tooManyRequestsCount++
  286. }
  287. if (tooMuchBandwidth) {
  288. metrics.tooMuchBandwidthCount++
  289. }
  290. chunks.sort(sortByStartASC)
  291. return chunks
  292. }
  293. /**
  294. * @param {Array} chunks
  295. * @param {number} start
  296. * @param {number} end
  297. * @returns {Array}
  298. */
  299. function getInterleavingDynamicChunks(chunks, start, end) {
  300. const dynamicChunks = []
  301. for (const chunk of chunks) {
  302. if (start < chunk.start) {
  303. dynamicChunks.push({ start, end: chunk.start })
  304. }
  305. start = chunk.end
  306. }
  307. if (start < end) {
  308. dynamicChunks.push({ start, end })
  309. }
  310. return dynamicChunks
  311. }
  312. /**
  313. *
  314. * @param {Response} response
  315. */
  316. function getServerTime(response) {
  317. const raw = response.headers.get('Date')
  318. if (!raw) return new Date()
  319. return new Date(raw)
  320. }
  321. /**
  322. *
  323. * @param {Response} response
  324. */
  325. function getResponseSize(response) {
  326. const raw = response.headers.get('Content-Length')
  327. if (!raw) return 0
  328. return parseInt(raw, 10)
  329. }
  330. /**
  331. *
  332. * @param {Response} response
  333. * @param chunk
  334. */
  335. function getMultipartBoundary(response, chunk) {
  336. if (!Array.isArray(chunk)) return ''
  337. const raw = response.headers.get('Content-Type')
  338. if (raw.includes('multipart/byteranges')) {
  339. const idx = raw.indexOf('boundary=')
  340. if (idx !== -1) return raw.slice(idx + 'boundary='.length)
  341. }
  342. throw new OError('missing boundary on multipart request', {
  343. headers: Object.fromEntries(response.headers.entries()),
  344. chunk,
  345. })
  346. }
  347. /**
  348. * @param {string} boundary
  349. * @param {number} start
  350. * @param {number} end
  351. * @param {number} size
  352. * @return {string}
  353. */
  354. function composeMultipartHeader({ boundary, start, end, size }) {
  355. return `\r\n--${boundary}\r\nContent-Type: application/pdf\r\nContent-Range: bytes ${start}-${
  356. end - 1
  357. }/${size}\r\n\r\n`
  358. }
  359. /**
  360. * @param {Object} file
  361. * @param {Array} chunks
  362. * @param {Uint8Array} data
  363. * @param {string} boundary
  364. * @param {Object} metrics
  365. */
  366. function resolveMultiPartResponses({ file, chunks, data, boundary, metrics }) {
  367. const responses = []
  368. let offsetStart = 0
  369. const encoder = new TextEncoder()
  370. for (const chunk of chunks) {
  371. const header = composeMultipartHeader({
  372. boundary,
  373. start: chunk.start,
  374. end: chunk.end,
  375. size: file.size,
  376. })
  377. const headerSize = header.length
  378. // Verify header content. A proxy might have tampered with it.
  379. const headerRaw = encoder.encode(header)
  380. if (
  381. !data
  382. .subarray(offsetStart, offsetStart + headerSize)
  383. .every((v, idx) => v === headerRaw[idx])
  384. ) {
  385. metrics.headerVerifyFailure |= 0
  386. metrics.headerVerifyFailure++
  387. throw new OError('multipart response header does not match', {
  388. actual: new TextDecoder().decode(
  389. data.subarray(offsetStart, offsetStart + headerSize)
  390. ),
  391. expected: header,
  392. })
  393. }
  394. offsetStart += headerSize
  395. const chunkSize = chunk.end - chunk.start
  396. responses.push({
  397. chunk,
  398. data: data.subarray(offsetStart, offsetStart + chunkSize),
  399. })
  400. offsetStart += chunkSize
  401. }
  402. return responses
  403. }
  404. /**
  405. *
  406. * @param {Response} response
  407. * @param {number} estimatedSize
  408. * @param {RequestInit} init
  409. */
  410. function checkChunkResponse(response, estimatedSize, init) {
  411. if (!(response.status === 206 || response.status === 200)) {
  412. throw new OError('non successful response status: ' + response.status, {
  413. responseHeaders: Object.fromEntries(response.headers.entries()),
  414. requestHeader: init.headers,
  415. })
  416. }
  417. const responseSize = getResponseSize(response)
  418. if (!responseSize) {
  419. throw new OError('content-length response header missing', {
  420. responseHeaders: Object.fromEntries(response.headers.entries()),
  421. requestHeader: init.headers,
  422. })
  423. }
  424. if (responseSize > estimatedSize) {
  425. throw new OError('response size exceeds estimate', {
  426. estimatedSize,
  427. responseSize,
  428. responseHeaders: Object.fromEntries(response.headers.entries()),
  429. requestHeader: init.headers,
  430. })
  431. }
  432. }
  433. /**
  434. *
  435. * @param {string} url
  436. * @param {number} start
  437. * @param {number} end
  438. * @param {AbortSignal} abortSignal
  439. */
  440. export async function fallbackRequest({ url, start, end, abortSignal }) {
  441. try {
  442. const init = {
  443. headers: { Range: `bytes=${start}-${end - 1}` },
  444. signal: abortSignal,
  445. }
  446. const response = await fetch(url, init)
  447. checkChunkResponse(response, end - start, init)
  448. return await response.arrayBuffer()
  449. } catch (e) {
  450. throw OError.tag(e, 'fallback request failed', { url, start, end })
  451. }
  452. }
  453. /**
  454. *
  455. * @param {string} url
  456. * @param {number} start
  457. * @param {number} end
  458. * @param {Object} metrics
  459. * @param {Uint8Array} actual
  460. * @param {AbortSignal} abortSignal
  461. */
  462. async function verifyRange({ url, start, end, metrics, actual, abortSignal }) {
  463. let expectedRaw
  464. try {
  465. expectedRaw = await fallbackRequest({ url, start, end, abortSignal })
  466. } catch (error) {
  467. throw OError.tag(error, 'cannot verify range', { url, start, end })
  468. }
  469. const expected = new Uint8Array(expectedRaw)
  470. const stats = {}
  471. if (actual.byteLength !== expected.byteLength) {
  472. stats.sizeDiffers = true
  473. } else if (!expected.every((v, idx) => v === actual[idx])) {
  474. stats.mismatch = true
  475. } else {
  476. stats.success = true
  477. }
  478. trackChunkVerify(metrics, stats)
  479. return expected
  480. }
  481. /**
  482. * @param {Array} chunks
  483. * @param {Array} prefetched
  484. * @param {number} start
  485. * @param {number} end
  486. */
  487. function skipPrefetched(chunks, prefetched, start, end) {
  488. return chunks.filter(chunk => {
  489. return !prefetched.find(
  490. c =>
  491. c.start <= Math.max(chunk.start, start) &&
  492. c.end >= Math.min(chunk.end, end)
  493. )
  494. })
  495. }
  496. /**
  497. * @param {Object|Object[]} chunk
  498. * @param {string} url
  499. * @param {RequestInit} init
  500. * @param {Map<string, string>} cachedUrls
  501. * @param {Object} metrics
  502. * @param {boolean} cachedUrlLookupEnabled
  503. */
  504. async function fetchChunk({
  505. chunk,
  506. url,
  507. init,
  508. cachedUrls,
  509. metrics,
  510. cachedUrlLookupEnabled,
  511. }) {
  512. const estimatedSize = Array.isArray(chunk)
  513. ? estimateSizeOfMultipartResponse(chunk)
  514. : chunk.end - chunk.start
  515. const oldUrl = cachedUrls.get(chunk.hash)
  516. if (cachedUrlLookupEnabled && chunk.hash && oldUrl && oldUrl !== url) {
  517. // When the clsi server id changes, the content id changes too and as a
  518. // result all the browser cache keys (aka urls) get invalidated.
  519. // We memorize the previous browser cache keys in `cachedUrls`.
  520. try {
  521. const response = await fetch(oldUrl, init)
  522. if (response.status === 200) {
  523. checkChunkResponse(response, estimatedSize, init)
  524. metrics.oldUrlHitCount += 1
  525. return response
  526. }
  527. if (response.status === 404) {
  528. // The old browser cache entry is gone and the old file is gone too.
  529. metrics.oldUrlMissCount += 1
  530. }
  531. // Fallback to the latest url.
  532. } catch (e) {
  533. // Fallback to the latest url.
  534. }
  535. }
  536. const response = await fetch(url, init)
  537. checkChunkResponse(response, estimatedSize, init)
  538. if (chunk.hash) cachedUrls.set(chunk.hash, url)
  539. return response
  540. }
  541. /**
  542. * @param {Object} file
  543. * @param {number} start
  544. * @param {number} end
  545. * @param {Array} dynamicChunks
  546. * @param {boolean} prefetchXRefTable
  547. * @param {number} startXRefTableRange
  548. */
  549. function addPrefetchingChunks({
  550. file,
  551. start,
  552. end,
  553. dynamicChunks,
  554. prefetchXRefTable,
  555. startXRefTableRange,
  556. }) {
  557. // Prefetch in case this is the first range, or we are fetching dynamic
  558. // chunks anyway (so we can ride-share the round trip).
  559. // Rendering cannot start without downloading the xref table, so it's OK to
  560. // "delay" the first range.
  561. if (!(start === 0 || dynamicChunks.length > 0)) {
  562. return
  563. }
  564. let extraChunks = []
  565. if (prefetchXRefTable) {
  566. // Prefetch the dynamic chunks around the xref table.
  567. extraChunks = skipPrefetched(
  568. getInterleavingDynamicChunks(
  569. getMatchingChunks(file.ranges, startXRefTableRange, file.size),
  570. startXRefTableRange,
  571. file.size
  572. ),
  573. file.prefetched,
  574. startXRefTableRange,
  575. file.size
  576. )
  577. }
  578. // Stop at the xref table range if present -- we may prefetch it early ^^^.
  579. const prefetchEnd = startXRefTableRange || file.size
  580. extraChunks = extraChunks.concat(
  581. skipPrefetched(
  582. getInterleavingDynamicChunks(
  583. getMatchingChunks(file.ranges, end, prefetchEnd),
  584. end,
  585. prefetchEnd
  586. ),
  587. file.prefetched,
  588. end,
  589. prefetchEnd
  590. )
  591. )
  592. let sum = estimateSizeOfMultipartResponse(dynamicChunks)
  593. for (const chunk of extraChunks) {
  594. const downloadSize =
  595. chunk.end - chunk.start + HEADER_OVERHEAD_PER_MULTI_PART_CHUNK
  596. if (sum + downloadSize > PDF_JS_CHUNK_SIZE) {
  597. // In prefetching this chunk we would exceed the bandwidth limit.
  598. // Try to prefetch another (smaller) chunk.
  599. continue
  600. }
  601. const sibling = dynamicChunks.find(
  602. sibling => sibling.end === chunk.start || sibling.start === chunk.end
  603. )
  604. if (sibling) {
  605. sum += downloadSize
  606. // Just expand the existing dynamic chunk.
  607. sibling.start = Math.min(sibling.start, chunk.start)
  608. sibling.end = Math.max(sibling.end, chunk.end)
  609. continue
  610. }
  611. if (dynamicChunks.length > MULTI_PART_THRESHOLD) {
  612. // We are already performing a multipart request. Add another part.
  613. } else if (dynamicChunks.length < MULTI_PART_THRESHOLD) {
  614. // We are not yet performing a multipart request. Add another request.
  615. } else {
  616. // In prefetching this chunk we would switch to a multipart request.
  617. // Try to prefetch another (smaller) chunk.
  618. continue
  619. }
  620. sum += downloadSize
  621. dynamicChunks.push(chunk)
  622. }
  623. dynamicChunks.sort(sortByStartASC)
  624. // Ensure that no chunks are overlapping.
  625. let lastEnd = 0
  626. for (const [idx, chunk] of dynamicChunks.entries()) {
  627. if (chunk.start < lastEnd) {
  628. throw new OError('detected overlapping dynamic chunks', {
  629. chunk,
  630. lastChunk: dynamicChunks[idx - 1],
  631. })
  632. }
  633. lastEnd = chunk.end
  634. }
  635. }
  636. class Timer {
  637. constructor() {
  638. this.max = 0
  639. this.total = 0
  640. this.lastStart = 0
  641. }
  642. startBlockingCompute() {
  643. this.lastStart = performance.now()
  644. }
  645. finishBlockingCompute() {
  646. if (this.lastStart === 0) return
  647. const last = performance.now() - this.lastStart
  648. if (last > this.max) {
  649. this.max = last
  650. }
  651. this.total += last
  652. this.lastStart = 0
  653. }
  654. reportInto(metrics) {
  655. const max = Math.ceil(this.max)
  656. const total = Math.ceil(this.total)
  657. if (max > metrics.latencyComputeMax) {
  658. metrics.latencyComputeMax = max
  659. }
  660. metrics.latencyComputeTotal += total
  661. }
  662. }
  663. /**
  664. *
  665. * @param {string} url
  666. * @param {number} start
  667. * @param {number} end
  668. * @param {Object} file
  669. * @param {Object} metrics
  670. * @param {Map} usageScore
  671. * @param {Map} cachedUrls
  672. * @param {boolean} verifyChunks
  673. * @param {boolean} prefetchingEnabled
  674. * @param {boolean} prefetchLargeEnabled
  675. * @param {boolean} tryOldCachedUrlEnabled
  676. * @param {AbortSignal} abortSignal
  677. */
  678. export async function fetchRange({
  679. url,
  680. start,
  681. end,
  682. file,
  683. metrics,
  684. usageScore,
  685. cachedUrls,
  686. verifyChunks,
  687. prefetchingEnabled,
  688. prefetchLargeEnabled,
  689. cachedUrlLookupEnabled,
  690. abortSignal,
  691. }) {
  692. const timer = new Timer()
  693. timer.startBlockingCompute()
  694. preprocessFileOnce({ file, usageScore, cachedUrls })
  695. const startXRefTableRange =
  696. Math.floor(file.startXRefTable / PDF_JS_CHUNK_SIZE) * PDF_JS_CHUNK_SIZE
  697. const prefetchXRefTable =
  698. prefetchingEnabled && startXRefTableRange > 0 && start === 0
  699. const prefetched = getMatchingChunks(file.prefetched, start, end)
  700. // Check that handling the range request won't trigger excessive sub-requests,
  701. // (to avoid unwanted latency compared to the original request).
  702. const chunks = cutRequestAmplification({
  703. potentialChunks: skipPrefetched(
  704. getMatchingChunks(file.ranges, start, end),
  705. prefetched,
  706. start,
  707. end
  708. ),
  709. usageScore,
  710. cachedUrls,
  711. metrics,
  712. start,
  713. end,
  714. prefetchLargeEnabled,
  715. })
  716. const dynamicChunks = skipPrefetched(
  717. getInterleavingDynamicChunks(chunks, start, end),
  718. prefetched,
  719. start,
  720. end
  721. )
  722. const size = end - start
  723. if (
  724. chunks.length === 0 &&
  725. prefetched.length === 0 &&
  726. dynamicChunks.length === 1 &&
  727. !prefetchXRefTable
  728. ) {
  729. // fall back to the original range request when no chunks are cached.
  730. // Exception: The first range should fetch the xref table as well.
  731. timer.finishBlockingCompute()
  732. timer.reportInto(metrics)
  733. trackDownloadStats(metrics, {
  734. size,
  735. cachedCount: 0,
  736. cachedBytes: 0,
  737. fetchedCount: 1,
  738. fetchedBytes: size,
  739. })
  740. return fallbackRequest({ url, start, end, abortSignal })
  741. }
  742. if (prefetchingEnabled) {
  743. addPrefetchingChunks({
  744. file,
  745. start,
  746. end,
  747. dynamicChunks,
  748. prefetchXRefTable,
  749. startXRefTableRange,
  750. })
  751. }
  752. const byteRanges = dynamicChunks
  753. .map(chunk => `${chunk.start}-${chunk.end - 1}`)
  754. .join(',')
  755. const coalescedDynamicChunks = []
  756. switch (true) {
  757. case dynamicChunks.length === 0:
  758. break
  759. case dynamicChunks.length === 1:
  760. coalescedDynamicChunks.push({
  761. chunk: dynamicChunks[0],
  762. url,
  763. init: { headers: { Range: `bytes=${byteRanges}` } },
  764. })
  765. break
  766. case dynamicChunks.length <= MULTI_PART_THRESHOLD:
  767. // There will always be an OPTIONS request for multi-ranges requests.
  768. // It is faster to request few ranges in parallel instead of waiting for
  769. // the OPTIONS request to round trip.
  770. dynamicChunks.forEach(chunk => {
  771. coalescedDynamicChunks.push({
  772. chunk,
  773. url,
  774. init: { headers: { Range: `bytes=${chunk.start}-${chunk.end - 1}` } },
  775. })
  776. })
  777. break
  778. default:
  779. coalescedDynamicChunks.push({
  780. chunk: dynamicChunks,
  781. url,
  782. init: { headers: { Range: `bytes=${byteRanges}` } },
  783. })
  784. }
  785. const params = new URL(url).searchParams
  786. // drop no needed params
  787. params.delete('enable_pdf_caching')
  788. params.delete('verify_chunks')
  789. const query = params.toString()
  790. // The schema of `url` is https://domain/project/:id/user/:id/build/... for
  791. // authenticated and https://domain/project/:id/build/... for
  792. // unauthenticated users. Cut it before /build/.
  793. // The path may have an optional /zone/b prefix too.
  794. const perUserPrefix = url.slice(0, url.indexOf('/build/'))
  795. const requests = chunks
  796. .map(chunk => ({
  797. chunk,
  798. url: `${perUserPrefix}/content/${file.contentId}/${chunk.hash}?${query}`,
  799. init: {},
  800. }))
  801. .concat(coalescedDynamicChunks)
  802. let cachedCount = 0
  803. let cachedBytes = 0
  804. let fetchedCount = 0
  805. let fetchedBytes = 0
  806. const reassembledBlob = new Uint8Array(size)
  807. // Pause while performing network IO
  808. timer.finishBlockingCompute()
  809. const rawResponses = await Promise.all(
  810. requests.map(async ({ chunk, url, init }) => {
  811. try {
  812. const response = await fetchChunk({
  813. chunk,
  814. url,
  815. init: { ...init, signal: abortSignal },
  816. cachedUrls,
  817. metrics,
  818. cachedUrlLookupEnabled,
  819. })
  820. timer.startBlockingCompute()
  821. const boundary = getMultipartBoundary(response, chunk)
  822. const blobFetchDate = getServerTime(response)
  823. const blobSize = getResponseSize(response)
  824. if (blobFetchDate && blobSize) {
  825. // Example: 2MB PDF, 1MB image, 128KB PDF.js chunk.
  826. // | pdf.js chunk |
  827. // | A BIG IMAGE BLOB |
  828. // | THE FULL PDF |
  829. if (chunk.hash && blobFetchDate < file.createdAt) {
  830. const usedChunkSection =
  831. Math.min(end, chunk.end) - Math.max(start, chunk.start)
  832. cachedCount++
  833. cachedBytes += usedChunkSection
  834. // Roll the position of the hash in the Map.
  835. usageScore.delete(chunk.hash)
  836. usageScore.set(chunk.hash, CHUNK_USAGE_THRESHOLD_CACHED)
  837. } else {
  838. // Blobs are fetched in bulk, record the full size.
  839. fetchedCount++
  840. fetchedBytes += blobSize
  841. }
  842. }
  843. timer.finishBlockingCompute()
  844. const buf = await response.arrayBuffer()
  845. timer.startBlockingCompute()
  846. const data = backFillObjectContext(chunk, buf)
  847. if (!Array.isArray(chunk)) {
  848. return [{ chunk, data }]
  849. }
  850. return resolveMultiPartResponses({
  851. file,
  852. chunks: chunk,
  853. data,
  854. boundary,
  855. metrics,
  856. })
  857. } catch (err) {
  858. throw OError.tag(err, 'cannot fetch chunk', { chunk, url, init })
  859. } finally {
  860. timer.finishBlockingCompute()
  861. }
  862. })
  863. )
  864. timer.startBlockingCompute()
  865. rawResponses
  866. .flat() // flatten after splitting multipart responses
  867. .concat(prefetched.map(chunk => ({ chunk, data: chunk.buffer })))
  868. .forEach(({ chunk, data }) => {
  869. if (!chunk.hash && chunk.end > end) {
  870. // This is a (partially) prefetched chunk.
  871. chunk.buffer = data
  872. file.prefetched.push(chunk)
  873. if (chunk.start > end) return // This is a fully prefetched chunk.
  874. }
  875. // overlap:
  876. // | REQUESTED_RANGE |
  877. // | CHUNK |
  878. const offsetStart = Math.max(start - chunk.start, 0)
  879. // overlap:
  880. // | REQUESTED_RANGE |
  881. // | CHUNK |
  882. const offsetEnd = Math.max(chunk.end - end, 0)
  883. const oldDataLength = data.length
  884. if (offsetStart > 0 || offsetEnd > 0) {
  885. // compute index positions for slice to handle case where offsetEnd=0
  886. const chunkSize = chunk.end - chunk.start
  887. data = data.subarray(offsetStart, chunkSize - offsetEnd)
  888. }
  889. const newDataLength = data.length
  890. const insertPosition = Math.max(chunk.start - start, 0)
  891. try {
  892. reassembledBlob.set(data, insertPosition)
  893. } catch (err) {
  894. const reassembledBlobLength = reassembledBlob.length
  895. const trimmedChunk = {
  896. start: chunk.start,
  897. end: chunk.end,
  898. hash: chunk.hash,
  899. objectId: new TextDecoder().decode(chunk.objectId),
  900. }
  901. throw OError.tag(err, 'broken reassembly', {
  902. start,
  903. end,
  904. chunk: trimmedChunk,
  905. oldDataLength,
  906. newDataLength,
  907. offsetStart,
  908. offsetEnd,
  909. insertPosition,
  910. reassembledBlobLength,
  911. })
  912. }
  913. })
  914. timer.finishBlockingCompute()
  915. timer.reportInto(metrics)
  916. trackDownloadStats(metrics, {
  917. size,
  918. cachedCount,
  919. cachedBytes,
  920. fetchedCount,
  921. fetchedBytes,
  922. })
  923. if (verifyChunks) {
  924. return await verifyRange({
  925. url,
  926. start,
  927. end,
  928. metrics,
  929. actual: reassembledBlob,
  930. abortSignal,
  931. })
  932. }
  933. return reassembledBlob
  934. }