SDS Status Report: January 10

A full month of crawling has passed, leaving the database pretty full and everyone involved with the project ecstatic to see everything coming together. A lot of progress has been made since the last report, so there is a lot to report on here. Strap in!

On January 3, this discussion took place:

January 3, 2010 chat between Blake "ROOT" and Harry "BlackSyte":

Blake: SDS is running a lot slower now that things are filling up, and the partitioning [of the database in an attempt to make things faster] didnt go over too well. My next attempt will be to do manual partitioning, but I dont want to do it right now because I just worked pretty hard to repair the damage the automatic partitioning did...It slowed things down to 1 process per minute.

With the current table loads and everything back to normal, its about 50 profile processes per minute. Its not THAT bad, but it isnt fast enough. Something exciting, though; SDS has reached the edge nodes. The very first Steam user has been crawled, and the very last Steam user (as of this writing) has been crawled. All that is left is everyone in between! But, it stands to prove that my theory might hold weight afterall. It shows that someone, thereby everyone, in the SDS Steam group is connected to both the minimum and maximum edges.

On January 18, SixDegreeSteam Local Server 1.5.87C (the current version) was implemented. It is thus far the most stable release with many improvements over the initial release from December. Family 1.5 brought in better error handling, a logging mechanism, parameter-based execution, a "prioritize child nodes" option for high-priority queue entries, and some programmatic fine-tuning. Release 1.5.87 introduced multi-threading for running multiple local servers (crawlers) consecutively and fixed some profile tracking issues that were previously irreproducible in production.

On January 21, the client algorithm was successfully executed. The interface is still a couple weeks out, but is coming quickly. Work on the interface was stalled after the 21st due to coursework and may continue to be stalled for 4 more weeks.

As of this writing, the database reports these statistics:

- Users crawled: 2,518,356
- Groups crawled: 748,140
- Profiles pending: 5,988,765
- Total discovered users: 7,791,431
- Total discovered groups: 748,141
- Average time between discovery and crawling: 9 days

Bonus: This is a discussion that took place on January 5. It doesnt do much to prove progress of the project, but does offer some interesting food for thought:

January 5, 2010 chat between Blake "ROOT", Dallas, and Harry "BlackSyte":

Blake: Its amazing how quickly the graph edges progressed.
Dallas: But the surface has only been barely scratched.
Blake: Exactly! I mean, we arent even half way through all the users, yet a streamlined backbone has emerged. That raises a concern...Perhaps there are more profiles with a betweenness centrality less than or equal to their degree centrality than I thought. Since a rigid, well-defined backbone has already formed so early in the project, yet there are relatively no user discoveries, it makes me think[...]

There are two possible conditions under which this would happen, guessing that the crawler itself is not at fault, and my confidence of that is fairly high as of 1.5C. First [possibility], there are a shitload of people who form "clicks" [or] small collections of friends who do not join groups or befriend "outsiders"...and by shitload, I mean over 80% of the entire demographic. Thats hard to believe, but not improbable.

The second case, which is even mmore unlikely but is very possible given a generational standpoint, is that there are sections of the entire demographic who are only friends with other members of the same section. So, you have 4 million users in segment A who are friends with other users in that same section, but none of them are friends with users from section B.Its incredibly unlikely, but its a valid portrayal of an existing graph theory called generational demography -- Newer users tend to be friends with other newer users, while older users tend to be friends with other older users, and never shall the two meet.

Heres another interesting observation Ive made. The queue timeframe is currently 9 days...Now, what that means is that there is a 9-day waiting period between discovery and crawling. Its a common occurrence in the crawler that a profile will become invalidated within those 9 days; A wildly common occurrence, in fact. People are deleting their profiles or changing their profile names way too often, somewhere between 1 to 9 days!
Harry: Does that hamper the crawling process?
Blake: In the first release, yes. The crawler would actually crash with a fatal error because it was expecting the profile to be there, but it wasnt. That would happen in the first couple days of launch before I patched it, which is pretty funny because that means the profiles were becoming invalidated within 1-3 days!

SixDegreeSteam: Synopsis

I was curious as to a means that people like myself could come to an understanding on roughly how this program works... I understand what the goal of it is, but how do you intend to do this?...

- TopRaman

While I have explained a lot of SixDegreeSteam's abstract mechanics in previous articles, I feel they were not programmatically detailed enough to give a good picture of how exactly the program operates. So, Ill try to fill that gap here. There are three components to the project; Ill try to discuss all of them as simply and cleanly as possible.

