New Motivation Experiments

apavlo commented 12 years ago

Note that for each trial in an experiment, we want to run it three times and then take the average of the results.

Denormalization

This experiment is meant to explore the trade-offs of embedding for a simple workload. We are going to show how embedding the comments documents inside of the articles documents can affect performance. The workload for this experiment is that we want to select a random article and the top 10 comments for that article (sorted by the synthetic user rating).

There are going to be two sets of trials. In the first trial, the comments for each article are embedded as a list of nested documents inside of the corresponding article. For the other trial, they are stored in a separate collection. We're going to use a single node cluster with a fixed number of clients. The number of comments for each article will be the same, but we are going to vary the number of comments per article (e.g., 10, 100, 1000, 10000, 100000).

Questions:

Do we want to maybe consider adding writes to the workload? This might show that writes get more expensive as the embedded document gets slower.
Do we want pick the articleId in each invocation from a uniform distribution or do we want to add Zipfian skew? The latter seems more realistic but may mask the problems of embedding really large documents in a read-only workload.
Sharding

This experiment will show how picking the correct sharding key is important for performance for a DBMS cluster. We are going to vary the number of nodes in the cluster (scaling up the number of client threads too). I think that we may want to model something like reddit we need to read articles and comments and then have people post new comments. We will use a zipfian distribution to select what article we are going to write a new comment to. The read/write ratio for each article should be 90/10.

For the first trial, we are going to shard the articles and comments collection using just the articleId. In the second trial, we are going to use a composite key consisting of the articleId and the articleDate. This should be using range partitioning so that as we insert new articles they always get appended to the "current" shard. For the composite key sharding, the documents will get distributed evenly among all of the shards to ensure that the load is balanced.

Questions:

Is this really convincing? What kind of blog is going to be passing both the articleId and the articleDate to the database? And wouldn't hash partitioning solve the hot spot problem?
Right now we are using a globally unique commentId for all of the comment documents. A better approach is to maintain a counter in each article document that keeps track of the number of comments that it has. We can just increment and get the next commentId when inserting a new comment. To get a particular comment record, you will need to pass in the articleId and commentId.
Index Keys

New Version: We are going to show how the performance changes when the working set of indexes fits in RAM. This is to show the importance of being able to select indexes that are larger than the amount of RAM available on a node. We are going vary the amount of skew in the workload from 0% to 100% (this is along the x-axis). The skew percentage determines which operations we will grab an articleId using a Zipfian random number generator versus a uniform distribution random number generator. The number of indexes will be fixed for all experiments. This will be on a single node experiment. The workload is going to be broken into read queries and write queries, and then for the two trials we are going vary the read/write ratio. The first trial will consist of 90% reads and 10% writes. The second trial will be 80% reads and 20% writes.

We are going to vary the number of indexes used for the articles collection. That means the workload is going to need to consist of queries that perform look-ups on the articles using different keys:

Retrieve a single document using an articleId
Retrieve all articles for a single author
Retrieve all articles from a specific date.
Retrieve all articles from a single author on a specific date.

The write portion of the workload can simply be incrementing a view counter on the article. Again, this seems trite though.

Questions:

This experiment seems obvious and not interesting. We may want to figure out some experiment that can capture the importance of selecting indexes that have the bulk of the operations occur on the right side of the trees.
We should ask Spencer how close they are to releasing hash table indexes, because that will add a new dimension to the problem.
It seems that showing how covering indexes improve performance is more interesting here, but how common are they in workloads?

apavlo commented 12 years ago

The Index Keys experiment is contrived. We should think about doing something better. We may also want to measure how memory the indexes take up and report on that.

zifnab87 commented 12 years ago

About Sharding.1. Is this really convincing? What kind of blog is going to be passing both the articleId and the articleDate to the database? And wouldn't hash partitioning solve the hot spot problem?

According to the video I have sent to you, hashing can certainly solve the hot spot problem but introduces another problem in case we are going to use that in an index as well. The problem it introduces is that we just can't take a piece of index and have it in memory for long as the entries are completely random and with high probability not the ones we want (e.g the recent ones). In case we use the combination of year,month and articleId in that order as sharding and indexing key c , we solve the hot spot problem and also we just have to keep a small part of index in memory that will certainly have what we need, as it will have index values of last month for example. From that, I think becomes clear that it is a good idea to have an index on the sharding key if that's not being done by default.

I am pretty sure about the index key and not that sure about the shard key, though

