Chapter 166 Forget it

The background noise on the other end of the phone was a complete mess.

Someone was yelling at the network administrator, "Add ten yuan to machine number three in section C!" Another person was banging on the table and cursing, "You threw a grenade! It blinded me!" Interspersed with a series of coughs and the sound of a lighter lighting a cigarette. Chen Zhuo moved the landline microphone a little further away.

"Wait a minute."

Chu Ge called out from the other end, followed by the sound of a chair being dragged, the noise subsiding slightly as if they had moved to a different corner. "Alright, go ahead, I found the pen."

Chu Ge chewed on a candy, his left hand gripping the microphone tightly between his shoulder and ear, while his right hand rummaged through a jumble of keyboard cables and pulled out a ballpoint pen. There was no paper on the table, so he glanced around, then casually pulled over the half-eaten Master Kong braised beef noodle cup, peeled off the cardboard lid with a few drops of chili oil, and flipped it over. The back of the lid was slightly damp, but it didn't affect his writing.

Chen Zhuo stood by the living room window, looking at the thin layer of frost on the glass, and reached out to draw a line on it.

"How was the database built in Beijing?" Chen Zhuo asked.

"Relationship-based, a typical tree structure."

Chu Ge took two big bites of the candy.

"They want to create a six-degrees-of-separation social network. The underlying logic is very simple: I am A, I know B, and the database is built along one edge. Searching for my friends is very fast, and searching for my friends' friends is also barely manageable." Chu Ge's voice had a dryness from staying up all night.

"But if you search down three or four levels, once the concurrency exceeds two hundred people, the database has to perform infinite nested join queries. A table with hundreds of thousands of users instantly generates tens of millions of redundant data entries." "That guy in Beijing said that they were doing a stress test just now. Two hundred virtual accounts simultaneously clicked on the 'People You May Know' feature. The server fans were spinning like helicopters, the CPU was at 100%, and the database was locked after three seconds."

Chu Ge sighed.

"Now this has become a dead end. To be fast, all the relationships need to be calculated in advance and stored in the cache, but this requires a huge amount of memory. They can't afford that many servers. If they don't calculate in advance and check in real time, the database will crash if just a few people access it at the same time."

Chen Zhuo listened without speaking immediately.

He walked to the sofa, sat down, picked up a peanut in its shell from the fruit plate, and gently cracked it open in his hand.

"Aren't you computer science students a bit stubborn?"

Chen Zhuo rubbed off the peanut skins, his tone slightly amused.

"What do you mean?"

Chu Ge was taken aback.

"This is a purely graph theory problem. Why are you trying to solve it like you're checking a census register?"

Chen Zhuo threw the peanut into his mouth.

"Discard your nested queries, and think of all users as points in a high-dimensional space. The relationship between users is a line." Chu Ge didn't say anything, his pen tip resting on the instant noodle lid.

"Create an adjacency matrix."

Chen Zhuo's voice was very steady, as if he were explaining a first-year calculus problem to someone in a university study room.

"Suppose there are 100,000 users, which is a 100,000 by 100,000 matrix A. If user i and user j are friends, the value of (i, j) in the matrix is ​​1; otherwise, it is 0." "Wait a minute."

Chu Ge interrupted him.

"Ten thousand by ten thousand, that's ten billion data points. Have you calculated how much memory that would take up? The server would crash on the spot."

"Chu Ge".

Chen Zhuo chuckled softly on the other end of the phone.

Do you have 100,000 friends in real life?

"No, I don't even have ten."

Chu Ge answered honestly.

"No normal person would do that."

Chen Zhuo said.

"Therefore, 99.99% of the values ​​in this matrix are 0, making it an extremely sparse matrix." Chu Ge's fingers tightened suddenly as he held the pen.

"In memory, you don't need to store those 10 billion points; you only need to store the coordinates that are 1."

Chen Zhuo continued speaking.

"This is a simple coordinate mapping. Next, how do you mathematically represent finding your friend's friend, that is, second-degree connections?" Chu Ge's mind raced. The linear algebra knowledge he had learned in his freshman year, which he had almost forgotten, suddenly flashed through the chaos in his mind like lightning. "Matrix multiplication."

Chu Ge blurted out.

