Page Index Toggle Pages: [1] 2 
Topic Tools
Very Hot Topic (More than 25 Replies) PMs to be more "instant" (Read 9,355 times)
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #29 - Jul 19th, 2009 at 9:18pm
Post Tools
Matt Siegman wrote on Jul 19th, 2009 at 3:47pm:
What do you think?

I think that to put it in without trying to get it right will lead to wasted effort early, bugs, and then duplicated effort later.  In my experience, if you want to put in future support for a feature, you have to still plan out how you will implement it, including the algorithms to do so.

If support is to be included, we should try to get it right in the sense that, at the very least, the DB structure has to be built to allow it in the future.  Thankfully, that's as simple as doing what I stated earlier: storing references to replies twice, which will cost very little storage overhead but will minimize processing overhead to store replies, and allow full thread or message tree traversal with only N queries (the overhead of which should be small), or possibly fewer.

Alternatively, if we don't want to store forward references twice, we can at the very least store backwards references for each post (a "replyToID" pointing to the parent post), and can then rebuild the DB with forward references later using this ID.  I'd go with the the former method, though - it will save time later.

However, I'd also be glad to spend time brainstorming the algorithms and data structures with you (in a separate thread, if you want Smiley) now, so we at least have the plan in place and can work other things around it, even if it's not fully implemented until 3.1 or whatever.
  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #28 - Jul 19th, 2009 at 3:47pm
Post Tools
Perhaps we should just put support for a fully threaded board into the database and post code and then not worry about the different display methods until later. That would let us support adding fully-threaded-ness in the future, but without requiring us to try and get it working right for the first Y3 release.

What do you think?
  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #27 - Jul 19th, 2009 at 6:45am
Post Tools
Matt Siegman wrote on Jul 19th, 2009 at 6:17am:
We were planning on putting in support for both types. I think the best way to do it is a depth and lineage method. We don't want to load all the messages in the entire thread unless we have to.

If you want to support a fully-threaded mode but don't want to load the whole thread, then I agree an n-ary tree will be the best option, although when I say tree I really mean records referencing other records... I wouldn't suggest placing replies to one message in the same record as the original message, because AFAIK that's inefficient for storage (I think you have to re-store the entire message tree every time a reply is posted).  Storing each message in a separate record does mean you have to make multiple recursive queries to retrieve the full tree of replies, but it scales as n, not n2, so it's still rather efficient and you only add the overhead of making multiple queries, which is small compared to the data volume.

Additionally, by storing it that way, support for flat-threaded mode is automatically built-in, especially if you store the references twice: the thread record contains the time-ordered reference list, and each message contains a reference list of replies to that message.

Then, in flat-threaded mode, you query the thread time-ordered list for X posts made after the Nth post (where X is the number of posts displayed per page and N is the first post on the page).  In fully-threaded mode, you query for exactly the same thing but from the other reference list, and recurse through each message to get the replies.

The one problem I have with implementing fully-threaded mode: that makes sense for blog-type displays, e.g. Slashdot, Engadget, whatever, because what's threaded is the comments section; the original "post" (the blog entry) stands alone.  In a BB, the original post doesn't stand alone; every subsequent message is a reply to the OP (or to a nested reply)... that means there will only be ONE top-level message, which to me would generate a rather confusing layout - it would either unnecessarily indent every reply to the OP, or if "level 1" replies are not indented, it breaks the consistency (since they would be on the same "level" as the OP, even though they are replies).