apavlo commented 11 years ago

Denormalization

Change the article and comment content to be fixed length.
Estimate the max # of comments that you can fit into a article without going over the 16MB document size limit.
Come up with the lower, upper, and middle bounds for the # of comments to use per article.

zifnab87 commented 11 years ago

Re: Estimate the max # of comments that you can fit into a article without going over the 16MB document size limit. well this takes forever..the estimation would be better to be estimated according to the schema of each comment (assuming strings are Unicode)- I am confused

comment = { "id": commentCtr, 4bytes "article": articleId, 4bytes "date": lastDate, 4bytes "author": commentAuthor, 15x4bytes "comment": commentContent, 300x4bytes "rating": 100 4bytes } and the attribute names would put even more size ... 12bytes+60+1200+4 = 1276bytes ==> ~15000 comments

Update: So with comment content size equal to 300 characters the single article document could hold ~41,000 comments before pymongo error because of Mongodb document size limit (16mb)

Running the script again with comment content size equal to 1024 we get ~13-14000comments per article before the Mongodb document size limit

it seems that the each string character takes 1 byte of space and not 4bytes as if it were Unicode

zifnab87 commented 11 years ago

Questions on the Indexing Experiment: 1)will I use Zipfian for selecting by date? 2)will I use Zipfian for selecting author too? 3)what about quering articles by date and author? - the chances to retrieve any articles having two zipfian "guesses" on date and author name are slight.. 4)when you say that the experiment will be broken into reads and writes. you don't mean that the reads will be first and writes after them right? I can have a random generator for 0-1.0 and if it is more than 0.7 I can do I write, but if it is less than 0.7 I can do a read. 5) the experiment is fine to be run on a normalized base (no comments in each article) right?

apavlo commented 11 years ago

1)will I use Zipfian for selecting by date

Yes.

2)will I use Zipfian for selecting author too?

Yes.

3)what about quering articles by date and author too - the chances to have any articles having two zipfian "guesses" on date and author are slight..

You can skip this for now.

4)when you say that the experiment will be broken into reads and writes. you don't mean that the reads will be first and writes after them right? I can have a random generator for 0-1.0 and if it is more than 0.7 I can do I write, but if it is less than 0.7 I can do a read.

Yes, that sounds right.

5) the experiment is fine to be run on a normalized base (no comments in each article) right?

Yes.

zifnab87 commented 11 years ago

what happens if all the articles have 17 of 20 authors and then the zipfian gets one of those three authors with no articles?

apavlo commented 11 years ago

The assignment of authors to articles should be uniform. No author should have zero articles.

zifnab87 commented 11 years ago

So this is guaranteed because of the big number of articles ... but what about dates?? should I track which dates were used to do the queries later?

apavlo commented 11 years ago

Uniformly distribute the articles per date. You don't need to track anything because you know the start and stop dates.

zifnab87 commented 11 years ago

Yeah that's what I do but if zipfian gets a date that doesn't have any article to retrieve? - unless they are discrete date values and not truly uniform..

apavlo commented 11 years ago

Don't worry about doing queries by date then.

apavlo commented 11 years ago

Sharding

Instead of choosing a composite sharding key based on articleDate, we're going to use the articleSlug. Change the articleSlug value to be a 64-character zero-padded string of the hash of the string version of the articleId. This is will to provide us with the randomness that we need.

articleSlug = '%064d' % hash(str(articleId))

The first sharding key will be on articleId. The second sharding key will be [articleId, articleSlug].

Don't worry about doing writes for now. Just focus on reads.

zifnab87 commented 11 years ago

Index experiments update 1) we will use the index on author for the first line of the experiments (trial 1) 2) we will use one index on author and one index on tags for the second line of the experiments (trial 2) 3) the x-axis will still be skew factor 4) the read queries will be either select by author or select by tags 5) read/write ratio will be fixed - let's start with 80/20 6) articles will be 60000 - no comments per article 7) we will have more authors than 32 8) let's start with 20 tags per article out of a pool of 6000 tags 9) queries will have 1 tag for selecting an article

zifnab87 commented 11 years ago

The trial 1 used to have findbytag - so that was a problem as it didn't use any index

that's the new setup for read/writes per trial:

(trial 1) index(author),index(id) findbyauthor, inc by id (trial 2) index(author),index(id),index(tags) findbyauthor, findbytags inc by id the author id index is 200mb, as is the id too , the tags index is 4.2Gb

cmu-db / mongodb-d4