"A multiplied by A, A squared".

"right."

Chen Zhuo stood up, walked to the coffee table, and poured a glass of warm water.

"The square of A represents the second degree of connection, and the cube of A represents the third degree of connection."

Chu Ge stared at the instant noodle lid, unconsciously drawing circles on it with his ballpoint pen, his breathing becoming rapid.

"However, matrix multiplication is too computationally intensive, especially high-order multiplication, which the CPU still cannot handle."

Chu Ge raised the most crucial question.

"That's because you're too greedy. You want to calculate everyone's relationship network all at once."

Chen Zhuo took a sip of water to moisten his throat.

"The server doesn't need to know who everyone knows. The server only needs to respond to the request of the currently logged-in user. Therefore, you don't need to do matrix multiplication." Chen Zhuo's voice became a little soft, but it sounded like a thunderclap to Chu Ge's ears.

"The currently logged-in user is not a matrix, but a vector."

Chen Zhuo provided the final solution.

"Take a vector where only its own position is 1 and all the others are 0. Multiply this one-dimensional vector by the sparse matrix once to get its direct friend vector. Then multiply the result by the matrix once to get its second-degree friend vector."

Chen Zhuo paused for a moment, then added a sentence.

"The time complexity of multiplying a vector by a sparse matrix is ​​O(N). Even if he has connections everywhere, a computer can do this kind of one-dimensional array multiplication in less than a millisecond." In the internet cafe, Chu Ge had already chewed up the candy in his mouth.

He only realized what was happening when Luo bit into the candy stick and flung it to the ground.

His eyes were fixed on the instant noodle paper lid stained with chili oil in front of him.

There were two lines of somewhat messy formulas written on it.

The database deadlock problem, which had plagued a startup team in Beijing for half a month and was considered an unsolvable hardware bottleneck by several top students from Tsinghua University's computer science department, was utterly crushed into dust by a few basic linear algebra concepts in the mouth of this twelve-year-old boy.

"I understand."

Chu Ge's voice trembled slightly.

"Abandon relational queries in the database, extract all relational tables, maintain a sparse matrix in memory, perform all queries by vector multiplication in memory, calculate the result, and then use the user ID to retrieve the avatar and name from the database."

"right."

Chen Zhuo responded.

"But there's a problem."

Chugo's programmer mindset quickly identified the vulnerability.

"A knows B, B knows C, and C knows A. In graph theory, this is a cycle. If the vectors keep multiplying, won't it create an infinite loop and exhaust the computing power?" "Chu Ge."

Chen Zhuo sighed on the other end of the phone, his tone tinged with helplessness.

"This is an engineering problem, not a mathematical proof. For the result of vector multiplication, for any value greater than 0, you can simply use a hash table to record 1D. The next time you encounter a value that has already been recorded, you can just skip it." Chen Zhuo gently shook his head.

"You're a coder, don't expect math formulas to calculate how many squares of paper you need to poop. Use some common sense as a programmer, okay?" Chu Ge suddenly grinned as he listened to the teasing on the phone.

"Alright, brother, I accept your favor. Consider this a debt I owe you."

Chu Ge folded the instant noodle lid twice and carefully stuffed it into his inner pocket.

"After the New Year, when you come back to USTC, I'll treat you to a month's worth of stir-fries in the cafeteria. I have to hang up now; I need to finish writing this underlying memory daemon process as soon as possible." Before Chen Zhuo could speak, the phone went dead.

Chen Zhuo put down the microphone, shook his head, and smiled.

He turned around and went to the kitchen to get bowls and chopsticks, preparing for dinner.

The capital city is more than a thousand kilometers away from Zeyang City.

In a dilapidated residential building near Zhongguancun.

The room was dark, with only three or four monitors emitting a pale white light. Occasionally, a few brilliant fireworks flashed outside the window, illuminating the cigarette butts and leftover takeout boxes scattered on the floor. Wang Xing, wrapped in a cotton coat, was huddled in his computer chair, his eyes bloodshot, staring intently at the post-dated log on the screen.

They wanted to create a truly real-name campus social networking site in this primitive era of the internet, and the idea was excellent. Several of Wang Xing's even secured hundreds of thousands of yuan in angel investment based on their PowerPoint presentations. However, technical bottlenecks held them back.