WARNING: Previous articles have focused on previous versions of the project. Likewise, this article with focus on the current version of the project as of this writing (1.5C). I feel this current version is the most efficient, so it is likely to stick around for a long time. But, this is a disclaimer just in case the project does change again substantially.

The first and (thus far) most time-consuming component is the crawler. Without it, the project would not have a dataset. The crawler has the straight-forward job of collecting links to other profiles from one profile, saving (queueing) those links, then opening them back up sequentially to collect more links. The process continues until all links are collected and thereby all profiles are analyzed. This process of collecting, storing, reading, and repeating is called crawling. The specific crawling logic will not be described here for the sake of brevity, but all the details can be found in an earlier post titled SixDegreeSteam: Challenges. Program-wise, though, the crawler downloads the pages containing the links, extracts the links using a combination of Regular Expressions and XML parsing, and inserts them into a SQL database table called the crawler queue. The crawler also extracts some basic profile information, such as SteamID, profile name, and avatar, in a similar manner and inserts it all into another table called the user dataset (or group dataset). The complete list of datums stored per user is SteamID, last crawl time (to prevent recrawling a user too frequently), profile name, avatar, friends, and group memberships. The complete list of datums stored per group is similar: SteamID, last crawl time, group name, avatar, and members.

Given that the crawler does its job correctly, we are left with a database filled (and I mean FILLED) with information about the users and groups of the Steam Community. Oddly enough, the information is pretty inconsequential without a way to harness the datasets. So, our second component, aptly named Pathfinder, is arguably as important as the crawler. Pathfinder has the soul purpose of using the information available through the database to calculate a lowest-cost path between two given nodes. To do this, Ive opted for an object-oriented rendition of the breadth-first search graph theory algorithm. Once again, for the sake of brevity, I wont go into detail about the algorithm. If you are curious about it, follow the link or run a Google search. There are tons of articles that have covered it far better than I can. After the algorithm is applied, a list of users and groups used to reach profile B from profile A the quickest is displayed with links to each profile and avatars for recognition purposes.

The third and newest addition to the component set is a sort of network browser. Using a graphical, navigable web of the dataset, users will be able to quickly traverse the entire Steam Community social network, allowing them to get a better idea of just where they fit into it all. This component is simply an auxiliary to the project and is not a real focus. As such, it will be the last to be implemented and will only even enter the development picture after the crawler and Pathfinder are thoroughly completed.

As was said about Pathfinder, the information gathered by the crawler is pretty useless to the end user until a method of putting it to work is created. This explains why the crawler has been operational for nearly a month now, yet the site is still empty.

SDS Finished (For Real This Time!)

The centerpiece of the project, the SixDegreeSteam crawler/server, has been thoroughly completed. Since the promised launch date of December 25, the crawler was experiencing memory issues that would cause it to die roughly 5 minutes after startup. Im very pleased to announce that version 1.5.77C of the crawler (yes, it seriously took that many revisions to get everything up to working conditions) is now in effect, and running smoothly!

Now I can switch over to working on the client software. More about that will be released later. Here are some statistics about the limited runtime the crawler got between its crashes.

- Uptime: 2 hours
- Users crawled: 1,961
- Groups crawled: 10,337
- Users/Groups pending: 408,376

A special thanks to everyone who has sent me emails, joined the Steam group, and otherwise completely overwhelmed me with their gracious comments! Its truly inspiring to see so many people in support of what I invisioned to be a small personal project. As always, feel free to email me with questions, comments, concerns, or funny lolcats. blake.oxx@gmail.com (remove the dot)

SixDegreeSteam Finished

After about 3 months of development, SixDegreeSteam has reached the final steps in the launch process. The database has been set up, the crawler has been completed, and the folks at Valve have been sent "please let me borrow your bandwidth" cookies. Everything is pumped and primed. However, the project has not yet been released on the community. Why? Because Valve has not yet agreed. As soon as the green flag is given, the experiment will begin full-force.

As a side note, a previous article I posted about how SDS would acquire information is wrong. Actually working on the program and digging through the Steam Community site has enlightened me a little more about the crawling process. The article will be corrected as soon as I have time.

SixDegreeSteam Mailbag 2

@SixDegreeSteam: Bump bump bump! Updates, please!

- Anonymous

