[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6,"_7":8,"_9":10,"_11":12},"actionData","errors","root",{"_180":-5,"_183":184,"_185":186},"routes/shell",{"_43":44,"_179":-5,"_180":-5,"_181":182},"routes/repo",{"_34":-7,"_35":36,"_37":38,"_39":40,"_41":42,"_43":44,"_45":32,"_46":32,"_47":32,"_48":32,"_49":32,"_50":32,"_51":52,"_53":52,"_54":32,"_55":-7,"_56":-7,"_57":58,"_59":60,"_61":62,"_63":-5,"_64":65,"_66":67,"_68":69,"_70":71},"routes/repo.blob",{"_13":14,"_15":16,"_17":18,"_19":20,"_21":22,"_23":24,"_25":-5,"_26":27,"_28":29,"_29":30,"_31":32,"_33":14},"ref","main","path","crates/ltx/src/client/epochs.rs","oid","7b856ad0763948889c05e15831079c9815be1176","size",5847,"commit","90b43017241f81189453d326d05948f388b34652","mounts",[],"source","plain",{"_13":14,"_15":16},"kind","text","//! A restore view over the epochs of one cell.\n//!\n//! A paged activation continues the chain it paged in: its first object\n//! follows the cut's last txid instead of opening the epoch with a\n//! whole-database snapshot (see [`crate::db::Db::seed_continuation`]). The\n//! objects a restore needs can therefore span epochs. The chain walks down\n//! from the newest epoch until one that opens with a snapshot, lists every\n//! level of each visited epoch once, clips an epoch to the txids before the\n//! next epoch's first (a fold that landed after the cut was never part of\n//! it), and routes every read by txid. The planner and the page map then\n//! run over it unchanged.\nuse crate::client::ReplicaClient;\nuse crate::compaction_level::SNAPSHOT_LEVEL;\nuse crate::error::Error;\nuse crate::error::Result;\nuse crate::ltx::FileInfo;\nuse crate::TXID;\nuse async_trait::async_trait;\nuse futures_util::stream;\nuse futures_util::StreamExt;\nuse futures_util::TryStreamExt;\n\n/// Listings per epoch in flight while a chain builds.\nconst LIST_CONCURRENCY: usize = 4;\n\nstruct Span {\n epoch: u64,\n client: C,\n /// The first txid this epoch serves; the span before it ends just short.\n lo: TXID,\n /// Files by level, clipped to this span.\n levels: Vec>,\n}\n\npub struct EpochChain {\n spans: Vec>,\n}\n\nimpl EpochChain {\n /// Walks `epochs` (ascending) down from the newest until an epoch that\n /// opens with a snapshot, listing every level of each visited epoch. The\n /// link below a continued epoch is the epoch whose objects, clipped to\n /// the txids before the continuation's first, end exactly at the cut; an\n /// epoch below that ends elsewhere is skipped. A fenced owner's late\n /// snapshot can land in an intermediate epoch, whole but older than the\n /// cut, and taking it as the base loses the writes between it and the\n /// cut (CelldPersistencePaged.tla, `BreakLinkByOrder`). An epoch without\n /// objects contributes nothing; no chain at all is `TxNotAvailable`.\n pub async fn build(mut epochs: Vec<(u64, C)>) -> Result {\n let mut spans: Vec> = Vec::new();\n while let Some((epoch, client)) = epochs.pop() {\n let mut levels = list_levels(&client).await?;\n if let Some(above) = spans.last() {\n // Clip to the txids before the continuation's first, then\n // the link must end at the cut.\n for files in &mut levels {\n files.retain(|f| f.max_txid < above.lo);\n }\n let ends = levels.iter().flatten().map(|f| f.max_txid).max();\n if ends != Some(TXID(above.lo.0 - 1)) {\n continue;\n }\n }\n let Some(lo) = levels.iter().flatten().map(|f| f.min_txid).min() else {\n continue;\n };\n spans.push(Span {\n epoch,\n client,\n lo,\n levels,\n });\n if lo == TXID(1) {\n break;\n }\n }\n if spans.is_empty() {\n return Err(Error::TxNotAvailable);\n }\n spans.reverse();\n Ok(Self { spans })\n }\n\n /// The epochs in the chain, oldest first, each with the first txid it\n /// serves.\n pub fn spans(&self) -> Vec<(u64, TXID)> {\n self.spans.iter().map(|s| (s.epoch, s.lo)).collect()\n }\n\n /// The last txid of the chain: the cut a continuation starts after.\n pub fn max_txid(&self) -> TXID {\n self.spans\n .iter()\n .flat_map(|s| s.levels.iter().flatten())\n .map(|f| f.max_txid)\n .max()\n .unwrap_or(TXID(0))\n }\n\n fn span(&self, txid: TXID) -> &Span {\n self.spans\n .iter()\n .rev()\n .find(|s| s.lo <= txid)\n .unwrap_or(&self.spans[0])\n }\n}\n\nasync fn list_levels(client: &C) -> Result>> {\n stream::iter(0..=SNAPSHOT_LEVEL)\n .map(|level| async move { client.ltx_files(level, TXID(0)).await })\n .buffered(LIST_CONCURRENCY)\n .try_collect()\n .await\n}\n\n#[async_trait]\nimpl ReplicaClient for EpochChain {\n async fn ltx_files(&self, level: i32, seek: TXID) -> Result> {\n Ok(self\n .spans\n .iter()\n .flat_map(|s| s.levels.get(level as usize).into_iter().flatten())\n .filter(|f| f.min_txid >= seek)\n .cloned()\n .collect())\n }\n\n async fn open_ltx_file(&self, level: i32, min_txid: TXID, max_txid: TXID) -> Result> {\n self.span(min_txid)\n .client\n .open_ltx_file(level, min_txid, max_txid)\n .await\n }\n\n async fn read_range(\n &self,\n level: i32,\n min_txid: TXID,\n max_txid: TXID,\n offset: u64,\n len: u64,\n ) -> Result> {\n self.span(min_txid)\n .client\n .read_range(level, min_txid, max_txid, offset, len)\n .await\n }\n\n async fn write_ltx_file(\n &self,\n level: i32,\n min_txid: TXID,\n max_txid: TXID,\n data: &[u8],\n ) -> Result {\n self.span(min_txid)\n .client\n .write_ltx_file(level, min_txid, max_txid, data)\n .await\n }\n\n async fn delete_ltx_files(&self, files: &[FileInfo]) -> Result<()> {\n for file in files {\n self.span(file.min_txid)\n .client\n .delete_ltx_files(std::slice::from_ref(file))\n .await?;\n }\n Ok(())\n }\n\n async fn delete_all(&self) -> Result<()> {\n Err(Error::Other(\"an epoch chain is a restore view\".into()))\n }\n}\n","editable",false,"branch","documentNavigation","repo","denoland/celld","repoId","a23b8a10-92cf-4dc4-a7ab-a04e58298dde","ownerId","org:42048915","organization",true,"site","nexthub","private","admin","settings","maintainer","triage","starred","stars",1,"watchers","watching","pinned","notify","views",[135,136,137,138,139,140,141,142,143,144,145,146,147],"navigation",{"_57":58,"_93":94,"_95":96,"_97":98,"_99":100,"_101":102,"_103":104},"sources",[],"viewer","meta",{"_85":86,"_87":88,"_89":90,"_45":32,"_91":14,"_92":32,"_51":52,"_53":52},"branches",[14],"tags",[72,73,74,75,76,77,78,79,80,81,82,83,84],"cloneUrl","https://git.nexthub.sh/denoland/celld.git","v0.0.1","v0.0.2","v0.1.0","v0.2.0","v0.2.1","v0.3.0","v0.4.0","v0.4.1","v0.5.0","v0.5.1","v0.6.0","v0.6.1","v0.6.2","description","self-hosted, distributed Durable Objects","owner","denoland","section","","head","empty","pins",[118,119,120],"documents",{"_113":114,"_115":116},"code",{"_110":111,"_112":106},"automations",{"_108":52,"_109":-5},"delivery",{"_105":106,"_107":-5},"tag","7gTA52Z9a1vO6FP6eCQPix9zO4O","releases",0,"applications","workflows","deployments","commits",13,"changes","counts",{"_117":116},"total",38,"issue",{"_121":112,"_123":133,"_15":112,"_125":134,"_55":42,"_127":32,"_128":42,"_129":106},{"_121":130,"_123":131,"_15":130,"_125":132,"_55":42,"_127":32,"_128":42,"_129":106},{"_121":122,"_123":124,"_15":122,"_125":126,"_55":42,"_127":32,"_128":42,"_129":116},"id","issues","name","Issues","filters",{},"saved","pinnable","count","tasks","Tasks",{},"Changes",{},{"_121":112,"_123":133,"_15":112,"_125":178,"_55":42,"_127":32,"_128":42},{"_121":130,"_123":131,"_15":130,"_125":177,"_55":42,"_127":32,"_128":42},{"_121":122,"_123":124,"_15":122,"_125":176,"_55":42,"_127":32,"_128":42},{"_121":173,"_123":174,"_15":173,"_125":175,"_55":32,"_127":32,"_128":42},{"_121":170,"_123":171,"_15":170,"_125":172,"_55":32,"_127":32,"_128":42},{"_121":108,"_123":168,"_15":99,"_125":169,"_55":32,"_127":32,"_128":42},{"_121":109,"_123":165,"_15":166,"_125":167,"_55":32,"_127":32,"_128":42},{"_121":105,"_123":163,"_15":105,"_125":164,"_55":32,"_127":32,"_128":42},{"_121":159,"_123":160,"_15":161,"_125":162,"_55":32,"_127":32,"_128":42},{"_121":95,"_123":157,"_15":95,"_125":158,"_55":32,"_127":32,"_128":32},{"_121":154,"_123":155,"_15":154,"_125":156,"_55":32,"_127":32,"_128":32},{"_121":151,"_123":152,"_15":151,"_125":153,"_55":32,"_127":32,"_128":32},{"_121":148,"_123":149,"_15":148,"_125":150,"_55":32,"_127":32,"_128":32},"decisions","Decisions",{},"changelog","Changelog",{},"roadmap","Roadmap",{},"Documents",{},"activity","Activity","insights",{},"Releases",{},"Deployments","automations/deployments",{},"Workflows",{},"discussions","Discussions",{},"goals","Goals",{},{},{},{},"groups","user","agents",[],"now",1794616983779,"sidebar","expanded"]