Tomorrow is the third day of the Lunar New Year, and investors are asking to see a demo of a system that can support 500 people online simultaneously.

Wang Xing hasn't slept for three days.

Once the concurrency level increases, the database lookup function for "friends' friends" will overwhelm the entire system like an avalanche. The MSN icon in the lower right corner of the screen suddenly started flashing.

Wang Xing's bloodshot eyes flickered, and he clicked the mouse.

It was Chu Ge, the USTC hacker who was far away in Huizhou and whom he had brought in as a free technical assistant.

"Old Chu, don't bother."

Wang Xing typed a line of text and sent it, his fingers a little stiff.

"We tried adding cache and creating indexes, but it didn't work. Relational databases can't handle this kind of multi-level network query; the hardware can't handle it." A few seconds later, Chu Ge sent over a compressed file.

It's less than Z0KB.

Immediately afterwards, Chu Ge's message popped up.

"Delete all your previous relationship query code, and attach this C language daemon process to the server."

Wang Xing was taken aback.

"What is this?"

"A memory-level sparse matrix multiplication tool."

Chugo's reply was simple.

"You just need to export a plain text copy of your relationship table and feed it to it. From now on, all friend queries will be done without going through the database. Just send the command to this process, and it will calculate it in memory and return the friend ID array to you."

Wang Xing looked at that passage and was somewhat confused.

But he's now desperate and has no other options but to try anything.

He received the file, unzipped it, dragged the source code into the compiler, and gave it a cursory glance.

Upon seeing this, Wang Xing broke out in a cold sweat.

The code is extremely concise, containing no library files linked to from any databases. It consists entirely of low-level memory pointer operations and a few loops multiplying one-dimensional arrays that he didn't quite understand. There isn't a single SL statement in it.

Wang Xing took a deep breath, attached the compiled executable file to the back of the test server, and then inserted tens of thousands of test relationship data entries. The process started silently, using less than 50 megabytes of memory.

"Run a stress test."

Wang Xing turned his head and called out to Wang Huiwen, who was already slumped over in sleep.

Wang Huiwen rubbed his eyes groggily and typed a stress test command on the keyboard.

"Simulate 500 concurrent requests and perform a deep query on three levels of friends."

Wang Huiwen pressed Enter.

"Xing-ge, get ready to restart the server. It's probably still three seconds old..."

Before she could finish speaking, Wang Huiwen's voice caught in her throat.

The progress bar of the load testing tool didn't freeze like before; instead, it filled up instantly at a speed almost imperceptible to the naked eye, turning the screen completely green.

Wang Xing sat up abruptly, the chair creaking under the weight.

He stared intently at the compiled data of the stress test results.

Number of requests completed: 500.

Number of failures: 0.

Average response time: 3 milliseconds.

Wang Xing felt his eyes were playing tricks on him, so he turned to look at the server's system resource monitoring.

During the stress test, the CPU utilization only jumped briefly to 8% before quickly dropping back to 1%. The server fans didn't even have time to speed up before the query was finished.

The room was so quiet that the only sound was the faint buzzing of the computer case.

"Brother Xing..."

Wang Huiwen, standing next to him, swallowed hard, his hand trembling as he pointed at the screen.

"What's going on? The database didn't transfer?"

"No database available."

Wang Xing's voice became hoarse as he stared intently at the C code he had just read, finally understanding the terrifying mathematical logic within it. This wasn't data lookup.

This involves performing dimensionality reduction calculations on the entire user relationship network directly in memory.

Wang Xing's fingers were a little numb. He switched back to the MSN chat window and typed rapidly, not even bothering to correct the several typos. "Old Chu! Who wrote this underlying logic?!"

Wang Xing sent three consecutive shaking windows.

"This is pure graph theory and higher-order linear algebra! It directly dumps the database work onto the CPU and memory for vector calculations!" Wang Xing's heart was pounding.

"Don't tell me you came up with this yourself. Do you have an algorithm team from the Chinese Academy of Sciences behind you? Or did you get help from some big shot in Silicon Valley who works on search engines?" In an internet cafe in a small county town.