Good timing! It just so happens there is yet another development in the SDS programming progress. I decided to set aside all of the existing code for further development and implementation at a later time, and start over yet again. In this new iteration, I intend to keep things simple with a focus on mechanics and practicality, not resources and scalability. This aids the project in two ways. First, interest in hosting slave servers has been very low. So, it seems like a waste to work so hard on a component that may not even be used (or necessary, for that matter). Second and most obviously, deployment has stalled, and stalled, and stalled some more. I am very dissatisfied with the current timeline for completion compared to the originally proposed timeline. Going back to basics will speed up development phenominally and consequentially lead to a much closer launch date.

Where will the project be accessible from?

- Anonymous

The brand-new subdomain on my brand-new server/site will be the point of deployment. While we are on the subject, I will also be moving my blogs to the new site once the general site is set up.

This article is a reply to an email. If you would like to ask a question or suggest a new article, email me. blake.oxx@gmail.com (remove the dot)

SixDegreeSteam: Programmatic

First of all, thanks to everyone who have subscribed to my Devlog, sent me emails, or have otherwise expressed great interest in SixDegreeSteam. You all serve as my motivation, and I am very proud to be so highly regarded. Thank you all! Now, as promised, here is another SDS tech article.

From the conception of the project, SixDegreeSteam has changed fundamentally a couple times. The reason for this is because there are so many factors to consider that it is near impossible for me alone to take them all into effect. I've sat down and worked out the best approaches I can conceive, but after putting them all into working code, something new will show itself and justify a rethinking. The major issue here is that there are two conflicting, equally and critically important aspects to this project; bandwidth and memory usage.

Bandwidth and memory are quasi-mutually exclusive. In other words, you can not optimize one in a program that utilizes both technologies without negatively impacting the other. The reason for this is simple. In SixDegreeSteam, with the exception of static and very few dynamic data, anything that we transfer (bandwidth usage) is useless to the crawler and is therefore unnecessary to keep in memory (memory usage). Likewise, anything kept on the client side for a longer time, indefinately, or otherwise in a non-time-critical manner is not likely to be needed by the server, hence memory on the client is used in favor of bandwidth. While this trade-off does have its implementations, bandwidth is a much more precious commodity in the long run. Memory can be reclaimed by throwing away data, but bandwidth comes in limited amounts (for most of us) on a monthly basis. However, the more memory available to the program, the faster and larger the resulting dataset can be. I've had to rewrite the messaging protocol between the server and client once, the crawler module thrice, and the program base twice as a result of trying to find the best trade-off between the two technologies. I have a sick feeling there will be a few more rewrites to come, and many more after the project goes public.

The bandwidth-versus-memory conundrum has led to a change in the structure of the program as a whole. In previous articles and discussions, I spoke of a multi-threaded program layout consisting of a server and a client (slave threader), with the client managing "slave threads" responsible for the actual crawling operations. As of this writing, multi-threading is still a part of the server aspect in order to allow the server to communicate with multiple clients at once. But, the client has been changed from the slave threader approach to a single-thread, single-crawler, tree-based data collection scheme. The client starts by requesting a Steam profile to begin crawling from the server. Then, an object at the top of a tree data structure is created to represent the profile. The object then crawls the ID, friends, and groups of the profile, creating leaf objects for each in the data structure as they are found. After the data structure reaches a set capacity, it's compressed and sent to the server. The client then removes the obsolete data and continues crawling profiles not yet completed. Two questions arise from this approach.

First, how do we make sure we aren't wasting memory and a small amount of bandwidth by crawling profiles the server already has on record? The simple answer: by wasting an even smaller amount of bandwidth between the client and server to ask if the server needs the profile. When a profile is queued for crawling on the dataset, the client will send a message to the server containing the profile ID. The server will then respond with a message stating whether to continue crawling or remove the object from the queue. Herein lies the problem outlined before by our memory-bandwidth trade-off. On one hand, we could save bandwidth between the client and server by just crawling all objects put on the stack at the expense of the memory the objects would consume. On the other, we could save that memory at the expense of bandwidth to ask the server if all the profiles we queue have already been crawled. The problem is made even more complex by the thought that any profiles we remove from the dataset after sending to the server or after discovering it has already been crawled will not be known to the client in the future. The possibility of the profile resurfacing is almost definate (which is the purpose of the project to find out!). So, question two arises.

Two, how do we stop the client from crawling profiles more than once? As the answer to question one pointed out, we have the opportunity to just ask the server if we have crawled it before or not. But, this will inevitably turn out to be a gigantic waste of bandwidth because we will have to ask the server the same question more than once to receive the same answer. The alternative is to implement a low-impact cache, capable of quickly and compactly storing/recovering which profiles the client has been instructed are crawled. And, you guessed it, the trade-off is presented. The cache increases memory usage to relieve bandwidth usage.

