From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 Received: from tb-ob1.topicbox.com (tb-ob1.topicbox.com [64.147.108.173]) by inbox.vuxu.org (Postfix) with ESMTP id 40AFE29A17 for ; Thu, 13 Jun 2024 06:08:27 +0200 (CEST) Received: from tb-mx0.topicbox.com (tb-mx0.nyi.icgroup.com [10.90.30.73]) by tb-ob1.topicbox.com (Postfix) with ESMTP id 38E8A1FF40 for ; Thu, 13 Jun 2024 00:08:26 -0400 (EDT) (envelope-from bounce.mM7cf5960cda854dba36823793.r522be890-2105-11eb-b15e-8d699134e1fa@9fans.bounce.topicbox.com) Received: by tb-mx0.topicbox.com (Postfix, from userid 1132) id 367FE1BC7EA3; Thu, 13 Jun 2024 00:08:26 -0400 (EDT) ARC-Authentication-Results: i=2; topicbox.com; arc=pass; dkim=pass (1024-bit rsa key sha1) header.d=eigenstate.org header.i=@eigenstate.org header.b=kRzKd1DI header.a=rsa-sha1 header.s=mail x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=eigenstate.org; spf=pass smtp.mailfrom=ori@eigenstate.org smtp.helo=mimir.eigenstate.org; x-internal-arc=fail (as.1.topicbox.com=pass, ams.1.topicbox.com=fail (message has been altered)) (Message modified while forwarding at Topicbox) ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=message-id:to:subject:date:from:in-reply-to :mime-version:content-type:content-transfer-encoding:list-help :list-id:list-post:list-subscribe:reply-to:list-unsubscribe; s= sysmsg-1; t=1718251706; bh=c13DTKKNCF9pj9+gwwAEtmHPoqyrBgvORx0mN egNiHo=; b=jqcUoUTSVnb2yrSmmczY61hoCaUnCB1NQuH7TU9r7BPAIKMPcjQRx xaUKp6/tgCQ6Z3nrbeY693aTJlw3g4xZQdencequORqyPXUjokz1xLBPzqCy9WuC zEsE7KNTgVJkRBmH4V6LBsxwXsbRRUSX5V+RODb5EoDgX/XHWdM2nI= ARC-Seal: i=2; a=rsa-sha256; cv=pass; d=topicbox.com; s=sysmsg-1; t= 1718251706; b=uIrqWhVJDnjixDAGEw9xpWUdEMaGypX3IF7qFCUBv8f35mQKEC sY2CZwZGd4SJWczKk0yQ62rTcAvEy5pZV3Rtl8csX78GVBqx4wLbNV39L0z8eC7g oDL0HoV96SFOVYeOTin7aWDnmzYXb5dxgVS7RQdnB+5BhBTUDGo1H2OI0= Authentication-Results: topicbox.com; arc=pass; dkim=pass (1024-bit rsa key sha1) header.d=eigenstate.org header.i=@eigenstate.org header.b=kRzKd1DI header.a=rsa-sha1 header.s=mail x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=eigenstate.org; spf=pass smtp.mailfrom=ori@eigenstate.org smtp.helo=mimir.eigenstate.org; x-internal-arc=fail (as.1.topicbox.com=pass, ams.1.topicbox.com=fail (message has been altered)) (Message modified while forwarding at Topicbox) X-Received-Authentication-Results: tb-mx0.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC Policy is not at enforcement); dkim=pass (1024-bit rsa key sha1) header.d=eigenstate.org header.i=@eigenstate.org header.b=kRzKd1DI header.a=rsa-sha1 header.s=mail x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=eigenstate.org; iprev=pass smtp.remote-ip=206.124.132.107 (mimir.eigenstate.org); spf=pass smtp.mailfrom=ori@eigenstate.org smtp.helo=mimir.eigenstate.org; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=mimir.eigenstate.org policy.ptr=mimir.eigenstate.org; x-return-mx=pass header.domain=eigenstate.org policy.is_org=yes (MX Records found: eigenstate.org,mail.pikopiko.org,kusuri.pikopiko.org,nokogiri.pikopiko.org); x-return-mx=pass smtp.domain=eigenstate.org policy.is_org=yes (MX Records found: eigenstate.org,mail.pikopiko.org,kusuri.pikopiko.org,nokogiri.pikopiko.org); x-tls=pass smtp.version=TLSv1.2 smtp.cipher=ECDHE-RSA-AES256-GCM-SHA384 smtp.bits=256/256; x-vs=clean score=0 state=0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed; d=9fans.net; h=message-id :to:subject:date:from:in-reply-to:mime-version:content-type :content-transfer-encoding:list-help:list-id:list-post :list-subscribe:reply-to:list-unsubscribe; s=dkim-1; t= 1718251706; x=1718338106; bh=M8QWSDosjuodd6Id21ZSCpft+lQjdba5FU6 XDJfWu1k=; b=f39qRcxuPzcKVlta+gou+jLDkkTJ+gx6j9NXXw4sBpVGH6CTpX8 0pnJLmiOZiVZ0zQD66qs6Rnq1ApTtxEngAyakHrRS2mwM5y4HqzZK2FBQkL0Y9mj vDVyO/QLbZASFvkOzqTDF56UCQD7lAjMrBpB3tZnYA1ugMkYQDWwcfW4= Received: from tb-mx0.topicbox.com (localhost.local [127.0.0.1]) by tb-mx0.topicbox.com (Postfix) with ESMTP id 974B41BC7A6C for <9fans@9fans.net>; Thu, 13 Jun 2024 00:08:08 -0400 (EDT) (envelope-from ori@eigenstate.org) Received: from tb-mx0.topicbox.com (localhost [127.0.0.1]) by tb-mx0.topicbox.com (Authentication Milter) with ESMTP id 6058C49617F; Thu, 13 Jun 2024 00:08:08 -0400 ARC-Seal: i=1; a=rsa-sha256; cv=none; d=topicbox.com; s=arcseal; t= 1718251688; b=WX1Bk2Q0XU4QCa8BMSUDRTs3xI95Pg/u2Y26/ShkzxLe5Hp6hi vXYnrNc6fy1EDu/UEbivYcb/lDng6o/Gw3mTmZcas7u9B9WxeWyK1H2AmtrmbToB 4ajETOKSk0qEGqvH5n6uQ3c4wJ1iqxnc6c8SBXz9sLMA/oxTQn78MhZu/j0HNVTq q3K8hZMTG2TK6vCwsDVFRJANafQ6Zk601UPECzt17zY82MB9uBXCq/8lmuaWzM60 DZDmXMIeIX0QCXUAFolL+f9ekSGvZeSZrhQ2gMOcLh0vjN6R5qyy69YiqOZDxzUo cONkfOLdicEXjwGPiq+Plp98HorpsIF5FJ5w== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= topicbox.com; h=message-id:to:subject:date:from:in-reply-to :mime-version:content-type:content-transfer-encoding; s=arcseal; t=1718251688; bh=ttvyJijcSdUlp3HKuvoiVKX+I5bk3t2cmlHVbUgCQ1Y=; b= f1znsuX8VaCKzWTRyAHrVlsaYYpL6uC8hPdIzaXl0xRoPZoBPEY5fBw0aGy5pIPm kJxXtckuJm1PimlSZu16UgonCTz+NRuoaZHTYNI5E3pabMgOYTR5UoPxFOy0pugX 3xAc2hEEsgqwICR0Ni7f+96k5o/HMen3S1psciVLp7GSvTlFJkDUYYx2TeD3EXr5 INuVupsrXCQp0/L58ZwrkvL3A6kSsqo1wUA+K4QE2e49aci45Ahz/QOWRB/NRxpL CZa4c1Ha6VM2TnZgyW0/MpjbaFjZuoOFtMBXPYf52DgrgwxJ8A31Atj99DwmXnnO EoDTdBKtw0VUjcm3USQdzA== ARC-Authentication-Results: i=1; tb-mx0.topicbox.com; arc=none (no signatures found); bimi=skipped (DMARC Policy is not at enforcement); dkim=pass (1024-bit rsa key sha1) header.d=eigenstate.org header.i=@eigenstate.org header.b=kRzKd1DI header.a=rsa-sha1 header.s=mail x-bits=1024; dmarc=pass policy.published-domain-policy=none policy.applied-disposition=none policy.evaluated-disposition=none (p=none,d=none,d.eval=none) policy.policy-from=p header.from=eigenstate.org; iprev=pass smtp.remote-ip=206.124.132.107 (mimir.eigenstate.org); spf=pass smtp.mailfrom=ori@eigenstate.org smtp.helo=mimir.eigenstate.org; x-aligned-from=pass (Address match); x-me-sender=none; x-ptr=pass smtp.helo=mimir.eigenstate.org policy.ptr=mimir.eigenstate.org; x-return-mx=pass header.domain=eigenstate.org policy.is_org=yes (MX Records found: eigenstate.org,mail.pikopiko.org,kusuri.pikopiko.org,nokogiri.pikopiko.org); x-return-mx=pass smtp.domain=eigenstate.org policy.is_org=yes (MX Records found: eigenstate.org,mail.pikopiko.org,kusuri.pikopiko.org,nokogiri.pikopiko.org); x-tls=pass smtp.version=TLSv1.2 smtp.cipher=ECDHE-RSA-AES256-GCM-SHA384 smtp.bits=256/256; x-vs=clean score=0 state=0 X-ME-VSCause: gggruggvucftvghtrhhoucdtuddrgedvledrfeduiedgheefucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggvpdfu rfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucenucfjughrpefkvffuff fhjgggtgfgsehtkeejtddttdejnecuhfhrohhmpehorhhisegvihhgvghnshhtrghtvgdr ohhrghenucggtffrrghtthgvrhhnpeefgfevieduhfehieduteffveehffehjeejvefhue eghfevffeludejtdevgeegffenucffohhmrghinhepthhophhitggsohigrdgtohhmnecu kfhppedvtdeirdduvdegrddufedvrddutdejpddutdekrdeirddvgedrvdenucevlhhush htvghrufhiiigvpedtnecurfgrrhgrmhepihhnvghtpedvtdeirdduvdegrddufedvrddu tdejpdhhvghlohepmhhimhhirhdrvghighgvnhhsthgrthgvrdhorhhgpdhmrghilhhfrh homhepoehorhhisegvihhgvghnshhtrghtvgdrohhrgheqpdhnsggprhgtphhtthhopedu pdhrtghpthhtohepoeelfhgrnhhsseelfhgrnhhsrdhnvghtqe X-ME-VSScore: 0 X-ME-VSCategory: clean Received-SPF: pass (eigenstate.org: 206.124.132.107 is authorized to use 'ori@eigenstate.org' in 'mfrom' identity (mechanism 'ip4:206.124.132.96/28' matched)) receiver=tb-mx0.topicbox.com; identity=mailfrom; envelope-from="ori@eigenstate.org"; helo=mimir.eigenstate.org; client-ip=206.124.132.107 Received: from mimir.eigenstate.org (mimir.eigenstate.org [206.124.132.107]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by tb-mx0.topicbox.com (Postfix) with ESMTPS for <9fans@9fans.net>; Thu, 13 Jun 2024 00:08:07 -0400 (EDT) (envelope-from ori@eigenstate.org) Received: from mimir.eigenstate.org (localhost [127.0.0.1]) by mimir.eigenstate.org (OpenSMTPD) with ESMTP id e6bb1382 for <9fans@9fans.net>; Wed, 12 Jun 2024 21:08:05 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=eigenstate.org; h=message-id :to:subject:date:from:in-reply-to:mime-version:content-type :content-transfer-encoding; q=dns; s=mail; b=CMiT9jo8R1fyR5iFXXh T3icpYhOG48coD+PAi91QNtAzMeX7boT/3BX++EMnkl8lZLKNAbLcCW+x9UWgB1B GVdB/ktv4yV/lo8jJ6FB/fop7+22atakDW/xAlT9dLHaSluKQOwWAzLbjMDyH+J1 FvCJCi4uAEDxdn3uCxlEFkeg= Received: from abbatoir (pool-108-6-24-2.nycmny.fios.verizon.net [108.6.24.2]) by mimir.eigenstate.org (OpenSMTPD) with ESMTPSA id 40b5920c (TLSv1.2:ECDHE-RSA-AES256-SHA:256:NO) for <9fans@9fans.net>; Wed, 12 Jun 2024 21:08:05 -0700 (PDT) Message-ID: <9C832F275135C5830776F4656A698D43@eigenstate.org> To: 9fans@9fans.net Subject: Re: [9fans] yet another try to fixup venti Date: Thu, 13 Jun 2024 00:08:03 -0400 From: ori@eigenstate.org In-Reply-To: <17181391500.35F5.93227@composer.9fans.topicbox.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Topicbox-Policy-Reasoning: allow: sender is a member Topicbox-Message-UUID: 8dc5a724-293a-11ef-b8d5-1578048c7b06 Archived-At: =?UTF-8?B?PGh0dHBzOi8vOWZhbnMudG9waWNib3guY29tL2dyb3Vwcy85?= =?UTF-8?B?ZmFucy9UMjE4NzhhYTUzODg0OTExYi1NN2NmNTk2MGNkYTg1NGRiYTM2ODIz?= =?UTF-8?B?NzkzPg==?= List-Help: List-Id: "9fans" <9fans.9fans.net> List-Post: List-Software: Topicbox v0 List-Subscribe: Precedence: list Reply-To: 9fans <9fans@9fans.net> List-Unsubscribe: , Topicbox-Delivery-ID: 2:9fans:437d30aa-c441-11e9-8a57-d036212d11b0:522be890-2105-11eb-b15e-8d699134e1fa:M7cf5960cda854dba36823793:1:-2u7o60M7jHyG_Z4GydqfXT4uCfubdo3eNg2X_bhYiY Sounds fairly interesting, though I'm curious how it compares; my guess was that because of the lack of locality due to using hashes for the score, a trie wouldn't be that different from a hash table. Quoth wb.kloke@gmail.com: > After studying Steve Stallion's=C2=A0 SSD venti disaster, I decided to do= my own try to fix the issues of venti. >=20 > Despite my reservations on the lasting wisdom of some of the design choic= es, I try to use the traditional=C2=A0 arena disk layout. > Only the on-disk index is replaced with a trie-based in-memory structure. >=20 > The trienodes represent either the score and IAddr data as leaves or 16 i= ndices for the next nibble of the score to search further. There is no need= for a Bloom filter, as the trie search is not less performant for negative= results. The actual trienode size is 64 bytes now, but can probably shorte= d to 48 bytes. >=20 > So far, I have managed to convert buildindex into buildtrie.=C2=A0 If -v = option is used, the contents of the trie are printed in lexical order of th= e score. >=20 > The data from my experiments are: >=20 > I used my 4 arena files, each 20GB, containing about 10 million clumps in= standard 500MB arenas. Data from the arena directories are read in in abou= t=C2=A0 one and a half minute. (There is one error in one of the arenas.) I= MHO this is acceptable as startup time for a venti server. >=20 > The trie has about 14m nodes, which are stored in a contiguous array. The= trie, which is now 32 bit indexed, thus may be reduced to 24 bit index for= the current data amount. >=20 > For larger storage, there is a design choice, either use 24 bit indices a= nd 48 byte trie nodes, and 256 trie arrays, or use 32bit indices and 64 byt= e trienodes in a single array. >=20 > After I=C2=A0 manage to=C2=A0 push my data to a planport fork on github, = you will hear more. ------------------------------------------ 9fans: 9fans Permalink: https://9fans.topicbox.com/groups/9fans/T21878aa53884911b-M7cf59= 60cda854dba36823793 Delivery options: https://9fans.topicbox.com/groups/9fans/subscription