I'm sure that can be overcome somehow, but this is what I meant about not liking a fully-threaded interface for BBs, because it encourages people to separate their replies to replies versus their replies to the OP, etc. and IMHO breaks the flow of conversation.  That's not a reason not to implement it (since it's just my opinion), but it's a concern I have in terms of usability for others.
  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #26 - Jul 19th, 2009 at 6:17am
Post Tools
We were planning on putting in support for both types. I think the best way to do it is a depth and lineage method. We don't want to load all the messages in the entire thread unless we have to.

I would think that this kind of thing would be an admin option. If switched on or off the pertinent code to generate depth/lineage information. That way we could avoid unnecessary work.
  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
Unilat
Development Team
Theme Team
****
Offline



Posts: 1,047
Location: Columbus Ohio, USA
Re: PMs to be more "instant"
Reply #25 - Jul 19th, 2009 at 3:20am
Post Tools
The simplest way for legitimate threading would be to have a thread id, a reply order id, and a post id.

The thread id is obviously which thread it belongs to. The reply order id is basically just numbered sequentially by post date and time and would be the id that another post uses in its "postid" field. Then post id would be the post it is in response to.

For real threaded messages then, all posts with threadid = 1023923 would be loaded. Then the first post would be added to an array or something, the next one down would check its postid, which would have to be 0 as its the first reply, then adds it to the array. The next post could either be postid 1 or 0 and then stick that where it belongs in the array. Then for each after that find the location of the post with reply order id = post id of the current post and stick it n the array there, finally just print in the order that the array ends up with.

That seems stupid though, but thats how I imagine it works.
  
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #24 - Jul 19th, 2009 at 12:05am
Post Tools
Matt Siegman wrote on Jul 19th, 2009 at 12:00am:
supporting a threaded board means that individual posts get replied to instead of just the thread in general.

Ooooh, you wanted to support FULL threading, not just "hybrid" threading (where it's just a long string of messages, not considering replies to individual posts).  You want it kind of like a slashdot layout, then...

To tell you the truth, for public forums I actually don't like the full thread, because it makes it very hard to reply to multiple posts at once... it encourages a lot of smaller posts (individual replies) instead of larger, more comprehensive ones.  To me, it also really breaks up the flow of conversation; I know that sounds counterintuitive, but for me, that's how it is.  I actually think flat-threads are easier to read and follow than fully-threaded formats.

If we supported both modes, that would be fine, though more work... but if you're doing only one, I would vote for the regular "flat" thread format (like we have now) rather than a fully threaded format.  It's also a lot easier to optimize for speed using a flat-thread format. Smiley

(I know fully-threaded makes it easier to follow individual replies, but I've seen how fully-threaded forums look, e.g. slashdot and other places, and I just don't think they flow well at all.)
« Last Edit: Jul 19th, 2009 at 12:07am by cepheid »  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #23 - Jul 19th, 2009 at 12:00am
Post Tools
Well, just storing the thread ID is fine for a flat board, but supporting a threaded board means that individual posts get replied to instead of just the thread in general. To do that properly, we have to be a little fancier ;) The trick is: properly built (normalized) databases optimize data integrity. What we're optimizing is speed, so there will be some inefficiencies in our DB structure. I haven't written the schema for the DB yet.

It's a subset because the sql parser is a pre-built thing. (Just the parser, I have to write all the storage code. SQL::Statement is the module that parses, I've written everything in YaBB3::DataSources::File) I also worry that implementing more things would cause unacceptable performance for the flat file source.
« Last Edit: Jul 19th, 2009 at 12:00am by Matt Siegman »  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #22 - Jul 18th, 2009 at 10:53pm
Post Tools
Matt Siegman wrote on Jul 18th, 2009 at 8:31pm:
For this, I was thinking of just storing the lineage in the table.