This is a small glimpse into the current layout of the program. It most likely does not do justice to the project complexity, but should work to give you an idea of how the program will work and why it's taking me so long to complete it.

SixDegreeSteam Mailbag

Any updates on SixDegreeSteam? You said you would keep us posted, but it's been a while since I heard anything.

- Anonymous

Work and college stuff has been keeping me pretty preoccupied, so I havent had time to do a whole lot with SDS lately. Im currently working on a low-bandwidth method of transferring data between the clients (slave threaders) and server. I also hope to post another article about the technical goodies behind the project, like what exactly a slave threader is. In the meantime, Ive been considering multiple web hosting opportunities to run the SDS server on. I think I will also use the space to start work on the full-fledged BlakeNet (under a different name, as I said before). I still have no word from Valve about using Steamworks or the acceptability of the bandwidth costs on their end. Ill have to shoot some more emails later.

Could I convince you to make SDS open-source?

- Anonymous

I have never been one to hold source code for personal projects from anyone interested in reading through it. However, I will have to keep it under wraps until development has ceased and I feel confident with its efficiency. Shortly after the project goes main-stream, the source code will be readily available for all to enjoy.

This article is a reply to an email. If you would like to ask a question or suggest a new article, email me. blake.oxx@gmail.com (remove the dot)

SixDegreeSteam Official Group Open

The official SixDegreeSteam group (SixDegree$team) is now open for all interested Steam users to join. While project news and developmental goodies will be pushed here first, the SDS Steam group will be updated with important project updates only. Joining is a good way to get involved and show your support if you use Steam. Being a member of it will also grant you bragging rights when/if the project becomes mainstream, because members of the group will be the first to be crawled when we launch!

SixDegreeSteam: Challenges

There are a few caveats to consider when developing this project. I have laid the information out in a (hopefully) easy-to-follow situation-caveat format. An important thing to remember is that not all caveats have an inherent solution, and the best solution is not always the most favorable.

Situation: First and foremost is the way Steam Community presents the information we are hoping to use. Since all information will be acquired by following "tips" from one page to a handful of others, and continuing on this pattern until all pages are analyzed, we call the process crawling. It works similar to a crawler for a search engine; Where a search engine crawler follows links on one page to others, our crawler will read IDs from one page and create new links pointing to sequential pages. Crawling friend information is easy, as the entire list of friends for a profile is in an HTML file. All we have to do is download the file from the site, extract all friend IDs, and queue them for crawling. Similarly, there is an XML file for each user containing profile information, including the groups the user is a member of. As far as crawling groups goes, a set of XML files for each group exists that lists all member IDs (one XML file per 1000 members). Note that the XML file we use to get group memberships of a user is not ideal, since it contains a lot more information than we need. This means that the speed of download and bandwidth usage (on both the crawling server and the Steam Community network) are impacted unnecessarily. A solution to this may be to use the Steamworks API available from Valve to developers, which features the ability to directly access community information without the need to crawl community pages, thus reducing bandwidth usage and overhead. However, Valve has declined granting me usage rights to Steamworks.
Caveat: Steam users have the ability to set privacy options that affect who is allowed to view their profiles. The current privacy options are private, public, and friends-only. Our crawler will only be able to use public profiles. Something to note, though, is that groups are always public, therefore all members are visible. This means that we can at least gather group membership information for non-public profiles. Likewise, if the private user is a friend of a public user, we will still be able to link the two users in our dataset since friendship on Steam is mutually inclusive (user A cannot have user B on their friend list without user B also having user A on theirs).

