On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo wrote:

Rich Neswold ha scritto:

...

On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo > wrote:

I need a simple, concurrent safe, database, written in Haskell. A database with the interface of Data.Map would be great, since what I need to to is atomically increment some integer values, and I would like to avoid to use SQLite.

How about "MVar (Map k Int)"? or even "Map k (MVar Int)"?

Yes, it is a solution; and I can run a thread that every N seconds writes the database to a file.

But this works only if the database is used by only one process.

Ah. When you said "concurrent safe", I thought you meant within the application. You're looking for something like thishttp://hackage.haskell.org/cgi-bin/hackage-scripts/package/anydbm . -- Rich LOI: https://www.google.com/reader/shared/00900594587109808626

Achim Schneider wrote:

"Rich Neswold" wrote:

...

On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo wrote: ...

...

But this works only if the database is used by only one process.

Ah. When you said "concurrent safe", I thought you meant within the application. You're looking for something like thishttp://hackage.haskell.org/cgi-bin/hackage-scripts/package/anydbm .

Or even HApps-State (http://happs.org/) for moar 0v3rk1ll, of which you can never ever have enough.

HAppS-State doesn't currently solve the problem of the database being used by more than one process (does it?) In the current stable version, it basically maintains its data in-memory and keeps a checkpointed transaction log. This can be used with a "sharded" approach where each process manages its own little chunk of the data, which can work well for certain data access patterns. But if you want each process to have access to a common database, HAppS-State currently only gives you the low-level building blocks for that. I understand that there are plans and prototypes and work being done on more sophisticated features, like multi-master replication, but I don't think anything like that is usable today. Depending on the application requirements, it might be simple enough to implement a custom data access layer over a set of happs shards to do things like retrieve individual values that aren't in the current process, or perhaps do a MapReduce-style operation over all processes. But there's nothing like that out of the box, yet. Anton

Rich Neswold ha scritto:

[...] On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo mailto:manlio_perillo@libero.it mailto:manlio_perillo@libero.it>> wrote:

I need a simple, concurrent safe, database, written in Haskell. A database with the interface of Data.Map would be great, since what I need to to is atomically increment some integer values, and I would like to avoid to use SQLite. [...]

Ah. When you said "concurrent safe", I thought you meant within the application. You're looking for something like this http://hackage.haskell.org/cgi-bin/hackage-scripts/package/anydbm.

I'm not an expert with Haskell, but anydbm does not seem to be very safe to use... Thanks Manlio Perillo

Marc What is this strange syntax columns = [ ("trackId", conT *''Int* ) It looks like a not ended string literal unless I still have sth to learn about Haskell. Thank you J-C On Thu, Sep 25, 2008 at 12:03 AM, Marc Weber wrote:

On Wed, Sep 24, 2008 at 11:17:01PM +0200, Manlio Perillo wrote:

...

Hi.

I need a simple, concurrent safe, database, written in Haskell. A database with the interface of Data.Map would be great, since what I need to to is atomically increment some integer values, and I would like to avoid to use SQLite.

I've tried writing at least part of that. But it's still higly experimental and uses template haskell. It looks like this: from that some datastructures are defined which look like tables used in traditional RDBMS such as SQLite.. However if you don't want to use many "tables" you may be a lot faster writing down what you need yourself. My lib automacially generates code for inserting / deleting tuples into multi indexes such as (Map Int (Map Int PrimIdx)).

$(let cds = defaultTable { tblName = "cds" , columns = [ ("cdId", conT ''Int) , ("title", conT ''Int) ] , primary = PrimaryUniq [ "cdId" ] [| 0 |] , indexes = [ Index "title" [] ] , tblStates = [ ( "nextCdId", [t| Int |], [| 0 |] ) ] }

tracks = let a="a" -- updateNumRows n = [| \n -> cdUpdateByPK (\r -> r { num_tracks = (num_tracks r) + $(n) } ) |] in defaultTable { tblName = "tracks" , columns = [ ("trackId", conT ''Int ) , ("name", conT ''String) , ("cd", conT ''Int) -- foreign key ] , primary = PrimaryUniq [ "cd", "trackId" ] [| 0 |] , indexes = [ Index "cd" [ IndexUnique "trackId" ] ] --the id is uniq foreach cd -- checks = [ foreignConstraint "cd" "cds" "id" ] -- triggers = [ InsertUpdate (Just ["cd"]) [| cdUpdateByPK ( updateNum_tracks (+1) ) . pk |] -- DeleteUpdate (Just ["cd"]) [| cdUpdateByPK ( updateNum_tracks (-1) ) . pk |] -- ] } db = defaultDB { dbName = "my" , tables = [ cds, tracks] , statistics = True } in createDB db)

If you're interested drop me a mail.

Marc _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Thu, Sep 25, 2008 at 11:52:26AM +0200, jean-christophe mincke wrote:

Marc

What is this strange syntax

columns = [ ("trackId", conT ''Int )

Hi J-C, I'ts part of template haskell and tells ghc to use the type referenced by Int. There are some getting started guides on haskell.org By the way you can enhance readability of your messages if you only keep that part of the message you're refering to. Sincerly Marc Weber

Marc Weber ha scritto:

On Wed, Sep 24, 2008 at 11:17:01PM +0200, Manlio Perillo wrote:

...

Hi.

I need a simple, concurrent safe, database, written in Haskell. A database with the interface of Data.Map would be great, since what I need to to is atomically increment some integer values, and I would like to avoid to use SQLite.

I've tried writing at least part of that. But it's still higly experimental and uses template haskell.

What do you use as low level storage?

[...]

Thanks Manlio Perillo

Graham Fawcett ha scritto:

On Wed, Sep 24, 2008 at 5:17 PM, Manlio Perillo wrote:

...

Hi.

I need a simple, concurrent safe, database, written in Haskell. A database with the interface of Data.Map would be great, since what I need to to is atomically increment some integer values, and I would like to avoid to use SQLite.

If that's the entire requirement, and you're looking for something really fast, perhaps you could use a shared-memory region between the processes (your keys would map to addresses in shared memory), and use a compare-and-set algorithm to handle the atomic increments.

If you're on Intel/Itanium, I believe there's a CMPXCHG instruction that will do atomic compare-and-set on a memory address, and I'm not sure you could get much faster than that. :-)

I have an early draft of this type of database (written in D). Operations on integers use CMPXCHG, and for other operations a simple spin lock (implemented following the implementation in Nginx) is used. The problem is that it is a simple shared array! This means that you need to know in advance the data index in the array; for some type of applications this is true, I was trying to implement that database for using it in my HTTP Digest authentication implementation (http://hg.mperillo.ath.cx/wsgix/file/tip/wsgix/auth/auth_digest.py), in order to improve security, using "not so restful" support in the RFC 2617.

Graham

Manlio Perillo

Graham Fawcett ha scritto:

On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo wrote:

...

Graham Fawcett ha scritto:

...

If you're on Intel/Itanium, I believe there's a CMPXCHG instruction that will do atomic compare-and-set on a memory address, and I'm not sure you could get much faster than that. :-) I have an early draft of this type of database (written in D). Operations on integers use CMPXCHG, and for other operations a simple spin lock (implemented following the implementation in Nginx) is used.

And I thought I was being original. :-)

...

The problem is that it is a simple shared array!

I'm guessing you've also ruled out sparse arrays? If not, what complexity is acceptable on your lookup function?

Never though about sparse array, what is the advantage? For the complexity, the same of a good hash map.

[...]

By the way, for the moment I think I will use Data.Map, serializing it to a file, since only one process will update it, and the other processes needs not to read an up-to-date snapshot. The only thing that needs to be taken care of, is to write the file atomically, but this is easy. Thanks Manlio Perillo

Graham Fawcett ha scritto:

[...]

...

Never though about sparse array, what is the advantage? For the complexity, the same of a good hash map.

Almost certainly worse complexity than a hash map; but the overhead could be much smaller. If (for example) you only needed a small number of key/value pairs (say, hundreds of thousands), you could implement your "database" trivially, e.g. a NULL-terminated array of key/value structs in shared memory. (Though having separate arrays for keys and values might help cache locality and boost performance). Lookup might be O(n) but with a small-ish N and with such a low overhead, it could perform very, very well.

This seems an interesting idea, thanks. Manlio Perillo

On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo wrote:

Graham Fawcett ha scritto:

...

On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo wrote:

...

Graham Fawcett ha scritto:

...

If you're on Intel/Itanium, I believe there's a CMPXCHG instruction that will do atomic compare-and-set on a memory address, and I'm not sure you could get much faster than that. :-)

I have an early draft of this type of database (written in D). Operations on integers use CMPXCHG, and for other operations a simple spin lock (implemented following the implementation in Nginx) is used.

And I thought I was being original. :-)

...

The problem is that it is a simple shared array!

I'm guessing you've also ruled out sparse arrays? If not, what complexity is acceptable on your lookup function?

Never though about sparse array, what is the advantage? For the complexity, the same of a good hash map.

Almost certainly worse complexity than a hash map; but the overhead could be much smaller. If (for example) you only needed a small number of key/value pairs (say, hundreds of thousands), you could implement your "database" trivially, e.g. a NULL-terminated array of key/value structs in shared memory. (Though having separate arrays for keys and values might help cache locality and boost performance). Lookup might be O(n) but with a small-ish N and with such a low overhead, it could perform very, very well. Of course, you know what your requirements are, and I don't. :-) But I think if one needed a "shared map, size N, of integers to incrementing registers" where N wasn't enormous, then this might be attractive. Cheers, Graham

By the way, for the moment I think I will use Data.Map, serializing it to a file, since only one process will update it, and the other processes needs not to read an up-to-date snapshot. The only thing that needs to be taken care of, is to write the file atomically, but this is easy.

Thanks Manlio Perillo