Is there a reason to even consider a tree?  The DB is relational, so each post record can have a "threadID" field, and the query to the DB would be "return all posts with this threadID" ... if that is too server-intensive (because there could be thousands of posts but we're looking for only a few), then you could do it backwards: each thread record has a "containedPosts" field, which is a list of all the postIDs contained in the thread (in the order in which they appear), so you then just run a query to retrieve those posts.

I'm not an expert on DB access so forgive me if that sounds stupid...

If you describe (or point me to where you have already described) your idea for the data structure in the DB, I can hopefully give you a better suggestion.  I'm generally pretty good at optimizing algorithms and data structures, at least once I know the background of what you're trying to do. Wink  (My favorite CS classes were the algorithms and data structures courses.)

Matt Siegman wrote on Jul 18th, 2009 at 8:31pm:
Since the subset of SQL that is allowed by DataSource doesn't support self joins

Is there a reason that DataSource only supports a subset of SQL?  Is it a pre-built package or are you writing it from scratch?  Since I'm new to the innards of Y3, I obviously don't know too much about the history of the individual pieces.
« Last Edit: Jul 18th, 2009 at 10:57pm by cepheid »  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #21 - Jul 18th, 2009 at 8:31pm
Post Tools
I've been thinking about these things for a while, even back on the old Y3 code base. There are some very nice solutions to these problems, that I have seen the other big systems start to pick up recently.



That's easy, actually. The trick is getting a whole tree in one query. For boards, I was thinking of using a "Nested Set" model (also called a pre-order tree traversal). It's pretty cool. It allows you to get a whole hierarchy with a single query. Since creating boards happens infrequently, it's not a big deal to recompute the tree every time boards are added/moved/removed.

Since the subset of SQL that is allowed by DataSource doesn't support self joins, it requires us being slightly more creative in writing the code to use it.

http://www.sitepoint.com/print/hierarchical-data-database/
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html



For threads, it is a simple board-thread relationship.



For posts in threads, it's a bit trickier. I imagine every post will have a thread it belongs to. To support a thread view, we could do another pre-ordered tree, but posts get added a lot more often and this could really make load excessive. For this, I was thinking of just storing the lineage in the table. It wouldn't be too hard to do, just requires a little planning Smiley

http://www.sqlteam.com/article/more-trees-hierarchies-in-sql



I'm looking at this site:
http://74.125.47.132/search?q=cache:wqhiNhZELHIJ:www.evolt.org/node/4047+storing... (cached copy because main site wasn't working)

If it has any good ideas, I may use them.
« Last Edit: Jul 18th, 2009 at 8:35pm by Matt Siegman »  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #20 - Jul 18th, 2009 at 7:48pm
Post Tools
OH Eng wrote on Jul 18th, 2009 at 2:09pm:
It may create an impression that privacy in the PMs is less than it is now, however.

The messages wouldn't show up in the BoardIndex... they would still be in the Private Messages center.  They would just "look" like Boards, much the same way Gmail handles it.  Privacy shouldn't be an issue, but we can make that explicit.

Matt Siegman wrote on Jul 18th, 2009 at 5:46pm:
We could reuse a lot of the board display code without adding it into the board index. We could probably do threaded messaging, but it may be tricky.

The idea would be to keep it in its own PM Center, yes.  I don't know that threaded messaging would be that tricky... it would require a rewrite of how PMs work now, but I think it can be done by integrating much of the existing PM code with thread display code.

Matt Siegman wrote on Jul 18th, 2009 at 5:46pm:
the code to do this won't know whether or not it's flat-file or db.

Ah, right.  I'd certainly have to think about how to do threaded messaging using that abstraction layer.  I have a solid idea how to do it with a flat file, but I'd have to wait until the abstraction layer is in place to figure it out with that.  In principle, it shouldn't be difficult.

Basically, when you send a message, it would be sent using the existing code... but it would be associated with a "PMThread ID" which would then allow the display code to show them in a threaded manner, just like all threads.

I think this would be a great idea but we should probably put it on the back burner until the abstraction layer is complete.
  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #19 - Jul 18th, 2009 at 5:46pm
Post Tools
We could reuse a lot of the board display code without adding it into the board index. We could probably do threaded messaging, but it may be tricky.

cepheid: the code to do this won't know whether or not it's flat-file or db. To everything except the DataSource code, it all looks like a database.
  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
OH Eng
Past Team Members
Documentation Team
Offline



Posts: 4,026
Location: Pensacola, Florida USA
Re: PMs to be more "instant"
Reply #18 - Jul 18th, 2009 at 2:09pm
Post Tools
That is definitely different.  It may create an impression that privacy in the PMs is less than it is now, however.  Mods, Gmods, and Admins can do things to boards that users cannot, and I would imagine the question arising about whether or not their PMs could be read by anyone with mod powers.  I think changing to that kind of format would require something up front to let users know it isn't diminishing privacy of their PMs.
  

 
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #17 - Jul 18th, 2009 at 4:51am
Post Tools
Matt Siegman wrote on Jul 18th, 2009 at 4:40am:
I don't want to also have to defend polling AJAX stuff as being resource light.

I can certainly understand that, and yes, I can see wanting to avoid officially implementing anything that looks like a chat.  'nuff said.

Matt Siegman wrote on Jul 18th, 2009 at 4:40am:
If this can be done without a separate PM center, cool.

I'm not sure I can see how it can, but maybe someone can come up with an idea.  That said, I support retaining a separate PM center... however, I can think of one neat idea, which is to treat a user's PM center like a Board and messages would be in threads, very much like how Gmail treats email threads...

If you make the PM center into a Board, then you don't need any inbox or outbox; every message thread is treated as an actual thread.  We would obviously need modifications from regular Boards so that users could forward/delete individual messages, and each new PM ("post") would need a recipient list, but otherwise it can be handled very similarly to a private Board for that user.  Also, we can implement multiple folders, which would be treated as different Boards (e.g. there would be the main Messages board, plus one or more user-created Storage boards).

For flat-file storage, each user's .im file now becomes a directory containing the individual message threads (or, it can all be done in a single file, but putting it in a directory allows re-use of some existing thread-handling code).  For DB, it's obviously much easier to do, since each message can have a thread-index or some other relational connection.

What do you think of that?  It would still be a dedicated PM center, but it would look and operate very much like the BoardIndex and could therefore re-use a lot of that code and template.  It would be a Gmail-like interface, and I can't think of any other BB software that has a PM center like that, so it would be a uniquely-YaBB feature.
  
Back to top
WWW  
IP Logged
 
Matt Siegman
YaBB Legends (Inactive)
*
Offline



Posts: 3,380
Location: Wichita, KS
Re: PMs to be more "instant"
Reply #16 - Jul 18th, 2009 at 4:40am
Post Tools
We will not do AJAX polling. I don't care how well it's implemented. We write message board software, not chat software. Instant PMs via polling AJAX is essentially chat. We've said no to chat at least a hundred times. There is a reason and I really don't feel like explaining it, again. Web hosts see chat as server intensive. They also see YaBB as server intensive. If they see YaBB + chat supported in an official way, that's one more check against us. We already have to convince people that PHP is not necessarily less intensive on the server than Perl, and that by using a DB they are just shifting load to a less visible program. I don't want to also have to defend polling AJAX stuff as being resource light.

The PM pages will not go away entirely, we need to allow longer-term retention. If this can be done without a separate PM center, cool. I'd imagine that most of it can go away from user's normal routine--they'd only have to see it if they want to access old stuff.
  

-- Matt Siegman 8) Wish List
Back to top
 