Situation: As was previously stated, the project is very web-intensive, utilizing a crawler technique to gather our data. This is a massive undertaking, requiring a huge amount of page/file downloads and subsequent parsing. While it is impossible to give an exact number to represent the size of our resulting dataset, the number of files we will need to download can be represented by a simple formula. We need at least one page per user (the profile information XML file, which also contains group membership information). This page is used to tell if the profile is public by checking to see if we get an access error, data is missing, or the privacy setting is explicitly shown. If its private, it would be wasteful to download the next file, as we dont have permission to view it and will just get a similar error to the first file. If its publicly viewable, we download a second file (friend list HTML) to complete our data collection for that user. Groups are a lot simpler as they are always public and will always have at least one member, therefore at least one file (the member list XML). Our formula to represent how many files we will need to download is A + B + (C * ceil(D/1,000)), where A is the number of Steam users, B is the number of users with public profiles, C is the number of groups, and D is the average number of members per group. As of this writing, there are over 53,300,212 Steam users and 1,101,806 groups. Guessing that at least three quarters of all users have public profiles and every group has 2,000 members (in reality, some users are only in one group where others are in one hundred, and some groups have one member where others have one million. 2,000 members per group is the best on-the-spot average estimation I can come up with for now), our file count is 53,300,212 + (53,300,212*(3/4)) + (1,101,806 * ceil(2,000/1,000)) = 53,300,212 + 39,975,159 + 2,203,612 = 95,478,983.
Caveat: To put that into data consumption terms, a member list for a group that has 1,000 members is about 42 KB, a friends list containing 50 friends is about 40 KB, and a complete profile page (used to get group memberships) displaying 10 group memberships is about 14 KB. Its very rare that a single file will be greater than 42 KB. Also, the user profile XML is what we use to tell if a profile is private or not, so its important to point out that the file returned for a private profile is about 366 B. So, modifying our previous formula to calculate bandwidth usage, we get (53,300,212 * 0.36) + (39,975,159 * (40 + (14-0.36))) + (2,203,612 * 42) = 2,256,007,309 KB = 2.10 TB. That is a serious amount of data to be transferring! We wont keep all of it, but as pointed out in Caveat 1, this is how we have to collect the data for lack of an alternative.

Situation: Caveat 2 points out that there is a lot of data transfer involved. So, bandwidth usage is definately an issue. Naturally, processing time for the data is also a factor. We cant provide accurate estimates for how long the data parsing for each of the three files would take because some computers are faster than others, processing time changes as memory becomes/is no longer available, etcetera. In either case, the obvious solution to speeding up both crawling and processing, as well as spreading bandwidth usage, is to use more than one computer. To speed processing up even further, we can create more than one instance of the program and have each instance work on a different page concurrently. This means we can process ten or more pages in the time it would take a single instance to process one. I will discuss both of these in-depth in a later article.
Caveat: Creating a control structure that can manage multiple instances (called threads) is one thing. Creating a server program that can remotely manage multiple programs running multiple instances is a completely different thing. The architecture of the server and its complimenting "slave threaders" will have to be such that each slave threader is capable of working, to an extent, on its own. The only time the slave threader should call home to the server is when the global scope of the dataset needs to be analyzed or all threads are idle (more work is needed). We adopt this minimalistic communication policy to make sure the bandwidth usage of the data between the two components does not become a factor in itself. This is a very intrinsic topic that requires extra thought in its own. As such, a future article will be devoted to this topic alone.

These are only a handful of issues we need to consider when tackling this project. They represent the major challenges I am facing right now in the design of the program. In an upcoming article, Caveat 3 will be examined more closely to show how I intend on structuring the server-slave threader relationship and my implementation of thread pooling.

Edited: This post was updated for correctness on January 14, 2010.

SixDegreeSteam: The Intro

As my previous article hinted to, I am planning to write a program that expresses the link between every Steam user. As of this article's writing, there are exactly 53,300,212 accounts registered with Steam. This includes active, inactive, banned, duplicate, publisher/staff, and Internet Cafe ("multiseat") accounts. It is impossible to distinguish just how many of those accounts are actually worth the effort of this project without walking through each account profile (ironically, that's just what this project sets out to do). Each of those accounts is allowed to have a maximum of 255 friends, and an unknown (perhaps unlimited?) amount of group memberships. Now that we have some numbers down, let's talk about the actual program.

Introducing SixDegreeSteam, an attempt at mapping the Steam social network. The name is a reference to the Six Degrees of Separation sociological theory that the project is based on, which states that every person in the world is linked to every other person by no more than six people. My theory is that a similar phenomenon exists between all social mediums, specifically the Steam platform's underlying network Steam Community. However, there is a fundamental difference between Steam and other social networking mediums; Some people only use Steam to game, not make friends! This means that some accounts will have 100 friends and be members of 10 different groups, while others will have 0 friends and 0 groups. The network is even more obfuscated because some people may have friends and group memberships, but only with people they know well. This makes the web of connections incredibly shallow and in severe cases exclusive, with no connections to the mainstream web or other exclusive webs. In other words, "Everybody knows everybody" only works if "everybody" is not limited to a select few.

There are also a couple technical caveats we must address. They will be discussed in an upcoming article.