|
Home > Archive > Unix Programming > April 2004 > Help for a Client Server Project
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Help for a Client Server Project
|
|
|
| Hi,
I need some help regarding the following Project. The main hint
required is how to make a good design for the problem given, since a
good design would result in a much simpler and effective coding.
Can someone pls help me out.
Thanks in Advance
Objectives
The aim of this project is to develop a centralised database of
strings. Users that log into the system should be allowed to remove,
modify, append and search through the string data. Each user should be
given the impression of being a sole user and maximum concurrency and
efficiency should be provided.
Preliminaries
It is very common that some sort of data is maintained on a single
machine, for reasons of security, data centralisation, etc. In
addition, when this data is accessed continuously it is usual to
develop some form of concurrency allowing multiple users to manipulate
the data without having to wait for other users to stop manipulating
the data. One such application is a central repository of long
strings, such as DNA strings, proteins, etc. Such research areas
require un-deterministic access and concurrent modification of the
database
Implementation
You are requested to develop a server system that will allow the
storage of strings of arbitrary length in a central file-system. Each
of these strings is considered as one data entry and each operation on
each data string should be atomic. You can assume that the data will
always exist on the server machine. Any user will be allowed to run an
application on the database machine that will enable him or her to
manipulate the data. An appropriate menu system should be provided for
the user. A user will be allowed to delete strings depending on string
position in the database given or after a search for a particular
string. In addition, a user is allowed to enter new strings of
arbitrary length in any position of the file or merely append to the
end of the file. Also a user will be allowed to search through the
file by giving an exact match for the string. A user should also be
allowed to modify any string within the database. Note that the only
character not legal in any part of the string is the "\0" character.
Also strings in the database are not required to be unique.
Multiple users can be manipulating the string database concurrently.
The maximum amount of efficiency should be maintained, thus allowing
potentially hundreds of users to be operating on the database of
strings. It is important to guarantee that at all points of execution,
the database system is in a consistent state and that client
applications always produce a valid result. You can assume that the
database of strings is too large to fit within the memory of the
computer.
Remarks
Special attention to race conditions should be considered. As is
common in systems programming, completely design your system first
before starting any coding efforts. Efficiency of the system will be
considered an asset especially in terms of inter-process
communication. Also pay special attention to errors that might occur
when using system calls and report them accordingly. You should not
rely on a socket interface since it is not an efficient mechanism in
this case.
| |
| Nick Landsberg 2004-04-25, 10:34 am |
| Xarky wrote:
> Hi,
> I need some help regarding the following Project. The main hint
> required is how to make a good design for the problem given, since a
> good design would result in a much simpler and effective coding.
>
> Can someone pls help me out.
> Thanks in Advance
>
>
>
> Objectives
> The aim of this project is to develop a centralised database of
> strings. Users that log into the system should be allowed to remove,
> modify, append and search through the string data. Each user should be
> given the impression of being a sole user and maximum concurrency and
> efficiency should be provided.
>
>
> Preliminaries
> It is very common that some sort of data is maintained on a single
> machine, for reasons of security, data centralisation, etc. In
> addition, when this data is accessed continuously it is usual to
> develop some form of concurrency allowing multiple users to manipulate
> the data without having to wait for other users to stop manipulating
> the data. One such application is a central repository of long
> strings, such as DNA strings, proteins, etc. Such research areas
> require un-deterministic access and concurrent modification of the
> database
>
Wow, a real-world problem! 
>
> Implementation
> You are requested to develop a server system that will allow the
> storage of strings of arbitrary length in a central file-system. Each
> of these strings is considered as one data entry and each operation on
> each data string should be atomic. You can assume that the data will
> always exist on the server machine. Any user will be allowed to run an
> application on the database machine that will enable him or her to
> manipulate the data. An appropriate menu system should be provided for
> the user. A user will be allowed to delete strings depending on string
> position in the database given or after a search for a particular
> string. In addition, a user is allowed to enter new strings of
> arbitrary length in any position of the file or merely append to the
> end of the file. Also a user will be allowed to search through the
> file by giving an exact match for the string. A user should also be
> allowed to modify any string within the database. Note that the only
> character not legal in any part of the string is the "\0" character.
> Also strings in the database are not required to be unique.
I'll give a shot at some "off the top of the
head" design.
One implied requirement here is that
there is the concept of "order" in that a user is allowed
to insert a string into any position ("after"). There is
also the requirement to delete depending on "string position
in the database"
For the insertion requirements, since the new string
may be longer than the old string, a simplistic approach
in which the whole file gets rewritten upon an insert is
out of the question. (Efficiency). Thus I would consider
a B-Tree or T-Tree indexing scheme, where the index
preserves order and has some kind of pointer to the
actual string. Because the strings can be of arbitrary
length, it is impractical to store the string as
part of this index, though. I would then consider
another table of actual strings, probably organized
as a hash table on disk. The hash would provide an
efficient access for queries for individual strings.
It would also include as part of the record, the
"sequence number" of this string. This sequence
number is what the B-tree would index on and the
pointer in the B-Tree is the "hash-bucket" which
contains the actual string.
This would also allow for >1 string to have the
same codes in it, but, by having a sequence
number, there is uniqueness.
Look up appropriate references for B-Tree
implementations and disk-based hash tables.
>
> Multiple users can be manipulating the string database concurrently.
> The maximum amount of efficiency should be maintained, thus allowing
> potentially hundreds of users to be operating on the database of
> strings. It is important to guarantee that at all points of execution,
> the database system is in a consistent state and that client
> applications always produce a valid result. You can assume that the
> database of strings is too large to fit within the memory of the
> computer.
This implies that both the B-Tree "page" pertinent
to that record and the hash-table "bucket" pertinent
to that record must be locked prior to update,
both updated and then both unlocked. Either both
updates must happen or no updates must happen.
Notice I said "page" and "bucket" rather than
table, because of the need for multi-user accesses.
I would *not* lock on just a plain "read", but would
apply the locks at the time of update. You might
also consider "optimistic locking". (Again, research
this technique.)
The knowledge of which pages are locked should
also be centralized on the server. There are
many possible designs, e.g. keep a table of locks
on disk, keep it in a shared memory segment,
or keep the knowledge in a "lock server", etc.
Each has it's own pros and cons.
Keeping tables either on disk or shared memory
implies a secondary mutex around the lock table.
Having a lock server involves yet another IPC.
You decide where the tradeoffs lie for your design.
>
>
> Remarks
> Special attention to race conditions should be considered. As is
> common in systems programming, completely design your system first
> before starting any coding efforts. Efficiency of the system will be
> considered an asset especially in terms of inter-process
> communication. Also pay special attention to errors that might occur
> when using system calls and report them accordingly. You should not
> rely on a socket interface since it is not an efficient mechanism in
> this case.
I have no idea what your prof has against sockets and I
would disagree with him/her. If by that he/she meant
that sockets should not be used on the server between
processes, then that's probably a valid concern. However,
I would still use them between client PC's and the
server.
Hope this starts you off thinking in some
direction that helps you solve the problem
(and it *is* a very good problem to attack).
Nick L.
--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch
| |
|
| Hi,
First of all thanks for the help given.
My main problem was not with what to use if B-Trees, Hash tables
or things like that. (The lecturer told us that they are not so
important and we could search in the file by a linear search, and also
deletion is not physical but logical).
I was going to make the file structure something this way:
String; Deleted;
where deleted would be 1 valid, 0 invalid.
My main problem is what exactly I have to do in the client and in
the server, ie when to fork and when to enter critical sections for
Race Conditions. I don't know if you are understanding my point and
if you can give me some help, I hope so.
By the way, its my first experience that I am writing an
application making use of systems programming, so if I have writen
some stupidity, forgive me.
Thanks in Advance
| |
| The King of Pots and Pans 2004-04-26, 3:34 am |
| On Mon, 26 Apr 2004 at 05:27 GMT, Xarky spoke:
> The lecturer told us that they are not so important and we could
> search in the file by a linear search, and also deletion is not
> physical but logical.
Send me $1,000 US and I will get you a "A" on your school work for
this assignment.
Or you can read your textbooks and write practice programs for fun,
all for free, and you're likely also to get an A and save $1,000 US.
Unless you have a ton of money to buy people off, you are going to
fail in the real world when you get out of school, unless you do your
own work.
You should choose a different course of study since you aren't
passionate or interested in learning the fine art of code poetry.
--
The King of Pots and Pans
| |
| Nick Landsberg 2004-04-26, 5:34 am |
| The King of Pots and Pans wrote:
> On Mon, 26 Apr 2004 at 05:27 GMT, Xarky spoke:
>
>
>
>
> Send me $1,000 US and I will get you a "A" on your school work for
> this assignment.
Gee, K o' P & P, you come cheap!
>
> Or you can read your textbooks and write practice programs for fun,
> all for free, and you're likely also to get an A and save $1,000 US.
>
>
> Unless you have a ton of money to buy people off, you are going to
> fail in the real world when you get out of school, unless you do your
> own work.
>
> You should choose a different course of study since you aren't
> passionate or interested in learning the fine art of code poetry.
>
Trying to help the OP without doing the HW for him...
First, before worrying about the details of
"when to fork," etc. you have to decide how
to partition the functionality between
client side and server side. There are
two approaches, "fat client" and "thin client".
In a "fat client" architecture, most of the
application logic is in the client code and the
"server" is relatively dumb. Mainly responding
the the client requests for data handling.
In the "thin client" approach, most of the
application logic is in the server code
and the client acts primarily as a UI/display
agent.
(This is an oversimplification. But it's a good
abstraction.) Both approaches have pros and
cons. However, mixing the two indiscriminantly
is *not* a good idea. What is there about
this problem which makes one of the above
more or less attractive? Why? (Questions
to ask yourself, or to ask your instructor.)
"Critical Regions" are those where more than
one entity (process/thread) may be trying
to modify the same resource more-or-less at
the same time. For example, userA and userB
may be trying to append to the database at
the same time. Simplistic pseudo-code to handle
this request might read something like
seek to EOF
write record.
Howevere, consider the sequence:
UserA - seek to EOF
UserB - seek to EOF
UserA - write record.
UserB - write record.
In this sequence of events, User A's
record is overwritten by user B's record.
You have to guard against that.
You have to logically find every place
in your design that is changing the
data file (your resource) and put
locks/semaphores/mutexes in place to
avoid data loss and/or corruption
just in case more than 1 user is
writing to the file at the same time.
First, you should map out your data-handling
strategy (how to do updates, appends, deletes,
etc.) and then, only after that, worry
about the details of exactly which functions
to call to do the locking and when.
This exercise usually leads to some redesign
in order to minimize the code length within
the critical regions, but that's phase 3.
Don't worry about the mechanics of the locking
and when/how to fork, etc just yet.
--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch
|
|
|
|
|