From mboxrd@z Thu Jan  1 00:00:00 1970
From: Jeff Garzik <jeff@garzik.org>
Subject: Re: Design challenges in chunkd self-checking
Date: Tue, 22 Dec 2009 22:36:16 -0500
Message-ID: <4B319030.9070906@garzik.org>
References: <20091222144111.789a5b91@redhat.com>	<4B314BAE.4010805@garzik.org> <20091222184014.22c5d1c5@redhat.com>
Mime-Version: 1.0
Content-Transfer-Encoding: 7bit
Return-path: <hail-devel-owner@vger.kernel.org>
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=domainkey-signature:received:received:sender:message-id:date:from
         :user-agent:mime-version:to:cc:subject:references:in-reply-to
         :content-type:content-transfer-encoding;
        bh=u9uJgYQ7Y8dvsQdcZjEFY6BnvtvA2eHHCYm4mrUCpmE=;
        b=ne3iyXPKgH4CwTS6ssk7XZ/M8e9V5/zj3OFBG0zyccbq8vgPyPK5xQv0iXb1s5kU8k
         jdc6BuB6FnTm3zB0ozGO6Sw0KwiZQgvk8c1W/0qCaPRl3Qtd07ofUyezW0HnaeNRTwXF
         yKarMsyq3pzJqaejym3WlfSg6H1ioAmPh3j4k=
In-Reply-To: <20091222184014.22c5d1c5@redhat.com>
Sender: hail-devel-owner@vger.kernel.org
List-ID: <hail-devel.vger.kernel.org>
Content-Type: text/plain; charset="us-ascii"; format="flowed"
To: Pete Zaitcev <zaitcev@redhat.com>
Cc: Project Hail List <hail-devel@vger.kernel.org>

On 12/22/2009 08:40 PM, Pete Zaitcev wrote:
> On Tue, 22 Dec 2009 17:43:58 -0500
> Jeff Garzik<jeff@garzik.org>  wrote:
>
>> It is normal and reasonable to maintain global information about all
>> in-progress operations.  Caching systems do that, for example, to ensure
>> multiple cache requests for object A do not initiate multiple
>> simultaneous back-end requests for object A.
>
> Unfortunately, this requires a data structure that permits searching.
> Since I lack the classical CS education, I cannot select an appropriate
> structure beyond "double-linked list and a hope that we'll never see
> more than 10 simultaneous I/Os".

What are the operational parameters?

* at beginning of object write, add entry to ADT (abstract data type, a 
list/table/whatever)

* at end of object write, remove entry from ADT

* lookup entry in ADT, where search key == object id.  if search 
succeeds, that object is guaranteed to be young and not need 
verification.  if search fails, the object (a) does not exist, or (b) 
has been completely written to disk.

Seems like a mutex-wrapped GLib hash table would work...

	Jeff