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. Thanks Manlio Perillo
On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo <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.
How about "MVar (Map k Int)"? or even "Map k (MVar Int)"? -- Rich LOI: https://www.google.com/reader/shared/00900594587109808626
Rich Neswold ha scritto:
On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo <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.
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. Manlio Perillo
On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo <manlio_perillo@libero.it>wrote:
Rich Neswold ha scritto:
On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo <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.
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 this<http://hackage.haskell.org/cgi-bin/hackage-scripts/package/anydbm> . -- Rich LOI: https://www.google.com/reader/shared/00900594587109808626
"Rich Neswold" <rich.neswold@gmail.com> wrote:
On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo <manlio_perillo@libero.it>wrote:
Rich Neswold ha scritto:
On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo <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.
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 this<http://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. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or broadcasting of this signature prohibited.
Achim Schneider wrote:
"Rich Neswold" <rich.neswold@gmail.com> wrote:
On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo <manlio_perillo@libero.it>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 this<http://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
Anton van Straaten <anton@appsolutions.com> wrote:
Achim Schneider wrote:
"Rich Neswold" <rich.neswold@gmail.com> wrote:
On Thu, Sep 25, 2008 at 11:09 AM, Manlio Perillo <manlio_perillo@libero.it>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 this<http://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.
After watching the BayFP presentation I assumed that they've got cross-master synchronising going, and that's nearly a year old news now. Merely synchronising processes is trivial if you can do that. If the HAppS documentation wasn't as lacking as it is or I'd have more time, I would know more about this. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or broadcasting of this signature prohibited.
Rich Neswold ha scritto:
[...] On Wed, Sep 24, 2008 at 4:17 PM, Manlio Perillo <manlio_perillo@libero.it <mailto:manlio_perillo@libero.it> <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
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
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 <marco-oweber@gmx.de> 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
"jean-christophe mincke" <jeanchristophe.mincke@gmail.com> wrote:
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.
' isn't special in Haskell, it's idiomatic: you often see things like foo' = bar foo , as mathematicians and haskellers are to lazy to think of a new name for foo just because they got a derived foo. I, too, have no idea what *''Int* means. It's part of the "just use the *&%*$^!#!$%!^ operator" problem. -- (c) this sig last receiving data processing entity. Inspect headers for copyright history. All rights reserved. Copying, hiring, renting, performance and/or broadcasting of this signature prohibited.
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
Hello jean-christophe, Thursday, September 25, 2008, 1:52:26 PM, you wrote:
columns = [ ("trackId", conT ''Int )
It looks like a not ended string literal unless I still have sth to learn about Haskell.
it's TemplateHaskell, look for Reification in http://www.haskell.org/bz/thdoc.htm -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
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
On Wed, Sep 24, 2008 at 5:17 PM, Manlio Perillo <manlio_perillo@libero.it> 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. :-) Graham
Graham Fawcett ha scritto:
On Wed, Sep 24, 2008 at 5:17 PM, Manlio Perillo <manlio_perillo@libero.it> 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
On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo <manlio_perillo@libero.it> 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? Graham (sorry if this heading off-topic for the list.)
Graham Fawcett ha scritto:
On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo <manlio_perillo@libero.it> 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
On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo <manlio_perillo@libero.it> wrote:
Graham Fawcett ha scritto:
On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo <manlio_perillo@libero.it> 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
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
So the issue is one writer, many readers across processes? Creating an actual mini-db-server might be the proper way to do this. Expose a simple socket by which other processes can query the DB state. If you need persistence between runs of your main server you can always snapshot on shutdown, or for error-tolerance you can also write to a transactional log (probably with a single writer thread that takes input over a chan). Assuming its still in good shape, haxr [http:// www.haskell.org/haxr/] would simplify writing the socket portion. Depending on how you wrote the surrounding server, you might be able to avoid mvars altogether (i.e. if your server was built in an "agent" style with only a single request handler thread, then state could just be passed between recursive calls [or even stashed in a State monad] and the request serialization would handle concurrency issues for you). Regards, S. On Oct 1, 2008, at 3:09 PM, Manlio Perillo wrote:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Tue, Sep 30, 2008 at 9:18 AM, Manlio Perillo <manlio_perillo@libero.it> wrote:
Graham Fawcett ha scritto:
On Thu, Sep 25, 2008 at 5:09 PM, Manlio Perillo <manlio_perillo@libero.it> 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
participants (9)
-
Achim Schneider -
Anton van Straaten -
Bulat Ziganshin -
Graham Fawcett -
jean-christophe mincke -
Manlio Perillo -
Marc Weber -
Rich Neswold -
Sterling Clover