Chu Ge stared at the string of exclamation marks and the frantically flashing windows on the screen, a wide, exaggerated smile spreading across his tired face. He picked up the box of candy he'd asked a friend to buy for him, took out a piece, and popped it into his mouth.

Chu Ge flicked the cigarette ash into the instant noodle bowl, placed his hands on the greasy keyboard, slowly typed a line, and pressed enter to send: "No team."

"It was one of my roommates who happened to be home for winter break. He just called and helped me out."

After sending that message, Chu Ge paused, then added another blow.

"Oh, by the way, he's twelve years old this year, and he's probably being called by his mom to eat dumplings right now."

On the other end of MSN, Wang Xing's avatar remained completely still.

A full five minutes passed.

Wang Xingcai sent over a string of ellipses.

Then came a sentence.

"Old Chu, if the investors' money comes through tomorrow, I'll give you 5% of the shares. And your roommate... could you bring him into our team as a technical consultant? He can name his price." Chu Ge chuckled as he read this.

Forget it.

Chu Ge typed.

"With our lousy team, you actually dare to expect a guru like him to be your technical advisor? Consider these few lines of code my New Year's gift to you. I'm logging off now, going to sleep." Chu Ge decisively logged out of MSN.

The air in the internet cafe was still stuffy. Several young men who had stayed up all night were already asleep on their keyboards, emitting soft snores. Chu Ge stood up, stretched, and his bones cracked a few times.

He went to the bar, paid the bill, and pushed open the glass door of the internet cafe.

A biting gust of cold wind swept in, instantly dispelling the smell of smoke and the distinctive greasy hair odor from the internet cafe.

The sky was already beginning to lighten.

On the morning of the third day of the Lunar New Year, the streets were deserted, littered with the remnants of red firecrackers set off the night before, their gleaming contrast against the lingering snow. Chu Ge turned up the collar of his old military overcoat and put his hands in his pockets.

He walked down the deserted street, exhaling a puff of white breath.

On the eve of this era of rapid growth.

Some people stay up all night at the card table, while others stay up until their eyes are bloodshot in front of the computer.

And what is the person who truly showed them the right path doing now?

Chu Ge couldn't help but smile, stepping on the scraps of paper on the ground as he walked towards the guesthouse.

At the same time.

Sunshine Family Compound, Zeyang City.

The television in the Chen family's living room was on, replaying last night's Spring Festival Gala.

Feng Gong's line, "I missed you all so much," echoed throughout the room.

The kitchen was steaming hot.

"Xiao Zhuo! Stop loitering around the living room and go wash your hands!"

Liu Xiuying came out of the kitchen carrying two plates of freshly cooked dumplings, the steam blurring her face.

"Dumplings on the first day of the Lunar New Year, noodles on the second, and dumplings on the third. Today we're having sauerkraut and pork dumplings. Come and eat them while they're hot, or they'll clump together and won't taste good!" Chen Jianguo said, sitting down at the table with a few cloves of garlic and a bottle of aged vinegar.

"Here it comes, here it comes."

Chen Zhuo responded, walked to the bathroom, and turned on the faucet.

The fleeting thoughts of matrices, vectors, and high-dimensional space mappings that had just crossed my mind vanished instantly the moment I heard Liu Xiuying call for dumplings, like soap suds being rinsed away with water. What internet, what six degrees of separation?

On this snowy, vinegar-scented morning of the third day of the Lunar New Year, nothing felt as comforting as a steaming plate of sauerkraut dumplings on the table. Chen Zhu dried his hands and sat down at the table.

"Mom, pour me some vinegar."

Chen Zhuo pushed the small porcelain dish over, his tone carrying the self-assurance typical of a twelve-year-old boy.

Liu Xiuying picked up the vinegar bottle and poured half a dish of vinegar for him.

"Eating dumplings without garlic diminishes the flavor by half; go peel your own garlic."

Chen Jianguo threw two cloves of garlic in front of Chen Zhuo.

Chen Zhuo picked up the two cloves of garlic, pinched them hard with his thumb and forefinger, and the garlic skin cracked open with a crisp sound.

Sunlight streamed through the glass of the window, illuminating Chen Zhuo's gentle and refined face.

Everything seemed so calm, so natural.