IP Logged
 
cepheid
Senior Member
****
Offline



Posts: 516
Re: PMs to be more "instant"
Reply #15 - Jul 18th, 2009 at 3:25am
Post Tools
Unilat wrote on Jul 18th, 2009 at 3:06am:
AJAX polling is also out of the question in my opinion.

FWIW, as I said, I've run chat software with 2-second queries by 20-30 users for an hour, with absolutely no server issues on even a crappy Pentium 4 server, and on a shared account.

I'm not voting for AJAX polling, I'm just recommending that it not be "out of the question," because it can be done if done carefully.

Unilat wrote on Jul 18th, 2009 at 3:06am:
Plus, I had an ajax update to the shoutbox mod and its just a pain in the rear in general because of server times and browser issues.

I would recommend looking at the source code for AJAX Chat; they push a lot of the processing to the client via JS so it saves a lot of server load.

Unilat wrote on Jul 18th, 2009 at 3:06am:
PM pages are eliminated and confined to popups

I would strongly oppose this.  Members need a personal messaging location where they can store their PMs, both ingoing and outgoing, to read however many times they want.  Many members on this and other forums use PMs to send quite detailed messages, basically the same way they would use email.  Eliminating that feature would be a big step backwards, in my opinion.
  
Back to top
WWW  
IP Logged
 
Page Index Toggle Pages: [1] 2 
Topic Tools
 
  « Board Index ‹ Board  ^Top